package backtracking; // le problème des N reines public class Queens { static int count = 0; // la ligne r est-elle cohérente avec les précédentes ? static boolean check(int[] cols, int r) { for (int q = 0; q < r; q++) if (cols[q] == cols[r] || Math.abs(cols[q] - cols[r]) == r - q) return false; return true; } static boolean findSolutionRec(int[] cols, int r) { if (r == cols.length) return true; for (int c = 0; c < cols.length; c++) { cols[r] = c; count++; if (check(cols, r) && findSolutionRec(cols, r + 1)) return true; } return false; } static int[] findSolution(int n) { int[] cols = new int[n]; if (findSolutionRec(cols, 0)) return cols; throw new Error("no solution for n=" + n); } static int naiveCountRec(int[] cols, int r) { if (r == cols.length) return 1; int f = 0; for (int c = 0; c < cols.length; c++) { cols[r] = c; count++; if (check(cols, r)) f += naiveCountRec(cols, r + 1); } return f; } static int naiveCount(int n) { int[] cols = new int[n]; return naiveCountRec(cols, 0); } static int countSolutionsRec(int a, int b, int c) { if (a == 0) return 1; int e = a & ~b & ~c, f = 0; while (e != 0) { int d = e & -e; count++; f += countSolutionsRec(a - d, (b + d) << 1, (c + d) >> 1); e -= d; } return f; } static int countSolutions(int n) { return countSolutionsRec(~(~0 << n), 0, 0); } public static void main(String[] args) { for (int n = 1; n <= 14; n++) { System.out.print("n = " + n + " : "); try { double start = System.currentTimeMillis(); findSolution(n); double time = System.currentTimeMillis() - start; System.out.println("solution found " + time); start = System.currentTimeMillis(); count = 0; int fn = naiveCount(n); double time1 = System.currentTimeMillis() - start; System.out.println(" f("+n+")="+ fn + " " + count + " (" + time1 + "ms)"); start = System.currentTimeMillis(); count = 0; int on = countSolutions(n); double time2 = System.currentTimeMillis() - start; System.out.println(" f("+n+")="+ on + " " + count + " (" + time2 + "ms " + (time1 / time2) + ")"); } catch (Error e) { System.out.println("no solution"); } } } }