Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Java N Queens backtracking

  1. Feb 10, 2017 #1
    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






    Nqueen1.png

    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?

    Nqueen2.png

    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.



     
  2. jcsd
  3. Feb 10, 2017 #2
    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, wich should come after the if/else statement. You could only skip it if the board[][] array is a local variable wich would be passed by value to NQueensBackTrack(). Adding and later removing the queensl should be faster.
     
  4. Feb 10, 2017 #3
    So its right after the if else statement on the same level as it but not within it?
     
  5. Feb 10, 2017 #4
    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
     
  6. Feb 11, 2017 #5
    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.
     
  7. Mar 28, 2017 #6
    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.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: N Queens backtracking
  1. Number of digits in n! (Replies: 8)

  2. C++ power of n number (Replies: 13)

  3. N-body problem in Python (Replies: 10)

Loading...