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
(`Decision`s, `DecisionBuilder`s, ...) 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:
`SymmetryBreaker`s 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``enum`s.*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`SymmetryBreaker`s 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.2. Implementation of a basic model
- 5.3. Basic working of the solver: the search algorithm
- 5.4.
**cpviz**: how to visualize the search - 5.5. Basic working of the solver: the phases
- 5.6. Out of the box variables and values selection primitives
- 5.7. Customized search primitives:
`DecisionBuilder`s and`Decision`s - 5.8. Breaking symmetries with
`SymmetryBreaker`s - 5.9. Summary

[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. |