- Games, Toys, and Hobbies»
- Puzzles, Logic Problems & Brain Teasers
Sudoku Sherlock-Style: Getting To N-1
At a bare-bones level, all Sudoku solving is about eliminating the impossible until just one alternative remains—as Holmes observed, the remaining possibility must represent the answer we seek. I like to call this “getting to N-1,” perhaps because it makes me feel more mathematically adept that I actually am.
The first tack most of us take to get to N-1 is what I’ve called “cross-referencing.” In this strategy, we look at a particular digit—say, all the 1s—in a grid, observing where their “lines of influence” intersect, as illustrated in the grid below:
For each “subgrid”—that’s just my terminology, by the way—there are nine boxes, so our “N” for the subgrid starts out as 9. If the subgrid is the intersection of two columns and two rows containing ones as shown, then 8 boxes will be ruled out, since you can never have two 1s in the same row or column. That means N–1 possibilities have been ruled out! That leaves just one box that can contain a 1, so we can write a 1 in it with full confidence that it is correct.
By the way, when we do write that number in, it is a good idea to check immediately whether this new digit gets us to N-1 in some other subgrid—that is, it’s a good idea if we want to solve our puzzles faster! Here’s an idealized (unrealistic but clarified) example, based on the previous grid:
The new “1” we write in eliminates one of two possible boxes for the digit “2”—blocking it out, as it were. This brings up the fact that, unlike our first example, most subgrids in most puzzles already have some boxes with numbers entered when we begin. Naturally, these numbers reduce “N” accordingly. For example, the highlighted subgrid in the example below has 5 boxes already filled, so “N” for that box starts out as 4—and luckily for the solver, a single well-placed 1 eliminates 3 of them at a stroke—and voila! we have “N-1!”
Sometimes we don’t quite make it to N-1, naturally; the information we need isn’t yet available. But that doesn’t mean we should give up on the angle we’ve been considering—at least, not just yet. Sometimes “N-2,” or even “N-3,” implies “N-1” somewhere else in the layout.
At first blush, it might seem that there is nothing that can be done with this layout. None of the digits we need in our right-hand ‘target’ subgrid are helpfully placed in the left-hand subgrid. However, we can place one of them—“1”—to N-3. Specifically, we know it’s found somewhere within the three boxes of the top row. And since those boxes are contained within a single row, they are just as useful as an actual written “1” for getting to N-1 in the target subgrid.
Here’s how it looks:
It’s as if the unseen digit casts a shadow across the rest of the row, so I call this strategy “shadow theory.” It’s a surprisingly versatile solving tool, and the second pillar of my Sudoku strategy “CSI”—“Cross-reference, Shadow, Inventory.”
So far we’ve been looking at possibilities only in terms of physical position with a sub-grid. But it’s often necessary to consider possibilities from the angle of numerical complements as well. What does that mean?
Well, since every row, column or subgrid must contain all the digits from 1-9 with no duplications, it’s easy to make a list of the missing digits. For example, if a particular row contains the digits 1-6, we can conclude that the missing digits in that row must be 7-9. Of course, that means that each of the three empty boxes in that row can only be 7, 8 or 9. I call this “inventorying possibilities”—and yes, that is the “Inventory” in “CSI.”
Now, here’s the good part. If any two of these three digits affect one of the empty boxes, then we’ve reached N-1 for that box, and have found our answer!Here’s an idealized example of this highly effective technique:
One of the cool things about this is that it very often leads to the other missing digits, too, if you follow up properly. For example, if you have either a “1” or “2” showing anywhere in the bottom 6 boxes of the top middle subgrid, you’ll be able to fill in both digits of the right hand row. Here’s how that might look:
Examples 8a and 8bClick thumbnail to view full-size
Once you get the “2”, the “1” follows by simple elimination. (This isn't the purest example, because you could do the same thing without this technique by starting instead with the 2s. But doing it the way we did illustrates the technique--and sometimes there really is no alternative.)
The same principle applies, naturally, with filling subgrids instead of columns or rows, although admittedly it looks a little different:
It doesn’t have to look as neat as that, either; the open boxes in the target subgrid could have been arranged any old way, but as long as one of them aligns with two of the missing digits somewhere, you have reached N-1. Here’s a “messier,” but still idealized example:
This layout is also a good example of how easy it is to miss inferences that are right in front of you, if you don’t make a real point of always following up. If you didn’t pick up on this, there is a second digit you can place, without any additional clue. Here’s the grid after placing the “3” via inventorying; click the thumbnail to see the other digit:
Examples 11a and 11bClick thumbnail to view full-size
Just to hammer the point home, this also gives you the last digit by elimination:
This technique is highly fruitful, especially with harder puzzles. Almost by definition it generates information about digits that we have relatively less information about. In doing so, it takes us beyond what cross-referencing can do—and that’s almost always crucial in moderate or hard puzzles.
Let’s close with one last wrinkle on these concepts. In harder puzzles it’s frequent to come to a “bottleneck,” where there seems at first to be no way forward. Often a combination of “inventory” and “shadow” techniques will provide the key we need. In the partially completed grid below we have a similar situation.
The way forward is not so obvious. (By the way, ‘true’ bottlenecks—ones where there is one, and only one, way forward--are less common than they seem. In writing this Hub, I discovered that more than one example of a bottleneck I had carefully saved, I had actually overlooked a more straightforward way forward.)This may be a true bottleneck; certainly, the way forward I found is not so straightforward. But perhaps there’s an easier way I missed. At any rate, my way begins with a complex combination of all three ‘CSI’ tactics. Consider first the highlighted column shown below:
Inventorying the missing numbers in this column, we find that the 3, 4, 6 and 9 are missing. We then cross-reference to see where they might fall, using shadow theory as necessary. Because the bottom box of the column is aligned with both 3 and 9, we can conclude that that box must be either 6 or 4 (an N-2 situation.)
Let’s postulate which one it is, and see where it leads us. If we pick the wrong digit, at some point we will reach a contradiction and we’ll know we have to go back and proceed from the opposite assumption. But we’ll be pretty sure at that point we’re right.
Let’s try the 6 in that spot, and see what happens. If you’d like to work this through on your own, why not hit my ‘Blank Grid’ Hub and print out a grid you can work yourself? (You can get there with one click using the "series" arrow at the bottom of the page.) In my next example I’ll give what I subjectively consider the fairly immediate consequences of the choice of 6, discuss it a bit and then move forward with the puzzle.
There are immediate consequences from here, but having the 4 and 6 complete for the entire grid makes a good point to pause. The 6 in the upper left subgrid follows immediately by cross-referencing, as does the one in the lower middle subgrid. The one in the upper right is implied by the new 6 we just found in the upper left subgrid.
There are simpler ways to proceed, but let’s practice the technique we just learned. Consider the grid as it now stands, and especially the highlighted boxes:
Inventorying reveals that these two boxes must contain a 3 and a 9. But cross-referencing doesn’t tell us which is which. So we can inventory again—this time finding that the other two boxes in the subgrid must contain a 2 and a 5. These boxes are shown in orange highlighting below:
Unfortunately, cross referencing still doesn’t help us. But one more inventory does the trick, as shown below:
OK, there were a lot simpler ways to get here! But I did say the point was to practice the techniques, right?
Let’s continue on.
That’s about 3 cross-references, with the third column from the right then completed by inventorying and cross-referencing. This is going well—no contradictions so far--so let’s continue.
This sequence started with an inventory of the upper right subgrid and proceeded in a very straightforward way from there. By now, one gets the feeling that we probably picked the right digit when we posited 6 rather than 4.
Yup, we backed the right horse, all right! And we’re rewarded with a completed Sudoku.
Well, thanks for following this somewhat lengthy discussion of Cross-referencing, Shadow Theory and Inventorying. I hope they help you solve more challenging puzzles faster—and more, that you have more fun doing it!
- How (not) to replace a door
A Do It Yourself project that's much easier than you might think--and that can really add value to your home. Learn some tricks and traps here.
- How (Not) To Practice Music Efficiently, Part Two
So many ways not to practice music efficiently! But who can afford to waste the time? Learn how NOT to, with this, the more 'niity-gritty' of two Hubs on practicing music.
- Inuk Was A-Positive: A Brief Meditation
there you are, living life--and some cute little new item smacks you right between the eyes. "Inuk was A-positive. For some reason, that information hit me with a certain imaginitive force..."
- "Fixing Climate": A review
Where did all this concern about climate come from? One man's story. "Dr. Wally Broecker is no fan of large bureaucracies, which is why, though he is a grand old man of contemporary climate science..."