Trying to represent sudoku as an integer program leads to a natural way to represent the board: a 9x9x9 boolean grid where x and y are the board dimensions and z is the number in each square.
You end up with three symmetric constraints + the box constraint:
- The sum along any x, y, or z row is 1 (one of each number per row, one of each number per column, and one number per square)
- The sum of each 3x3x1 box slice is 1 (one of each number per box)
I really like the symmetry between the row sum constraints here. And it does pretty neatly align with the way many people solve Sudoku by writing little numbers in the squares to represent possible values before pruning impossible ones.
That representation of a Sudoku is elegant, but I think it is not the most natural representation. The base constraint programming style will use a variable per square with domain 1-9, and then 27 all_different constraints. This representation is a lot closer to how people talk about the rules of Sudoku, which in my mind makes it more natural.
A full MiniZinc program would look like this
int: n = 3;
int: s = n*n;
set of int: S = 1..s;
array[S, S] of opt S: puzzle;
array[S, S] of var S: board;
% Sudoku constraints
constraint forall(row in S) ( all_different(board[row, ..]) );
constraint forall(col in S) ( all_different(board[.., col]) );
constraint forall(r, c in {1, 4, 7}) (
all_different(board[r..<r+n, c..<c+n])
);
% Set up puzzle
constraint forall (r, c in S where occurs(puzzle[r, c])) (
board[r, c] = puzzle[r, c]
);
solve satisfy;
Dancing links is a very cute data-structure for a backtracking search, but there are a lot more aspects of writing a good Sudoku solver than just having a good data-structure for backtracking. Propagation (making deductions), heuristics, learning, parallelism, restarts, no-goods, ...
While 9x9 Sudoku problems are trivial to solve for more or less any program, 25x25 Sudoku instances are quite tricky and a simple and fast but naive search for a solution can easily take hours.
For generating puzzles it's really useful since it lets you determine if a randomly generated puzzle has only one possible path to solving it (exact cover problem). And it's fast so adding it to a pipeline doesn't incur much if any overhead.
You end up with three symmetric constraints + the box constraint:
- The sum along any x, y, or z row is 1 (one of each number per row, one of each number per column, and one number per square)
- The sum of each 3x3x1 box slice is 1 (one of each number per box)
I really like the symmetry between the row sum constraints here. And it does pretty neatly align with the way many people solve Sudoku by writing little numbers in the squares to represent possible values before pruning impossible ones.
A full MiniZinc program would look like this
And an instance file looks like thisWhile 9x9 Sudoku problems are trivial to solve for more or less any program, 25x25 Sudoku instances are quite tricky and a simple and fast but naive search for a solution can easily take hours.