N Queen Problem

What is N Queen Problem?

N Queen problem is the classical Example of backtracking. N-Queen problem is defined as, “given N x N chess board, arrange N queens in such a way that no two queens attack each other by being in same row, column or diagonal”.

• For N = 1, this is trivial case. For N = 2 and N = 3, solution is not possible. So we start with N = 4 and we will generalize it for N queens.

4-Queen Problem

Problem : Given 4 x 4 chessboard, arrange four queens in a way, such that no two queens attack each other. That is, no two queens are placed in the same row, column, or diagonal.

• We have to arrange four queens, Q1, Q2, Q3 and Q4 in 4 x 4 chess board. We will put ith queen in ith row. Let us start with position (1, 1). Q1 is the only queen, so there is no issue. partial solution is <1>
• We cannot place Q2 at positions (2, 1) or (2, 2). Position (2, 3) is acceptable. partial solution is <1, 3>.
• Next, Q3 cannot be placed in position (3, 1) as Q1 attacks her. And it cannot be placed at (3, 2), (3, 3) or (3, 4) as Q2 attacks her. There is no way to put Q3 in third row. Hence, the algorithm backtracks and goes back to the previous solution and readjusts the position of queen Q2. Q2 is moved from positions (2, 3) to
  (2, 4). Partial solution is <1, 4>
• Now, Q3 can be placed at position (3, 2). Partial solution is <1, 4, 3>.
• Queen Q4 cannot be placed anywhere in row four. So again, backtrack to the previous solution and readjust the position of Q3. Q3 cannot be placed on (3, 3) or(3, 4). So the algorithm backtracks even further.
• All possible choices for Q2 are already explored, hence the algorithm goes back to partial solution <1> and moves the queen Q1 from (1, 1) to (1, 2). And this process continues until a solution is found.
• All possible solutions for 4-queen are shown in fig (a) & fig. (b)

We can see that backtracking is a simple brute force approach, but it applies some intelligence to cut out unnecessary computation. The solution tree for the 4-queen problem is shown in Fig. (c).

Fig. (d) describes the backtracking sequence for the 4-queen problem.

The solution of the 4-queen problem can be seen as four tuples (x₁, x₂, x₃, x₄), where x_i represents the column number of queen Q_i. Two possible solutions for the 4-queen problem are (2, 4, 1, 3) and (3, 1, 4, 2).

8-Queen Problem

Problem : Given an 8 x 8 chessboard, arrange 8 queens in a way such that no two queens attack each other.

Two queens are attacking each other if they are in the same row, column, or diagonal. Cells attacked by queen Q are shown in fig. (e).

• 8 queen problem has ⁶⁴C₈= 4,42,61,65,368 different arrangements. Of these, only 92 arrangements are valid solutions. Out of which, only 12 are the fundamental solutions. The remaining 80 solutions can be generated using reflection and rotation.
• The 2-queen problem is not feasible. The minimum problem size for which a solution can be found is 4. Let us understand the workings of backtracking on the 4-queen problem.
• For simplicity, a partial state space tree is shown in fig. (f). Queen 1 is placed in the first column in the first row. All the positions are crossed in which Queen 1 is attacking. In the next level, queen 2 is placed in a 3rd column in row 2 and all cells that are crossed are attacked by already placed queens 1 and 2. As can be seen from fig (f), no place is left to place the next queen in row 3, so queen 2 backtracks to the next possible position and the process continues. In a similar way, if (1, 1) position is not feasible for queen 1, then the algorithm backtracks and puts the first queen in cell (1, 2), and repeats the procedure. For simplicity, only a few nodes are shown in fig. (f).

• A complete state space tree for the 4-queen problem is shown in fig. (g)
• The number within the circle indicates the order in which the node gets explored. The height of the e from the t indicates row and label, besides the arc indicating that the Q is placed in an ith column. Out of all the possible states, only a few are the answer states.

• Solution tuple for the solution shown in fig (h) is defined as <4, 6, 8, 2, 7, 1, 3, 5>. From observations, two queens placed at (i, j) and (k, l) positions, can be in same diagonal only if,

                                 (i – j )   =   (k – l) or

                                  (i + j)   =   (k + l)

From first equality, j – l   =   i – k

From second equality, j – l = k – i

So queens can be in diagonal only if |j – l| = | i – k|.

The arrangement shown in fig. (i) leads to failure. As it can be seen from fig. (i), Queen Q6 cannot be placed anywhere in the 6th row. So the position of Q5 is backtracked and it is placed in another feasible cell. This process is repeated until the solution is found.

Algorithm

The following algorithm arranges n queens on n x n board using a backtracking algorithm.

Algorithm

N_QUEEN (k, n)
// Description : To find the solution of n x n queen problem using backtracking
// Input : 
n: Number of queen
k: Number of the queen being processed currently, initially set to 1.

// Output : n x 1 Solution tuple 

for

i ← 1 to n 

do

if

PLACE(k , i) 

then

    x[k] ← i
    

if

k == n 

then

      print X[1…n]
    

else

      N_QUEEN(k + 1, n)
    

end

end

end

• Function PLACE (k, i) returns true, if the k^th queen can be placed in the i^th column. This function enumerates all the previously kept queen’s positions to check if two queens are on the same diagonal. It also checks that i is distinct from all previously arranged queens.
• Function abs(a) returns the absolute value of argument a. The array X is the solution tuple.
• Like all optimization problems, the n-queen problem also has some constraints that it must satisfy. These constraints are divided into two categories : Implicit and explicit constraints

Function

PLACE(k, i)
// k is the number of queen being processed
// i is the number of columns

for

 j ← 1 to k – 1 

do

if

x[j] == i OR ((abs(x[j]) - i) == abs(j - k)) 

then

return

false
  

end

end

return

true

Explicit Constraints:

• Explicit constraints are the rules that allow/disallow selection of x_i to take value from the given set. For example, x_i = 0 or 1.

                      x_i      =   1 if LB_i  ≤  x_i  ≤ UB_i

                      x_i      =   0 otherwise

• Solution space is formed by the collection of all tuple which satisfies the constraint.

Implicit constraints:

• The implicit constraint is to determine which of the tuple of solution space satisfies the given criterion functions. The implicit constraint for n queen problem is that two queens must not appear in the same row, column or diagonal.
• Complexity analysis : In backtracking, at each level branching factor decreases by 1 and it creates a new problem of size (n – 1) .  With n choices, it creates n different problems of size (n – 1) at level 1.
• PLACE function determines the position of the queen in O(n) time. This function is called n times.
• Thus, the recurrence of n-Queen problem is defined as, T(n) = n*T(n – 1) + n². Solution to recurrence would be O(n!).

Popular problems solved using backtracking:

Backtracking is useful in solving the following problems:

• N-Queen problem
• Sum of subset problem
• Graph coloring problem
• Knapsack problem
• Hamiltonian cycle problem

---

Additional Reading: Read more