Beginner's guide to Solving the N-Queens problem using backtracking method

This post serves as a good introduction to the backtracking method which is used widely in various types of problems to find a possible solution. Here we'll be seeing how to solve the classical N-Queens problem using backtracking method.

Backtracking:

The Wikipedia page for Backtracking defines it as "a general algorithm in which, we try to incrementally build candidates to the solutions, and discard a candidate as soon as we get to know that the candidate cannot possibly be completed to a valid solution". If that sounds complicated and confusing, don't worry! Let us understand it by running through a small example.

• Consider you are trapped in a haunted house with five rooms named A, B, C, D and E.
• Initially, you are in room A and you need to reach room E to exit the house.
• Below is an image of the rooms in the house.

• The arrows in the image indicate the directions in which you can move. For example, you can move to rooms B and C from A but, you cannot move back to room A from B.
• So, now let us build solutions for the above problem using the Backtracking algorithm.
1. Initially we are at room A and that's the only candidate we have
2. From A we can get two candidates B and C
3. First, Let us select B and continue building our solution
4. From B, we can move to either D or E
5. Let us select D
6. Now after going to D, we can no longer reach E! So with candidate D we can never find a possible solution.
7. So we discard candidate D and we go back to its parent candidate B. This is exactly what we call as backtracking. When we can no longer proceed from a point, we go back and select some other option.
8. From B we select the remaining option E and thus we found a solution!
9. We can stop at this point as we have found a solution or we can find all solutions by going through each and every candidate exhaustively.
10. As there is no point in continuing our search from E, we backtrack to its parent B
11. From B as we have no other options to select, so we once again backtrack to A
12. From A, we select the only remaining option C
13. From C we go to E and thus we have found all the solutions!
14. Below is the image of the process in which we built the solutions. The arrows 3, 5 and 6 indicate the steps where we backtracked and went back to previous candidate to select other option.

• This was a simple example for understanding the backtracking algorithm. Now let us see how we can use backtracking to solve the N-Queens problem.

N-Queens problem:

Before building an algorithm, let us solve the problem pictorially, Here's  a picture of a solution to 4 queens problem using backtracking:

• First, we place queen at (1,1)
  
• Now the second queen cannot be placed in columns 1 and 2 as those positions can be attacked by the first queen.
• So we place queen two initially at (2,3)
  
• Now when we try to place a queen in the third row, No possible location is present as all locations can be attacked by either first queen or second queen.
• So we backtrack and change the second queen's positon to (2,4)
  
• Now while placing the third queen there is only one possible location which is (3,2) so we place the third queen at (3,2)
  
• Once again we end up with no possible locations for placing the next queen. So we backtrack, but there are no alternative positions even for the third and second queens. So we backtrack and change the position of the first queen as (1,2)
  
• Now for placing the second queen, we have only on choice which is (2,4)
  
• Similarly, for placing the third queen, we have only one possible location (3,1)
  
• Finally, we have one possible location for placing the fourth queen which is (4,3)
  
• Thus a possible solution to the N-Queens problem is obtained and the algorithm terminates
• We can continue our algorithm to find all possible solutions. But I'll only be explaining here how to find a single possible solution.

Now let's build an algorithm to solve N-Queens problem. In order to build an algorithm to solve N-Queens problem, we'll be using two functions:

1. isAttacked(): to check whether the newly placed queen on the board can be attacked or not. Here's algorithm for it:
2. nQueens(): To solve the nQueens problem. This function uses isAttacked() method and backtracking to find a solution. The algorithm:

Now finally, here's the implementation of the above algorithm in java:
Check out the solutions for 8, 15, 20 queens problem obtained using the above implementation:

Hope this post has helped you understand what is backtracking and how to use it to solve the classical N-Queens problem.

Using the method of backtracking you can develop a simple program to solve any given Sudoku puzzle! I'd recommend you check out the following article Developing Sudoku solver! You can even add it as a project on your resume :-)