3 ms·
Solvers aside, many puzzles like Sudoko require another family of algorithms, to generate puzzles that a human can solve without brute force. Finding the right
by JoshTriplett 11y ago
Solvers aside, many puzzles like Sudoko require another family of algorithms, to generate puzzles that a human can solve without brute force. Finding the right hints to offer seems rather orthogonal to writing a brute-force solver.
> So yes, I expect it would be fairly easy to write a backtracking kakuro solver. But the way I solve kakuro is very little like naive backtracking. I do things like - this row can only have numbers two to six, and this column can only have numbers five-plus, so this square is either five or six. But the row can only have one of those numbers, which means this square is two to four, and of those, four is the only number that fits in this column.
For Sudoku puzzles generated for humans, the simplest algorithm doesn't require any backtracking or brute force at all: note for every square which numbers can still potentially work there, and at each step, select one of the squares that has only one number, fill in that number, and update all other squares accordingly. Any puzzle that that algorithm can't solve qualifies as "hard".
One of the rules I use (in that and similar puzzles) for harder puzzles: if you've determined that a pair of squares can each only have X and Y, or a trio of squares can each only have X, Y, and Z, then you know those squares contain those numbers, just not which square contains which number. So you can (for instance) eliminate X and Y from the possibilities for other squares accordingly, which may then provide more steps. Puzzles where I can recognize and apply higher-level, complex rules like that have more staying power with me.
However, it may or may not make sense to teach a computer that special-case rule. A solver may find it easier, rather than recognizing that pattern, to instead just do a search, with transposition tables and similar to avoid duplication. Providing special-case reasoning rules for specific patterns may speed up or slow down such a search, depending on how often the pattern occurs, how much brute-force it eliminates, and how much computation recognizing it requires.
- philh 11y ago> For Sudoku puzzles generated for humans I agree that there's a significant difficulty jump, when that algorithm fails to suffice, and I think it's fair to say that's the "hard" jump. But I think a lot of puzzles intended for humans are "hard", by this definition. Teaching a computer that special-case rule might not make sense for speedy computer solving, but I think it would make sense for telling a human "here's how you could have found this number".
- JoshTriplett 11y agoAgreed; the difference between "easy" and "hard" is whether a square always exists with one choice, but the difference between levels of "hard" is how complex a reasoning rule you have to apply. No human should be expected to apply a brute-force backtracking solver, but humans can be expected to apply highly complex pattern-matching rules, or even invent new methods and sets of puzzles solvable with those methods.