2. First steps with or-tools: cryptarithmetic puzzles

This chapter introduces the basics of the or-tools library. In particular, we show how to use the Constraint Programming Solver (CP Solver). It takes a while to get used to the logic of the library, but once you grasp the basics explained in this chapter, you’re good to go and you should be able to find your way through the numerous examples provided with the library.

Overview:

We start with a discussion on the setup of the library, then walk through a complete example to solve a cryptarithmetic puzzle. Along the way, we see how to create the CP solver and populate it with a model, how to control the search with a DecisionBuilder, collect solutions with SolutionCollectors and change the behavior of the program with parameters (through the Google gflags library). Finally, we say a few words about the other supported languages (Python, Java and C#).

The section At a glance summarizes in two Figures all the required steps to write a basic program.

Prerequisites:

• basic knowledge of C++.
• basic knowledge of Constraint Programming (see the chapter Introduction to constraint programming).

Classes under scrutiny:

IntVar, AllDifferent, DecisionBuilder, SolutionCollector, Assignment, SearchMonitor.

Files:

The files used in this chapter are:

• cp_is_fun1.cc: Our first example: a simple cryptarithmetic puzzle to show the basics.
• cp_is_fun2.cc: Use of SolutionCollectors to collect some or all solutions.
• cp_is_fun3.cc: Use of the Google gflags library to parse command line parameters.
• cp_is_fun4.cc: Use of read-only solver parameters.

Content:

• 2.1. Getting started
• 2.2. Running the tutorial examples
  • 2.2.1. C++ examples
• 2.3. The cryptarithmetic puzzle problem and a first model
  • 2.3.1. Description of the problem
  • 2.3.2. How to solve the problem?
• 2.4. Anatomy of a basic C++ code
  • 2.4.1. At a glance
  • 2.4.2. Headers
  • 2.4.3. The namespace operations_research
  • 2.4.4. The CP solver
  • 2.4.5. Variables
  • 2.4.6. Assert-like macros
  • 2.4.7. Constraints
  • 2.4.8. The Decision Builder
  • 2.4.9. The search and the solutions
  • 2.4.10. The end of the search
• 2.5. SolutionCollectors and Assignments to collect solutions
  • 2.5.1. SolutionCollectors
  • 2.5.2. Assignments
• 2.6. Parameters
  • 2.6.1. Google’s gflags
  • 2.6.2. CP Solver‘s parameters
• 2.7. Other supported languages
• 2.8. Summary