In our recent blog by Fernando Donati Jorge, he explains how to use rules in Blaze for solving Sudoku puzzles.
In this version of Solving Sudoku, I am going to present a different set of tools and techniques for solving such problems, namely Constraint Programming. Since the first Sudoku puzzles made their way into European journals in the mid-2000s this puzzle has become a favorite for explaining the basic ideas of Constraint Programming. To visualize the results, I will explain how to make use of the Mosel package mmsvg, to not only display but also animate the solving process.
Some historical notes:
Constraint Programming, or CP for short, has evolved since the 1970s/80s out of a combination of techniques from various areas, including
The term ‘Constraint Programming’ is commonly used since the early 1990s (the first international scientific conference specifically dedicated to this topic ‘Principles and Practice of Constraint Programming’ took place in 1995).
Commercial tools, initially usually implemented with Prolog, later on, more often as extensions to other programming languages such as C++ or Java have become available since the late 1980s. Constraint solvers are typically classified by the type of variable domains over which they work (e.g. finite domains, floating point, intervals, sets).
In this blog, we are going to work with Xpress Kalis – a component of FICO Xpress Optimization that employs the Artelys Kalis solver by Artelys SA . Kalis has solvers for discrete (finite domain) and continuous (floating point intervals) problems.
Basic principles of CP:
A constraint system is defined by:
The goal is to find an assignment of values to the variables that satisfy all the constraints.
Finite domain solvers usually implement local consistency algorithms that check the system of constraints for inconsistencies and remove infeasible values from the variables’ domains. If any domain changes occur, these are propagated iteratively via the constraint relations to all other possibly affected variables, this process is known as constraint propagation (illustrated in the figure below). If a domain becomes empty then there is no solution.
Figure: Constraint propagation for a 3x3 subsquare of a Sudoku board (each cell needs to take a different value from all others)
To represent the Sudoku problem as a Constraint Programming problem we work with discrete (finite domain) decision variables v(columnindex, rowindex) that each takes values from the set {1,…9}.
Figure 4: Initial board
Formulating the constraints
Now the remaining task is the formulation of the constraints: different values for all cells belonging to the same row, the same column, or the same 3x3 subsquare of the board. We might choose to work with pairwise disequalities, e.g. to state that all cells in the same row need to take different values:
This ‘alldifferent’ relation is a so-called global constraint: it works on a larger (sub)set of decision variables, allowing the local consistency checks to adopt a more global view of the problem than what would be possible, for instance, through the pairwise disequality constraints.
The effect of adding the row-wise alldifferent constraints for the Sudoku instance from Figure 4 shown in the following graphic:
Figure 5: After posting row-wise alldifferent constraints
We also need to state the column-wise alldifferent relations:
Figure 6: After posting column-wise alldifferent constraints
And finally, the constraints that all cells in the 3x3 subsquares must take different values:
Figure 7: After posting square-wise alldifferent constraints
After posting all constraints to the solver we may find that not all cells have been reduced to a single value, in which case we need to start enumerating the remaining values to obtain a solution to our puzzle instance (typically a CP problem will include the specification of a search strategy, however, for this simple problem we can work with the preconfigured default strategy):
Can we do any better?
Xpress Kalis provides a configuration option for the ‘alldifferent’ constraint that allows the user to choose between different (local consistency) algorithms for the implementation of this constraint relation. The default configuration (option KALIS_FORWARD_CHECKING) implements a weaker consistency level (i.e. less work performed at every evaluation of the constraint relation) than the alternative configuration KALIS_GEN_ARC_CONSISTENCY:
With this stronger consistency algorithm for all ‘alldifferent’ constraints, fully-defined (single solution) Sudoku instances will typically be solved simply by stating all constraints without any need for search. Incomplete instances (admitting multiple solutions) still require search, but solutions tend to be reached more quickly.
Recommendation to model developers: whether to use weaker or stronger constraint algorithms for a particular problem needs to be tested with representative data instances.
Figure 8: After posting all constraints with strong consistency algorithm
In this version of Solving Sudoku, I am going to present a different set of tools and techniques for solving such problems, namely Constraint Programming. Since the first Sudoku puzzles made their way into European journals in the mid-2000s this puzzle has become a favorite for explaining the basic ideas of Constraint Programming. To visualize the results, I will explain how to make use of the Mosel package mmsvg, to not only display but also animate the solving process.
Some historical notes:
Constraint Programming, or CP for short, has evolved since the 1970s/80s out of a combination of techniques from various areas, including
- Techniques from Logic Programming (logical inference, resolution principle)
- Search methods from Artificial Intelligence
- Consistency techniques from Constraint Satisfaction research
- Filtering algorithms using results from Operations Research and graph theory
The term ‘Constraint Programming’ is commonly used since the early 1990s (the first international scientific conference specifically dedicated to this topic ‘Principles and Practice of Constraint Programming’ took place in 1995).
Commercial tools, initially usually implemented with Prolog, later on, more often as extensions to other programming languages such as C++ or Java have become available since the late 1980s. Constraint solvers are typically classified by the type of variable domains over which they work (e.g. finite domains, floating point, intervals, sets).
In this blog, we are going to work with Xpress Kalis – a component of FICO Xpress Optimization that employs the Artelys Kalis solver by Artelys SA . Kalis has solvers for discrete (finite domain) and continuous (floating point intervals) problems.
Basic principles of CP:
A constraint system is defined by:
- A set of variables
- A set of constraints over these variables, where a constraint is a relation between a set of variables
The goal is to find an assignment of values to the variables that satisfy all the constraints.
Finite domain solvers usually implement local consistency algorithms that check the system of constraints for inconsistencies and remove infeasible values from the variables’ domains. If any domain changes occur, these are propagated iteratively via the constraint relations to all other possibly affected variables, this process is known as constraint propagation (illustrated in the figure below). If a domain becomes empty then there is no solution.
Figure: Constraint propagation for a 3x3 subsquare of a Sudoku board (each cell needs to take a different value from all others)
Stating the Sudoku problem as CP model
To represent the Sudoku problem as a Constraint Programming problem we work with discrete (finite domain) decision variables v(columnindex, rowindex) that each takes values from the set {1,…9}.
(Note that since all variables have the same domain of values the domain can be specified via the default bound settings of Xpress Kalis, alternatively the setdomain routine could be applied after the definition of the decision variables.)
A given Sudoku instance is specified through an array of integer values that can be read in from an external file using standard Mosel functionality:
A given Sudoku instance is specified through an array of integer values that can be read in from an external file using standard Mosel functionality:
The Mosel module mmsvg can be used for displaying the current state of the Sudoku board with just a few additional lines of Mosel code. By default, every constraint stated in Mosel is immediately sent to the Kalis solver, triggering a new round of constraint propagation after which we can retrieve the current domain for each variable to redraw the current state of the board.
Figure 4: Initial board
Formulating the constraints
Now the remaining task is the formulation of the constraints: different values for all cells belonging to the same row, the same column, or the same 3x3 subsquare of the board. We might choose to work with pairwise disequalities, e.g. to state that all cells in the same row need to take different values:
This ‘alldifferent’ relation is a so-called global constraint: it works on a larger (sub)set of decision variables, allowing the local consistency checks to adopt a more global view of the problem than what would be possible, for instance, through the pairwise disequality constraints.
The effect of adding the row-wise alldifferent constraints for the Sudoku instance from Figure 4 shown in the following graphic:
Figure 5: After posting row-wise alldifferent constraints
We also need to state the column-wise alldifferent relations:
Figure 6: After posting column-wise alldifferent constraints
And finally, the constraints that all cells in the 3x3 subsquares must take different values:
Figure 7: After posting square-wise alldifferent constraints
After posting all constraints to the solver we may find that not all cells have been reduced to a single value, in which case we need to start enumerating the remaining values to obtain a solution to our puzzle instance (typically a CP problem will include the specification of a search strategy, however, for this simple problem we can work with the preconfigured default strategy):
Can we do any better?
Xpress Kalis provides a configuration option for the ‘alldifferent’ constraint that allows the user to choose between different (local consistency) algorithms for the implementation of this constraint relation. The default configuration (option KALIS_FORWARD_CHECKING) implements a weaker consistency level (i.e. less work performed at every evaluation of the constraint relation) than the alternative configuration KALIS_GEN_ARC_CONSISTENCY:
With this stronger consistency algorithm for all ‘alldifferent’ constraints, fully-defined (single solution) Sudoku instances will typically be solved simply by stating all constraints without any need for search. Incomplete instances (admitting multiple solutions) still require search, but solutions tend to be reached more quickly.
Recommendation to model developers: whether to use weaker or stronger constraint algorithms for a particular problem needs to be tested with representative data instances.
Figure 8: After posting all constraints with strong consistency algorithm
If you are interested to solve your own Constraint Programming models then download and install Xpress for free under the Xpress Community License.
The CP model with graph drawing can be found in the Xpress online examples database. After the initial display of the Sudoku board with the input data configuration, the board is redrawn after the propagation for every new constraint relation and in every node of the branching tree, showing the progress of solving. The display of the individual SVG graphs is programmed to remain visible for a short delay (specified via Mosel’s ‘sleep’ command), resulting in a movie-style display sequence of a solver run.
[Video1]
In the same location as the CP model you will also find a Mosel implementation of the same problem as a Mixed Integer Programming (MIP) model solved with Xpress Optimizer, equally with some graphical representations of the Sudoku board at different stages of solving. An implementation with Python of the same MIP model can also be found in the online examples database.
Interested in keeping in touch with this type of content? Make sure to subscribe to our Optimization blog to be updated on these types of topics.
The CP model with graph drawing can be found in the Xpress online examples database. After the initial display of the Sudoku board with the input data configuration, the board is redrawn after the propagation for every new constraint relation and in every node of the branching tree, showing the progress of solving. The display of the individual SVG graphs is programmed to remain visible for a short delay (specified via Mosel’s ‘sleep’ command), resulting in a movie-style display sequence of a solver run.
[Video1]
In the same location as the CP model you will also find a Mosel implementation of the same problem as a Mixed Integer Programming (MIP) model solved with Xpress Optimizer, equally with some graphical representations of the Sudoku board at different stages of solving. An implementation with Python of the same MIP model can also be found in the online examples database.
Interested in keeping in touch with this type of content? Make sure to subscribe to our Optimization blog to be updated on these types of topics.
Updated 5 years ago
Version 3.0