Sudoku puzzles can trace their lineage from the magic square (carrés magiques) of 18th century mathematical genius Euler, via latin squares, through American and then Japanese versions in the 80s (from which the name arises- roughly translated, it means solitary number), to their current surge in popularity in the UK, fuelled by publication in most of the quality newspapers (having first appeared in late 2004, however, in the Daily Mail).

For a month or so now, a few of my fellow students have been whiling away time in our own mathematical square, plugging away at Suduko grids from brightly coloured Japanese puzzle collections (combined circulation of dedicated Sudoku books in Japan is around 600,000 a month). Since I like to fuel the illusion that I know a thing or two about numbers, but am in fact generally rubbish at puzzles, I avoided attempting any until earlier this week when I spotted a bunch in The Independent- the next thing I knew, I'd lost my Wednesday afternoon.

Of course, I mangled the first one horribly, so sat down to approach the second one in a more systematic fashion. The simplest trick, as described by Sir Norris above, is to find cells which, through a combination of pressures from the row, column and 3*3 block, can only take a single value. After getting bored with pencilling in possibilities, I knocked together a Maple worksheet that generated lists of possible values for each cell. The best case of this brute force approach is when singletons appear- by plugging those back in and repeating the process, I solved the elementary problem from the Indie entirely mechanically. Which, although a triumph for my feeble coding skills, wasn't particularly enlightening with regards to the subtleties of Sudoku. So I fed the most difficult problem in, and was rewarded with not one cell that was completely determined. Now I had a challenge :)

Possibly ruining all the fun, and listed in order of desperation- the further you get in this list, the more fiendish the original puzzle.

So, having carried out the entirely routine steps of identifying potential values (either through fancy computing or writing extremely small in pencil), and assuming that wasn't sufficient to solve the grid, we're in a position to apply some logic. The hope here is that through reasoning, we can reduce or eliminate entirely the need for guesswork and backtracking. Of course, a lucky guess will speed things up, so a combination of reason and intuition make for a true sudoku master. These methodical steps seem like an ideal starting point for a full-fledged solver program, should any of you coders fancy a distraction.

#### Effective singletons

If no singletons have been identified, then the best case is a collection of cells with only two options. If in any given row, column or block there are two such cells with identical options, then their fates are inextricably linked- determine one, and you know the other. Often, this can set up a chain reaction across the board as a whole. But they can also force the value of another cell, as the following example shows.

```
-------------------------
|(4,5) :    3    :       |
|  2   :         :       |
|      : (4,5,9) : (4,5) |
-------------------------

```

Here the values 2 and 3 are given, and we've worked out the options for three cells of interest. If we figure out which of (4,5) the top left cell is, then we get the bottom right for free. But we immediately know the value of the (4,5,9) cell, which may help us determine entries elsewhere if we're currently stumped by the (4,5) choice. This is because whichever the top left cell turns out to be, 4 or 5, the bottom right cell will be the other, 5 or 4. So really, no other cell in this block can be a 4 or a 5, so the (4,5,9) entry is in fact the singleton (9).

This works just as well in a row or column, but the block was a bit easier to display in ascii art. Furthermore, larger cases are theoretically possible- cells with the options (3,4,5), (3,4,5), (3,4,5), (3,4,5,6) force the 6 for the last cell; or (1,2), (1,2), (3,4), (3,4), (1,2,3,4,5) forces the 5 in a cell that seemed to have unassailably many options. But such intricate cases require more cells to be just-so, and hence are rarer.

#### The importance of once-and-only-once

So far, the approach of identifying singletons or effective singletons has relied on the fact that a given number may appear only once in the row/column/block- we generate lists of potential values by eliminating the ones that have been 'used up' by already making an appearance. But we have a two way condition- each value needs to appear precisely once. So instead of looking for cells that can only take a single value, we look for values that can only occupy a single cell. Here's another block to illustrate.

```
---------------------------
|(4,6) :    3    : (1,7,9) |
|  2   :  (1,4)  : (7,8,9) |
|(7,9) : (4,5,9) :  (4,5)  |
---------------------------

```

In this complicated looking list of options, we can in fact determine two of the values. The top left cell has to take the value 6, since no other can; and similarly the 8 must lie in the middle of the third column.