-
Notifications
You must be signed in to change notification settings - Fork 15
SE121 Equivalence between Naked Sets, Hidden Sets and Fishy patterns
This page illustrates the equivalence between three classes of Sudoku solving techniques: Naked Sets (Naked Pair, Naked Triplet and Naked Quad), Hidden Sets (Hidden Pair, Hidden Triplet and Hidden Quad) and Fishy Patterns (X-Wing, Swordfish and Jellyfish). This is an illustration, not a formal proof; and only the equivalence between Naked Pair, Hidden Pair and X-Wing is shown.
It is assumed you already have a good knowledge of Sudoku and Sudoku solving techniques. The solving techniques are not explained there.
Just to make things clear: "equivalent" is to be taken in the sense "implementable by the same algorithm".
Sudoku Explainer - a step-by-step Sudoku solver
Sudoku Explainer FAQ
Some interesting Sudokus for exploring the solving techniques
Sudoku on Wikipedia - The free encyclopedia
Sudoku Susser - another Sudoku solver
Sudoku Assistant/Solver - another Sudoku solver (in Javascript)
Sudoku Players' Forums
Sudoku Programmers' Forums
The following figure illustrates a sample X-Wing in an abstract way.
..+..+... --X--X--- ..+..+... ..+..+... --X--X--- ..+..+... ..+..+... ..+..+... ..+..+...
Let's assume the X-Wing is on the value 1 (every step can be generalized to any value). The 81 symbols of the figure above correspond to the 81 cells of the Sudoku, and have the following meanings:
- "X": the cell has the value 1 as a candidate. In this particular example, the cells R2C3, R2C6, R5C3 and R5C6 have the value 1 as a candidate. (Notation: R2C3 means the cell located at the 2nd row and 3rd column)
- "-": the cell does not have the value 1 as a candidate. In this particular example, no cell of the rows 2 and 5, except R2C3, R2C6, R5C3 and R5C6, has the value 1 as a candidate.
By definition, the two above constraints defines an X-Wing on the value 1: in the rows 2 and 5, the value 1 only occurs in the same two columns 3 and 6. By applying the X-Wing rule, the remaining symbols have the following meanings:
- "+": the value 1 can be excluded from these cells (if present)
- ".": Nothing can be deduced on these cells
Since now, we have just illustrated and explained the X-Wing solving technique. Now, we will show that the same illustration, when interpreted in a different way, exactly illustrates and explains the Hidden Pair rule.
When illustrating the X-Wing rule, we chose the value 1. For the Hidden Pair rule, we will not choose any value, but rather a region (row, column or block), for example, the first 3x3 block (again every steps can be generalized to any region). This time, the illustration does not represent the 81 cells of a Sudoku. For the Hidden Pair illustration, the rows and columns have the following meanings:
- The 9 columns correspond to the 9 cells of the first 3x3 block.
- The 9 rows correspond to the 9 possible values (or symbols) 1 to 9.
Let's show the illustration again:
..+..+... --X--X--- ..+..+... ..+..+... --X--X--- ..+..+... ..+..+... ..+..+... ..+..+...
And define the following meanings for the symbols:
- "X": the cell corresponding to the column has the value corresponding to the row as a potential value. In this particular example, the 3rd and the 6th cell of the block both have the values 2 and 5 as potential values.
- "-": the cell corresponding to the column does not have the value corresponding to the row as a potential value. In this particular example, no cell except the 3rd and the 6th have the values 2 and 5 as potential values.
Did you follow everything? Let's summarize: our example illustrates a situation where, within a given block, two different values (2 and 5) can only be located in two different cells (the 3rd and the 6th or the block). This is by definition an Hidden Pair!
To make the Hidden Pair equivalent to the X-Wing, it suffices to define the remaining symbols as:
- "+": the value corresponding to the row can be excluded from the cell corresponding to the column. In this particular example, we can exclude all values except 2 and 5 from the 3rd and 6th cells.
- ".": Nothing can be deduced for the cells and values.
Again, this exactly corresponds to what we do when we apply the Hidden Pair rule.
Both the X-Wing and the Hidden Pair can be converted to a representation consisting of 9 x 9 "states" (represented by the symbols "X", "-", "+" and "." in the illustrations). The conversion of the X-Wing is quite straightforward. The conversion of the Hidden Pair is more subtle. But in this representation, both solving techniques can be detected and applied by the same algorithm.
Everything we have applied on the Hidden Pair can also be applied to the Naked Pair. The only difference is that the meanings of the rows and columns of the illustration must be exchanged, compared to the Hidden Pair:
- The 9 columns correspond to the 9 possible values (or symbols) 1 to 9.
- The 9 rows correspond to the 9 cells of the first 3x3 block.
With this in mind, the equivalence between the X-Wing and the Naked Pair is quite straightforward. This is left as an exercise to the reader.
..+..+... --X--X--- ..+..+... ..+..+... --X--X--- ..+..+... ..+..+... ..+..+... ..+..+...
By the way, if X-Wing and Hidden Pair are equivalent, and X-Wing and Naked Pair are equivalent, then Hidden Pair and Naked Pair are equivalent too. The equivalences we have shown between the X-Wing, Hidden Pair and Naked Pair can be extended, using the same representation, to the Swordfish, Hidden Triplet and Naked Triplet, or to the Jellyfish, Hidden Quad and Naked Quad. What I still do not understand is why there are still people and tools out there which pretend that
is an unsupported HTML feature. Nevertheless, this concludes the proof of equivalence, which, again, is not a formal proof, but an illustration.
| Last update: 2006-04-07 |