Sudoku Programmers Forum Index

 
 FAQFAQ   SearchSearch   MemberlistMemberlist   UsergroupsUsergroups   RegisterRegister   ProfileProfile   Log inLog in          Games  Calendar

Log in to check your private messagesLog in to check your private messages   

12 logical rules of solving sudoku

 
Post new topic   Reply to topic    Sudoku Programmers Forum Index -> Solving sudoku
View previous topic :: View next topic  
Author Message
Bob Hanson

Joined: 05 Oct 2005
Posts: 187
:
Location: St. Olaf College

Items
PostPosted: Fri Dec 02, 2005 3:28 pm    Post subject: 12 logical rules of solving sudoku Reply with quote

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)

Code:

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 8:49 am; edited 2 times in total
Back to top
View user's profile Send private message Send e-mail Visit poster's website
Pep

Joined: 27 Nov 2005
Posts: 10
:
Location: Bath, UK

Items
PostPosted: Fri Dec 02, 2005 7:42 pm    Post subject: Reply with quote

This analysis is very similar to what I'm slowly working towards. The main difference is that I'm keen to show the human viewer exactly where the chains and clashes are. It is taking some time to catch up with you.

However, is it true that you only consider single cells at the intersections between r/c/b's?

We need a term for a r/c/b since it is irrelevant what they are to your description. I've been using tuple, but I see that you've taken that. Perhaps domain or something similar might be better.

In any case, it could be that a link's strength depends on what the intersection is with its neighbour? For example, if a cell might be 9 in a domain, then it implies that both of two other cells are not 9, and if either of the other two are a 9, then the first one is not, which makes the link strong if the connection to the next link contains both of the pair (like a r/b intersection).
Back to top
View user's profile Send private message
Bob Hanson

Joined: 05 Oct 2005
Posts: 187
:
Location: St. Olaf College

Items
PostPosted: Fri Dec 02, 2005 10:41 pm    Post subject: Reply with quote

Quote:
However, is it true that you only consider single cells at the intersections between r/c/b's?


Not at all. The intersection of a row with a block is three cells.


We need a term for a r/c/b since it is irrelevant what they are to your description. I've been using tuple, but I see that you've taken that. Perhaps domain or something similar might be better.

"house" is sometimes used. My point here is to not use jargon if possible. They all can be summed up using "house" pretty much. But I've never felt that was very clear.

I don't really understand what you are getting at in terms of "links" and "strong" here.
_________________
Bob Hanson
Professor of Chemistry
St. Olaf College
Northfield, MN
http://www.stolaf.edu/people/hansonr
Back to top
View user's profile Send private message Send e-mail Visit poster's website
Pep

Joined: 27 Nov 2005
Posts: 10
:
Location: Bath, UK

Items
PostPosted: Sat Dec 03, 2005 8:05 pm    Post subject: Reply with quote

The comment about links was in the wrong place. I'll start a new thread about Medusa chains instead of trying to hijack this one.
Back to top
View user's profile Send private message
dukuso

Joined: 14 Jul 2005
Posts: 424
:
Location: germany

Items
PostPosted: Sun Dec 04, 2005 10:06 am    Post subject: Reply with quote

exact cover:
c:constraint (one of the 324 columns in the binary exact-cover-matrix A)
r:placement (one of the 729 rows in the exact cover matrix)
N(c): all placements which satisfy a constraint N(c)={r,A(r,c)=1}
N(r): all constraints which are fullfilled by placement r
N(C): union of N(c) with c in C
N(R): union of N(r) with r in R
A-r: row r deleted (marked used)
A[r]: delete r,N(r),N(N(r)) (mark used)

task:
find R with N(R) is the set of all 324 columns and N(r1) disjoint
to N(r2) for all r1,r2 in R
So(A) is the collection of all such R ("solutions")


singles:
N(c)={r} ==> So(A)=So(A[r]) (placement r is forced)


locked candidates:
N(c1) < N(c2) , r in N(c2)-N(c1) ==> So(A)=So(A-r) (placement r can be deleted)
("Jaap1")


tuples:
Let D be a set of k different,mutually nonadjacent columns.
Assume N(D) partitions into k disjoint sets R1,..,Rk
each consisting of mutually adjacent rows.
If r is a row not in N(D) but adjacent to all rows in R1 then
So(A)=So(A-r) , i.e. r can be deleted.


X-wing:
"Jaap2"
Back to top
View user's profile Send private message Send e-mail Visit poster's website
Display posts from previous:   
Post new topic   Reply to topic    Sudoku Programmers Forum Index -> Solving sudoku All times are GMT
Page 1 of 1

 
Jump to:  
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
Sudoku Programmers topic RSS feed 


Powered by phpBB © 2001, 2005 phpBB Group

Igloo Theme Version 1.0 :: Created By: Andrew Charron