3 ms·
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
by mzl 1y ago
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/ai26-simonis-cp2005ws.pdf 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.