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 = [x1, x2, x3, …., xn]. Each xi = 1, 2, …, n. If queen Qi can be placed successfully in column j, then set
xi = j. Qi is always placed in row i.
Step 1: Place Q1 on (1, 1) → Successful
Step 2: Place Q2 on (2, 1) → Fail → Backtrack
Step 3: Place Q2 on (2, 2) → Fail → Backtrack
Step 4: Place Q2 on (2, 3) → Successful
Step 5: Place Q3 on (3, 1) → Fail → Backtrack
Step 6: Place Q3 on (3, 2) → Fail → Backtrack
Step 7: Place Q3 on (3, 3) → Fail → Backtrack
Step 8: Place Q3 on (3, 4) → Fail → Backtrack
Step 9: Place Q3 on (3, 5) → Successful
Step 10: Place Q4 on (4, 1) → Fail → Backtrack
Step 11: Place Q4 on (4, 2) → Successful
Step 12: Place Q5 on (5, 1) → Fail → Backtrack
Step 13: Place Q5 on (5, 2) → Fail → Backtrack
Step 14: Place Q5 on (5, 3) → Fail → Backtrack
Step 15: Place Q5 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 6th column, the second queen is in the 4th column, the third queen is in the 7th column and forth queen is in the 1st column.
Given arrangement of queen is,
- Assume queen Q1 is placed on position (i, j) and Q2 is placed on position (k, l). Q1 and Q2 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 Q4 = (4, 1) → position of queen in row 4
Q5 = (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