How does backtracking work in solving the n queens problem?

[FallenApple]

I'm watching a vid on the n queens problem. Basically I have find out how to put n queens on a chess board of size n without them attacking each other. It's a rather famous puzzle.

"The eight queens puzzle is the problem of placing eight chess queens on an 8×8 chessboard so that no two queens threaten each other. Thus, a solution requires that no two queens share the same row, column, or diagonal. The eight queens puzzle is an example of the more general n queens problem of placing n non-attacking queens on an n×n chessboard, for which solutions exist for all natural numbers n with the exception of n=2 and n=3."

https://en.wikipedia.org/wiki/Eight_queens_puzzle

here there is no positions after the second level of the recursion. So it makes sense that after the third level of the recursion is popped from the stack, the second level will just continue the for loop.But why is the previous placement replaced?

He mentions that when the backtrack happens, the queen is placed on the 4th column. But that is only possible if the previous placement is nullifed. But how? I see nothing in the code that can erase the result of board[2][3]==2.

 

[willem2]

Even a youtube commenter got this:

Shouldn't there be a line to unplace a queen like this: board[row][column] = false; Otherwise, the queen will never be unplaced after the recursive call.

answer yes, there should be such a line, which should come after the if/else statement. You could only skip it if the board[][] array is a local variable which would be passed by value to NQueensBackTrack(). Adding and later removing the queensl should be faster.

 

[FallenApple]

Even a youtube commenter got this:

Shouldn't there be a line to unplace a queen like this: board[row][column] = false; Otherwise, the queen will never be unplaced after the recursive call.

answer yes, there should be such a line, which should come after the if/else statement. You could only skip it if the board[][] array is a local variable which would be passed by value to NQueensBackTrack(). Adding and later removing the queensl should be faster.

So its right after the if else statement on the same level as it but not within it?

 

[willem2]

So its right after the if else statement on the same level as it but not within it?

It seems the progam continues after "Print board" to find other solutions, so you should remove the queen always, so the program can continue, so it should not be in the else block, but after the entire if-else

 

[FallenApple]

It seems the progam continues after "Print board" to find other solutions, so you should remove the queen always, so the program can continue, so it should not be in the else block, but after the entire if-else

That makes sense. So the backtrack happens when the for loop finds nothing. If the for loop keeps finding something, eventually it will just hit print board, and never returns to the earlier call to reset the queen as removed.

 

[Aufbauwerk 2045]

For an explanation of this problem see Wirth, Algorithms + Data Structures = Programs (1976), Section 3.5. The whole of chapter 3 deals with recursive algorithms with great clarity.