What is Constraint Programming ? What are the advantages/limits ? Can we make a sudoku solver in less than thirty minutes ?
One of those answers is yes.
Introduction
Lets start easy: What is constraint programming ?
CP is a declarative programming paradigm, which consist of solving a problem by defining the properties of the answer instead of the problem itself. Of all the programming paradigm, I think it’s the most elegant. In contrary of the “classical” approaches, based on a structure of following blocs of execution, we will focus on the analysis of the variables of our problem, and the constraint between those variables. We focus on what defines the problem instead of how to solve it.
Those constraints are then solved by a constraint propagation engine, which is an abstraction layer for us, and returns the variables, with their values constraints.
One of the advantages of working on constraints instead of the way to solve the problem by hand is the most convenient aspect of CP: it is possible to efficiently prove that a solution is (not) possible. Constraint programming is a heavy process for our computers, but in the case of an impossible problem, the contradiction is reached swiftly.
In summary, here is the principal uses for CP:
- Prove that a solution exists
- Prove that a solution does not exist
- Solve easily non-linear problems (e.g.: in robotics applications)
Advantages
If the conditions are correct, using this method is much faster than usual programming. The “solving a sudoku” example at the end of this post is a good demonstration: It took only one evening, a few hours of work, to make the all program, from loading the grid from an image with OpenCV to resolving the grid.
The fact that CP finds easily if a solution exists allows us to find instantly if the user gave us an impossible grid. No need to check all possibilities.
Using differential constraints allows us to resolve easily complex problems in robotics application, in particular non-linear state estimation problems, which are usually difficult to solve. CP solves the “kidnapped robot” problem, data delay and position estimation.
Limits
Obviously and as always, nothing is true and perfect and CP comes with (ironically) its own constraints.
First, constraint programming is a memory and CPU intensive process for a computer. Depending on methods and my own comprehension, constraint propagation is made with a graph or matrices. Thus, this process is not truly “embedded friendly”, and a microcontroller implementation do not exist for now.
Furthermore, because CP returns the reduces input variables, we can only obtain so much precision. The final solutions are almost always contained in an interval. If this interval is big, in a non-discrete context (like estimating a mobile robot position), CCP could be insufficient.
In my opinion, CP should not be use alone, and needs other algorithms to further strengthen the results.
Secondly, CP is really really sensible to outliers in the input data. Those outliers are rare (hence their name), but can still occur, and get in our system. A single outlier can produce an outlier constraint, which will prevent CP to find a single solution.
Solving a Sudoku
What about an example ? Try to make in your head a program able to solve a sudoku…
How do we handle the existence of several solutions ? Add movement constraints, like horseman movements (as in chess), a magic square for the middle square, a layout change, … We can find quickly complex solving procedures, but this kind of algorithm will take some time to write and test. Furthermore, a quick and naive approach would be pretty hard to modify to take on more complex cases like those mentioned earlier.
By using constraint programming, we only have to make a list of all the variables in our problem (here, the cells of the sudoku) and write the constraints that link those variables.
I already made a small project with Python, which uses CP to solve this problem.
In the file “SudokuSolver.py”, the function set_constraints handles the variable (at most 81 for a classical 9 x 9 grid) and the constraints.
The heart of the algorithm goes with 81 + 27 constraints:
- Each cell can take the value 1 to 9, excluding those already set at the start
- 9 lines in which each cell must have a different value
- 9 columns in which each cell must have a different value
- 9 squares in which each cell must have a different value