The New Sudoku Players' Forum

[John Francis]

Hi, folks. I've just found this forum (I know, a bit late ..), but I've
been poking around at solving techniques for Sudoku ever since my
local newspaper (the San Jose Mercury News) started including a
Sudoku puzzle in September 2005. I've coded up my own Sudoku
game/assistant for the Pocket PC, and a solver testbed on the PC.

Because I've come late to the table I'm not familiar with all the names
used here and elsewhere for solving techniques. One thing I do notice,
though, is that there seem to be several different names used for
techniques which I've always considered to be equivalents. I don't
just mean the various Swordfish-like techniques which only differ in
the number of rows/columns under consideration; I think the two
uses which surprise me the most is the way Blocks are often treated
differently from Rows or Columns even when there is no inherent
reason for doing so, and the distinction between Naked and Hidden
pairs, triples, etc. One thing I realised very early on is that what
can be referred to as "Hidden N" is, in fact, identical to "Naked 9-n".

In fact in my solver (and in the Pocket PC assistant) I only really
have what I consider to be six separate techniques. The first two
establish the contents of a cell; the others simply remove candidates.

1) Unique candidate in cell. This is the only technique I have
automated on my Pocket PC implementation; if hints are
enabled, and there are one or more cells where only one
candidate remains, then I can fill in all those cells with a
single operation.

2) Unique position for a digit within a Unit (Row/Column/Block).
Here I do not distinguish between Blocks and other Units.

3) Naked/Hidden pairs, triples, etc. This is handled in a general
form; I never treated any one variation as a special case.

Just those three techniques are enough to solve the vast majority of
the Sudoku puzzles published in newspapers, so I was then able to
concentrate on techniques to solve the harder cases that remained.
I eventually got round to trying a little web research, and found some
pointers to solving techniques which allowed me to implement:

4) Row/Block interactions (and, of course, Column/Block interactions).
I implemented this very early on, and am not really happy with the
way I did it; I think I ought to be able to abstract this in a way that
will also cover Block/Block interactions.

5) X-Wing, Swordfish, et. al. - implemented in a fully-generalised
abstraction that works for any number of rows and columns.

That's where things stood for quite some weeks - by this time I was
down to just a handful of puzzles that didn't respond to these tools.
But I kept on turning the problem over in the back of my mind, and
I eventually came up with the following technique (which is easy for
an automated solver, but can be done manually for simple grids).

The first thing I do is to come up with a list of strong implications
(similar to those used in colouring or chains). These are derived
from Bi-valued cells, or Bi-locatable digits - for a Bi-valued cell the
presence of one of those values in any cell that can see the cell in
question forces the other value into our cell, and similarly for the
Bi-locatable digits; if that digit is present in any cell that can see
one of the two possible locations then it forces the digit into the
other location.

Once I have this list is is possible to find the closure of these rules
(and also detect loops, although I haven't yet found a use for this).
This gives me a list of consequences which will be forced by any
particular choice of a digit in one of the un-solved cells. Inspection
of these lists often shows contradictions (two different digits forced
into the same cell, or the same digit in two different cells in one unit).
A candidate placement which leads to a contradiction can be eliminated.

When I applied this to my remaining unsolved puzzles, it handled them
all. Encouraged by this I started looking around the 'net for other
puzzles. I did find a few that don't respond to this treatment, but
only a few - a lot of the other 'hard' puzzles I found succumbed.

What I like most about this is that it is a technique which doesn't rely
on Trial-and-Error/backtracking; it's totally derived from analysis of
the board position and following a chain of simple strong inferences.

I've got a couple of ideas of how to use this list of inferences (and
the set of negative inferences inherent in the rules of the puzzle)
to attack those few recalcitrant problems I've yet to crack, but I
thought some of you might be interested in a view from outside
the established solving community.

[RW]

The technique you are describing is often called "Error Net", basically you find that the implication A=x leads to a contradiction => A<>x. If you do this by analyzing strong interferences in the puzzle at a certain point, it's kind of a lighter version as you don't use the strong interferences created on the way. Error nets is probably the most powerful technique of them all and it can solve most of the puzzles (all puzzles if you allow multiple implications). I like to use this technique a lot, also in manual solving, but I know there's many people who consider this T&E. I don't want to get in on the T&E discussion now, as it tends to be a long and painful one.

If you really wanna give your solver a challenge, try ravels list of The hardest sudokus.

RW

[algernon]

Hi John,

I am quite new on this forum, too. Just want to share my opinion
on you topic:

I think even your short list of methods is not yet fully orthogonal;
I consider Hidden/Naked Singles as a special case of Hidden/Naked
N-tupples ("GenericTupple").
And line/box or similar interactions are a special case (1st order) of
a generic swordfish ("GenericInteraction").

So to solve "ordinary newspaper sudokus" you need only these two
algorithms.

Many other technics like XY_Wing/Chain, remote pairs, turbot fish,
simple coloring etc. are in the end also handled by "AIC",
a technic based on strong/weak links similar to what you describe.

That leaves uniqueness exploits (UR, BUG, ..) and stranger seefood
(Sashimi/Finned/Big/Franken-fish), which are quite rare,
even more so if you apply AIC first.

After that there are very advances technics "on the edge of" T&E.....

Michael

[John Francis]

Interesting observations.
I had, of course, recognised the hidden/naked singles as a special case of the N-tuple situation. There are reasons to continue to treat them as a special case as far as human players are concerned, though; they are the (obvious) cases that allow a cell to be filled in. In fact a hidden single is also a special case of a swordfish, too.

I hadn't got as far as treating line/box interactions as similar to swordfish and the like - I implemented line/block quite early on, and it wasn't until I came to look at X-wing and swordfish that I started to look for generalisations. The first one I found, naturally, was the generalisation to N rows & columns; this is a direct analogue of the naked/single N-tuple generalisation. I'd also spotted what looked like a good way to generalise line/block to include block/block, but hadn't got round to any serious investigation.Now that you've pointed it out, though, I've got some new avenues to consider there - thanks for bringing this possibility to my attention.

As you say, just those are enough to solve most newspaper sudokus. Not quite all of them, though - every now and then there's a puzzle that doesn't succumb to those techniques. That's why I was working on other possibilities.

I've now read up on Alternating Inference Chains. This is, indeed, close to what I was doing, only I was working with a rather more complex primitive consisting of an adjacent strong/weak link pair. I'll definitely have to take a closer look at this kind of thing. I've got a couple of other avenues yet to explore, but I can see there could be benefits to separating into the two constituent links.

As a personal preference I'm not partial to uniqueness exploits, so I've deliberately ignored those in my research so far.

I also find it hard to decide just where the edge of trial-and-error starts. You could say that a naked pair was a trial-and-error technique, although most people would probably regard that as an overstatement. But beyond that it gets harder to define just where the boundary lies. The progression of solving techniques through XY-wing, remote pairs, etc. doesn't have any hard edges.

[John Francis]

If you really wanna give your solver a challenge, try ravels list of The hardest sudokus.

RW

Thanks for the reference. My solver solves a little over half the top1645 list. Not too bad, but I guess I've got a little more to do.

[Havard]

Thanks for the reference. My solver solves a little over half the top1645 list. Not too bad, but I guess I've got a little more to do.

Yup, Mike Barkers solver solves over a 1000 sudokus on that list (assuming you meant the top1465) , and that is only using pattern-based techniques.

Havard

[algernon]

Yup, Mike Barkers solver solves over a 1000 sudokus on that list (assuming you meant the top1465) , and that is only using pattern-based techniques.
Havard

Arrggh, I score only 631 or so, and that is _with_ AIC. But I avoid
uniqueness exploits. Maybe the big thing is finned fishes? But then again
nearly all seafood from ruuds benchmark is handled by AIC !?
I have APE but no ATE and no ALS/SueDeCoq.
As I saw somewhere Mike Barkers is heavy into ABC...STUVWXYZ-wings.
I do only WXYZ, and even that only with a 4-valued hinge and three
bi-valued pincers (this was the definition on scanraid and I didn't fully
understand the general case w/o bi-valued pincers).

Seems there is a lot to do...

Is there a batch solver with configurable techniques, so I could check if my
solver matches all patterns it should?

[Havard]

But I avoid
uniqueness exploits.

Is that because you want your solver to be able to solve unsolvable sudoku?

Håvard

[algernon]

As a personal preference I'm not partial to uniqueness exploits, so I've deliberately ignored those in my research so far.

I do not like them either. I understand the target of soduko like:
"Find a solution and proove it is unique."
But others supposedly understand it as:
"Find a solution, given it is unique."

I also find it hard to decide just where the edge of trial-and-error starts. You could say that a naked pair was a trial-and-error technique, although most people would probably regard that as an overstatement. But beyond that it gets harder to define just where the boundary lies. The progression of solving techniques through XY-wing, remote pairs, etc. doesn't have any hard edges.

Agreed.
Maybe we can talk about exhaustive-search instead of trial-and-error.
If I have to do a search in the magnitude of exhaustive-search, I could
as well use a backtracking solver. A human could surely do so if he/she had
enough time and paper. And if exhaustive-search finds a solution, this
solution is also a (big big) pattern on its own, so the wording "pattern based"
(which I personally _like_) won't draw a clear line, too.

[algernon]

Is that because you want your solver to be able to solve unsolvable sudoku?

Ok, you wan't to get me with the definition of sudoku as a puzzle which
_must_ have a unique solution. Given this definition, you are right.

So I must admit perhaps my definition is wrong , and sudokus which
would only be solvable under my definition are considered "illegal".

In this sense, yes, I wan't to solve unsolvable sudoku!

It surely is a matter of (my strange) taste.

Michael