In the following sections, we'll illustrate the CP solver by a combinatorial problem based on the game of chess. In chess, a queen can attack horizontally, vertically, and diagonally. The N-queens problem asks:
How can N queens be placed on an NxN chessboard so that no two of them attack each other?
Below, you can see one possible solution to the N-queens problem for N = 4.
No two queens are on the same row, column, or diagonal.
Note that this isn't an optimization problem: we want to find all possible solutions, rather than one optimal solution, which makes it a natural candidate for the CP solver. The following sections describe the CP approach to the N-queens problem and present a Python program that finds all solutions using the CP solver.
The CP approach to the N-queens problem
To find all solutions to the N-queens problem, the CP solver systematically tries all possible assignments of values to the variables, to see which ones give feasible solutions to the problem (see A brief introduction to the CP solver). In the 4-queens problem, the solver starts at the leftmost column and successively places one queen in each column, at a location that is not attacked by any previously placed queens.
Propagation and backtracking
There are two key elements to a CP search:
- Propagation — Each time the solver assigns a value to a variable, the constraints add restrictions on the possible values of the unassigned variables. These restrictions propagate to future variable assignments. For example, in the 4-queens problem, each time the solver places a queen, it can't place any other queens on the row and diagonals the current queen is on. Propagation can speed up the search significantly by reducing the set of variable values the solver must explore.
- Backtracking occurs when either the solver can't assign a value to the next variable, due to the constraints, or it finds a solution. In either case, the solver backtracks to a previous stage and changes the value of the variable at that stage to a value that hasn't already been tried. In the 4-queens example, this means moving a queen to a new square on the current column.
Next, you'll see how the CP solver uses propagation and backtracking to solve the 4-queens problem.
The solver starts by arbitrarily placing a queen in the upper left corner. That's a hypothesis of sorts; perhaps it will turn out that no solution exists with a queen in the upper left corner.
Given this hypothesis, what constraints can we propagate? One constraint is that there can be only one queen in a column (the gray Xs below), and another constraint prohibits two queens on the same diagonal (the red Xs below).
Our third constraint prohibits queens on the same row:
Our constraints propagated, we can test out another hypothesis, and place a second queen on one of the available remaining squares. Our solver might decide to place in it the first available square in the second column:
After propagating the diagonal constraint, we can see that it leaves no available squares in either the third column or last row:
With no solutions possible at this stage, we need to backtrack. One option is for the solver to choose the other available square in the second column. However, constraint propagation then forces a queen into the second row of the third column, leaving no valid spots for the fourth queen:
And so the solver must backtrack again, this time all the way back to the placement of the first queen. We have now shown that no solution to the our queens problem will occupy a corner square.
Since there can be no queen in the corner, the solver moves the first queen down by one, and propagates, leaving only one spot for the second queen:
Propagating again reveals only one spot left for the third queen:
And for the fourth and final queen:
We have our first solution! If we instructed our solver to stop after finding the first solution, it would end here. Otherwise, it would backtrack again and place the first queen in the third row of the first column.
Python solution to the N-queens problem
The N-queens problem is ideally suited to constraint programming. In this section we'll walk through a short Python program that uses OR-Tools to solve N-queens for any value of N.
Declare the solver
The following code creates the CP solver for the program.
from ortools.constraint_solver import pywrapcp
def main(N):
# Creates the solver.
solver = pywrapcp.Solver("n-queens")
Create the variables
The solver's Int_Var method creates the variables for the problem as
an array named queens.
# Creates the variables. # The array index is the column, and the value is the row. queens = [solver.IntVar(0, N - 1, "x%i" % i) for i in range(N)]
queens[j] represents the square on the chessboard whose column number is
the index j, and whose row number (going from
top to bottom) is the value of queens[j]. For any solution,
queens[j] = i means there is a queen in column j and row
i.
Create the constraints
Here's the code that creates the constraints for the problem.
# Creates the constraints. # All rows must be different. solver.Add(solver.AllDifferent(queens)) # All columns must be different because the indices of queens are all different. # No two queens can be on the same diagonal. solver.Add(solver.AllDifferent([queens[i] + i for i in range(N)])) solver.Add(solver.AllDifferent([queens[i] - i for i in range(N)]))
Let's see how these constraints guarantee the three conditions for the N-queens problem (queens on different rows, columns, and diagonals).
No two queens on the same row
Applying the solver's AllDifferent method
(corresponding to the C++ method
MakeAllDifferent) to queens
forces the values of
queens[i] to be different for each
i, which means that all queens must be in different rows.
No two queens on the same column
This constraint is implicit in the definition of queens.
Since no two elements of queens
can have the same index, no two queens can be in the same column.
No two queens on the same diagonal
If two queens lie on the same diagonal of a chessboard, then
either the row
number plus the column number for both queens are equal, or the row number minus
the column number are equal (depending on whether
the diagonal goes up or down as you move from left to right). You can
convince yourself that this is so by trying a few examples. Since
queens[i] is the row number of the queen with column number i,
the following constraints ensure that no two queens are on the same diagonal:
- The values of
queens[i] + iare different for eachi. - The values of
queens[i] - iare different for eachi.
The code above adds this constraint by applying the
AllDifferent method
to queens[i] + i and queens[i] - i,
for each i.
Add the decision builder
The next step is to create a decision builder, which sets the search strategy for the problem. The search strategy can have a major impact on the search time, due to propagation of constraints, which reduces the number of variable values the solver has to explore. You have already seen an example of this in the 4-queens example.
The following code creates a decision builder using the solver's
Phase method.
db = solver.Phase(queens,
solver.CHOOSE_FIRST_UNBOUND,
solver.ASSIGN_MIN_VALUE)
See Decision builder for details on the
input arguments to the Phase method.
How the decision builder works in the 4-queens example
Let's take a look at how decision builder directs the search in the
4-queens example.
The solver begins with queens[0],
the first variable in the array,
as directed by CHOOSE_FIRST_UNBOUND. The solver then assigns queens[0]
the smallest value that hasn't already been tried, which is 0 at this stage,
as directed by ASSIGN_MIN_VALUE. This places the first queen in the
upper left corner of the board.
Next, the solver selects queens[1], which is now
the first unbound variable in queens.
After propagating the constraints, there two possible
rows for a queen in column 1: row 2 or row 3. The ASSIGN_MIN_VALUE option
directs the solver to assign
queens[1] = 2. (If instead, you set IntValueStrategy to
ASSIGN_MAX_VALUE, the solver would assign queens[1] = 3.)
You can check that the rest of the search follows the same rules.
Call the solver and display the results
The following code runs the solver and displays the solution.
solver.NewSearch(db)
# Iterates through the solutions, displaying each.
num_solutions = 0
while solver.NextSolution():
# Displays the solution just computed.
for i in range(N):
for j in range(N):
if queens[j].Value() == i:
# There is a queen in column j, row i.
print("Q", end=" ")
else:
print("_", end=" ")
print()
print()
num_solutions += 1
solver.EndSearch()
Here's the first solution found by the program for an 8x8 board.
_ _ _ Q _ _ _ _ _ Q _ _ _ _ _ _ _ _ _ _ Q _ _ _ _ _ _ _ _ _ _ Q _ _ _ _ _ Q _ _ Q _ _ _ _ _ _ _ _ _ Q _ _ _ _ _ _ _ _ _ _ _ Q _ ...91 other solutions displayed... Solutions found: 92 Time: 9 msYou can solve the problem for a board of a different size by passing in N as a command-line argument. For example,
python projects/queens.py 6solves the problem for a 6x6 board.
The number of solutions goes up roughly exponentially with the size of the board:
| Board size | Solutions | Time to find all solutions (ms) |
|---|---|---|
| 1 | 1 | 0 |
| 2 | 0 | 0 |
| 3 | 0 | 0 |
| 4 | 2 | 0 |
| 5 | 10 | 0 |
| 6 | 4 | 0 |
| 7 | 40 | 3 |
| 8 | 92 | 9 |
| 9 | 352 | 35 |
| 10 | 724 | 95 |
| 11 | 2680 | 378 |
| 12 | 14200 | 2198 |
| 13 | 73712 | 11628 |
| 14 | 365596 | 62427 |
| 15 | 2279184 | 410701 |
The entire program
Here is the entire program for the N-queens program.
"""
OR-tools solution to the N-queens problem.
"""
from __future__ import print_function
import sys
from ortools.constraint_solver import pywrapcp
def main(N):
# Creates the solver.
solver = pywrapcp.Solver("n-queens")
# Creates the variables.
# The array index is the column, and the value is the row.
queens = [solver.IntVar(0, N - 1, "x%i" % i) for i in range(N)]
# Creates the constraints.
# All rows must be different.
solver.Add(solver.AllDifferent(queens))
# All columns must be different because the indices of queens are all different.
# No two queens can be on the same diagonal.
solver.Add(solver.AllDifferent([queens[i] + i for i in range(N)]))
solver.Add(solver.AllDifferent([queens[i] - i for i in range(N)]))
db = solver.Phase(queens,
solver.CHOOSE_FIRST_UNBOUND,
solver.ASSIGN_MIN_VALUE)
solver.NewSearch(db)
# Iterates through the solutions, displaying each.
num_solutions = 0
while solver.NextSolution():
# Displays the solution just computed.
for i in range(N):
for j in range(N):
if queens[j].Value() == i:
# There is a queen in column j, row i.
print("Q", end=" ")
else:
print("_", end=" ")
print()
print()
num_solutions += 1
solver.EndSearch()
print()
print("Solutions found:", num_solutions)
print("Time:", solver.WallTime(), "ms")
# By default, solve the 8x8 problem.
N = 8
if __name__ == "__main__":
if len(sys.argv) > 1:
N = int(sys.argv[1])
main(N)