Dan Rice's Sudoku Blog

Anatomy of a Solution (part 1) - The Eyeball

Up to now I've focused on solution rules in isolation, always assuming that a complete set of "pencil marks" (candidate numbers for a cell) are available.  For a computer, this is no problem.  But when solving a puzzle with pencil and paper, it's useful to have some strategies that can allow you to make progress without requiring all those marks.

Today I'd like to talk about what I like to call "eyeballing" (that is, solving just by looking at things) - filling in numbers based on elimination along rows and columns.  Every 3x3 box has 4 other boxes that influence it.  For example, the top middle box is influenced by the two top corner boxes to its left and right, and the two boxes below it:

A value in any of those 4 "influencing" boxes will let use eliminate that value from the portion of the box that occupies the same row or column.  In the best case, we might have four clues that, taken together, only leave one possible cell that can hold the value.  In the diagram below, 4 X's together tell us the only possible location of the X in box 2.

What's really going on here?  This is just the rule of uniqueness looked at in a slightly different way. We can fill in the X in box 2 because there is only one possible cell that can hold it.

Of course, there are rarely going to be 4 values so strategically placed.  Fortunately, if some cells are already occupied by clues and previously filled-in values, we can learn something from only 1 or 2 values in "influencing" boxes:

Since two boxes are already occupied by clues ("A" and "B"), the two X's in the corner boxes give us  enough information to place the middle X. In general, we want to look for common values in the 4 related boxes, so that there is a chance that we can cross out all but one cell of the box we're interested in. We want to pay extra attention to "crowded" areas of the box where just a few values might be enough to let us cross out all but one cell.

Let's solve Thursday's  puzzle step by step, starting with eyeballing some values.  Here are the clues:

We see a lot of 2's in the boxes that influence box 1.  Let's see what happens when we cross out all of the rows and columns that contain 2's.  Only one space is left in box 1, so the 2 must go there:

We can do the same for 7's surrounding box 2:

Now we use the 8's in the boxes below box 3 to locate the 8 in that box:

This type of "eyeballed" value is particularly easy to find - both values lie in the same column of boxes so we don't have to look in two directions.

We can use the new values we've just filled in to help us eyeball additional values.  Since we filled in a 7 in box 2 a few moments ago, now we have enough information to eyeball the 7 in box 3.

This 7, in turn, lets us eyeball the 7 in box 9:

See if you can eyeball any more values.  Two possibilities are shown below.

Note that the two 9's in the left columns would have given us enough information by themselves to place the 9 in box 1.  Because column 3 of box 1 already has two values filled in, we don't need to look in the boxes to the right for help.

There are at least three more values in this grid that can be eyeballed.  Probably there are a few more that I haven't managed to spot.

Next time I'll show how eyeballing can give us information even when we can't fill in a number right away.

A Table of Contents

Here's a list of all the posts so far on Sudoku solution tips.  Each one builds on the ideas of the previous entries.

1. Introduction to Sudoku
2. Process of Elimination
3. The Unbearable Uniquness of Sudoku 
4. Unique x 20
5. Going Pair-Shaped
6. Triple Play
7. Interlocking Triples
8. Looking Inward
9. Where do Sudoku Boards Come From?
10. Two and Three in a Bed
11. X-Wings
12. The Password is... Swordfish!

  There are also some blank Sudoku grids for your printing pleasure.

Some blank sudoku grids

It seems a lot of people come here to find blank Sudoku grids.

Here's a PDF file with 4 completely blank grids:

Download SudokuBlank.pdf

Here's a PDF file with 4 blank grids filled with numbers from 1 to 9 that can be crossed out when solving:

Download SudokuBlank1.pdf

Enjoy!

The password is... Swordfish!

Finally the time has come to explain the Sudoku Swordfish rule!  I've noticed this is one of the most popular search terms leading to this blog, so I'm happy to be able to help out.

Consider this board:

Following elimination, we reach the position below.  I've highlighted some areas in red.  In row 5, there are two places where we can place a 9, in columns 4 and 6.  In row 7, 9 can appear in columns 4 and 9 only, and in row 9 it can appear in columns 6 and 9 only.

The curved red lines show how the cells involved in the swordfish form a kind of loop.  Placing a value in one of the cells implies its positions in the rest of the loop. Suppose the 9 in row 5 appears in column 4, that is, in cell (4, 5).  Then cell (6, 5) can't contain a 9, so cell (6, 9) must (because it's the only other place in column 6 than can).  That implies that (9, 9) can't contain a 9, so (9, 7) must.  Alternatively, if the 9 in row 5 appears in cell (6, 5), following things around the loop we see that 9's must also appear in cells (9, 9) and (4, 7).  Either way, we've placed a 9 in each of the three columns 4, 6, and 9.  We can eliminate any other possible 9's in those columns, namely the ones highlighted in blue.

Another way to see things is to notice is that there are three 9's to be placed in three rows (5, 7, and 9), and exactly three columns (4, 6, and 9) intersecting those rows where they can be placed.  Each column must receive a 9 in one of the three rows.

The swordfish can also appear in a vertical orientation.  In this case, we notice three columns that each can take a given number only in two places.  Between the three columns, the places that can hold that number fall into exactly three rows.  The board below provides an example:

I've highlighted the vertical swordfish (on the number 3) in the grid following eliminations:

The 3's can be removed from rows 4, 6, and 7 (outside of columns 1, 4, and 9 that make up the swordfish).

A swordfish could also involve three rows (or columns) that each have the same three possible places for a number.  Say the value is placed in the upper-leftmost cell of the pattern; then the lower-left cell (which lies in the same column) can no longer hold the value.  The remaining cells form an X-Wing pattern.  The same X-Wing appears if the value belongs in the lower-leftmost cell.  I'll try to come up with an example of this type of swordfish in the near future.

So, to summarize, the pattern consists of three rows, and a total of three columns within those rows where a given value can be placed.  The value can be removed from the remainder of those columns.  The same rule applies if the words "row" and "column" are switched.

I hope this helps to clarify the Swordfish rule!

Technorati Tags:Su Doku Sudoku

X-Wings

Last time I discussed a pattern involving an interaction between a box and a row or column that passes through that box. If the only places left in the box for a particular value all lie in the same row or column, it's possible to eliminate the value from the part of the row or column that lies outside the box. By localizing a value in one type of group, we manage to localize it in an intersecting group.

Today I'm going to write about a pattern that involves the intersections between rows and columns, specifically where we know something about four cells that share two rows and two columns (i.e., they lie at the corners of a rectangle).

Consider this grid (you may want to try to solve it before reading further):

Without using any new rules, we can get to this situation:

In column 2, the number 3 can only appear in the cell (2, 2) or (2, 5). Similarly, in column 5, 3 can only appear in (5, 2) or (5, 5). I‘ve circled the possible cells in red, and highlighted the columns in red as well.

Suppose cell (2, 2) has the value 3. Then (5, 2) can't take a 3 because it is in the same row as (2, 2); thus (5, 5) is the only place left in column 5 that can take a 3. Conversely, if (2, 5) has the 3 for column 2 then (5, 2) must have the 3 for column 5. So either (2, 2) and (5, 5) contain 3's, or else (2, 5) and (5, 2) contain 3's. In short, there must be 3's at two opposite corners of the "X" formed by (2, 2), (2, 5), (5, 2), and (5, 5). This is the "X-Wings" (or "X-Wing") pattern, named for the way the values appear at the corners of an "X" shape. By coincidence, I'm writing this entry from the Electronic Theater at Siggraph 2005 , where a replica of a Star Wars T-65 X-Wing Starfighter  is sitting in the lobby a couple of hundred feet away.

Now that we know that there are 3's at two opposite corners, we have accounted for the 3's in row 2 and row 3. We can remove all the other 3's in row 2 and row 5. I've highlighted the pencil marks that we can now erase in blue.

Note that we started out knowing that a number can be located at two places within each of two columns, and we ended up determining that it can occur in only two places in each of two rows. Again, localizing within one group or set of groups (the columns) enables us to localize in a related group or group (the rows). The key is that the cells involved form the corners of a rectangle.

Another example occurs later in the solution of the same grid (I won't draw circles around the corners anymore in order to simplify the diagrams a bit):

The corners of the red rectangle show the only places for a 5 in columns 2 and 3. The blue squares show where we can remove 5's in row 2. There's yet another X-Wing hidden in the grid:

Columns 5 and 7 have only two places for the number 9, which are in rows 2 and 3 for each column. We can remove 9's from the rest of those rows.

We can also start by locating a value in two cells of a each of two rows, and use this information to eliminate values up and down the columns. I call this type "horizontal X-Wings," as opposed to the "vertical X-Wings" discussed above.

This board contains a couple of examples of horizontal X-Wings:

Take a look at this stage in the solution:

The only places for the number 8 in row 1 and row 2 are in columns 2 and 4, so we remove the other remaining 8 in column 4.

The same grid also contains this pattern:

Note that we remove 6's from all of column 3, apart from rows 2 and 4 that make up the X-Wing pattern. So the 6 at (3, 3) is removed, along with the 6 at (3, 9). Don‘t be fooled by the "box" shape — only two rows and two columns are involved in the X-Wing pattern itself.

Next time I'll show how to extend the same reasoning to a more difficult (but rarer) pattern known as the Swordfish.

Two and Three in a Bed

So far, I've discussed rules that take place within a single group — a row, column, or box. All of these rules can be summarized as follows:

• If N cells together contain exactly N values, remove those values from the other cells of the group
• If N values can only appear in exactly N calls, remove the other values from those cells

When N is 1, the first rule is the rule of elimination; when N is 2, it's the rule of pairs, when N is three it's the rule of (interlocking) triples, etc.

When N is 1, the second rule is the rule of uniqueness. I don‘t have a good name for the second rule when N is larger than 1. Any suggestions? (Someone suggested biniques.)

Now we are ready to look at rules that look outside a single group, and deal with the interactions between groups. In particular, today's rule deals with the interaction between a box and the rows and columns that intersect it.

Consider the lower-right box (box 9) in the grid below. I've outlined the right part of the box in red. Notice that the only places that can contain a 2 are along the right side of the box. While we don‘t know which cell of the box actually contains the 2, we can be certain that it will be one of the cells in column 9. So, we can remove 2's from the rest of column 9 (the blue rectangle).

Similarly, the only places in cell 3 that can hold a 7 are in column 7 (inside the green oval). So, we can remove the rest of the 7's in that column (inside the orange rectangle).

Some Sudoku enthusiasts refer to this technique as “2 in a bed“ and “3 in a bed“ (for the case where there are three possible cells for a value within a box, all in the same row or column).

The rule can be reversed: if there are only two or three places in a row (or column) that can contain a value, and those places all live inside the same box, the value may be removed from the rest of the box.

Here‘s an example of a “reverse bed”:

In row 5 (highlighted in red), there are two cells (circled) that can hold a 3, and both happen to be in box 6. This allows us to remove the 3 from the rest of box 6 — cells (7,6) and (9,6), circled in blue.

Here are some puzzles that use “beds“ and “reverse beds”:

Where do Sudoku boards come from?

How do we generate random Sudoku boards?  There are several possible approaches.  A simple one is outlined below in pseudo-code:

Board create() {
  construct an empty board
  addToBoard(board, 0);
  return board;
}

void addToBoard(Board board, int cell) {
  if (level == 81) return;

  for each digit in permute(1,2,...,9) {
    place digit in cell
    if no constraint is violated
      if (addToBoard(board, cell + 1) return true;

  place 0 in cell
  return false;
}

What's happening here? First off, we've organized the board into an array of 81 cells; each cell contains a number from 1 to 9, or 0 to indicate a blank cell. We start placing numbers in the first cell and gradually make our way through the board. For each cell, we try each number in some random order, and try to fill in the rest of the board recursively for each choice. If we make an impossible choice, eventually we will be backed into a corner where no choice is possible for a particular cell. When that happens, addToBoard will empty the cell and return false.  Another value will be tried for the previous cell.  If we ever reach 81 levels of recursion, we‘re done.

The clause "no constraint is violated" is easy to implement. I generate a series of tables, one for each cell, that provide the indices of all cells that are in the same row, column, or box as the cell. There are 8 other cells in the same row, 8 in the same column, and 4 cells that are in the same box but not in the same row or columns, for a total of 20 cells related to a given cell.

Because we fill the cells in a particular order every time, there might be some bias. Some boards may be generated more frequently than others. One way to make things more random would be to generate a random permutation table, and to fill in the cells in the order given by the table.

Once we have a random grid, we need to decide on a set of clues. Here we need a way of solving a board from a set of clues. Actually, the routine that generates the boards is almost a solver in itself. If it is modified to skip over cells that already have been assigned a value, it will find a solution for any board where a solution is possible. This is the backtracking solution, aka the "total guess." A more interesting approach is to mimic human solution techniques, in order to only accept boards that have logical solutions. My solver implements the techniques that I have discussed previously, as well as some others that I will be writing about soon.

Given a solver, a set of clues is easy to generate. Create an empty board, and copy as many values from the solved board as you like. If you want a symmetrical board, copy cells in symmetrical pairs. If you want a board that spells out someone‘s initials, that‘s also possible. Now run the solver on the clue board. If it comes up with a solution, great. If not, you can either reveal more squares, reveal a different set of squares, or start again from square one by generating a new board.

Once you have a clued board, you‘ll want to be sure it has a unique solution. If your solver is based on logic, this will be guaranteed automatically. Every move that the solver makes is forced, so whatever solution it arrives it must be the only one possible. If you are using a backtracking solver, it can be modified to continue generating solutions after finding the first one. Keep a counter of how many solutions have been found; when the counter reaches 2, quit the solution process.

The folks at Sky TV neglected this step, leading to the world's largest Sudoku blunder !

An additional bit of finesse (which I haven't yet implemented) would be to ensure that all of the clues are necessary. Remove a clue (or a pair of clues if you are enforcing symmetry) and see if the gird still has a unique solution. If not, put the clue or pair of clues back and try removing another. Eventually you must reach a set of clues where no clue can be removed. This may not be the smallest set of clues that work for the board, but it will be minimal in the sense that no clue can be derived from the rest of the clues.

Some Sudoku generators skip the step of generating a board altogether. It's enough to place some random numbers in the board and see if it has a solution. For a backtracking solver, which can solve puzzles very quickly, the time wasted analyzing impossible sets of clues will be minor. For a human-style solver, it seems reasonable to exclude the possibility of self-contradictory clues by first generating a consistent underlying board. But, I haven't experimented with this possibility.

You can start with a full board, and remove values until you no longer have a unique solution, or you can start with an empty board and add values until you do. Which way you go is a matter of taste.

Looking Inward

Just as the rule of triples and the rule of interlocking triples generalize the rule of pairs, it's possible to extend the uniqueness/pigeonhole rule to more than one cell.

For pairs, we noted that if N cells in the same group (row, column, or box) contain exactly N values between them, then those values can be eliminated from the rest of the group. This is possible since we know that all of the N values have to live in exactly those N cells.

Recall that the pigeonhole rule is the observation that if there is exactly one place in a group that can hold a particular value, then it must contain that value. We can eliminate all of the other values that we previously thought were possible for that cell.

Suppose that there are exactly two places in a group that can hold two particular values A and B. Then we can eliminate all other values from those cells; if they had any other values, there would be no place for one or both of the values A and B. This works for any number of values: if N values can only live in N cells within a group, all other values can be removed from those N cells.

So the rules of pairs, triples, etc., allow us to remove impossible values from cells outside a particular set of cells. The rule of uniqueness and its more general version that we're discussing here allow us to remove extraneous values from the cells inside the group.

Time from some examples. Consider this puzzle:

Using elimination and uniqeness, we can get this far:

I've circled the places where there are two values that can only be in two cells in a group. The red circles show the only places in row 7 that can hold 1 and 7. The blue circles show the only places in column 3 that can hold 5 and 7. Finally, the green circles show the only places in box 6 that can hold 5 and 6 (note: the same is not true of column 9).

Now we can remove values besides 1 and 7 from the red circles, values besides 5 and 7 from the blue circles, and values beside 5 and 6 from the green circles. The results are shown below:

Another place to apply the rule has come to light. Circled in red are the only places for 4 and 8 in row 7. Removing the additional values, we get to here:

Completing the solution uses the rules of pairs and interlocking triples.  The solution (no peeking) is:

I hope you are enjoying these notes. Next time I will start to tackle some more advanced rules that require looking outside of a single group of cells — X-Wings, Swordfish, and Two-or-Three in a Bed (silly names, I know). I'll also discuss some rules that blur the lines between logical solutions and solutions that involve guessing.

Interlocking Triples

The Sudoku rule of triples I discussed in the previous entry is actually stricter than it needs to be. Suppose you have a row that looks like this:

There are 3 cells that together contain only 3 values: {2,4}, {4,8}, and {2,8}. Sippose the first cell actually contains a 2. Then the third cell must contain an 8 and the middle cell must contain a 4. Alternatively, if the first cell contains a 4, the second cell must contain an 8 and the third cell must contain a 2. Either way, these three cells are forced to contain the values 2, 4, and 8 in some order. Therefore, none of the other cells in the same group can have any of those values, and they can be eliminated.

Here‘s a puzzle that can take advantage of this rule.

After some elimination and filling in unique values, we arrive at this point:

Notice the values {4,8}, {1,8}, and {1,4} in column (the ones circled in red). We can remove 1‘s, 4‘s, and 8‘s from the rest of the column, and we find out that cell (7,3) must contain a 9.

Later in the same puzzle, we arrive at the grid below. Another interlocking triple is present, (appallingly badly) highlighted.

We can remove the numbers 2, 4, and 7 from the rest of the box:

The rest of the solution proceeds using elimination and uniques:

There's a subtle variation in the rule that can also come in handy. As long as the three cells contain exactly three possible values between them, the rule is valid:

For example, the values {2,4}, {4,8}, and {2,4,8} form an interlocking triple as well. If the first cell contains a 4, the second must contain an 8 and the third must contain a 2. If the first cell contains a 2, the other two cells form a pair on {4,8}. Either way, the cells in the rest of the group can't contain any of the values 2, 4, or 8. Cells {2,4}, {2,4,8}, and {2,4,8} would also form an interlocking triple: if the first cell contains a 2, the other two cells form the pair {4,8}; if it contains a 4, the other two cells form the pair {2,8}.

The rule of pairs and triples actually generalizes to N-tuples: if any N related cells contain exactly N possible values between them, those values can be removed from the rest of the group. The rule of elimination is just the case where N=1. The rule of pairs is the case where N=2. For N=3, as we have seen, there are several ways in which 3 cells can hold 3 values. Ignoring ordering, the ones we‘ve seen so far look like this:

{A}   {B}   {C}   -> nothing to do
{ABC} {ABC} {ABC} -> rule of triples
{AB}  {AC}  {BC}  -> interlocking triples
{AB}  {AC}  {ABC} -> interlocking triples (variation)

The rule can be extended to quadruples, quintuples, etc. But I expect that these cases are rare in practice, and quite difficult to spot.

Here are a few puzzles that can benefit from the interlocking triples pattern. At least that's the case in my solver program. Your experience may differ since the order in which rules are applied affects which rules may come into play. An interesting future project would be to examine all possible solution orders, and find puzzles that absolutely require a particular rule for their solution (given a particular set of allowable rules).

Puzzle 1:

Puzzle 2:

Puzzle 3:

Puzzle 4:

Triple Play

Here's another Sudoku rule that can be useful in solving puzzles. If you followed the discussion about the rule of pairs, you should be ready to grok the rule of triples. Simply put, if three related cells (cells in the same row, column, or box) can only contain a set of three possible values (that is, we've eliminated all other possible values using other rules), then no other cell in the same group can contain any of those values. For now, we'll only consider the case where all three cells can contain exactly the same three values; next time I'll discuss what I call interlocking triples.

Triples don't come up terribly often in practice, at least not just by chance. Of course you can design a puzzle to contain triples. My puzzle generator typically needs to search for several minutes in order to find a puzzle that requires the use of the rule of triples to be solved. Here's such a puzzle:

Using elimination, uniques, and pairs, we can get to this point:

Notice that the triple (1,3,6) appears in three cells in row 8. These values can be removed from cells (3,8), (5,8), and (7,8), leaving the grid:

Now cell (7,8) has only the value 2 left, so we can fill it in and use it to eliminate a bunch more values. Eventually, we arrive at the solution to the puzzle:

Here are a couple of puzzles that can be solved only using the rules I've discussed so far, including the rule of triples.