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.