Comment by MontagFTB
2 months ago
There are plenty of posts out there on using Knuth’s dancing links as a fast sudoku solver. Has it fallen out of fashion?
2 months ago
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.