I found a 8-Queen solution that I was able to compile and run in Eclipse. I believe this solution follows the backtracking approach and meat of the work is done in the solution
and unsafe
functions, but I am having a hard time understanding the code paths in there. Can someone please help me understand what this code is doing.
My Source - http://rosettacode.org/wiki/N-queens_problem#Java I verified the output against the 92 solutions published on other sources. Looks good. So I know the code works.
I have tried to format it and add some basic notes to clear things up -
private static int[] b = new int[8];
private static int s = 0;
public static void main(String[] args) {
// solution from - http://rosettacode.org/wiki/N-queens_problem#Java
new QueenN();
}
public QueenN() {
solution();
}
public void solution() {
int y = 0;
b[0] = -1;
while (y >= 0) {
do {
b[y]++;
} while ((b[y] < 8) && unsafe(y));
if (b[y] < 8) {
if (y < 7) {
b[++y] = -1;
} else {
putboard();
}
} else {
y--;
}
}
}
// check if queen placement clashes with other queens
public static boolean unsafe(int y) {
int x = b[y];
for (int i = 1; i <= y; i++) {
int t = b[y - i];
if (t == x || t == x - i || t == x + i) {
return true;
}
}
return false;
}
// printing solution
public static void putboard() {
System.out.println("
Solution " + (++s));
for (int y = 0; y < 8; y++) {
for (int x = 0; x < 8; x++) {
if (b[y] == x)
System.out.print("|Q");
else
System.out.print("|_");
}
System.out.println("|");
}
}
End.
See Question&Answers more detail:os