package backtracking; import java.io.File; import java.io.FileNotFoundException; import java.math.BigInteger; import java.util.Arrays; import java.util.Scanner; public class Sudoku { private int[] grid; // 0..80 (9 * row + col) Sudoku() { this.grid = new int[81]; } Sudoku(String s) { this.grid = new int[81]; for (int i = 0; i < 81; i++) this.grid[i] = s.charAt(i) - '0'; printSpace(); } void printSpace() { int z = 0; BigInteger s = BigInteger.ONE; for (int i = 0; i < 81; i++) if (this.grid[i] == 0) { z++; int c = 0; for (int v = 1; v <= 9; v++) { grid[i] = v; if (check(i)) c++; } grid[i] = 0; s = s.multiply(BigInteger.valueOf(c)); System.err.print(c + "*"); } System.err.println(); System.err.println(z + " cases vides"); BigInteger b = BigInteger.valueOf(9).pow(z); System.err.println("9^" + z + " = " + b + " = " + b.doubleValue()); System.err.println("espace = " + s + " = " + s.doubleValue()); } int row(int c) { return c / 9; } int col(int c) { return c % 9; } int group(int c) { return 3 * (row(c) / 3) + col(c) / 3; } boolean sameZone(int c1, int c2) { return row(c1) == row(c2) || col(c1) == col(c2) || group(c1) == group(c2); } // vérifie que la valeur dans p est compatible avec les autres cases boolean check(int p) { for (int c = 0; c < 81; c++) if (c != p && sameZone(p, c) && this.grid[p] == this.grid[c]) return false; return true; } // stats int[] levels = new int[82]; int level = 0; // essaye de résoudre la grille courante et renvoie un booléen indiquant le succès boolean solve() { levels[level++]++; for (int c = 0; c < 81; c++) if (this.grid[c] == 0) { for (int v = 1; v < 10; v++) { this.grid[c] = v; if (check(c) && solve()) return true; } this.grid[c] = 0; level--; return false; } return true; } int count = 0; // essaye de résoudre la grille courante et renvoie un booléen indiquant le succès void count() { levels[level++]++; for (int c = 0; c < 81; c++) if (this.grid[c] == 0) { for (int v = 1; v < 10; v++) { this.grid[c] = v; if (check(c)) count(); } this.grid[c] = 0; level--; return; } level--; count++; } void print() { for (int i = 0; i < 9; i++) { if (i % 3 == 0) System.out.println("+---+---+---+"); for (int j = 0; j < 9; j++) { if (j % 3 == 0) System.out.print("|"); System.out.print(this.grid[9*i+j]); } System.out.println("|"); } System.out.println("+---+---+---+"); } void stat() { System.out.println(Arrays.toString(levels)); // for (int i = 0; i < levels.length; i++) // System.out.println(i + " " + levels[i]); int tot = 0; for (int v: levels) tot += v; System.out.println(tot + " calls"); } public static void main(String[] args) throws FileNotFoundException { double start = System.currentTimeMillis(); Sudoku sk; sk = new Sudoku("200000060000075030048090100000300000300010009000008000001020570080730000090000004"); // sk = new Sudoku("000316059006000807000000200050030090790602018010080040008000000309000600560847000"); sk.print(); sk.solve(); sk.print(); sk.stat(); System.out.println(((System.currentTimeMillis() - start) / 1000) + " s"); //System.exit(0); start = System.currentTimeMillis(); sk = new Sudoku("200000060000075030048090100000300000300010009000008000001020570080730000090000004"); // sk = new Sudoku("200000060000075030048090100000300000300010009000008000001020570080730000090000004"); // 1 solution // sk = new Sudoku("200000060000075030048090100000300000300010009000008000001020570080730000090000004"); // sk = new Sudoku("200000060000070030048090100000300000300010009000008000001020570080730000090000004"); // 7 solutions // sk = new Sudoku("200000060000070030048090100000000000300010009000008000001020570080730000090000004"); // 7 solutions // sk = new Sudoku("200000060000070030048090100000300000300010000000008000001020570080730000090000004"); // 433 solutions sk.print(); sk.count(); System.out.println(sk.count + " solutions"); sk.stat(); System.out.println(((System.currentTimeMillis() - start) / 1000) + " s"); // System.exit(0); Scanner sc = new Scanner(new File("sudoku.txt")); while (sc.hasNext()) { String s = sc.nextLine(); System.out.println("s = " + s); Sudoku sks = new Sudoku(s); sks.print(); System.out.println(); if (sks.solve()) sks.print(); else System.out.println("pas de solution"); System.out.println(); } sc.close(); System.out.println((System.currentTimeMillis() - start) / 1000); } } /* expérience : maintenir la liste des cases à remplir (par ex. dans une pile) * n'améliore en rien les performances */