Puzzled about backtracking in Eight Queen

问题:

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.

回答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.

回答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).

回答3:

You have to remember that there are two reasons for moving a queen down the board :

• It isn't in a safe position
• It IS in a safe position, but when you tried placing the next queen, the recursive call returned false, meaning you've exhausted all possibilities in the next column.

Your program was stalling at Queen 5 because it failed to account for the second condition. There is no need for tracking positions, as James said, each recursive call has implicit tracking for the queen it has to place.

Try to imagine the call stack (actually, you could modify your program to generate the same kind of output) :

Queen 1 is safe on row 1
    Queen 2 is safe on row 3
        Queen 3 is safe on row 5
            Queen 4 is safe on row 2
                Queen 5 is safe on row 4
                    No more rows to try for Queen 6. Backtracking...
                Queen 5 is safe on row 8
                    No more rows to try for Queen 6. Backtracking...
                No more rows to try for Queen 5. Backtracking...
            Queen 4 is safe on row 7
                Queen 5 is safe on row 2
                    Queen 6 is safe on row 4
                        Queen 7 is safe on row 6
                           No more rows to try for Queen 8. Backtracking...

Each time you're backtracking, realize that you get back to the previous function call, in the same state you left it. So when you reach Queen 6 and there are no possibilities, the function returns false, which means you've completed the solveNQUtil(board, col + 1) call for Queen 5. You are back in the for loop for Queen 5, and the next thing that's going to happen is that i gets incremented and you try to put Queen 5 on row 5 and so on...

I suggest you to play around with this demo (try the Placement Control : "Manual With Help" option), our brains are way better at understanding things visually. Code is too abstract.