5.9. Summary

This chapter is the first one of the second part of this manual and we have switched into high gear. The first part was about the basics of the solver, now we entered the core part: how to customize the CP solver to our needs. This cannot be done without a basic understanding of the solver and this chapter provided you with enough insights into the main solving algorithm. In particular, we saw some search primitives and how to customize them. We also saw how they are called in the main search algorithm.

Our illustrative problem for this chapter is the n-Queens Problem. We have only proposed a basic model as our focus was to customize search primitives, not devise a good model. To better compare search strategies, we saw how to use the cpviz library to visualize the search tree and the propagations of the constraints.

Search primitives are blocks used by the CP solver to construct the search tree and conduct the search. Among them, we saw in details:

• SearchMonitors to control and monitor the search;
• DecisionBuilders and Decisions to create the search tree.

To customize search primitives, you can, in order of complexity:

• combine existing ones;
• redefine callbacks;
• implement your own version of some search primitive classes;
• mix all of the above.

For each case, we have seen an example.

Finally, we continued our discussion of symmetries in the search tree and saw a new way to skip them on the fly with the help of SymmetryBreakers. By devising better search primitives and algorithms, we went from a few seconds to only a few milli-seconds to solve the n-Queens Problem for .

You might be curious, as we are, to combine our best search strategy and the SymmetryBreakers. This is done in the next sub-section.

5.9.1. Combining both approaches

1. C++ code:
   1. nqueens8.cc

We have improved our search strategy and search time little by little. We started by a simple approach (file nqueens1.cc and algorithm A in the next table) and ended up with our best algorithm discussed in section Second try: dynamic variable selection (and define our own DecisionBuilder class). We then saw a completely different approach and used SymmetryBreakers with a default search algorithm (file nqueens7.cc and algorithm B in the next table). What about combining both approaches (file nqueens8.cc and algorithm C in the next table)?

	Statistics	Algorithm A	Algorithm B	Algorithm C
7	Failures	92	24	24
	Branches	82	44	41
8	Failures	328	71	54
	Branches	654	139	100
9	Failures	1216	272	186
	Branches	2430	541	367
10	Failures	4500	1074	642
	Branches	8998	2142	1275
11	Failures	17847	4845	2465
	Branches	35692	9686	4924
12	Failures	86102	23159	11770
	Branches	172202	46312	23511

To give you an idea of the progress we made, the following table gives you the time needed to solve the 14-Queens Problem with the three algorithms:

Algorithms	Time (s)
A	21,582
B	6,096
C	2.945

Combining both approaches did result in a clear cut gain but it is not always the case. Sometimes, two good ideas don’t mix that well.