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.