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
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.
#choices = 6
#fail = 1
#propag = 1306
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]);
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.
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
global cardinality but haven't done any systematic comparison. Sometimes the
global cardinality approach is better, sometimes it is somewhat worse.
Also see: Gecode's Sudoku solver is very fast, and includes 88 different problems.