5. Defining search primitives: the n-Queens Problem

This chapter is about the customization of the search. What stategy(ies) to use to branch, i.e. what variables to select and what value(s) to assign to them? How to use nested searches, i.e. searches in subtrees? And so on.

The or-tools CP solver is quite flexible and comes with several tools (Decisions, DecisionBuilders, ...) that we call search primitives. Some are predefined and can be used right out of the box while others can be customized thanks to callbacks. You can also combine different search strategies. If needed, you can define your own search primitive classes by inheriting from base classes.

To efficiently use your tools, you need to know them a little and this chapter introduces you in a gentle manner to the inner working of the solver. The covered material is enough for you to understand how you can customize your search primitives without being drowned in the often tedious details of the implementation[1].

To illustrate the customization of the search, we try to solve the n-Queen Problem that we have introduced in the chapter Introduction to constraint programming.

Overview:

We first discuss the n-Queen Problem and present a basic model to solve it. To go one step further and devise a search algorithm to solve this problem, we present a little bit the inner working of the solver. Specifically, we show how it traverses and constructs the search tree. We even can visualize the search thanks to the wonderful cpviz framework that we introduce next. Equipped with this knowledge and visualization capacity, we can better understand out of the box and customized primitives and apply them to solve the n-Queen Problem. We end this chapter with a relatively advanced feature: SymmetryBreakers that allow to break symmetries during the search (on the fly).

Prerequisites:

• Basic knowledge of C++.
• Basic knowledge of Constraint Programming and the n-Queens Problem (see chapter Introduction to constraint programming).
• Basic knowledge of the Constraint Programming Solver (see chapter First steps with or-tools: cryptarithmetic puzzles).
• The willingness to roll up your sleeves and be prepared to look under the hood.

Classes under scrutiny:

Decision, DecisionBuilder, DecisionVisitor, SearchMonitor, TreeMonitor.

Files:

The files used in this chapter are:

• nqueens_utilities.h: Contains helper functions to test the number of solutions found and to print a solution.
• nqueens1.cc: A first implementation of our basic model to find all solutions.
• nqueens2.cc: The same implementation as in nqueen1.cc but this time to find only one solution.
• nqueens3.cc: The same implementation as in nqueen2.cc but this time we use a TreeMonitor to visualize the search with the program cpviz.
• nqueens4.cc: The same implementation as in nqueen3.cc but with some added statistics.
• solver_benchmark.h: a basic SolverBenchmark class to benchmark different search strategies.
• phases1.cc: we use the SolverBenchmark class to test different search strategies to find the next variables and values to branch on among the predefined choices in the IntVarStrategy and IntValueStrategy enums.
• nqueens5.cc: we create our own customized search strategies to find the next variables and values to branch on with the help of callbacks.
• nqueens6.cc: We create our own customized search strategies to find the next variables and values to branch on by defining our own DecisionBuilder class.
• nqueens7.cc: We use SymmetryBreakers to speed up the search.
• nqueens8.cc: We combine both approaches from nqueens6.cc and nqueens7.cc.

Content:

• 5.1. The n-Queens Problem
  • 5.1.1. The n-Queens Problem in more details
  • 5.1.2. How to solve the problem?
• 5.2. Implementation of a basic model
  • 5.2.1. The model completed
  • 5.2.2. The helper functions
  • 5.2.3. The whole program bundled
  • 5.2.4. First results
• 5.3. Basic working of the solver: the search algorithm
  • 5.3.1. Basic definitions
  • 5.3.2. The basic idea
  • 5.3.3. The basic search algorithm and the callback hooks for the SearchMonitors
• 5.4. cpviz: how to visualize the search
  • 5.4.1. TreeMonitors to provide the cpviz input
  • 5.4.2. Interpreting the graphical results
• 5.5. Basic working of the solver: the phases
  • 5.5.1. DecisionBuilders and phases
  • 5.5.2. Decisions and DecisionVisitors
  • 5.5.3. Combining DecisionBuilders
  • 5.5.4. Nested searches
  • 5.5.5. The MakePhase() method more in details
• 5.6. Out of the box variables and values selection primitives
  • 5.6.1. IntVarStrategy enums to select the next variable
  • 5.6.2. IntValueStrategy enums to select the next value
  • 5.6.3. Results
• 5.7. Customized search primitives: DecisionBuilders and Decisions
  • 5.7.1. BaseObject and RevAlloc
  • 5.7.2. The basic search strategy visualized
  • 5.7.3. First try: start from the center (and use callbacks)
  • 5.7.4. Second try: dynamic variable selection (and define our own DecisionBuilder class)
  • 5.7.5. How to customize search primitives?
• 5.8. Breaking symmetries with SymmetryBreakers
  • 5.8.1. The basic idea
  • 5.8.2. SymmetryBreakers
  • 5.8.3. The SymmetryManager
  • 5.8.4. Results
• 5.9. Summary
  • 5.9.1. Combining both approaches

Footnote

[1]	If you take a look at the source code, we hope you will enjoy the clarity (?) of our code. We believe that the most efficient code should remain simple and allow for more complicated but more efficient specializations when needed.