by In this tutorial, we would try to understand the N-Queen problem. Then in the next tutorial, we see how to solve it in Python using CP-SAT solver. We would cover the following:
- What is the N-Queen Problem
- Constraint Programming Approach to N-Queens Problem
- Constraint Propagation
- Backtracking
- Algorithm for Solving the N-Queens Problem
1. What is the N-Queens Problem
The N-Queens problems is related with the game of chess and it try to find:
“How many ways can N queens be placed on an N by N chessboard such that none of them attacks each other?”
Two queens attach each other if they are in the same row, the same column, or the same diagonal.
The figure below shows one possible solution the the N-Queens problem for a 4 x 4 chessboard (N = 4)
2. Constraint Programming Approach to N-Queens
The CP approach proceeds by successively trying all possible assignments of values to variables. In the case of N-Queens problem, the solver starts by placing the first queen at the leftmost column. Then in each iteration, one queen is placed in the next available column such that it is not attacked by any previously placed queen.
Two important concepts in solving the N-Queens problem is propagation and backtracking, discussed next.
3. Propagation
In propagation, anytime a value is assigned to a variable, additional restrictions are imposed on the possible values that the remaining unassigned variables can take. Then, these restrictions propagate to future variable assignments.
In the case of N-Queens problem, each time a queen is placed, then any other queen cannot be placed on the column or diagonal of the current queen. This means that as the solutions progresses and more restrictions are placed, then the search space reduces since the variable values reduces.
4. Backtracking
Backtracking happens for either of two reasons:
- no value can be assigned to the next variable due to constraints
- value cannot be further assigned if a solution is found
In either of these cases, the solver backtracks to the previous state and changes the values of the variable at that stage to another value that has not been tried. In the 4 queens example, this would be to move a queen to another square in the same column. Let’s now see exactly how this works!
5. Solving the N-Queens Problem
Assuming we have a 4 x 4 chess board as shown below. We begin by placing the first queen in first column as shown
At this point, we can no longer place any other queen in that column. Also we can’t place any queen in the first row, or the diagonal of the first queen( red lines).
We now move to the second column, and place the second queen in the next available cell as shown below. At this point, the propagated constraints are marked with red lines as well
At this point, we see more constraints on the remaining cells as shown with brown lines. As you can see, we can’t place any other queen on the third column. So the only available cell on the last column. So we place another queen there as shown below.
At this point, we can’t go any further. Since we still have one queen left, it means that this solution does not work.
So what we do now is to go one step back to the second queen (backtracking) and move it to another cell (the 4th row of the 2nd column). Then we repeat the process. So the process of backtracking and propagating continues until a solution is found or all the values are have been tried. In the next part, we would see how we can solve this problem in Python using CP-SAT solver.
