It’s straightforward to model and solve a Sudoku puzzle using
MiniZinc. But the modern Sudoku world (as can be seen on the
Cracking the Cryptic Youtube
channel) is full of
variants with exotic constraints – let’s see how hard it is to model
those.
(A small disclaimer: I’m trying to model these constraints in a simple
way, not necessarily an efficient way!)
Normal sudoku rules apply
The standard rules of Sudoku are easy enough: an integer variable for
each of the 81 cells, constrained to take a value from 1 to 9, and
each row, column, and 3x3 box required to have no duplicates (to be
“all different”).
Some easy variants
Above is our first example puzzle: Dune: The Mentat’s Diversion by HalfBakedLunatic, featured in this video.
(Little) Killer sudoku and extra regions
A killer sudoku clue requires a set of cells to sum to a given number.
This is an easy case to model:
Little killer clues can be modelled the same way. Regular killer
clues also require the cage to act as an extra no-duplicates region,
which can be modelled simply with an alldifferent constraint:
Thermometers
A thermometer requires the numbers along the line to increase from the
bulb end, like the temperature markings on a thermometer. This is a
conjunction of simple arithmetic constraints:
In fact MiniZinc has a global constraint that does exactly this,
called strictly_increasing:
There’s also the constraint increasing for “slow” thermometers.
Kropki dots
Black kropki dots require one number to be double the other:
White kropki dots require the two numbers to be adjacent. There are
two simple ways to write it:
Example puzzle 1 model
These constraints can be wrapped in predicates and put together to
solve example puzzle 1. Chuffed 0.13.2 solves this in just over
200ms:
More constraints and extra variables
Example puzzle 2, A puzzle of two halves by Arbitrary (featured in this video).
In this puzzle the magenta lines are “renban” lines, where the digits
on the line must form a set of consecutive digits without repeats.
The letters A-F represent six different digits, and a letter in a
circle means that letter’s digit must appear in at least one of the
four surrounding cells.
The single arrow constraint is the easiest to model:
The renban constraint is more complicated. We assert that all the
digits along the line are different, and that the smallest and largest
digit are exactly n-1 apart, where n is the number of digits on the
line.
To model the letters representing digits, we introduce six more
variables and constrain them to be different:
For the letter-in-circle (“quad”) we assert that either the first cell
takes the given value, or the second one does, and so on. Note that
in this case the value v is not a fixed value but another variable.
Solving the model requires assigning values simultaneously to the
Sudoku cell variables in the array x and the a,b,c,d,e,f
variables. The full model, which Chuffed solves in about 270ms:
Conditional constraints and finding connected regions
Example puzzle 3, Zippery When Wet by Marty Sears (featured in this video).
This puzzle is quite a bit more difficult, both to solve by hand and
model in MiniZinc. It has a great variety of constraints and requires
us to cover the grid in land and water. These are the rules, from the
SudokuPad link where you can play
the puzzle:
YIN-YANG:
• Each cell is either land or water.
• All cells of the same type must be orthogonally connected.
• No 2x2 area may be entirely land or entirely water.
LINE TYPES:
• Renban (pink) - Digits on a pink line don't repeat, and form a consecutive sequence, but these can be arranged in any order along the line.
• Nabner (yellow) - A digit on a yellow line cannot be consecutive with (or the same as) any other digit anywhere on the line.
• German Whisper (green) - Adjacent digits on a green line must have a difference of at least 5.
• Region Sum (blue) - Digits along a blue line must have the same total within each 3x3 box.
• Parity (red) - Digits along a red line must alternate between odd and even.
• Entropic (orange) - Any group of 3 adjacent digits on an orange line must contain a low digit (1, 2 or 3), a medium digit (4, 5 or 6), and a high digit (7, 8 or 9).
• Palindrome (grey) - A grey line must read the same in either direction.
• Same Difference (turquoise) - Each pair of adjacent digits along a turquoise line must have the same difference.
ZIPPERY WHEN WET:
• Any line that is completely wet (only enters water cells) loses the property of its presenting colour, and instead becomes a zipper line. Along a zipper line, each pair of digits that are the same distance from the line's central cell, sum to the digit in that centre cell.
• Any line that is completely dry (only enters land cells) behaves normally, as described in the list above. It does not behave like a zipper line.
• If a line is partly dry and partly wet, it retains its presenting property, but it is ALSO a zipper line as well.
New constraints
Most of the line constraints are easy to model; here are two examples:
Yin-yang (land and water)
The requirement to find two connected regions is another story.
The first part is easy enough; introduce Boolean variables to enforce that each cell is
either land or water, and that there are no 2x2 blocks all of the same
type:
The tricky part is ensuring that all water (or land) cells are
connected. To do this we arbitrarily assign one cell as the “source”
cell, and imagine that the water flows from that cell into the other
cells. We have a variable for each water cell’s distance from that
source cell, and assert that if a cell has distance D from the
source, one of its neighbouring water cells must have distance D -
1. This ensures that there is some path from each cell back to the
source cell, and therefore that all cells are connected.
We also add constraints to choose (arbitrarily) the top-left-most cell
as the source cell, and force each cell’s distance value to be the
smallest possible value. These constraints eliminate redundant
solutions and reduce the search space.
Conditional constraints
The “zippery when wet” condition is then no problem:
For the purple line, it means: if it’s a bit wet it must act as
a zipper line, and if it’s a bit dry then it must act as a renban
line. The wet and dry predicates check if any cell of the given
coordinates is water or land.
Example puzzle 3 full model
The full model below finds the solution in 1.2 seconds. One
curiosity is that including the “shortest distance” constraint –
intended to eliminate redundant solutions and potentially improve
performance – makes the solving slower by about half a second.