Examples of N-Queen Problem

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:

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,

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: Examples