Cross-Hatch Scanning (looking for singles)
When a candidate k is possible in only a single cell of a row, column, or block, then that cell must be k.This situation can arise for one of two reasons. A naked single arises when there is only one possible candidate for a cell; a hidden single arises when there is only one possible cell for a candidate. Despite the name, hidden singles are far easier to find than naked singles. You should always start a Sudoku by finding all the hidden singles. No marks required!
The dots in the cell in row 3, column 5, indicate that in that cell the numbers 4, 5, 6, and 8 are all possible. But in that top middle block only one cell can hold a 5. That's a hidden single.
Row/Column Range Checking ("locked" candidates)
When a candidate is possible in a certain block and row/column, and it is not possible anywhere else in the same row/column, then it is also not possible anywhere else in the same block.The locked candidate rule, form 2:
When a candidate is possible in a certain block and row/column, and it is not possible anywhere else in the same block, then it is also not possible anywhere else in the same row/column.Once all the singles have been found, I usually start marking. Then the job is to eliminate marks until only one remains in a cell, so then we know that cell's value. In this next technique, we use the fact that once a number can be assigned to a given row or column of a specific block (even if its exact location is still unknown), no other block may have that same number in the same row or column.
Range checking can be tricky to catch on to. Don't worry if you don't get it right away. Many puzzles can be solved without it. But if you do start seeing it, you will find it helpful.
Subset Elimination
When n candidates are possible in a certain set of cells all in the same block, row, or column, and no other candidates are possible in those cells, then those n candidates are not possible elsewhere in that same block, row, or column.The hidden subset rule states:
When n candidates are possible in a certain set of n cells all in the same block, row, or column, and those n candidates are not possible elsewhere in that same block, row, or column, then no other candidates are possible in those cells.Thus if a "subset" of three cells can be identified for which the only possibilities are exactly three numbers, then even though we don't know which of those cells has which number in it, we still know that no other cells in the row, column, or 3x3 block containing that "subset" of cells can have any of those numbers.
Grid Analysis
When a candidate is possible in a certain set of cells that form the intersection of a set of n rows and n columns, but are not possible elsewhere in that same set of rows, then they are also not possible elsewhere in that same set of columns.and its flipside,
When a candidate is possible in a certain set of cells that form the intersection of a set of n rows and n columns, but are not possible elsewhere in that same set of columns, then they are also not possible elsewhere in that same set of rows.The grid technique involves picking a specifc number, such as 5, and checking for known allowed patterns of possibility such as X-wings and swordfish.
 An X-wing pattern. Within the two highlighted columns, a 4 must be contained in each of the upper and the lower rows. The possibility of 4 in all five circled cells can be eliminated. |
 Two intertwined "swordfish" patterns. The possibility of 5 in the circled cell can be eliminated. |
Note that grid analysis is essentially a form of 2-dimensional subset elimination, where now the subsets themselves are correlated over multiple rows or columns. So, for example, if you look at that blue pattern, there is a set of three columns (the third, the sixth, and the seventh) for which 5 can only be in rows 2, 5, and 7. Three columns...three rows. Just like "three numbers...three cells". In exact analogy to subset elimination, this means that for these three rows the five must be in one of these three columns. it's tricky! In fact, though, X-wings and swordfish are simply two simple varieties of a much broader category of beast.
 | A 5x5 circuit containing the candidate number "1" hiding in a simple Sudoku. There are five columns and five rows that make up the set. All possibilities for 1 in these five rows and columns that are not on the grid itself can be eliminated. Note that if we list the row numbers where candidate 1 appears, we get {379 469 14679 46 139 1(not shown)}. So in this case the two indicated marks can be eliminated either due to the 5x5 "hidden quintuplet" of 34679 or the "naked singlet" 1. |
The demonstration of this equivalence of all such "circuits" is the way in which the Sudoku Assistant handles all circuit analysis without distinction:
- Look for regions of the board that have a given candidate's possibilities lying on a grid of n columns and n rows. Additional possibilities may exist outside of this set of gridlines in either rows or columns, but not both.
- Eliminate all possibilities of that number in any row or column defined by that grid but not including the grid points themselves.
A 4x4 grid based on
the candidate number 4
Generalized Method Rule
If a candidate k is possible in the intersection of X and Y but not possible elsewhere in X, then it is also not possible elsewhere in Y.
3D Medusa Analysis
a complicated X cycle
|
| ||||||||||||||||||
|
|
Cells XA and XC cannot be X,
and the cell labeled "XB" must be X.
The Sudoku Assistant will find these sorts of hinges if the "hinge" box is checked.
|
| ||||||||||||||||||
|
|
The cell labeled "XC" must NOT be X.
The classic example of weakly linked chains in the form of a Y-cycle is an XY-wing, shown below.
|
X... and Y... here are weak links. The first links the strong chains XZ and XY; the second links the strong chains XY and YZ. It doesn't really matter if those links are there or not. (If they are not there, then we just have one strong chain.) The effect is the same: "NOT Z" in the lower left cell gets transmitted to the top right cell through the chain:
Z--X--(weak X)--X--Y--(weak Y)--Y--Z - + - + - + ------direction of transmission----> |
as "Z" at the other end. Or, if the other Z is false, then we have:
Z--X--(weak X)--X--Y--(weak Y)--Y--Z + - + - + - <-----direction of transmission----- |
So one or the other of the Zs on the ends must be TRUE, and the * cannot be Z.
The term I use for * in the above situation is weak corner. Here we have again A --- b --- C, for which A and C are members of strong chains. To be a weak node, A and b must be in the same row, column, block, or cell, and the same is true for for b and C. But if these aren't the same row, column, block, or cell, then we don't have a weak link. Instead, we have a weak corner. The "strongness" of one chain cannot be transferred to the other chain via a weak corner, With the proper connecting of strong chains by weak links, one can infer valuable information about such a node. In particular, the elimination of the corner node, b, can be forced by the right sort of chain connection.
Almost-Locked Sets
8 1 2
\| /
A--3...3--B
/| |
9 7.........7
|
So the possibility of 7 in the two cells r3c8 and r3c9 can be eliminated. Note that the 3 in r3c8 cannot be eliminated, because there is a 3 in r6c7, and r6c7 is not "seen" by r3c8. In order to be eliminated, the possibility must be in a cell that is weakly linked to ALL occurances of that value in BOTH almost-locked sets.
But it's better than that. If B has the 7, Set A cannot have it -- Set A must be 1, 3, 8, and 9. Likewise, if Set A has the 7, then Set B does not. It must have 2 and 3. And then A has 1, 3, 8, and 9. Ah, but these are the only two possibilities! Either the 7 is in Set A or Set B. In either case, A has a 1, 8, and 9; and B has a 2. then any other 8 or 9 weakly associated with A, and any other 2 weakly associated with B can be eliminated! This includes any 8s in the third block (in the cells highlighted in red) as well as the 8 in row 2, column 6. Neat, huh?
{569 57 19 27 25 16}
Now, one way to see that the 5 in "569" can be eliminated is that we have here a "naked triple subset" (also called a swordfish in this plane): {57 27 25}. But there is another way: The {27 25} constitutes an almost-locked set, as does the 57. We have:
2
|
5*...A--5...5--B
| |
7.........7
|
- Finds all possible almost-locked sets.
- Checks to see if there are any mutually-linked pairs of almost-locked sets. If so,
it checks for weak links and eliminates them.
8 1 2...2* \| / A--3...3--B /| | 9 7.........7...7* - Looks for nodes that are weak links to two already-linked almost-locked sets and eliminates them. (7* in this case).
2...2---B / | 3--A | \ | 7..7*...7 - Looks for strong chain nodes that are themselves weakly associated with an almost-locked chain. If a chain
or set of chains is connected in an impossible way, such that it would force two of the N candidates of the
almost-locked set to be FALSE, that chain can be eliminated.
Due to the chain, the 2* and 7* have to be such that either both are TRUE or both are FALSE. But they can't both be TRUE, because that would not leave enough candidates for almost-locked set A. They can be eliminated.2...2*--2 / 7 3*...3--A . \ . 7...7*---7-
Hypothesis and (Dis)Proof
The disproof strategy goes like this:
Consider a certain chain, 3, that has two possible states, 3C and 3c.
- Hypothesize that a weakly associated node, say one of the 3c-associated nodes, is TRUE -- that it cannot be eliminated.
- Mark all Chain 3c nodes with the lowercase letter "a" meaning FALSE -- "If the hypothesis is true, then this node must be FALSE.
- Mark all Chain 3C nodes with an uppercase "A" meaning "if the hypothesis is TRUE, then these nodes must also be TRUE (not eliminated)." This works because Chain 3 is a strong chain.
- Mark all associated weak nodes of 3C with a capital letter "B" meaning "if the hypothesis is TRUE, then these nodes will be false (that is, they can be eliminated)."
- Recursively add any chains directly involving any of these associated weak nodes with alternating capital letters/lowercase letters.
- Check to see if we have either of the following two forcing conditions within any subset (all of a specific candidate in a row, column, or block, or all the candidates of a given cell):
- All members are FALSE. Then, since one HAS to be true, the hypothesis is disproved.
- Two members are TRUE. Then, since one MUST be false, the hypothesis is disproved.
If either of these is the case, we are done. The hypothesis is disproved and the node can be eliminated.
- All members are FALSE. Then, since one HAS to be true, the hypothesis is disproved.
An example of a pattern that is handled easily by hypothesis and proof is what has been referred to as an XYZ-wing. Both the * and Z here are weak corners between the two strong chains XZ and YZ. Let's hypothesize that the * is Z. Any Z shown, then, would be FALSE. But the X of XZ and the Y of YZ both must be TRUE, because they are parts of the strong chains associated with that * node. OK, so if they are TRUE then they each force the X and Y of XYZ to be FALSE. But then all of X, Y, and Z have to be FALSE. That leaves nothing at that position, and the hypothesis is disproved. Therefore, * is not Z. QED.
|
Note that in practice you doesn't really have to think about chains at all if you don't want to. Just follow the logic. One node TRUE means all those "related to it" are FALSE. From there, look for strong connections -- a cell with only two values in it, or a row, column, or block with only two of the TRUE node's value. Those are the strong chains that can be set TRUE. Go from there to find more FALSE nodes, and on and on. Periodically look to see if there is any row, column, block, or cell that satisfies any of those last three conditions. It's really no more than that.
Depth
- +depth just adding analysis involving single cells, rows, columns, and blocks (singles and locked candidates), and
- ++depth also adding analysis involving multiple cells, rows, and columns (n-tuples, grids). Note that using
++depth amounts to more than just one level of what people usually refer to as "depth" because these
methods can't be replaced by simple "If X then Y" type logic. They require "If X and Y then Z" logic, and that
is the logic of depth. ("OK, let's hypothesize that X is true, and then let's also hypothesize that Y is true, then....")
Beyond These Techniques
--Bob Hanson