Solving the N Queen Problem

Introduction

The N Queen Problem is one of the best problem used to teach backtracking and of course recursion. Backtracking is a general algorithm which finds all complete solutions to a problem by building over partial solutions. In this process, the problem might reach to a partial solution which may not result into a complete solution. Such partial solutions are effectively rejected by the backtracking algorithm.

To know more about backtracking please visit the Wikipedia article.

The classic case of N Queen problem

In this problem, you are given an empty chess board of dimensions N * N. The task is to safely place N queens, one in each row such that they cause no harm to each other 🙂 . The basic idea is mentioned below:

  • Start from the first row
  • Select a column and if it is empty, well within the limits of the board and in no immediate danger, then place the queen in the cell
  • Proceed to the next row
  • Two conditions might occur,
    • all the rows are safely filled
    • somewhere down the line, one of the queens cant be placed in a row. Here we need to backtrack, because a decision was wrongly made in the past

This simple idea leads to a formal solution as described below. For simplicity of the code, we will just use a 5 * 5 board.

Formal Solution for N Queen Problem

The trick to the solution is to store the board correctly. You can either use a N * N array or simply a one dimensional array of length N. As you might have noticed that we only need to place N queens. We can very easily choose to store the position of the queen in each row. For e.g.
N Queen Problem

The first image shows an empty board, hence the array has -1. In the second image, there are queens in each row, the zeroth row contains a queen at index (0,4) of the matrix. The first row contains a queen at index (1, 1) and so on. Hence, the values in the array are 4, 1, 3, 0 and 2.

The second point in the above algorithm talks about the criteria for accepting a valid cell. A valid cell must have the below properties:

  • It must lie within the limits of the board
  • It must be empty
  • It must not be in immediate danger from the already placed queens (It must not lie in the same column and it must not lie on the major or minor diagonal)

What are major & minor diagonals ?

With respect to a cell(i, j), the major diagonal contains all the cells [(i+2, j+2),(i+1, j+1),(i, j), (i-1, j-1), (i-2, j-2), (i-3, j-3)] till the limits of the board. On similar lines the minor diagonal contains all the cells [(i+2, j-2), (i+1, j-1),(i, j), (i-1, j+1), (i-2,j+2), (i-3, j+3)] and so on till the limits of the board.

Here is a pictorial representation for the same. The blue ones are major diagonals and the red ones are minor diagonals.

N Queen Problem

It is evident that we need a method which can check if the current cell is safe. Here goes the method:

The backtracking step

Have a look at this small piece of code and then read the explanation below:

Check out the github link for the complete code

Explanation

  • Placing the first queen in the first row
    • Place it in the first cell (0,0) and check if it is safe
    • As this is the first queen, it is safe, so try placing the second queen in second row
  • Placing the second queen in the second row
    • Place the second queen in the cell(1,0) and check if it is safe
    • It is not safe because the zeroth column already has a queen, so remove the queen and try next cell
    • Place the queen at cell (1,1), it is still not safe because there is a queen at cell (0,0) which is the major diagonal of cell (1,1), so remove it and try next cell
    • Place the queen at cell (1,2). As it is safe, so try placing the third queen in the third row

That is the idea. The code goes through all possible arrangements and prints all of them.

Analysis for N Queen Problem

Space complexity

For this algorithm it is O(N). The algorithm uses an auxiliary array of length N to store just N positions.

Time complexity

  • The isSafe method takes O(N) time as it iterates through our array every time.
  • For each invocation of the placeQueen method, there is a loop which runs for O(N) time.
  • In each iteration of this loop, there is isSafe invocation which is O(N) and a recursive call with a smaller argument.

If we add all this up and define the run time as T(N). Then T(N) = O(N2) + N*T(N-1). If you draw a recursion tree using this recurrence, the final term will be something like n3+ n!O(1). By the definition of Big O, this can be reduced to O(n!) running time.

Let me know in comments if you are not able to derive the n! from the recurrence, I will try to draw the recursion tree.

Summary

Most of the time problems of backtracking can be easily identified by the following features:

  • It will have a lot of solutions
  • You will get some intuition that not all solutions will solve the problem and you might have to go back and change something
  • As each step, you have to verify the integrity of the solution. Like if it is safe to move etc
  • Based on the future steps, the present choice is considered a valid choice or not.
  • No need to worry about the backtracking part, the recursion stack takes care of it.

Problems like Knights Tour, Sudoku, Robots path in a grid are all of same kind.