Hacker News Reader

My apologies, the terminology is imprecise; basically, in as optimal a way as you can brute force a solution, if one exists, relying on the simplest heuristic for branching. The same way, really, as you'd do it by hand, if you wanted to guarantee a solution (if one exists). So, yes, a backtracking solver, a la (this is basically what Norvig did in the link someone else mentions; I implemented mine around the same time as his article was written, it looks like, as a fun college time killer, probably when Sudoku was first in vogue) -

Figure out the possibility sets of all empty squares (that is, a set of all possible values given the current state of the table, i.e., for each square, initialize them with 1-9, then remove every value that is already contained in the same row, column, and 3x3, thus figuring out for each "this square could be 1 or 5, and nothing else"). Grab the square with the fewest possibilities; does it have only one? If so, go with it, update all related squares (by removing that value from their possibility set), recurse. Is it of possibilities > 1? Take one of the values out of the possibility set. Push a copy of the table as it stands (without that removed value) onto a stack; put in the taken value for the value of that square, update all related squares, and recurse. If you ever find a possibility space of zero (that is, a square has neither a value, nor any possible values), throw out your current table and pop off the stack, recursing upon that. If you find a possibility space of zero, and the stack is empty, the sudoku is unsolvable. Otherwise, once every square has a value, you're finished.

I feel like I had done a little pondering on ways, while coding it up, to find better heuristics for picking what number to start with, in the event the square with the minimal number of possibilities had more than one (i.e., "this square could be 1 or 5", rather than just picking one arbitrarily, would choose one based on some criteria), but I never really got around to playing with it, as nothing took more than a few tenths of a second, and that was enough to say "there, I need never care about Sudoku"

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.

> 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".

Agreed; 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.

Do you count backtracking as 'mechanical'?

This could be relevant to you: http://norvig.com/sudoku.html

I count backtracking as mechanical; but I was also using it in a perhaps overly-broad sense, which includes that solver.