Sudoku solver

[Chris Angelico]

On Fri, Mar 27, 2015 at 1:14 AM, Dave Angel <davea at davea.name> wrote:
> On 03/26/2015 08:37 AM, Chris Angelico wrote:
>> Nothing. And solving a Sudoku puzzle - or any other puzzle - should
>> require no guessing. It should be possible to solve purely by logic.
>> Same goes for every other kind of puzzle out there; it's highly
>> unsatisfying to play Minesweeper and get to the end with a block of
>> four squares in a corner, two mines left, and no way of knowing which
>> diagonal has the mines and which is clear.
>>
>> No trial-and-error, thanks.
>
>
> I think you're making an unwarranted assumption here.  Your Minesweeper
> example has two solutions, so there's no way of telling which is the
> "correct" one.  But I'd claim that there are puzzles which have exactly one
> solution, but which need trial and error at some point to find that
> solution.

Only one can possibly be correct; if you dig one cell, you'll die, and
if you dig the other, you'll win. But you have no way of knowing which
is which, without dying, using some kind of "undo" feature (orange
smoke comes to mind), and trying the other. Or, of course, guessing
right, in which case you win.

> I'm not sure how to prove it, since somebody could claim that I just haven't
> tried all the non-trial-and-error rules.

With Sudoku, there are some pretty complicated rules and patterns.
Minesweeper is much simpler to prove. But there are still rules and
patterns, and at some point, you simply have to say that a puzzle is
"beyond the logic of this set of rules". It might not be beyond a more
comprehensive set of rules, but that doesn't matter; you've proven the
puzzle to be unsolvable *with your (program's) skill set*.

> I did write a Sudoku-solver many years ago, in C++, and it solved the
> typical Sudoku I fed it in about 2ms.  But it was deliberately written to
> apply only rules that humans could readily apply.  No backtracking. I did
> not at that time have any electronic source for puzzles, and I got bored
> with manually entering them in from puzzle books.  So I never actually
> encountered a puzzle it couldn't solve.  I mostly used it to determine that
> a puzzle I couldn't manually solve was in fact uniquely solvable, and that
> I'd just messed up somehow.
>
> I wish I still had that source code, as it probably sounds like I'm blowing
> smoke here.
>
> The general approach I used was to make objects of each of the cells, which
> tracked its neighbors to decide whether its value was determined.  And when
> it was determined, it notified its other neighbors.  In turn, if that
> decided a value for any of the neighbors, that cell notified its neighbors.
> Likewise each row or column or box kept track of its state and notified the
> appropriate cells whenever something interesting was discovered.  Then the
> outer loop just tickled each cell in turn, and the solution rippled out.

Not entirely sure I have this correct, but it sounds like you have a
basic solver that uses one rule: If there is no other value that can
be in this cell, you can write this one down. It's certainly possible
to add a lot more sophistication to a solver; for instance, in this
grid, it's possible to place a 4 with certainty:

. . . | . . . | . . .
. . . | 4 . . | . . .
. . . | . . . | . . 4
------+-------+------
. . . | . . . | . . .
. . . | . . . | . . .
. . . | . . . | . 4 .
------+-------+------
. . . | . . . | . . .
. . . | . 1 2 | . . .
4 . . | . . . | . . .

An examination of the bottom-center block shows that the 4 in it must
be on its top row (even though you don't know which of two
possibilities has it), ergo the bottom-right block must have its 4 on
the center row. The more of these kinds of rules you have, the more
puzzles you can solve - but I would still code the solver to avoid
guessing.

> Maybe I'm misinterpreting your phrase "No trial and error, thanks". Perhaps
> you're saying that puzzles that require trial and error are no fun to solve
> for humans.  And that's a different matter entirely.  I do the daily KenKen
> puzzles in my local paper, and they're just hard enough to be fun, seldom
> taking longer than I'm willing to take in the mornings.

I agree that they're no fun for humans. That's part of the point, but
not the whole point. Since we're talking about puzzles, here, the
primary purpose of a machine solver is (or should be!) to prove that a
puzzle is solvable, and thus worthy of being given to a human. So the
solver should restrict itself to what's considered worth working with
- and in some cases, might restrict itself even further ("generate an
easy puzzle, please"), by cutting out some forms of logic. Now, if
your humans are happy with puzzles that they have to guess, then sure,
incorporate guessing in your solver. But if the humans aren't, then
what do you prove by having an electronic solver that can do the
puzzle? There's a small mathematical curiosity to finding out just how
few clues can carry sufficient information to uniquely define a grid,
but that's already been proven. So, that's why I would avoid guessing.

I've written a lot of solvers for various puzzles. Minesweeper,
Sudoku, a binary Sudoku-like puzzle that I don't really have a good
name for, several others. Every time, I've tried to prove the puzzles
solvable by humans, and sometimes that means rejecting ones that could
technically be solved by brute force.

ChrisA