I thought about posting this in the "mathematics of sudoku" forum, but really what it is is
a statement of the common (and maybe not so common) rules for solving Sudoku, both in plain
English and in logical notation. If you are just interested in solving Sudoku, ignore the
funny notation; if you are interested in the mathematics, enjoy the symmetry.
I suggest that the following set of rules may constitute the entire set of
"standard" methods (not including simple chain-based logic) used to solve Sudoku puzzles.
Included here are:
1. naked singles
2. hidden singles
3,4. locked candidates
5. naked tuples
6. hidden tuples
7. grid analysis (X-wings, Swordfish, etc.)
8-11. generalized rules for larger than standard Sudoku
12. uniqueness (added 12/4/05)
Not included here are:
chain-based logic (coloring, x-cycles, y-cycles, 3D medusa)
trial and error (hypothesis and proof, bifurcation)
I offer here a simple picture of all basic methods. The picture is one of
INTERSECTING sets. The principle behind all these methods is simply that if
a candidate is located only in the intersection area of one of two overlapping
sets, then it is solely in the intersection area of the other set as well.
The statement is this:
If a candidate k is possible in area A^B (A intersect B)
and not elsewhere in A, then k can be eliminated from
any other position in B as well.
---------------
| A |
| |
| |
| ---------------
| | k | |
| | A^B | k |
| | k| k |
--------------- |
| k |
| k |
| k B |
---------------
implies
---------------
| A |
| |
| |
| ---------------
| | k | |
| | A^B | |
| | k| |
--------------- |
| |
| |
| B |
---------------
Methods involving more than one candidate simply
require more than one A and/or more than one B.
Code:
method A B candidate
singles row col k
col row k
block cell k
locked block row k
candidates block col k
tuples row (col)n (k)n
col (row)n (k)n
block (cell)n (k)n
X-wing (row)2 (col)2 k
swordfish (row)3 (col)3 k
n-grid (row)n (col)n k
--------- 4x4 Sudoku or larger ---------
n-locked (block)n (row)n k
candidates (block)n (col)n k
something (block)n (row)n (k)n
new (block)n (col)n (k)n
OK, here are the rules. Ignore the math if you just want to read the rule.
Key:
r a row
c a column
b a block
k a candidate
X_n a set of n of one of the above (X being r, c, b, or k)
!X not that row, column, block, or candidate
() is possible
!() is not possible
^/v and/or
Thus, for example:
r ^ c an intersection of a row and a column (i.e., a cell)
r ^ !c the other cells in that row
b ^ (r ^ c) a certain cell in a given block
b ^ !(r ^ c) the other cells in that block
(r ^ c ^ k) a candidate k is possible in a certain cell
(r ^ c ^ !k) candidates other than k are possible in a certain cell
!(r ^ c ^ !k) candidates other than k are not possible in a certain cell
Here we go:
1. naked singles:
1r. (r ^ c ^ k) ^ !(r ^ c ^ !k) --> !(r ^ !c ^ k)
1c. (r ^ c ^ k) ^ !(r ^ c ^ !k) --> !(!r ^ c ^ k)
1b. (b ^ (r ^ c) ^ k) ^ !(b ^ (r ^ c) ^ !k) --> !(b ^ !(r ^ c) ^ k)
(1r) says, "If a candidate k is possible in a certain intersection of
row and column (i.e., a cell), and no other candidates are possible
in that cell, then k is not possible elsewhere in that row."
(1c) says the same for "that column." (1b) says the same for "that block."
2. hidden singles:
2r. (r ^ c ^ k) ^ !(r ^ !c ^ k) --> !(r ^ c ^ !k)
2c. (r ^ c ^ k) ^ !(!r ^ c ^ k) --> !(r ^ c ^ !k)
2b. (b ^ (r ^ c) ^ k) ^ !(b ^ !(r ^ c) ^ k) --> !(b ^ (r ^ c) ^ !k)
(2r) says, "If a candidate k is possible in a certain intersection of
row and column (i.e., a cell) but is not possible elsewhere in that
row, then no other candidates are possible in the that cell."
(2c) says the same for "elsewhere in that column."
(2b) says the same for "elsewhere in that block."
Replacing either the r or the c with b gives us locked candidate rules:
3. locked candidates, type 1:
3r. (r ^ b ^ k) ^ !(r ^ !b ^ k) --> !(!r ^ b ^ k)
3c. (c ^ b ^ k) ^ !(c ^ !b ^ k) --> !(!c ^ b ^ k)
(3r) says, "If a candidate k is possible in a certain intersection of
row and block but is not possible elsewhere in that row, then it is
also not possible elsewhere in that block."
(3c) says the same for columns.
4. locked candidates, type 2:
4r. (r ^ b ^ k) ^ !(!r ^ b ^ k) --> !(r ^ !b ^ k)
4c. (c ^ b ^ k) ^ !(!c ^ b ^ k) --> !(c ^ !b ^ k)
(4r) says, "If a candidate k is possible in a certain intersection of
row and block but is not possible elsewhere in that block,
then it is also not possible elsewhere in that row."
(4c) says the same, but for columns.
This basic logic generalizes to ALL of the standard types of analysis.
Here X_n means a "exactly n of X", where X=r is row, X=c is column,
and X=k is candidate.
5. naked tuples (includes Rules 1r, 1c, and 1b):
5r. (r ^ c_n ^ k_n) ^ !(r ^ c_n ^ !k_n) --> !(r ^ !c_n ^ k_n)
5c. (c ^ r_n ^ k_n) ^ !(c ^ r_n ^ !k_n) --> !(c ^ !r_n ^ k_n)
5b. (b ^ (r ^ c)_n ^ k_n) ^ !(b ^ (r ^ c)_n ^ !k_n) --> !(b ^ !(r ^ c)_n ^ k_n)
(5r) says, "If n candidates are possible in a set of n columns of a given row,
and no other candidates are possible and in those n cells, then those n
candidates are not possible elsewhere in that row."
(5c) says the same for columns. (3b) says the same for blocks.
6. hidden tuples (includes Rules 2r, 2c, and 2b):
6r. (r ^ c_n ^ k_n) ^ !(r ^ !c_n ^ k_n) --> !(r ^ c_n ^ !k_n)
6c. (c ^ r_n ^ k_n) ^ !(c ^ !r_n ^ k_n) --> !(c ^ r_n ^ !k_n)
6b. (b ^ (r ^ c)_n ^ k_n) ^ !(b ^ !(r ^ c)_n ^ k_n) --> !(b ^ (r ^ c)_n ^ !k_n)
(6r) says, "If n candidates are possible in a set of n columns of a given row,
and those n candidates are not possible elsewhere in that row, then no other
candidates are possible in those n cells."
(6c) says the same for columns. (6b) says the same for blocks.
Note that exchanging k_n and !k_n and exchanging c_n and !c_n in 6r gives an
alternative statement of 5r:
5r'. (r ^ !c_n ^ !k_n) ^ !(r ^ c_n ^ !k_n) --> !(r ^ !c_n ^ k_n)
This says: "If other than n candidates are possible in other than n cells of a row,
and those other candidates are not possible in this set of n cells, then this
set of n candidates is not possible in those other cells. (5r) says the same thing,
but in a simpler fashion. What this exchanging shows is that naked tuples are the same
as hidden tuples, just seen from different perspectives.
7. grid analysis (X-Wings, Swordfish, etc.)
7r. (r_n ^ c_n ^ k) ^ !(r_n ^ !c_n ^ k) --> !(!r_n ^ c_n ^ k)
7c. (r_n ^ c_n ^ k) ^ !(!r_n ^ c_n ^ k) --> !(r_n ^ !c_n ^ k)
(7r) says, "If a candidate k is possible in the interesection of n rows and n
columns but is not possible elsewhere in those n rows, then it is also not
possible elsewhere in those n columns."
(7c) says the same, but reversing rows and columns.
--------------------------------------------------------------------------------------
If 7 is seen as an n-dimensionalization of 1 and 2, why not have an
n-dimensionalization of 3 and 4? The answer is that this is unnecessary. To
state, for example, "(r_n ^ b_n ^ k) ^ !(r_n ^ !b_n ^ k) --> !(!r_n ^ b_n ^ k)"
is just to state n versions of 3r.
The following rules are not necessary for standard (9x9) Sudoku because
for these puzzles a block only intersects three rows and three columns.
In that case, n can meaningfully only be 1 or 2, and (b ^ r_1) = !(b ^ r_2'),
where r_1 is a row and r_2' is the complementary set of two rows that intersect
the block. That is, b = (b ^ r_1) v (b ^ r_2'), so both cases have already been
taken care of. But in larger Sudoku, b != (b ^ r_1) v !(b ^ r_2'), because
there are more than three rows in a block.
8. generalized nxn Sudoku locked candidates, type 1:
8r. (r_n ^ b_n ^ k) ^ !(r_n ^ !b_n ^ k) --> !(!r_n ^ b_n ^ k)
8c. (c_n ^ b_n ^ k) ^ !(c_n ^ !b_n ^ k) --> !(!c_n ^ b_n ^ k)
(8r) says, "If a candidate k is possible in a certain intersection of
n rows and n blocks but is not possible elsewhere in those n rows,
then it is also not possible elsewhere in those n blocks."
(8c) says the same for columns.
9. generalized nxn Sudoku locked candidates, type 2:
9r. (r_n ^ b_n ^ k) ^ !(!r_n ^ b_n ^ k) --> !(r_n ^ !b_n ^ k)
9c. (c_n ^ b_n ^ k) ^ !(!c_n ^ b_n ^ k) --> !(c_n ^ !b_n ^ k)
(9r) says, "If a candidate k is possible in a certain intersection of
n rows and n blocks but is not possible elsewhere in those n blocks,
then it is also not possible elsewhere in those n rows."
(9c) says the same, but for columns.
10. generalized naked tuples, type 1:
10r. (r_n ^ b_n ^ k_n) ^ !(r_n ^ !b_n ^ k_n) --> !(!r_n ^ b_n ^ k_n)
10c. (c_n ^ b_n ^ k_n) ^ !(c_n ^ !b_n ^ k_n) --> !(!c_n ^ b_n ^ k_n)
(10r) says, "If n candidates are possible in the intersection of a set of n blocks
and a set of n rows, but are not possible elsewhere in those n rows,
then those n candidates are also not possible elsewhere in those n blocks."
(10c) says the same for columns.
11. generalized naked tuples, type 2:
11r. (r_n ^ b_n ^ k_n) ^ !(!r_n ^ b_n ^ k_n) --> !(r_n ^ !b_n ^ k_n)
11c. (c_n ^ b_n ^ k_n) ^ !(!c_n ^ b_n ^ k_n) --> !(c_n ^ !b_n ^ k_n)
(11r) says, "If n candidates are possible in the intersection of a set of n blocks
and a set of n rows, but are not possible elsewhere in those n blocks,
then those n candidates are also not possible elsewhere in those n rows."
(11c) says the same for columns.
--------------------------------------------------------------------------------------
12. Uniqueness. The uniqueness issue has been introduced at
http://www.sudoku.com/forums/viewtopic.php?t=890
Basically (I think) it amounts to having n of everything.
12. (b_n ^ r_n ^ c_n ^ k_n) ^ !(b_n ^ c_n ^ r_n ^ !k_n) --> puzzle is not unique
This says, "If there are n candidates that can only be found in the intersection of n rows,
n columns, and n blocks, and there are no other candidates in these cells, then this puzzle
is not unique."
This is because there would then be no way of distinguishing permutations of the puzzle.
Simple uniqueness tests amount to checking for this potential and heading it off by sometimes
being able to eliminating k_n from one of the cells. But one must be careful -- it is critical
that there be n blocks as well as n rows and n columns. If there are 2n blocks, then uniqueness
isn't an issue. For example, if n=2, so there two rows and two columns, two of the intersection
cells must be in one block, and two must be in another. If all four cells are in different blocks,
then there isn't a uniqueness problem.
_________________
Bob Hanson
Professor of Chemistry
St. Olaf College
Northfield, MN
http://www.stolaf.edu/people/hansonr
Last edited by Bob Hanson on Sun Dec 04, 2005 3:49 am; edited 2 times in total