Puzzled by the return to the eight queens

Question

I have a complicated understanding of time and recursion, although I did some simple exercises (like Fibonacci). So let me introduce my brain flow here:

• I read the tutorial and know that you can use backtracking to delete the previous queen if her current position precludes the possibility of placing the next queen in the next column. So it seems easy, and all I have to do is delete it and let the program decide the next possible place.

• After some time, I found that the program was stalled at the 6th queen, so I realized that if I just remove the fifth queen, the program will simply return it to its current position (that is, given that the first four queens, the 5th queen always gets to the same place, which is not surprising). So I thought I needed to track the position of the last queen.

• This is when I am puzzled. If I were to track the position of the last queen (so when I go back, the program is NOT allowed to put the queen in the same place), there are two potential difficulties:

a) Say that I am removing the fifth queen, and I must write code defining his next possible position. This can be solved by ignoring its current position (before deletion) and continues to search for possible places in the following lines.

b) Should I keep track of all previous queens? It seems so. Let's say that in fact I need to remove not one queen, but two queens (or even more), I definitely have to keep track of all their current positions. But it is much more complicated than it seems.

• So, I started looking for answers in the textbook. Unfortunately, it does not have a return code, but there is only a recursion code. Then I found the code here:

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

It really struck me because it is so simple and yet works! The only backing part is to remove the last queen! Therefore, the question arises: how does the following code make sure that if you set the position of 4 queens, the fifth does not always fall into the same place again and again? I think I don’t understand how you can return recursively (say you need to remove more queens). I have no problem moving forward recursively, but how can I go back 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 a code that works, but I basically changed my own codes to match the above, so I'm pretty 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; } 

Let's say that numQueen is 5, so in the for loop we check if the 6th queen can be placed. As we know, this is not possible 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. Therefore, ClearQueen (4) is called and the last queen (fifth) is deleted. Apparently, the for loop did not finish, so we will try the next line to see if it allows further development. those. we check whether the 5th Queen can be placed on the next line, and if this happens, we will additionally check whether the sixth queen can be placed and so on.

Yes, it seems to work, well, yes, yes.

Answer 1

Consider the source board:

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

When you first call your function, the algorithm puts the queen in column 0 and row 0 because you call it with col = 0 and because 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 try to put the queen in col=1 and line=0 . You get impossible placement because queens can take each other, so you continue the for (int i = 0; i < N; i++) loop for (int i = 0; i < N; i++) and ultimately succeed in putting the queen in col=1 and line=2 , you will get this board:

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

Now you continue to do this, increasing col each time. In the end, you will be taken to this board:

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

You have a problem because this board does not allow the queen's position in column 7. You will have to back off. It happens that a recursive function reaches return false; after all positions in the column have been taken and no position has been 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 loop body will be executed, i will increase, and the algorithm will continue to search. Think of it as a giant set of nested loops:

 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 } } 

What do you replace with recursive function calls. This illustrates that backtracking actually just allows the previous recursive level to move on to the next attempt. In this case, this means an attempt at a new position, while in other applications it will be an attempt at the next generated move.

I think you need to understand 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 stack is created for a new call to solveNQUtil . When this function returns, the previous one can continue execution and, in this case, increase on which line he is trying to place the queen.

Hope this helps. The best way to wrap your head around this stuff is to reduce your problem to a smaller domain (say, fewer queens) and do it with a debugger.

Answer 2

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

Which leads me to the next point: you say that the textbook does not have a return code, but only a recursion code. The recursion code is the return code. When recursing, each function instance has its own complete set of variables. Therefore, in this case, when solveNQUtil is solveNQUtil , the problem has already been solved for the first col - 1 columns. the function iterates through the lines, each time checking whether it can place the queen, and if so, then it is placed recursively. iteration ensures that all possible places will be considered (if necessary --- your code is completed as soon as we find a solution).

Answer 3

You must remember that there are two reasons for moving the queen down the board:

• It is not in a safe place.
• It is in a safe place, but when you tried to put the next queen, the recursive call returned false , which means you have exhausted all the possibilities in the next column .

Your program stopped at Queen 5 because it did not take into account the second condition. There is no need to track positions, as James said, every recursive call has implicit tracking for the queen that he must place.

Try to imagine a call stack (in fact, you can change your program to create the same type 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 go back, understand that you will return to the previous function call, in the same state in which you left it. Therefore, when you reach Queen 6 and there are no possibilities, the function returns false, which means you have completed the call to solveNQUtil(board, col + 1) for Queen 5. You are back in the for loop for Queen 5, and the next thing that should happen is in that i gets incremented and you try to put Queen 5 on line 5 and so on ...

I suggest you play with this demo (try the Placement Control: "Manual With Help" option), our brains are much better at seeing things visually. The code is too abstract.