The Science of Sudoku
Sudoku is a Japanese numerical puzzle arranged on a
nine-by-nine grid of squares:
Any number between 1 and 9 can appear in any square:
The numbers given are entered into the squares:
Definitions
ROW
Nine squares horizontally
COLUMN
Nine squares vertically
BLOCK
A three-by-three array of squares beginning only at the first, fourth
or seventh row, and only at the first, fourth or seventh column.
FIELD
Another word for BLOCK.
Rule 1
“Rows - Just One”
A number can appear only once in each row. Here we see the 2. This must
be eliminated as an option for the entire row. Similarly for the 1, the
8 and the 4.
This is repeated for all numbers throughout the grid:
Rule 2
“Columns - Just One”
A number can appear only once in each column. Here we see the 8, the 1,
the 7 and the 9. These must be eliminated throughout the column unless
already eliminated.
This is repeated for all numbers throughout the grid:
Rule 3
“Blocks - Just One”
A number can appear only once in each block. Here we see the 2 and
the 8. These must be eliminated throughout the block unless
already eliminated. The 8 was eliminated, the 2 not completely.
This is repeated for all numbers throughout the grid:
Rule 4
“Only Place”
If at any time the options have been reduced to a single number for
any square, that number may be entered at that point. Each time a
number is entered, the options in the grid must be reduced, as per
rules 1, 2 and 3.
This is repeated throughout the grid:
Rule 5
“Rows - Never None”
No number from 1 to 9 may be missing from a row. If a number, such as
the 2 shown, can appear in only one position, it may be entered into
the grid. The previous rules must be revisited each time a number is
entered.
This is repeated throughout the grid:
Rule 6
“Columns - Never None”
No number from 1 to 9 may be missing from a column. If a number can
appear only once in a column, it may be entered there and the previous
rules revisited. This applies throughout the grid:
Rule 7
“Blocks - Never None”
No number from 1 to 9 may be missing from a block. If a number can
appear only once in a block, it may be entered there and the previous
rules revisited. This applies throughout the grid:
Rule 8
“Rows - Non-obstruction”
No number from 1 to 9 may be missing from a block. Here we see the 1 in
the last block being placed somewhere in the bottom row. Accordingly,
the 1 cannot appear in the bottom row of the first block, or it would
eliminate a 1 from the last block. The 6, 3 and 4 may be similarly
evaluated.
This is repeated throughout the grid:
Rule 9
“Columns - Non-obstruction”
No number from 1 to 9 may be missing from a block. Here we see the 3 in
the middle block being placed somewhere in the middle column. Accordingly,
the 3 cannot appear in the middle column of the top block, or of the
bottom block.
This is repeated throughout the grid:
Using these rules, we can fill in the grid:
And again:
And again:
Finally, it is completed:
The constructions can then be hidden, by redrawing on a fresh grid:
It had been intended to show every move, but that would be boring.
If at any time, Rule 4, the "only place" rule, should fail, due to
a square having no options, it was either a human error or a defective
puzzle.
Sometimes, Rule 4 is broken because two options appear in perhaps six
places. It is usually found that this is an ambiguous puzzle with two or more
solutions. Number A can be exchanged with B which can be exchanged with
C in a circle, or A and B can be swapped to resolve C also.
Where a puzzle delivers no "only place", one should seek out a
square having two options, and try first one and then the other. It may
even happen that when option of A is tried, options C or D are found.
Similarly, if option B is tried, options E or F may appear. The method
is as with chess puzzles:
PLY 1 try A and
PLY 2 C and then D. Then back to
PLY 1 try B and
PLY 2 E and then F.
If more than one route gives a valid solution, there were not enough
numbers in the original puzzle to disambiguate it.
The process described can be mechanised. Such a program would be of use
to publishers, to test their puzzles. However, it is bad form for a
puzzle-solver to use machinery.
The complexity is due to the need to hold many pieces of information
in ones head at the same time. Right-clicking on the second image above
(right.gif) allows it to be copied to disk on Internet Explorer,
and most other browsers. It can then be printed out to help solve
difficult puzzles.
There are eighty-one squares in a puzzle. In a correct puzzle, only
one option is correct in each square. This leaves eight options that
can be eliminated. There are therefore 648 options that are invalid.
Each of these options can be invalidated by one of three routes - from
the row, the column or the block. There is therefore threefold redundancy.
Without this redundancy, there would be 1,944 cancellations to make.
A computer program would do this automatically. It is no hardship for a
machine to cancel three times on the same spot. However, for a human this
would be laborious.
Fortunately, therefore, if a human puzzle-solver misses cancelling an
option in a row, due to human error, he still has the chance to do so
when that number appears in a column or a block. This makes the puzzle
very error-tolerant.
(C) 2006 Charles Douglas Wehner.
Use freely but do not plagiarise.