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

Examples of N-Queen Problem

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:

Solutions: {1, 4, 2, 5, 3}, {2, 4, 1, 3, 5} and {2, 5, 3, 1, 4}
Examples of N-Queen Problem
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 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.
Examples of N-Queen Problem

Thus, final board position would be,

Backtracking is useful in solving the following problems:

 


Additional Reading: Examples

Leave a Reply

Your email address will not be published. Required fields are marked *