N-Queens 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.

4 x 4 Chessboard

• 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)

Fig. (a): Solution – 1

Fig. (b): Solution – 2

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. (c): State-space diagram for 4 – queen problem

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

Fig. (d): Backtracking sequence for 4-queen

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).

Fig. (e): Attacked cells by queen Q

• 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).

Fig. (f): Snapshot of backtracking procedure of 4-Queen problem

• 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.

Fig. (g): Solution of 8-queen problem

• 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.

Fig. (i): Non-feasible state of the 8-queen problem

Algorithm

• 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

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!).

Example: Find all possible solutions for the five queen problems using the backtracking approach.

Solution:

Solution of N queen problem is represented using
n-tuple X = [x₁, x₂, x₃, …., x_n]. Each x_i = 1, 2, …, n. If queen Q_i can be placed successfully in column j, then set
x_i = j. Q_i is always placed in row i.

Step 1:    Place Q₁ on (1, 1) → Successful

Step 2:    Place Q₂ on (2, 1) → Fail → Backtrack                  

Step 3:    Place Q₂ on (2, 2) → Fail → Backtrack                   

Step 4:    Place Q₂ on (2, 3) → Successful

Step 5:    Place Q₃ on (3, 1) → Fail → Backtrack                  

Step 6:    Place Q₃ on (3, 2) → Fail → Backtrack                  

Step 7:    Place Q₃ on (3, 3) → Fail → Backtrack

Step 8:  Place Q₃ on (3, 4) → Fail → Backtrack

Step 9:    Place Q₃ on (3, 5) → Successful

Step 10:  Place Q₄ on (4, 1) → Fail → Backtrack                  

Step 11:  Place Q₄ on (4, 2) → Successful

Step 12:  Place Q₅ on (5, 1) → Fail → Backtrack

Step 13:  Place Q₅ on (5, 2) → Fail → Backtrack                  

Step 14:  Place Q₅ on (5, 3) → Fail → Backtrack                  

Step 15:  Place Q₅ on (5, 4) → Successful

Thus, the solution of this instance is {1, 3, 5, 2, 4}.

Few more combinations are shown below:

Solutions: {1, 4, 2, 5, 3}, {2, 4, 1, 3, 5} and {2, 5, 3, 1, 4}

Solution: {3, 1, 4, 2, 5}, {3, 5, 2, 4, 1}, and {4, 1, 3, 5, 2}

Solution : {4, 2, 5, 3, 1}, {5, 2, 4, 1, 3}, {5, 3, 1, 4, 2}

Example: Current configuration is (6, 4, 7, 1) for 8-queens problem. Find answer tuple.

Solution:

Tuple (6, 4, 7, 1) indicates the first queen is in the 6^th column, the second queen is in the 4^th column, the third queen is in the 7^th column and forth queen is in the 1^st column.

Given arrangement of queen is,

• Assume queen Q₁ is placed on position (i, j) and Q₂ is placed on position (k, l). Q₁ and Q₂ would be on same diagonal if they satisfy following condition:

                   i + j    =   k + l OR

                   i – j    =   k – l

• We cannot place next queen on position (5, 1) as one queen is already in the same column. If we place next queen on (5, 2) then,

             Let Q₄    =   (4, 1) → position of queen in row 4

                     Q₅    =   (5, 2) → position of queen in row 5

• For these two queens, 4 – 1 = 5 – 2, so they are in same diagonal, so we cannot place next queen on position
  (5, 2). Try for next location (5, 3) and repeat the procedure for all possible positions.

Thus, final board position would be,