Common CP Tasks

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

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)

Send feedback about...

Optimization
Optimization