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. Before starting off, the prerequisites for understanding this post is:
  • Java programming (Or at least be able to understand an algorithm)
  • 2-Dimensional arrays
  • Recursions.
  • N-Queens problem (What it is. click on it to open Wikipedia page if you don't know.)

Backtracking:
  • Backtracking is a form of recursion.
  • A Recursion is a function/method calling itself.
  • An example of recursion is the following function:
  • The above function would print the integers from 1 to n when n is > 0
  • If you study carefully the above function(or any recursive function), it has three main characteristics. They are:
    1. The problem has a base case(also called terminating condition) which in this case is return when n <= 0.
    2. The problem is broken down into smaller problems of the same type. This is done in this function with the recursive call printNumbers(n-1);
    3. Finally, it must be made sure that the base case is reached before a stack overflow occurs. Try removing the base case(the if block). You'd end up with a stack overflow as one function calls the other endlessly.
  • Now coming back to Backtracking, here we divide the problem into many subproblems and solve every subproblem till a possible solution is obtained.
  • For example, consider a problem which is divided into two subproblems A and B. A is again subdivided into C and D (and) B is subdivided into E and F. 
  • Let's say E is the required solution. The following steps are followed in a backtracking algorithm.
    1. The problem is divided into A and B.
    2. A is again subdivided into C and D.
    3. The subproblem C is solved but the solution is not obtained, 
    4. so we backtrack and solve D.
    5. Even then the solution is not obtained, so we backtrack and go back to B. 
    6. B is subdivided into E and F
    7. E is solved and the required solution is obtained.
    8. The search for a possible solution is terminated.
  • This is a simple explanation of a backtracking algorithm. Now let us see how backtracking helps us solve 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
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! If you are interested, you can check out the following Developing Sudoku solver!

Comments

  1. Now I have understood the n Queens problem. Thank you for pictorials presentations of the problem. It is better that hackerearth https://www.hackerearth.com/practice/basic-programming/recursion/recursion-and-backtracking/tutorial/

    ReplyDelete
  2. The initial theory is very nicely put up. Cheers!

    ReplyDelete
    Replies
    1. Thanks mate! let me know if I could do anything even better :)

      Delete
  3. what is the time complexity ? (or in genral can you explain how to find time complexity)

    ReplyDelete
  4. time complexity for N-Queens? In general, as far as I know time complexity differs from algorithm to algorithm. For the N-Queens it's O(N!). Here's a post that can help you: https://stackoverflow.com/a/20050433/5281962

    ReplyDelete
  5. I feel that you backtracked earlier by one step, as 4th queen can be placed at (4,3). Please correct me if wrong.

    ReplyDelete
    Replies
    1. Please note that my above comment is for the very first backtrack.

      Delete

Post a Comment

Popular posts from this blog

Guide to Solving Maximal Subarray Problem using Kadane's Algorithm

PvP Chain reaction game using Python