In the following sections, we'll illustrate constraint programming (CP) 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 constraint programming. The following sections describe the CP approach to the N-queens problem, and present Python programs that solve it using both the CP-SAT solver and the original CP solver.
CP approach to the N-queens problem
A CP solver works by systematically trying all possible assignments of values to the variables in a problem, to find the feasible solutions. 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 constraint programming 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 constraint programming uses propagation and backtracking to solve the 4-queens problem.
Let's suppose 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 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.
Solution using CP-SAT
The N-queens problem is ideally suited to constraint programming. In this section we'll walk through a short Python program that uses the CP-SAT solver to find all solutions to the problem.
Declare the model
The following code declares the CP-SAT model.
from ortools.sat.python import cp_model def main(board_size): model = cp_model.CpModel()
Create the variables
The solver's NewIntVar method creates the variables for the problem as
an array named queens.
queens = [model.NewIntVar(0, board_size - 1, 'x%i' % i)
for i in range(board_size)]
Here we assume that
queens[j] is the row number for the queen in column j.
In other words, queens[j] = i means there is a queen in row
i and column j.
Note: When drawing a diagram of a solution, you will get a different picture depending on whether the rows are ordered from bottom to top or top to bottom (and whether the columns are ordered from left to right or vice versa). However, the ordering doesn't change the set of all possible solutions, just the way they are represented in a diagram.
Create the constraints
Here's the code that creates the constraints for the problem.
# The following sets the constraint that all queens are in different rows.
model.AddAllDifferent(queens)
# Note: all queens must be in different columns because the indices of queens are all different.
# The following sets the constraint that no two queens can be on the same diagonal.
for i in range(board_size):
# Note: is not used in the inner loop.
diag1 = []
diag2 = []
for j in range(board_size):
# Create variable array for queens(j) + j.
q1 = model.NewIntVar(0, 2 * board_size, 'diag1_%i' % i)
diag1.append(q1)
model.Add(q1 == queens[j] + j)
# Create variable array for queens(j) - j.
q2 = model.NewIntVar(-board_size, board_size, 'diag2_%i' % i)
diag2.append(q2)
model.Add(q2 == queens[j] - j)
model.AddAllDifferent(diag1)
model.AddAllDifferent(diag2)
The code uses the AddAllDifferent method,
which requires all the elements of a variable array to be different.
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 to queens
forces the values of
queens[j] to be different for each
j, 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
The diagonal constraint is a little trickier than the row and column constraints. First, if two queens lie on the same diagonal, one of the following conditions must be true:
- The row number plus the column number for each of the two queens are equal.
In other words,
queens(j) + jhas the same value for two different indicesj. - The row number minus the column
number for each of the two queens are equal. In this case,
queens(j) - jhas the same value for two different indicesj.
One of these conditions means the queens lie on the same ascending diagonal (going from left to right), while the other means they lie on the same descending diagonal. Which condition corresponds to ascending and which to descending depends on how you order the rows and columns. As mentioned in the previous section, the ordering has no effect on the set of solutions, just on how you visualize them.
So the diagonal constraint is that the values of queens(j) + j must all be different,
and the values of queens(j) - j must all be different, for different
j.
To apply the AddAllDifferent method to queens(j) + j, we
put the N instances of the variable, for j from 0 to N - 1, into an
array, diag1, as follows:
q1 = model.NewIntVar(0, 2 * board_size, 'diag1_%i' % i) diag1.append(q1) model.Add(q1 == queens[j] + j)
Then we apply
AddAllDifferent to diag1.
model.AddAllDifferent(diag1)
The constraint for queens(j) - j is created similarly.
Create a solution printer
To print all solutions to the N-queens problem, you need to pass a callback, called a solution printer, to the CP-SAT solver. The callback prints each new solution as the solver finds it. The following code creates a solution printer.
class SolutionPrinter(cp_model.CpSolverSolutionCallback):
"""Print intermediate solutions."""
def __init__(self, variables):
cp_model.CpSolverSolutionCallback.__init__(self)
self.__variables = variables
self.__solution_count = 0
def OnSolutionCallback(self):
self.__solution_count += 1
for v in self.__variables:
print('%s = %i' % (v, self.Value(v)), end = ' ')
print()
def SolutionCount(self):
return self.__solution_count
Note that the solution printer must be written as a Python class, due to the Python interface to the underlying C++ solver.
The solutions are printed by the following lines in the solution printer.
for v in self.__variables:
print('%s = %i' % (v, self.Value(v)), end = ' ')
In this example, self.__variables is the variable queens, and
each v corresponds to one of the eight entries of queens. This
prints a solution in the following form:
x0 = queens(0) x1 = queens(1) ... x7 = queens(7)
where xi is the column number of the queen in row i.
The next section shows an example of a solution.
Call the solver and display the results
The following code runs the solver and displays the solutions.
solver = cp_model.CpSolver()
solution_printer = SolutionPrinter(queens)
status = solver.SearchForAllSolutions(model, solution_printer)
print()
print('Solutions found : %i' % solution_printer.SolutionCount())
The program finds 92 different solutions for an 8x8 board. Here's the first one.
x0 = 0 x1 = 6 x2 = 4 x3 = 7 x4 = 1 x5 = 3 x6 = 5 x7 = 2 ...91 other solutions displayed... Solutions found: 92
The xi correspond to row numbers. So, for example,
x0 = 3 means that the row number for the queen in the first column is 3.
An alternative solution printer
The following code creates an alternative solution printer, which prints the solutions as chessboard diagrams.
class DiagramPrinter(cp_model.CpSolverSolutionCallback):
def __init__(self, variables):
cp_model.CpSolverSolutionCallback.__init__(self)
self.__variables = variables
self.__solution_count = 0
def OnSolutionCallback(self):
self.__solution_count += 1
for v in self.__variables:
queen_col = int(self.Value(v))
board_size = len(self.__variables)
# Print row with queen.
for j in range(board_size):
if j == queen_col:
# There is a queen in column j, row i.
print("Q", end=" ")
else:
print("_", end=" ")
print()
print()
def SolutionCount(self):
return self.__solution_count
You create this solution printer by the call
solution_printer = DiagramPrinter(queens)
Now when you run the program, it displays the diagrams for all solutions. The diagram for the first solution is
Q _ _ _ _ _ _ _ _ _ _ _ _ _ Q _ _ _ _ _ Q _ _ _ _ _ _ _ _ _ _ Q _ Q _ _ _ _ _ _ _ _ _ Q _ _ _ _ _ _ _ _ _ Q _ _ _ _ Q _ _ _ _ _ ...91 other solutions displayed... Solutions found: 92
You can solve the problem for a board of a different size by passing in N as
a command-line argument. For example, if the program is named queens,
python queens.py 6
solves the problem for a 6x6 board.
The entire program
Here is the entire program for the N-queens program.
from __future__ import print_function
import sys
from ortools.sat.python import cp_model
def main(board_size):
model = cp_model.CpModel()
# Creates the variables.
# The array index is the column, and the value is the row.
queens = [model.NewIntVar(0, board_size - 1, 'x%i' % i)
for i in range(board_size)]
# Creates the constraints.
# The following sets the constraint that all queens are in different rows.
model.AddAllDifferent(queens)
# Note: all queens must be in different columns because the indices of queens are all different.
# The following sets the constraint that no two queens can be on the same diagonal.
for i in range(board_size):
# Note: is not used in the inner loop.
diag1 = []
diag2 = []
for j in range(board_size):
# Create variable array for queens(j) + j.
q1 = model.NewIntVar(0, 2 * board_size, 'diag1_%i' % i)
diag1.append(q1)
model.Add(q1 == queens[j] + j)
# Create variable array for queens(j) - j.
q2 = model.NewIntVar(-board_size, board_size, 'diag2_%i' % i)
diag2.append(q2)
model.Add(q2 == queens[j] - j)
model.AddAllDifferent(diag1)
model.AddAllDifferent(diag2)
### Solve model.
solver = cp_model.CpSolver()
solution_printer = SolutionPrinter(queens)
status = solver.SearchForAllSolutions(model, solution_printer)
print()
print('Solutions found : %i' % solution_printer.SolutionCount())
class SolutionPrinter(cp_model.CpSolverSolutionCallback):
"""Print intermediate solutions."""
def __init__(self, variables):
cp_model.CpSolverSolutionCallback.__init__(self)
self.__variables = variables
self.__solution_count = 0
def OnSolutionCallback(self):
self.__solution_count += 1
for v in self.__variables:
print('%s = %i' % (v, self.Value(v)), end = ' ')
print()
def SolutionCount(self):
return self.__solution_count
class DiagramPrinter(cp_model.CpSolverSolutionCallback):
def __init__(self, variables):
cp_model.CpSolverSolutionCallback.__init__(self)
self.__variables = variables
self.__solution_count = 0
def OnSolutionCallback(self):
self.__solution_count += 1
for v in self.__variables:
queen_col = int(self.Value(v))
board_size = len(self.__variables)
# Print row with queen.
for j in range(board_size):
if j == queen_col:
# There is a queen in column j, row i.
print("Q", end=" ")
else:
print("_", end=" ")
print()
print()
def SolutionCount(self):
return self.__solution_count
if __name__ == '__main__':
# By default, solve the 8x8 problem.
board_size = 8
if len(sys.argv) > 1:
board_size = int(sys.argv[1])
main(board_size)
Solution using the original CP solver
The following sections present a Python program that solves N-queens using the original CP solver. (However, we recommend using the newer CP-SAT solver.)
Declare the solver
The following code declares the original CP solver.
from ortools.constraint_solver import pywrapcp
def main(board_size):
# Creates the solver.
solver = pywrapcp.Solver("n-queens")
Create the variables
The solver's IntVar 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, board_size - 1, "x%i" % i) for i in range(board_size)]
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(board_size)])) solver.Add(solver.AllDifferent([queens[i] - i for i in range(board_size)]))
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 to queens
forces the values of
queens[j] to be different for each
j, 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
The diagonal constraint is a little trickier than the row and column constraints. First, if two queens lie on the same diagonal, one of the following must be true:
- If the diagonal is descending (going from left to right), the row
number plus column number for each of the two queens are equal. So
queens(i) + ihas the same value for two different indicesi. - If the diagonal is ascending, the row number minus the column
number for each of the two queens are equal. In this case,
queens(i) - ihas the same value for two different indicesi.
So the diagonal constraint is that the values of queens(i) + i must all be different,
and likewise the values of queens(i) - i must all be different, for different
i.
The code above adds this constraint by applying the
AllDifferent method
to queens[j] + j and queens[j] - j,
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 are 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(board_size):
for j in range(board_size):
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
You 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 6
solves 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 |
Many solutions are just rotations of others, and a technique called symmetry breaking can be used to reduce the amount of computation needed. We don't use that here; our solution above isn't intended to be fast, just simple. Of course, we could make it much faster if we wanted to only find one solution instead of all of them: no more than a few milliseconds for board sizes up to 50.
The entire program
The complete program is shown below.
"""
OR-Tools solution to the N-queens problem.
"""
from __future__ import print_function
import sys
from ortools.constraint_solver import pywrapcp
def main(board_size):
# 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, board_size - 1, "x%i" % i) for i in range(board_size)]
# 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(board_size)]))
solver.Add(solver.AllDifferent([queens[i] - i for i in range(board_size)]))
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(board_size):
for j in range(board_size):
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.
board_size = 8
if __name__ == "__main__":
if len(sys.argv) > 1:
board_size = int(sys.argv[1])
main(board_size)