A concrete scheme for grading Su Doku puzzles

This page is really for Su Doku compilers. If you enjoy solving puzzles - consider not reading this page! It is much more fun to figure out a new rule to solve a puzzle then to read a list of them written by someone else.

On classical 9x9 Su Doku boards the grades in this scheme run from 0 to 9 - with 0 being the easiest and 9 being the hardest. The levels refer to 10 techniques, or rules of inference, that can be used for solving Su Doku puzzles. They're listed here in (a partly arbitrary) order of subtlety.

Value singletons: elimination of the values a cell may contain. (Sometimes called lone numbers)
Cell singletons: elimination of cells where a given value can be placed. (Often called slicing and dicing)
Venn pairs: two values in the cells common to a box and a row (or column).
Value pairs: two cells that can take only two values (often called hidden pairs).
Cell pairs: two values that can only be put in two cells (often called naked pairs).
Venn triples: three values in the cells common to a box and a row (or column).
Value triples: three cells that can take only three values (somtimes called hidden triples).
Cell triples: three values that can only be put in three cells (somtimes called naked triples).
Value quads: four cells that can take only four values.
Cell quads: four values that can only be put in four cells.

The level of a puzzle is given by the number of the hardest rule of inference required to solve it.

On 9x9 boards there are no higher rules of inference (of the kind listed here, at least) as the consideration of sets of n values is equivalent to the consideration of sets of (9-n) cells. Similarly, consideration of sets of n cells is equivalent to the consideration of sets of (9-n) values, so any rule involving quintuplets is equivalent to a simpler rule in its complement.

Rules 2 and 5 are anomalous as they depend on the fact that boxes overlap non-trivially with rows and columns. The name Venn is used here after John Venn whose diagrams capture the inclusion/exclusion principle at work in these forms of reduction.

Most puzzles that appear in the national newspapers in the UK fall into the first few categories. Puzzles published in The Times under the headings fiendish, extra fiendish and super fiendish seem to be the hardest and normally require the application of one of the rules in the range 2 to 5. Some of the Diabolical puzzles published in The Telegraph appear harder but cannot be given a grade in this scheme as the harder ones all seem to require trial and error.

It is possible to construct puzzles all the way up to level 9 - though the amount of computation required to generate them rises exponentially with the level. Finding symmetrical puzzles makes things even harder - it took many days of computation to find some of the puzzles on levels 8 and 9. Luckily, solving the hard puzzles is many orders of magnitude easier than finding them.

Many compilers use the term "valid" for puzzles which have a solution that can be found without trial and error. In Japan, where Su Doku puzzles have been created by hand for the last five years or so, "invalid" puzzles are considered inferior and many publications make a point of declaring that they won't publish them.

Interestingly, it appears that the number of rules of inference is essentially unbounded. If so, it will never be possible to have an absolute test of validity - as different algorithms will give different answers depending on which subset of the huge list of availible rules they choose to implement.

So, strictly, an algorithm should report either that a board is "valid" (if it can solve it) or "unknown" (if it can't). As long as a puzzle has a unique solution, no program can ever sure a puzzle is "invalid" - only that it cannot solve it. For practical purposes, however, most puzzles that have unique solution can be solved with a handful rules, and programs will tend to agree on the validity question in the vast majority of cases.

[Update - July 2005: Since writing this in early 2005, a more advanced evaluation scheme has been discussed here].

[Update - Oct 2005: And since writing that, a new implementation has appeared with very impressive (possibly complete?) coverage of the rules of inference that are known at this time. See The Sudoku Susser].