Brian's Guide to Solving Difficult Sudoku
Introduction
These are notes on what I have learnt so far from playing Sudoku on the Sudoku 2Go Pro App, which among other things has a great progressive hint system that teaches you things.
Here is some terminology that I use to help keep these notes compact:
Digit. A number that is the only possible contents of a cell (either provided at the outset, or discovered).
Box. A 3x3 subgrid of cells. The Sudoku puzzle comprises a partially-filled grid of 9 Boxes.
Line. A row or column comprising 9 cells.
Region. A Line or a Box. The basic rule of Sudoku can now be written as:
(The name “Sudoku”, by the way, is abbreviated from the Japanese suuji wa dokushin ni kagiru, which means “the numbers (or digits) must remain single”.)
Boxed Line. The part of a Line that falls inside a Box.
Candidates. Numbers that have been identified so far (e.g. 2,3,7) as the possible contents of a cell. In any Region, a particular Candidate can occur once (in which case it is promoted to a Digit) or many times.
Promote. Discovering that a Candidate must be the Digit in that cell, eliminate the other Candidate(s) in that cell.
Start: Identify Digits in Blank Cells Where Possible
S1. The first thing to do is to look at the Sudoku grid, one Digit at a time, and see if that same Digit can be placed somewhere else with certainty, obeying the basic Sudoko rule.
S2. Repeat this as new Digits are discovered, until no more possibilities exist.
Next: Identify Candidates in Each Box
(The order in which you choose Boxes to do this is discussed in the General Strategy section below.)
C1. For each empty cell in the Box, identify Candidates by eliminating those that match any Digit in the same Region (i.e. in the same Box or Line).
C2. Once that it is done, consider the immediate Elimination Possibilities for this Box as discussed in the next section.
C3. It is also useful at this stage to note for future reference any Candidates that appear in only one Line within the Box, i.e. in only one Boxed Line.
Some Elimination Possibilities - For Regions With No Empty Cells
E1. Singleton Candidates. If a Candidate appears only once in a Region (i.e. in a Line or Box), then Promote that Candidate. For example, a cell with Candidates [1,4,6,8] can become [4] if 4 appears only once in this Region.
E2. Naked Pairs (compare with E3). What you are looking for is two cells in the same Region containing ONLY the same pair of Candidates (e.g. [2,3] and [2,3]). In this example we know that 2 must be a Digit in one of the cells and 3 must be a Digit in the other. It doesn't matter if 2 or 3 appear as a Candidate in any other cells in the same Region - in fact it's useful if they do since we can eliminate them from those other cells.
E3. Hidden Pairs. This is kind of the other way round from Naked Pairs. What you are looking for here are two cells in the same Region containing not only the same pair of Candidates but also at least one other additional Candidate, e.g. [1,2,3,5,6,8] and [2,3,5,6,7,8].
Unlike Naked Pairs, however, neither 2 nor 6 in this example may occur elsewhere in this Region. In this situation we can eliminate the “extra” Candidates (red in the example) from the two cells, leaving [2,6] and [2,6].
A good way to discover Hidden Pairs is to pause whenever you discover only two occurrences of a particular Candidate (e.g. 2) in
a Region. Then in each of those two cells, check for another Candidate (e.g. 5) that occurs nowhere else in the Region.
If you find one in each of those two cells then you have discovered Hidden Pairs!
E4. Naked Triples (compare with E5). What you are looking for is a set of three numbers that appear as Candidates in three cells in the same Region. Two or three of these numbers (but no other numbers) must appear in each of the three cells.
Examples would be [2,4,7], [2,4,7], [2,4,7] or [2,4,7], [2,4,7], [2,7] or [2,4], [2,7], [4,7]. In these examples we know that those three numbers MUST be found in those three cells, even if some of those numbers also appear in other cells (in which case we can eliminate them from those other cells).
It isn't obvious, perhaps, why a group such as [2,4], [2,7], [4,7] meets the same criteria for Naked Triples as does [2,4,7], [2,4,7], [2,4,7]. It's worth understanding why:
Imagine that 4 was a Candidate in some other cell in the same Region, and is later discovered to be the actual Digit for that cell. This couldn't actually happen, because if it could then the original three cells would be reduced to [2], [2,7] and [7], and then because we now have a Digit [2] in the first cell, reduced again to [2], [7] and [7] - an incorrect solution.
E5. Hidden Triples. This is kind of the other way round from Naked Triples (and is often tough to spot). What you are looking for here are three cells in the same Region containing not only the same three Candidates, but also at least one of those cells has at least one additional Candidate (e.g. the three cells might have Candidates [1,2,6,7,9], [1,5,9] and [2,4,5,7,9]).
Unlike Naked Triples, however, the three Candidates must NOT appear in any other cells in the Region. In this situation we can eliminate the “extra” Candidates (the red Candidates in the example) from the three cells, leaving [1,7,9], [1,9] and [7,9].
For the same reason as in Naked Triples, not every number in the “triple” (for this example, 1 and 7 and 9) needs to appear in all of the three cells. For example, [1,2,7,9], [1,4,5,9] and [2,7,9] reduce through elimination to [1,7,9], [1,9] and [7,9] - provided, as with other Hidden Triples, that neither 1 nor 7 nor 9 appear in any other cells in the same Region.
A good way to discover Hidden Triples is to pause whenever you discover only three occurrences of a particular Candidate (e.g. 9) in a Region. Then in each of these three cells, check for at least one of two other Candidates (e.g. one or both of 1 and 7) that occur nowhere else in the Region, i.e. nowhere outside these three cells. If you find these, in a pattern that would be valid for Naked Triples, then you have discovered Hidden Triples!
Unfortunately, this method doesn't work if the actual (as yet undiscovered) Triples consist of three pairs of two Candidates, e.g. [2,4], [2,7], [4,7]. In order to cover this case you should pause whenever you discover three different Candidates in a Region that each occur only twice in that Region. If all these occurrences are confined to only three cells then you have again discovered Hidden Triples!
(I did say that Hidden Triples are often tough to spot.)
You might be suspecting at this point that there are also such things as Naked Quads and Hidden Quads. If so, you are right - luckily they are very rare. Follow the links to find out more!
E6. Last Man Standing. This is entirely obvious. If 8 Digits have been identified in a Region, then the last cell in that Region is not in doubt!
More Elimination Possibilities - Intersections of Lines with Boxes
You can check for these as soon as, or whenever, you have a line of three Boxes with filled-in Candidates, i.e. you have Candidates in all cells in Lines that pass through these Boxes.
(These checks are in addition to E1 to E6 above, which can of course be applied to Lines as well as to Boxes.)
Consider each Line passing through each Box. You may find these checks easier if you have done step C3 above.
X1. Locked Candidates (Box). Examine a Box. If all of one particular Candidate for this Box (e.g. every “5”
that occurs as a Candidate in this Box) falls on a single Boxed Line within the Box, as perhaps was identified
in step C3, then that Digit must actually be somewhere in that Boxed Line, and can be eliminated as a Candidate
from the rest of the Line.
X2. Locked Candidates (Line). Examine a Line. If all of one particular Candidate for this Line
(e.g. every “4” that occurs as a Candidate in this Line) falls within one Box, as perhaps was identified in step C3,
then that Digit must actually be somewhere in that Boxed Line, and can be eliminated as a Candidate from the rest of the Box.
When All Boxes in the Sudoku Grid Have Digits or Candidates
This is when the hard work really begins, especially if the puzzle is classed as “Fiendish”.
Before continuing, it's a good idea to check every occurrence of each Digit systematically, to make sure that there are no corresponding Candidates left in any of that Digit's Regions. There shouldn't be if you have made no mistakes... but I certainly make occasional mistakes.
It also helps to repeat check S1 (which can be done earlier as well) systematically for each Digit in turn. This will eliminate other Candidates in any cell in which you discover that that Digit must fall.
- Advanced Elimination Techniques (Short Version)
- Solving hard Sudoku puzzles may require new elimination techniques, in addition to those described above.
- These more difficult techniques require you to examine multiple columns and lines simultaneously.
- The main techniques here are the X-Wing (intersections of two columns and two lines, as shown here) and the Swordfish (intersections of three columns and three lines).
- There are also the so-called Finned Variations of these.
- I have found all of the above to be necessary at one time or another, and sufficient to solve all the "fiendish"-level puzzles that I have encountered so far, but there are still more elimination techniques that I have yet to explore.
- I may expand this section in the future. Meanwhile the links and the next section below may be helpful.
Example of an Advanced Elimination Technique
Here is an example of a Finned X-Wing - and to make things more interesting, it's not the “plain vanilla” version but the so-called Sashimi variant. You will find a good explanation of the Finned X-Wing and this variant if you click the image to the right, or go here.
Assuming that you did follow that link and that it made sense to you...
In this case we are focusing first on the orange-highlighted columns, looking for a Candidate in those columns that occurs only in all four of its intersections with two rows. If we found one then we could eliminate all such Candidates occurring in the blue-highlighted rows outside the intersections (X‑wing logic).
We almost find such a Candidate (2) in the intersections with the blue-highlighted rows - but one such Candidate has been replaced by a Digit (4).
This would be useless were it not for the “Fin”, which is Candidate 2 at the top of the left-hand orange-highlighted column (in cell R1C6). (It would also be pointless, since if the Fin weren't there you could immediately promote Candidate 2 in R4C6 to a Digit since it would be the only such Candidate in that column!)
Here's the important thing: what makes the Fin useful is that it is in the same Box as some (not all) of the Candidates that we would have been able to eliminate if it had been a normal X-Wing.
Now there are two possibilities: the Fin is where Digit 2 is, or it isn't. If the Fin contains Digit 2, then all matching Candidates in the same Box (red crosses in the image) would be eliminated. If the Fin doesn't contain Digit 2 then the cell in R4C6 must contain Digit 2, therefore the cell in R3C7 must also contain Digit 2 (X-Wing logic), and hence Candidate 2 can be eliminated from the cells marked with a red cross since they are on the same row.
It's important to understand that we don't know which of these two possibilities exist, but both possibilities result in the elimination of Candidate 2 from the red-cross cells.
If that all made sense to you then you have nothing to fear from fiendish-level Sudoku!
General Strategy
There are many strategies for approaching a solution. These are some notes on mine.
My aim is to proceed in such a way that Candidates are discovered as soon as possible. This makes later stages of solving the puzzle that much easier.
When I work on each Box in turn, as per steps C1 to C3, I choose Boxes that form a line (horizontal or vertical) to begin with. I do steps E1 to E6 for each Box, hopefully eliminating Candidates as I go. When I complete that line of Boxes I can also carry out steps X1 and X2 for those Boxes, and repeat steps E1 to E6 for each Line of nine cells running through the Boxes.
Next, I work on two more Boxes in a line of Boxes that intersects the first line. In that way, after only two more Boxes I can repeat steps X1 and X2 for that new line of Boxes, and repeat steps E1 to E6 for each Line of nine cells running through the Boxes.
It is now quick to complete each of the remaining lines of Boxes.
Once that's done, I work systematically again through each Box and then each column and then each row, now including (for columns and rows) the advanced checks outlined in the yellow panel above, and repeat as necessary as further eliminations take place.
Although the Sudoku 2Go Pro App eliminates most of the manual marking-up when solving Sudoku, I still find it useful to keep track of some things on paper.
In the middle stages of solving Sudoku, identifying an actual Digit may uncover other actual Digits, before I have finished dealing with the first one.
When I identify an actual Digit I note where it is on a simple 3x3 grid, and circle it. Before I finish processing the consequences of that discovery I note down the whereabouts of any other discovered Digits for future reference. When all the outcomes of the first Digit have been processed then I cross out that Digit on my paper grid, and circle another one (if any) and work on that until it, too, can be crossed out.
I find that this systematic approach really helps while there are still many cells with many Candidates. Eventually, or if the puzzle is easy to begin with, I dispense with the paper and just eliminate remaining Candidates “by eye”.
Help, I'm Stuck!
I know the feeling well, especially with fiendish-level puzzles and a sea of apparently intractable Candidates. I sometimes ask the App for a progressive hint, and then kick myself that I didn't see where to look.
Golden Rule: Take a break!
Then check every occurrence of each Digit again systematically, to make sure that there are no corresponding Candidates left in any of that Digit's Regions. This is a common reason for me to find that I can't make progress.
Then check again for the easy “Get Out of Jail Free” cards, which are Naked Pairs (E2), Naked Triples (E4) and Singleton Candidates (E1).
The best remedy after that, that I have found so far, is to repeat step C3 systematically for each Box or Line, looking for Candidates that appear only on one Boxed Line, and then explore all the possibilities (X1, X2) arising from those.
Finally have another look for Hidden Pairs (E3) and Hidden Triples (E5), and repeat carefully the advanced checks outlined in the yellow panel above.
Have fun!
- If you like this kind of thing...
- My "Did You Know?" page boldly goes where some remarkable discoverers have gone before, and tries to make sense of the amazing things that they found.
- Why do sunrises and sunsets not start to get earlier and later on the same date, after the winter solstice?
- What does Conway's Game of Life tell us about the real world?
- What is really going on in the awesomely beautiful and mysterious world of the Mandelbrot Set?