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:

`SearchMonitor`s to control and monitor the search;`DecisionBuilder`s and`Decision`s 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 `SymmetryBreaker`s. 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 `SymmetryBreaker`s. This is done in the next sub-section.

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 `SymmetryBreaker`s 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.