Puzzled about backtracking in Eight Queen

Question

I have a difficult time understanding recursion and backtracking, albeit I have done some simple exercises (e.g. Fibonacci). So allow me to present my "brain flow" here:

1. I read the textbook and know that you can use backtracking to remove the previous queen if its current position eliminates the possibility of placing the next queen in the next column. So this seems to be easy and all I need to do is to remove it and let the program decide the next possible place.

2. After a while I found that the program stalled at the 6th queen so I figured out that if I simply removed the 5th queen the program simply put it back to its current position (i.e. given the first four queens the 5th queen always falls into the same place, which is not surprising). So I thought that I need to track the position of the last queen.

3. This is when I got puzzled. If I were to track the position of the last queen (so that when I backtrack the program is NOT allowed to put the queen into the same place), there are two potential difficulties:

a) Say that I remove the 5th queen, and I have to write code deciding its next possible position. This can be solved by ignoring its current position (before been removed) and continues to look for possible places in the following rows.

b) Should I track all the previous queens? It seems to be so. Let's say that actually I have to remove not one queen, but two queens (or even more), I surely need to track all of their current positions. But this is much more complex than what it seems to be.

1. So I started to look for answers in the textbook. Sadly it does not have the backtracking code but only have the recursion code. Then I found the code here:

http://www.geeksforgeeks.org/backtracking-set-3-n-queen-problem/

It greatly amazed me because this is so simple and yet it works! The only backtracking part is to remove the last queen! So the question is: How does the following code make sure that when given the position of 4 queens the 5th one does not always fall into the same place again and again? I think what I do not understand is how can you backtrack recursively (say that you need to remove more queens). I have no problem when moving forward recursively, but how can I move backward recursively?

/* A recursive utility function to solve N Queen problem */
bool solveNQUtil(int board[N][N], int col)
{
/* base case: If all queens are placed then return true */
if (col >= N)
    return true;

/* Consider this column and try placing this queen in all rows
   one by one */
for (int i = 0; i < N; i++)
{
    /* Check if queen can be placed on board[i][col] */
    if ( isSafe(board, i, col) )
    {
        /* Place this queen in board[i][col] */
        board[i][col] = 1;

        /* recur to place rest of the queens */
        if ( solveNQUtil(board, col + 1) == true )
            return true;

        /* If placing queen in board[i][col] doesn't lead to a solution
           then remove queen from board[i][col] */
        board[i][col] = 0; // BACKTRACK
    }
}

 /* If queen can not be place in any row in this colum col
    then return false */
return false;
}

OK. Now I have some code that DOES work but I mostly modified my own codes according to the above ones so I'm quite shaky:

bool EightQueen(int& numQueen)  {   

if (numQueen == 8)  {
    return true;
}
if (numQueen == 0)  {
    PlaceQueen(0, 0);
    numQueen ++;
    EightQueen(numQueen);
}

int row = 0;

for (row = 0; row <= 7; row ++) {
    if (CheckThis(row, numQueen))   {   //Check if next queen can be  put
        PlaceQueen(row, numQueen);  //Place next queen
        numQueen ++;
        DisplayQueen();
        cout << endl;
        if (EightQueen(numQueen))   {   //Try next queen
            return true;
        }
        ClearQueen(numQueen - 1);
        numQueen --;
    }
}
return false;
}

Say that numQueen is 5, so in the for loop we are going to check if the 6th queen can be placed. As we know this is impossible for all rows, so the function returns false. I assume that it then "shrinks" back to where it was called, that is when numQueen is 4. So ClearQueen(4) is called and the last queen (the 5th) is removed. Apparently the for loop has not finished so we will try the next row to see if it allows further development. i.e. We check if the 5th Queen can be placed on the next row and if it does we will further check if the sixth queen can be placed and so on.

Yeah it seems to work, well, eh, yeah.

Answer 1

Consider your initial board:

+---+---+---+---+---+---+---+---+
|   |   |   |   |   |   |   |   |
+---+---+---+---+---+---+---+---+
|   |   |   |   |   |   |   |   |
+---+---+---+---+---+---+---+---+
|   |   |   |   |   |   |   |   |
+---+---+---+---+---+---+---+---+
|   |   |   |   |   |   |   |   |
+---+---+---+---+---+---+---+---+
|   |   |   |   |   |   |   |   |
+---+---+---+---+---+---+---+---+
|   |   |   |   |   |   |   |   |
+---+---+---+---+---+---+---+---+
|   |   |   |   |   |   |   |   |
+---+---+---+---+---+---+---+---+
|   |   |   |   |   |   |   |   |
+---+---+---+---+---+---+---+---+

When you first call your function, the algorithm places a queen at column 0 and line 0 because you call it with col = 0 and because the for (int i = 0; i < N; i++) starts at 0. Your board becomes

+---+---+---+---+---+---+---+---+
| Q |   |   |   |   |   |   |   |
+---+---+---+---+---+---+---+---+
|   |   |   |   |   |   |   |   |
+---+---+---+---+---+---+---+---+
|   |   |   |   |   |   |   |   |
+---+---+---+---+---+---+---+---+
|   |   |   |   |   |   |   |   |
+---+---+---+---+---+---+---+---+
|   |   |   |   |   |   |   |   |
+---+---+---+---+---+---+---+---+
|   |   |   |   |   |   |   |   |
+---+---+---+---+---+---+---+---+
|   |   |   |   |   |   |   |   |
+---+---+---+---+---+---+---+---+
|   |   |   |   |   |   |   |   |
+---+---+---+---+---+---+---+---+

Then, you call the function recursively, with col = 1, so you'll attempt to place a queen at col=1 and line=0. You get an impossible placement because the queens could take each other, so you continue the for (int i = 0; i < N; i++) loop and eventually succeed in placing a queen at col=1 and line=2, you get this board:

+---+---+---+---+---+---+---+---+
| Q |   |   |   |   |   |   |   |
+---+---+---+---+---+---+---+---+
|   |   |   |   |   |   |   |   |
+---+---+---+---+---+---+---+---+
|   | Q |   |   |   |   |   |   |
+---+---+---+---+---+---+---+---+
|   |   |   |   |   |   |   |   |
+---+---+---+---+---+---+---+---+
|   |   |   |   |   |   |   |   |
+---+---+---+---+---+---+---+---+
|   |   |   |   |   |   |   |   |
+---+---+---+---+---+---+---+---+
|   |   |   |   |   |   |   |   |
+---+---+---+---+---+---+---+---+
|   |   |   |   |   |   |   |   |
+---+---+---+---+---+---+---+---+

Now you keep doing this, incrementing col every time. Eventually, you'll get to this board:

+---+---+---+---+---+---+---+---+
| Q |   |   |   |   |   |   |   |
+---+---+---+---+---+---+---+---+
|   |   |   | Q |   |   |   |   |
+---+---+---+---+---+---+---+---+
|   | Q |   |   |   |   |   |   |
+---+---+---+---+---+---+---+---+
|   |   |   |   | Q |   |   |   |
+---+---+---+---+---+---+---+---+
|   |   | Q |   |   |   |   |   |
+---+---+---+---+---+---+---+---+
|   |   |   |   |   | Q |   |   |
+---+---+---+---+---+---+---+---+
|   |   |   |   |   |   |   |   |
+---+---+---+---+---+---+---+---+
|   |   |   |   |   |   | Q |   |
+---+---+---+---+---+---+---+---+

You have a problem here, because this board doesn't admit a queen position in column 7. You'll have to backtrack. What happens is that the recursive function only reaches return false; after all positions in a column were attempted and no position was found. When the function returns false, the previous function call will resume execution on the line

if ( solveNQUtil(board, col + 1) == true )

Since the call returned true, the rest of the for loop's body will be executed, i will be incremented and the algorithm will keep trying positions. Think of this as a gigantic set of nested for loop:

for(int i = 0; i < 8; ++i) {
  for(int j = 0; j < 8; ++j) {

    //Snip 6 other fors

    board[0, i] = 1;
    board[1, j] = 1;

    //Snip

    if(isValid(board)) return board;

    //Snip clean up
  }
}

That you replace with recursive function calls. This illustrates that "backtracking" is really just letting the previous recursive level iterate to its next attempt. In this case, it means trying a new position while in other applications it would be to attempt the next generated move.

I think what you need to understand is that the state of the previous recursive call is not lost when you call the same function again. When you reach the line

if ( solveNQUtil(board, col + 1) == true )

The state of the current function is still on the stack and a new stack frame is created for the new call to solveNQUtil. When that function returns, the previous one can continue its execution and, in this case, increment which line it's attempting to place the queen in.

Hope this helps. The best way to wrap your head around this stuff is to reduce your problem to a smaller domain (say a smaller amount of queens) and step through the execution using a debugger.

Answer 2

The direct answer to your question is simple: you position and remove the queen in a loop. The next time through the loop, you will try the next position.

Which brings me to the next point: you say that the text book doesn't have the backtracking code, but only the recursion code. The recursion code is the backtracking code. When recursing, each instance of the function has its own full set of variables. So in this case, when solveNQUtil is called, the problem has already been solved for the first col - 1 columns. The function iterates through the rows, each time testing whether it can place a queen, and if so, placing it, and recursing. The iteration ensures that all possible places will be examined (if necessary---your code terminates as soon as we find a solution).