Feb 18 2013

Sudoku: the basics

Those of us who think we'll live a long time (not me) have a couple near certain conditions to look forward to. For men, it's prostate cancer. But for either gender, it's dementia. Puzzles ward off dementia. I'm not all that good at puzzles. Over the years I've done crosswords, but they require a bit too much outside knowledge (not to mention having a large lexical database with words like oleo, Olin, Gynt, etc). For awhile I did the newspaper Cryptoquote, but those became a bit too easy.

But eventually, I did the LA Times' Sudoku, which I found appealing because it's somewhat more logical in nature than those other ones. I want to dig into some advanced techniques, because solving a Sudoku should (almost) never involve guessing. However, it's worth going over the basics of Sudoku.

All people can learn Sudoku. Sudoku has several difficulty levels, and the puzzle is classified roughly by how advanced the solution technique is. Gentle/easy is the lowest difficulty. These can be finished with only basic (direct) techniques. Moderate and Tough generally speaking require indirect techniques. Expert/Diabolical require the most advanced techniques. Today I only want to talk about basic technique.

Consider the following puzzle:


The Sudoku board is a 9 x 9 square board with squares of 3 x 3 grouped by dark lines (in the puzzle above, the darker colors of green also denote a separate box). There is only one rule: each line, column, and 3 x 3 box must contain every number between 1 and 9. Because each of those groups has nine entries, we can also say that no line, column, or 3 x 3 box will contain more than one of the same digit. This is how we solve the puzzle.

Any solution technique for Sudoku should also come along with it a search pattern. A strategy is not useful unless you know how to look for an instance of where it gets used. So, I'm going to go through the techniques I would use to first attack the puzzle.

Technique 1: Box by box

I start by looking at the upper left 3 x 3 box. I start with number 1, which is not filled in. Can I find out where 1 must be in that box? No. The only 1 that "touches" that box is the 1 in the next box over to the right, but that one only tells me that the 1 in the first box is not in the middle row, which is not enough to go on.

Then I count 2. Already there. 3, already there. Now 4.


The 4s in the next two boxes are in the first row and the second row. Mentally, I draw a line from each of these through the box I'm focusing on. I see that once those boxes that are excluded by those 4s are eliminated, there is only one possibility for where the 4 goes, in the bottom right square of the box.


I'm leaving the solved squares in yellow to remind us that they weren't in the original puzzle. I continue in this way. Can 5 be solved in the first box? No. 6? Yes.


The 6 in the box below it excludes it being in the first column, and the 6 in the upper right box excludes it from being in the center row. Had we not already solved for 4, we would still have two possibilities, but since we have, we know it must be in the upper right square.


Let's adopt a naming scheme. Let's call the upper left box "box 1", then number them going left to right. So, the box to its right is "box 2" and the one under box 1 is "box 4". "box 8" is the middle box of the bottom row of boxes. Then, we'll name each square in the box the same way. Rather than go through each deduction, I'll just summarize the ones I find by continuing with this strategy, then show you the board with all of them filled in.

Box 1, square 1 = 1
Box 1, square 5 = 7
Now in Box 1 there is only one square left open, so square 6 must = 5
Box 3, square 5 = 8
Box 4, square 4 = 2
Box 4, square 1 = 7
Box 4, square 8 = 5
Box 4 square 6 = 8
Now in Box 4, there is only one square left open, so square 9 must = 1
Box 5, square 8 = 3
Box 5, square 2 = 8
Box 5, square 5 = 1
Box 5, square 6 = 7
Therefore Box 5, square 4 = 5
Box 6, square 1 = 5
Box 6, square 2 = 1
Box 6, square 4 = 6
Box 6, square 9 = 7
Therefore Box 6, square 6 = 9
Box 7, square 5 = 1
Box 7, square 3 = 3
Box 7, square 2 = 6
Box 7, square 7 = 8
Therefore Box 7, square 1 = 4
Box 8, square 7 = 4
Box 8, square 8 = 6
Box 8, square 2 = 7
Box 8, square 3 = 5
Therefore Box 8, square 6 = 9
Box 9, square 1 = 2
Box 9, square 4 = 4
Box 9, square 5 = 6
Box 9, square 7 = 7
Therefore Box 9, square 9 = 1

At this point I've done one "pass" through the puzzle with only this technique. The board looks like this:


Wow, just one pass through the puzzle with the box-by-box search filled in most of the puzzle.

At this point, we actually have three columns with only one blank entry, and so we know that entry must be whichever number doesn't appear. Column 6 is missing an 8, column 7 is missing a 1, column 8 is missing a 7. Also, row 2 is missing a 2. Thus, these can be filled in immediately.


The remaining entries can be filled in without any other techniques necessary. That is, we got through the entire puzzle with just one strategy.


The full solution has all digits in every row, column, and box. Once you get good enough, such a puzzle takes about 3 minutes.

More to come.