Sudoku solver

[Chris Angelico]

On Fri, Mar 27, 2015 at 2:03 AM, Dave Angel <davea at davea.name> wrote:
> On 03/26/2015 10:41 AM, Chris Angelico wrote:
>  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.
>
>
> OK, we're on the same page.  I would use different terminology for some of
> it, but that's okay.

Good, I thought we were in agreement. And yeah, terminology is tricky.

> The purist in me would like to write a solver which (within a few seconds)
> could solve any unique puzzle, and identify puzzles which don't have a
> unique solution.  One reason I never got back to writing one was I also
> wanted a difficulty-ranker, which would identify how hard a human was likely
> to consider the puzzle.

It'd be pretty straight-forward. You simply define a number of
rule-difficulty-categories, something like this:

EASY
* If eight digits are "locked off" from a cell by already existing in
its neighbours, the remaining digit must be the one.
* If eight cells in a {row, column, square} have a given digit locked
off, then the remaining cell must contain that digit.

MEDIUM
* Construct "possibility regions" for digits in squares (ie all the
possible cells that that digit could be in). Any such region which
sits within a single row/column is equivalent to an actual digit in
that row/column for the purposes of exclusions.
* Likewise the converse - if both possible places for the 7 in this
row are in this square, we can depend on the 7 being in one of those,
and not anywhere else in the square.

HARD
* Any complex rule that you feel like coding up. There are plenty of
"Sudoku help" web sites out there that can provide rule definitions.

IMPOSSIBLE
* Brute force. Attempt to put a digit in a cell, then see if you can
solve the puzzle thereafter. If you prove the puzzle to have no
solutions, that digit cannot be in that cell.

Then, in your solver, you use EASY rules until they provide you with
no more material, and only then move on to MEDIUM rules, etc. The
highest difficulty class that you had to use in solving the puzzle is
the puzzle's difficulty class.

This isn't a perfect system, of course, but it's a decent start. It
also deals with the terminology problem: you can declare a puzzle
"solvable, but IMPOSSIBLE class difficulty", which means you have to
guess. Though I would strongly suggest disabling brute-forcing most of
the time, as it'll kill your CPU... especially if you have a puzzle
generation algorithm that looks like this:

Start with a blank grid.
While puzzle not solvable:
    Add random clue digit
For each clue digit:
    Remove clue
    If puzzle not solvable: Reinstate clue

With IMPOSSIBLE deactivated, this is a reasonably straight-forward way
to generate puzzles (and you can deactivate HARD to require a
medium-difficulty puzzle, etc). Otherwise... kerchug, kerchug,
kerchug....

ChrisA