I am doing some practice exercises with recursion and came across the nQueens problem here.
I am not sure whether I am misunderstanding what is happening with the recursion or not, but I don't understand how this code (below) is printing multiple solutions of the problem.
For example, if I run the program with a 4 queen solution, it prints out:
* Q * *
* * * Q
Q * * *
* * Q *
* * Q *
Q * * *
* * * Q
* Q * *
I am stepping through it too, and I still don't quite understand it.
Here is what I think is going on:
1. isConsistent is checking the logic/ whether it's safe to place a queen in the current spot or not
2. printQueens is printing the board
3. enumerate(int[] q, int n) is recursively placing the queens for ONE solution
4. (I would guess that) enumerate(int N) is what is enumerating through the multiple board solutions, but it is only called once. So, that can't be right. So, my next thought would be that it's just a method to call the recursive enumerate method. But then, that means that once the recursion is done finding the solution for the first board, it should stop. So, I'm back to my original question:
How/where is it calculating multiple solutions for the board?
I know it may be easy, but even with the debugger, I'm having trouble catching onto what is going on. If anyone could explain where it starts calculating the second solution for the board, I'd appreciate it.
/******************************************************************************
* Compilation: javac Queens.java
* Execution: java Queens N
*
* Solve the 8 queens problem using recursion and backtracing.
* Prints out all solutions.
*
* Limitations: works for N <= 25, but slows down considerably
* for larger N.
*
* Remark: this program implicitly enumerates all N^N possible
* placements (instead of N!), but the backtracing prunes off
* most of them, so it's not necessarily worth the extra
* complication of enumerating only permutations.
*
*
* % java Queens 3
*
* % java Queens 4
* * Q * *
* * * * Q
* Q * * *
* * * Q *
*
* * * Q *
* Q * * *
* * * * Q
* * Q * *
*
* % java Queens 8
* Q * * * * * * *
* * * * * Q * * *
* * * * * * * * Q
* * * * * * Q * *
* * * Q * * * * *
* * * * * * * Q *
* * Q * * * * * *
* * * * Q * * * *
*
* ...
*
******************************************************************************/
public class Queens {
/***************************************************************************
* Return true if queen placement q[n] does not conflict with
* other queens q[0] through q[n-1]
***************************************************************************/
public static boolean isConsistent(int[] q, int n) {
for (int i = 0; i < n; i++) {
if (q[i] == q[n]) return false; // same column
if ((q[i] - q[n]) == (n - i)) return false; // same major diagonal
if ((q[n] - q[i]) == (n - i)) return false; // same minor diagonal
}
return true;
}
/***************************************************************************
* Print out N-by-N placement of queens from permutation q in ASCII.
***************************************************************************/
public static void printQueens(int[] q) {
int N = q.length;
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (q[i] == j) StdOut.print("Q ");
else StdOut.print("* ");
}
StdOut.println();
}
StdOut.println();
}
/***************************************************************************
* Try all permutations using backtracking
***************************************************************************/
public static void enumerate(int N) {
int[] a = new int[N];
enumerate(a, 0);
}
public static void enumerate(int[] q, int n) {
int N = q.length;
if (n == N) printQueens(q);
else {
for (int i = 0; i < N; i++) {
q[n] = i;
if (isConsistent(q, n)) enumerate(q, n+1);
}
}
}
public static void main(String[] args) {
int N = Integer.parseInt(args[0]);
enumerate(N);
}
}
The important part is the enumerate method. It is holding an array of integers representing the column index for each row.
For example:
* Q * *
* * * Q
Q * * *
* * Q *
q will look like:
q[0] = 1
q[1] = 3
q[2] = 0
q[3] = 2
It is indeed going recursive, but not just for one solution. It will use backtracking instead of calculating everything all over again.
For example for N=4, the code will run equivalent to the following:
public static void enumerate(int[] q, int n) {
for(int a0=0;a0<4;a0++){
q[0]=a0;
if(isConsistent(q, 0)){
for(int a1=0;a1<4;a1++){
q[1]=a1;
if(isConsistent(q, 1)){
for(int a2=0;a2<4;a2++){
q[2]=a2;
if(isConsistent(q, 2)){
for(int a3=0;a3<4;a3++){
q[3]=a3;
if(isConsistent(q, 3)){
printQueens(q);
}
}
}
}
}
}
}
}
}
It will go over the entire solution space as far as possible. This means that it will break from the moment no further solution is possible for the rows to come but it will continue to where it was still possible to go further.
The isConsistent method is indeed checking if the current board is still valid. (diagonals/column, row is implicit in recursion)
The current board is printed out on the moment you encounter the N'th row. Because you have a board that's still valid having a queen on each row.
Check out this simulation to see the steps the algorithm does.