/    /  DAA- N-queens problem

N-queens problem

 

The n- queen problem is yet another example of problems that can be solved using backtracking. In the n-queens problem, a number of n queens are placed in a chessboard of n x n dimensions, in such a way that no queens attack each other by being in the same diagonal,  row, or column. It is generally seen in an 8 x 8 matrix. The generalized version, that is the 8- queens problem was proposed by Max Bezel. 

daa2

 

The n- queen problem must follow the following rules:

  1. There must be at least one queen in each column. 
  2. There must be at least one queen in each row. 
  3. There must be at least one queen in each diagonal. 

 

For example, let us take a chessboard of 4 x 4 dimensions, For the 4 x 4 chessboard, we will have 4 queens, q1, q2, q3, and q4. They are to be placed in such a way that they do not each other. So we need to put each queen in a different row, let us say row “i”. So, now we put the q1 in (1,1) and accordingly put q2, so they don’t attack each other. The first position to successfully achieve it is (2,3). But by doing so there will be no acceptable positions left for q3, so we backtrack q2, and put it in (2,4) which is the next best possible place on the chessboard. Then we can put q3 on (3,2), but if we do so we will not be able to find a position for q4. This time we have to backtrack from q1. We put q1 in the second-best position, which is (1,2), similarly, q2 goes to (2,4), q3 is placed in (1,2), and q4 is finally allotted to (4,3). Therefore, we get the solution : (2, 4, 1, 3). It is one of the possible solutions for the 4 – queens problem, another solution can be (3, 1, 4, 2), which is achieved by repeating the entire process for partial solutions. 

 

Algorithm for the n- queens problem:

Begin
 if there is a queen at the left of the current col, then
    return false
 if there is a queen at the left upper diagonal, then
    return false
 if there is a queen at the left lower diagonal, then
    return false;
 return true //otherwise it is a valid place
End

 

Using the is_safe() function:

This function is used so that we don’t have to check every element in the left and right diagonal, but just use the property of the diagonals. 

For the right diagonals, the sum of i and j are constant and unique. 

For the left diagonals, the difference between i and j are constant and unique. 

 

Applications of the n- queen problem:

The n- queen problem also has many practical applications, such as it is used in VLSI testing, traffic control, parallel memory storage schemes, and deadlock prevention. 

It can also be used for the traveling salesperson problem or TSP. 

For the n- queen problems we must keep the following terminologies in mind:

 

  • Distinct solution

 

It is found by performing rotation on the chessboard. 

 

  • Moves in chess

 

We must be aware of the movements of the queen. 

 

Reference

N-queens problem