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.
Is there any property in particular of dancing links that you think helps in determining this, or is it just that a backtracking search can be used to test all cases?
For pen-and-paper puzzles like Sudoku there is usually the goal that a solution should be findable by a series of deductive steps. For 9x9 Sudoku, most deductive steps used correspond to the effects well-known propagation techniques offer[1]. With a suitable propagation level, if the puzzle is solved search-free, then one knows that both there is only one solution and that there is a deductive path to solve it.
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
And an instance file looks like thishttps://news.ycombinator.com/item?id=44220245 on the same topic was posted four months ago and has more substance than this short 2007 post.
There are plenty of posts out there on using Knuthâs dancing links as a fast sudoku solver. Has it fallen out of fashion?
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.
Is there any property in particular of dancing links that you think helps in determining this, or is it just that a backtracking search can be used to test all cases?
For pen-and-paper puzzles like Sudoku there is usually the goal that a solution should be findable by a series of deductive steps. For 9x9 Sudoku, most deductive steps used correspond to the effects well-known propagation techniques offer[1]. With a suitable propagation level, if the puzzle is solved search-free, then one knows that both there is only one solution and that there is a deductive path to solve it.
[1]: See "Sudoku as a Constraint Problem", Helmut Simonis, https://ai.dmi.unibas.ch/_files/teaching/fs21/ai/material/ai... for some data on 9x9 Sudoku difficulty and the propagation techniques that are needed for search-free solving.