```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");
}
}
}
}
```