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.


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


Classes under scrutiny:

Decision, DecisionBuilder, DecisionVisitor, SearchMonitor, TreeMonitor.


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.



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

Google or-tools
open source library

User's Manual

Google search



Tutorial examples


Part I: Basics
Part II: Customization
Part III: Routing
Part IV: Technicalities