View previous topic :: View next topic 
Author 
Message 
smith55js
Joined: 29 Nov 2005 Posts: 9 Location: Logan, UT

Posted: Fri Dec 02, 2005 1:16 am Post subject: Sudoku Solving Techniques 


Just trying to get a good list of techniques people use in solving these puzzles. I'm looking for distinct, logical steps one can take.
For this I'll use the terms block, row, column, and group (3x3).
To determine value of block one of the following must be true:
1. Block only has one possiblity
2. A row/column/group's only possible location for a value is in the block
To eliminate values from a block's list of possiblities one of the following must be true:
1. Value occurs elsewhere in the same row/column/group
2. In a group, all possibilities for a value occur on the same row/column. This eliminates this value from all blocks in the said row/column outside this group.
3. Two blocks in a row/column/group have equivalent possiblity lists consisting of only 2 numbers. This eliminates those numbers from the rest of the row/column/group.
4. Three blocks in a row/column/group have equivalent possiblity lists consisting of only 3 numbers. This eliminates those numbers from the rest of the row/column/group.
Can anyone add to this list? It's hard to pull it off the top of my head. I'd just like a distinct list of logical rules to apply to these puzzles. Any help is appreciated. 

Back to top 


David Bryant
Joined: 29 Jul 2005 Posts: 559 Location: Denver, Colorado

Posted: Fri Dec 02, 2005 7:48 pm Post subject: Here are some tips 


Jake Smith wrote:  For this I'll use the terms block, row, column, and group (3x3) 
Most people call your block a "cell." Some people call your group a "group," but it's often referred to as a "block," and also as a "box."
Jake Smith wrote:  To determine value of block one of the following must be true:
1. Block only has one possiblity
2. A row/column/group's only possible location for a value is in the block. 
People generally refer to the possible values that can lie in a cell (your "block") as the candidates. So your rule #1 is called "sole candidate," or sometimes "naked singlet."
People usually refer to your rule #2 as "hidden singlet." It's said to be "hidden" because the list of candidates has more than one element, so one must examine all the cells in the row/column/group to determine that this value really goes right here.
Jake Smith wrote:  To eliminate values from a block's list of possiblities one of the following must be true:
1. Value occurs elsewhere in the same row/column/group
2. In a group, all possibilities for a value occur on the same row/column. This eliminates this value from all blocks in the said row/column outside this group.
3. Two blocks in a row/column/group have equivalent possiblity lists consisting of only 2 numbers. This eliminates those numbers from the rest of the row/column/group.
4. Three blocks in a row/column/group have equivalent possiblity lists consisting of only 3 numbers. This eliminates those numbers from the rest of the row/column/group. 
For your rule #2, most people speak of the "row/column on 3x3 block interaction," or maybe of the "row/column on group interaction." You might note a closely related corollary  if the only possibility for a particular value within a row/column lies entirely within one group, then possibilities in that group lying outside that row/column can be eliminated.
Your rule #3 is known as a "naked pair," or possibly as a "hidden pair." And your rule #4 is known as a "triplet," or possibly as a "hidden triplet." (I'll explain the terminology "hidden" in just a minute here.) You should also note an analagous possibility involving four distinct values in tour cells, called a "quadruplet"  this is possible, but doesn't occur in practice very often.
When the explicit enumeration of the candidate lists reveals a pair, or a triplet, or (rarely) a quadruplet, the set is said to be "naked." A "hidden" pair is also possible, usually arising from a setup that looks something like this.
Code:  . . . . 5 2
. . . . . .
. 8 1 . . .
2 . . . . .
. . . . . .
5 . . . . . 
In this (abbreviated) example explicit enumeration of the candidates in r2c2 and r2c3 would yield two very long lists. But we can see that the pair {2, 5} must be the _only_ candidates for these two cells because there's no other way these two values can possibly fit in the top left 3x3 box. (Note that "hidden" triplets and quadruplets are also possible, although they do not often arise in real world puzzles.)
Jake Smith wrote:  Can anyone add to this list? It's hard to pull it off the top of my head. I'd just like a distinct list of logical rules to apply to these puzzles. Any help is appreciated. 
You've already discovered the "elementary techniques," Jake. There are also a number of "advanced techniques," with names like XWing, and Swordfish, and Nishio, and Coloring, and XYWing. There's a message in another forum that provides several links to quite a bit of explanatory material.
Happy sudokuing! dcb 

Back to top 




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

Powered by phpBB © 2001, 2005 phpBB Group
