### Solving Pi Day Sudoku 2009 with the global cardinality constraint

Here is an update of the Pi Day Sudoku 2009 problem.

After a suggestion from Mikael Zayenz Lagerkvist (of the Gecode team) the model now uses just the `global cardinality`

constraint and is much faster than the model which used my own decomposition of `all_different_except_0`

(or rather `all_different_except_Pi`

) and the `count`

constraint.

Both of the new MiniZinc and Comet models solves the Pi Day Sudoku 2009 problem in less than a second (compared to couple of seconds before).

The **Comet** model has the following statistics for finding the first (and unique) solution.

time: 9

#choices = 6

#fail = 1

#propag = 1306

For **Gecode/FlatZinc**:

runtime: 20

solutions: 1

propagators: 35

propagations: 255

nodes: 3

failures: 0

peak depth: 2

peak memory: 158 KB

Compared to the former model, there are now much less failures.

**Some more about the global cardinality constraint**

Global cardinality (in Sudoku) is a way of stating how many occurrences there should be of each number per row, column or region. For the Pi Day Sudoku problem the following occurrences are needed:

Pi: 3 occurrences (coded as -1 in the model)

0: 0 occurrences (0 is a dummy value for handling the indata)

1..9: exactly one occurrence each

I MiniZinc the this is coded as

array[1..n, 1..n] of var -1..9: x;

array[-1..9] of 0..3: occ = array1d(-1..9, [3, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1]);

contraint

forall(i in 1..n) ( % rows

check([x[i,j] | j in 1..n], occ)

)

...

In Comet the function `cardinality`

is used, i,e, `m.post(cardinality(occ, all(j in 1..n) x[i,j]));`

.

For more information about the `global cardinality`

constraint, see the entry in Global Constraint Catalog.

**A comment**

Introductions to constraint programming nowadays tend to start with the Sudoko problem (or SEND + MORE = MONEY). These models often use the `alldifferent`

constraint, and seldom, if ever, have I seen any presentation using `global cardinality`

. One reason may be that alldifferent is easier to understand in a introduction, another reason may be that it is **general** a better constraint to use for these problems.

**"Vanilla" Sudoko solver using global cardinality**

I have compared some few "vanilla" Sudoku problems with either `alldifferent`

or `global cardinality`

but haven't done any systematic comparison. Sometimes the `global cardinality`

approach is better, sometimes it is somewhat worse.

sudoku_gcc.mzn is a "vanilla" Sudoku solver in MiniZinc using the `global cardinality`

constraint. And the same approach in Comet: sudoku_gcc.co. Note: These models includes just a few problems.

Also see: Gecode's Sudoku solver is very fast, and includes 88 different problems.

## Comments

The Pi Day Sudoku is very interesting. I'd also like to share a math puzzle that I recently came across: http://www.chycho.com/?q=Puzzle .

Posted by: Calvin | June 10, 2009 06:45 PM

Calvin: Nice puzzle.

I did a MiniZinc model that solve n=5 (instead of your n=10) in just a blink, and for n=6 in 15 seconds.

This is modelled as a variant of the Hidato puzzle (the MiniZinc model is hidato.mzn) with just a few extra constraints.

Posted by: hakank | June 10, 2009 08:46 PM

That's interesting, hakank. Did you try n=10 with MiniZinc?

Posted by: Calvin | June 12, 2009 09:52 PM

Calvin: Yes, I tried n = 10, but with my current MiniZinc model it simply takes too long. I have to think of a different approach.

By the way, the current model is here: calvin_puzzle.mzn. (Sorry for the name. :-)

Posted by: hakank | June 12, 2009 10:37 PM