3 ms·
I always thought one of the requirements for published Sudoku puzzles was that no trial and error should be required; it should be possible to deduce the single
by pdonis 7y ago
I always thought one of the requirements for published Sudoku puzzles was that no trial and error should be required; it should be possible to deduce the single unique solution from the clues given. This would mean the "search" part of Norvig's algorithm would not be required; constraint propagation alone would be enough.
- mcphage 7y ago> no trial and error should be required; it should be possible to deduce the single unique solution from the clues given Any sufficiently advanced solving heuristic is indistinguishable from trial and error.
- pdonis 7y agoHeuristic, yes. But I specifically said "deduce" to eliminate heuristics.
- l_t 7y agoI think technically, if constraint propagation can't solve the puzzle, that means it's either contradictory (zero solutions) or ambiguous (multiple solutions). However, it seems Norvig was feeding his program with all three types of puzzles -- zero, one, and multiple solutions -- so perhaps that led him to implement a more robust search.
- T-hawk 7y agoIf there is one unique solution, then constraint propagation always works, yes. But a propagated constraint isn't always just a single value at a time. There are cases where a solver (human or machine) needs to identify that a group of two or three or more cells mutually creates a constraint. ("Naked twins" and other such configurations, in Sudoku jargon.) Which can recursively cause to exist another such mutual constraint, and so on. Identifying every possible way such a constraint can arise isn't a simple operation either to implement or to execute, computationally speaking. For both Norvig's programmatic solver and for a human, it's possible and common for trial and error to be faster and more expedient than trying to identify and execute every possible means a constraint can arise. Norvig's aim was for implementational simplicity more so than computational elegance, deciding to care about only the simplest possible type of constraint, and let trial and error handle everything else.
- deleted 7y ago[deleted]
- femto113 7y agoThe search part is definitely considered “bad form” by human solvers. Author apparently lacked the insight that elimination is generalizable to “if any set of N peers contains exactly N distinct values you can eliminate those values from all peers not in the set”, rather than just “if 1 square contains 1 value ...”. That alone would solve all but the hardest puzzles with just a few more lines of code.
- T-hawk 7y agoI think the author had that insight, just chose not to use that route because it wasn't necessary. For either a human or machine solver, the trial and error route may well be simpler / less code / faster at runtime than implementing and executing every way to recognize a set of N peers for N values.