The following sections explain how to do some common tasks related to solving Constraint Programming problems.

## Combining constraints by "and" versus "or"

Any pair of constraints in an optimization problem can be combined by "and" or "or." We'll explain how to combine constraints both ways.

As an illustration, let's add a second constraint to the simple example shown previously. The constraints are now

- x ≠ y
- y ≠ z

The following sections show how to combine these two constraints by "and" and by "or":

- Combining constraints by "and"
- Combining constraints by "or"
- A Python program that illustrates both ways of combining constraints

**Combining constraints by "and"**

Combining two constraints by "and" is simple — just apply the `solver.Add`

method twice. For example

solver.Add(x != y) solver.Add(y != z)The solver searches for solutions for which both constraints hold. When you run the program with the constraints shown above, it returns the 12 solutions for which x != y and y != z.

Solution 1 x = 0 y = 1 z = 0 Solution 2 x = 0 y = 1 z = 2 Solution 3 x = 0 y = 2 z = 0 Solution 4 x = 0 y = 2 z = 1 Solution 5 x = 1 y = 0 z = 1 Solution 6 x = 1 y = 0 z = 2 Solution 7 x = 1 y = 2 z = 0 Solution 8 x = 1 y = 2 z = 1 Solution 9 x = 2 y = 0 z = 1 Solution 10 x = 2 y = 0 z = 2 Solution 11 x = 2 y = 1 z = 0 Solution 12 x = 2 y = 1 z = 2

**Combining constraints by "or"**

To combine the two constraints by "or," use the method `solver.Max`

as follows:

solver.Add(solver.Max(x != y, y != z) == 1)Since the numerical value corresponding to True is 1, while False is 0,

`solver.Max`

acts as a logical "or" between Boolean conditions. That is,
`solver.Max(x != y, y != z)`

equals 1 if either
x != y or y != z,
and 0 otherwise. As a result, the code above adds the constraint
x != y or y != z.
With this constraint, the program returns the 24 solutions for which x != y or y != z.

Solution 1 x = 0 y = 0 z = 1 Solution 2 x = 0 y = 0 z = 2 Solution 3 x = 0 y = 1 z = 0 Solution 4 x = 0 y = 1 z = 1 Solution 5 x = 0 y = 1 z = 2 Solution 6 x = 0 y = 2 z = 0 Solution 7 x = 0 y = 2 z = 1 Solution 8 x = 0 y = 2 z = 2 Solution 9 x = 1 y = 0 z = 0 Solution 10 x = 1 y = 0 z = 1 Solution 11 x = 1 y = 0 z = 2 Solution 12 x = 1 y = 1 z = 0 Solution 13 x = 1 y = 1 z = 2 Solution 14 x = 1 y = 2 z = 0 Solution 15 x = 1 y = 2 z = 1 Solution 16 x = 1 y = 2 z = 2 Solution 17 x = 2 y = 0 z = 0 Solution 18 x = 2 y = 0 z = 1 Solution 19 x = 2 y = 0 z = 2 Solution 20 x = 2 y = 1 z = 0 Solution 21 x = 2 y = 1 z = 1 Solution 22 x = 2 y = 1 z = 2 Solution 23 x = 2 y = 2 z = 0 Solution 24 x = 2 y = 2 z = 1

**A Python program that illustrates both ways of combining constraints**

The following program combines the two constraints using both "and" and "or," and displays the results in each case.

from __future__ import print_function import sys from ortools.constraint_solver import pywrapcp def main(comb): # Creates the solver. solver = pywrapcp.Solver("simple_example") # Creates the variables. num_vals = 3 x = solver.IntVar(0, num_vals - 1, "x") y = solver.IntVar(0, num_vals - 1, "y") z = solver.IntVar(0, num_vals - 1, "z") # Create the constraints. label = '' # Label for displaying results. if comb is 'A_and_B': # Combine constraints by "and." solver.Add(x != y) solver.Add(y != z) label = 'Solutions for which x != y and y != z:' elif comb is 'A_or_B': # Combine constraints by "or." solver.Add(solver.Max(x != y, y !=z ) == 1) label = 'Solutions for which x != y or y != z:' # Create the decision builder. db = solver.Phase([x, y, z], solver.CHOOSE_FIRST_UNBOUND, solver.ASSIGN_MIN_VALUE) solver.Solve(db) print(label) print() count = 0 while solver.NextSolution(): count += 1 print("Solution" , count, '\n') print("x = ", x.Value()) print("y = ", y.Value()) print("z = ", z.Value()) print() print("Number of solutions: ", count) # Boolean combinations for two statments: # A: x != y # B: y != z boolean_combs = ['A_and_B', 'A_or_B'] if __name__ == "__main__": for comb in boolean_combs: main(comb)

## Creating a solution collector

A *solution collector* enables you to store some or all of the solutions to
a CP problem. After the search is complete, you can get the solutions you are interested in
from the solution collector. The following code creates a solution collector for the
N-queens example and adds the solution variables,
which are contained in the array `queens`

.

collector = solver.AllSolutionCollector() collector.Add(queens)

The collector is created by the `AllSolutionCollector`

method (corresponding to
the C++ method
`MakeAllSolutionCollector`

),
which stores all solutions.

After creating the collector, you call the solver as follows:

solver.Solve(db, [collector])

Once the search is complete, you can print the solutions as follows:

# Add variables to the solution collector. solution = solver.Assignment() solution.Add(queens) collector = solver.AllSolutionCollector() collector.Add(queens) if solver.Solve(db, [collector]): solution_count = collector.SolutionCount() print("Solutions found:", solution_count, "\n") # Create the solution distribution array, whose ith entry will be the number of solutions # that have a queen in the first entry of row i. sol_dist = [] for i in range(board_size): sol_dist.append(0) for sol in range(solution_count): for i in range(board_size): if collector.Value(sol, queens[0]) == i: # The solution has a queen in the first entry of row i, so increment sol_ sol_dist[i] += 1 print("Row Number of solutions with a queen in the row's first entry\n") for i in range(len(sol_dist)): print(str(i), " ", str(sol_dist[i])) else: print("No solution found.")

This produces the same output as the previous N-queens example. The only difference is that the previous example prints the solutions while the solver is running, while this example stores the solutions and then prints them after the solver is done.

The main reason for using a solution collector is that it enables you to analyze the stored solutions after the search terminates. As an example, suppose you want to count, for each row of the board, the number of solutions that have a queen in the first entry of that row. You can do so as follows.

# Count number of solutions that have a queen in the first entry of row i, for each row. sol_dist = [0, 0, 0, 0, 0, 0, 0, 0] for sol in range(solution_count): for i in range(board_size): if collector.Value(sol, queens[0]) == i: # The solution has a queen in the first entry of row i, so increment sol_ sol_dist[i] += 1 print("Row Number of solutions with a queen in the row's first entry\n") for i in range(len(sol_dist)): print(str(i), " ", str(sol_dist[i]))

This returns the following:

Row Number of solutions with a queen in the row's first entry 0 4 1 8 2 16 3 18 4 18 5 16 6 8 7 4

Note that the closer a row is to the middle of the board, the more solutions there are that have a queen in the first entry of the row.

### Solution collector example

An example program that uses a solution collector is shown below.

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. 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)) # 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) # Add variables to the solution collector. solution = solver.Assignment() solution.Add(queens) collector = solver.AllSolutionCollector() collector.Add(queens) if solver.Solve(db, [collector]): solution_count = collector.SolutionCount() print("Solutions found:", solution_count, "\n") # Create the solution distribution array, whose ith entry will be the number of solutions # that have a queen in the first entry of row i. sol_dist = [] for i in range(board_size): sol_dist.append(0) for sol in range(solution_count): for i in range(board_size): if collector.Value(sol, queens[0]) == i: # The solution has a queen in the first entry of row i, so increment sol_ sol_dist[i] += 1 print("Row Number of solutions with a queen in the row's first entry\n") for i in range(len(sol_dist)): print(str(i), " ", str(sol_dist[i])) else: print("No solution found.") # 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)

## Search limits

Constraint programming problems with many variables can take a long time to solve. For example, on a typical computer, the CP solver takes almost seven minutes to find all solutions to the N-Queens problem for a 15-by-15 board—the number of solutions is 2,279,184.

For such problems, it is a good idea to set a search limit, which stops the search after a specified length of time or number of solutions returned.

### Time limits

To set a time limit on the solver, you need to add a solution collector, as described in the previous section, and then use the`TimeLimit`

method
(corresponding to the C++ method
`MakeTimeLimit`

). The following code sets
a time limit of 15000 milliseconds, or 15 seconds.
time_limit_ms = solver.TimeLimit(15000)

Then add the following call to the solver.

if solver.Solve(db, [time_limit_ms, collector]): print("Solutions found in 15 seconds for a 15-by15 board: ", collector.SolutionCount())

If you then call the program with a command-line argument of 15 (which sets the board size), the program returns the following output:

Solutions found in 15 seconds: 158501

Note that in 15 seconds, the program finds only a small fraction of the total number of solutions.

### Solution limits

You can set a limit on the number of solutions found by the solver using the
`SolutionsLimit`

method (corresponding to the C++ method
`MakeSolutionsLimit`

).
For example, if you just want to find one solution to the N-queens problem,
you can call the solver with a solution limit of 1 as follows.

solutions_limit = solver.SolutionsLimit(1) solver.Solve(db, [solutions_limit, collector])

Again, if you call the program with the command-line argument of 15, it produces the following output.

Solutions found: 1 Q _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ Q _ _ _ _ _ _ _ _ _ _ _ _ Q _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ Q _ _ _ _ _ _ _ _ _ Q _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ Q _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ Q _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ Q _ _ _ _ _ _ _ _ _ Q _ _ _ _ _ _ _ _ _ Q _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ Q _ _ _ _ _ _ Q _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ Q _ _ _ _ _ _ _ _ _ _ _ _ Q _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ Q _ _ _

### Solution limit example

An example program that sets a solution limit is shown below.

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. 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)) # 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) # Add variables to the solution collector. solution = solver.Assignment() solution.Add(queens) collector = solver.AllSolutionCollector() collector.Add(queens) solutions_limit = solver.SolutionsLimit(1) if solver.Solve(db, [solutions_limit, collector]): solution_count = collector.SolutionCount() print("Solutions found:", solution_count, "\n") for i in range(board_size): for j in range(board_size): if collector.Value(0, queens[j]) == i: print("Q", end=" ") else: print("_", end=" ") print() print() print("Time:", solver.WallTime(), "ms") else: print("No solution found.") # 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)