MathRec Home Sudoku Home Sudoku Archive Sudoku of the Day

Sudoku Methods

My apologies to early visitors. This section is still under construction. All of the methods are discussed, but will get more editing and more examples. It has a good discussion of the most important techniques that apply to the Sudoku of the Day and Cube Sudoku puzzles. Check out the section on Block Interactions and also on Pairs and Multiples.
Thanks,
Steve

There are many different methods that can be used to solve sudoku puzzles and there are many different sources available on the web that describe different methods. If you want a detailed, and somewhat mathematical discussion of methods, then you'll find what you're looking for here. If you're looking for a discussion of special sudoku techniques that apply to cube sudoku, jigsaw sudoku, Sudoku X, and other configurations, then you're in the right place. On the other hand, if you're a true novice, then you might start with sudokupuzz.com. For a more advanced treatment of common techniques, I'd suggest SadMan Software. (I also like their sudoku software.)

This discussion is intended to be comprehensive. It is not really a how-to manual—instead, I'm trying to explain how different techniques work. Methods are discussed in a way that is as general as possible, with special focus on how the methods apply to non-standard sudoku. I've noticed some overall deficiencies in other sites. While I'm trying to be comprehensive, I'd also like to address some of these deficiencies. Specifically, I'm trying to bring some clarity in the following areas:

These are the solution techniques that I discuss:

Elimination Methods

These methods are a direct consequence of the sudoku rules. In standard sudoku and almost all variants, there is exactly one of each value in each row, column and box. Knowing this allows you to make the following types of deductions.

The "pin" and "force" terminology isn't used much anymore, but it won't die. In any case, old content is still available on the web. The more common terminology of "hidden" and "naked" singles is prevalent. It arises from the most common form of markup, where all of the candidate values for each cell are written in that cell (usually as small numerals in the upper left corner). With this type of markup, a "naked single" appears as a single digit in a cell; a "hidden single" is harder to spot. I generally refer to these methods as elimination by row, column, box or cell.

These methods work the same way for jigsaw and cube sudoku.

Block Interactions

A sudoku puzzle is mostly solved by working back and forth between the four different types of elimination (row, column, box and cell). Determining a value for a particular cell affects the possibilities for other cells in the same row, column or box. Sometimes, however, you learn that a value is restricted to only two or three cells in a row, column or box, and that can be enough information to help solve the puzzle. In traditional sudoku, there are two types of block interaction:

These methods do not necessarily work the same way for jigsaw sudoku or for cube sudoku. Further Discussion

Markup Styles

When solving a difficult puzzle, it is necessary to make some kind of notation other than just filling in the blank cells in the grid. While elimination and block interactions can usually be used without marking up the puzzle, even pairs are hard to spot, just by looking at the clues and known values. The process of noting partial results in the puzzle grid is called markup. There are different ways to mark up the puzzle, but the most common is to list the possible values for each cell across the top of that cell. As each candidate is eliminated, it is crossed out. When only a single candidate is left at the top of the cell, then the cell must take that value (a naked single). It is also possible to scan each row, column and box to look for values that only appear in one cell (hidden singles). See this discussion on standard markup

You don't want to mark up too early, because you'll get a lot of crossed out numbers in your grid, and it will be hard to use the markup to find new deductions. I usually wait until I get stuck before doing the complete markup. On the other hand, I have a second type of markup that I often enter in the bottom of the cells. Whenever I find only two possible locations for a value in a box (but not in a row or column), then I write that value in the bottom of the two candidate cells. This has two advantages: 1) when I've made some progress in a box, then I don't have to repeat it later as I start working Nishio on the values; 2) I discover a lot of pairs—especially hidden pairs. In addition, it doesn't clutter the top of the cell in difficult puzzles, because I may still need to do a complete markup where I list all candidate values in every cell. See this discussion on marking strong links.

Pairs and Multiples (AKA Subsets)

Pairs come in two forms. These are often refered to as naked pairs and hidden pairs, where the meaning is the same as above for singles. If there are two cells in a row, column or box that can only take the same two values, then you know those two cells have those two values, even though you don't know which is which; therefore, those two values cannot be anywhere else in the same row, column or box. Similarly, if there are two values that can only be placed in the same two cells of a row, column or box, then those cells will have those two values; therefore, those cells cannot take any other values. Check here for examples of naked and hidden pairs.

Multiples work the same way as pairs. If there is a group of three cells in the same row, column or box, and those cells can only take three values, then those three values cannot occur elsewhere in the same row, column or box. Note that you may have eliminated some of the three values from some of the three cells, and you can still make the deduction. For example, if the candidate values for the three cells are 123, 123 and 123, then you know that those three cells contain the values 1, 2 and 3 in some order. But you also know this if the candidate values are 12, 23 and 123 (or 12, 23 and 13). That described naked triples, but you can also have hidden multiples. If there is a group of three values that can only appear in the same three cells in the same row, box or column, then no other values can appear in those cells.

You can have multiples up to octuples, although you probably wouldn't think of it that way. That's because you have a hidden multple every time you have a naked multiple—they are two sides of the same coin. Take, for example six cells with the following candidate values: 57, 13, 129, 357, 357, 129. There is a (naked) 357 triple (57, 357 and 357), but that means that the other three cells must form a hidden triple, because the other three values (1, 2 and 9) only appear in the other three cells. So, although you will sometimes have a hidden octuple, it probably makes more sense to think of it as a naked single. Check here for a discussion of multiples.

Finally, in sudoku variants, it is possible to have a group of cells that all neighbor each other pairwise, but are not in any one group. Check here for more about multiples in sudoku variants.

The Law of Leftovers

This method applies to jigsaw sudoku, but not to Cube Sudoku or the Sudoku of the Day puzzles. Essentially, you may have n rows or columns that cover almost the same region as n boxes. In that case, the cells left over from the group of rows or columns must hold the same values as the cells left over from the group of boxes. See this example of the Law of Leftovers for more information. This method is very important to solving jigsaw sudoku. My generator really did not work very well until I added it to the algorithm.

Nishio, Color Chains and Coloring

The Nishio technique is very general. For a particular value, look at all of the cells where that value might still be placed. For each cell, make sure that you can place the value in that cell and still place the value in the rest of the boxes (and rows and columns). Nishio only deals with one value at a time (although you sometimes notice additional constraints while you're doing Nishio).

Color chains are a subset of the general Nishio technique. Often you learn that a value will have to be placed in one of two cells in a particular block (row, column or box). This forms a strong link. You know if one cell holds the value, then the other cell does not (because they are in the same group), but you also know that if one cell does not hold the value then the other cell does. A weak link is formed between any two cells in the same group that can hold the value that you're considering. Alternating strong links and weak links force an implication along the chain. If it's not here, then it must be here, but then it can't be here, so it must be here… You can make an elmination in a cell if it neighbors a strong link on both ends of the chain. A Turbot Fish is the shortest color chain, composed of two strong links that neighbor each other at one end. (Actually, you could think of a block interaction as a one-link color chain, but no one uses the terminology that way.) An X-Wing is a special case of a Turbot Fish where the strong links are in rows and the weak links (and eliminations) are in columns, or vice versa—switching rows and columns.

General coloring is somewhere in between color chains and Nishio. When you're looking at how a value might be placed throughout the puzzle, you'll often find that there are groups of cells that go together—if you place the value in any of the cells in the group, then you'll place the value in every cell in the group. When the technique works, you always have two such groups, where you know that the value will be placed in one group or the other. The term coloring refers to coloring all of the cells in each group the same color. Then any cell that neighbors both groups cannot hold that value, because it would mean that you couldn't place the value in either group.

Any deduction that can be made with color chains can be made with general coloring. The cells on the left side of the strong links (if you were to write the chain in order) get one color, and the cells on the right side of the strong links get the other color. Any deduction that can be made with general coloring can be made with Nishio.

X-Wings, Swordfish and Jellyfish

An X-Wing is usually considered a more basic technique than Nishio or Coloring. It is a special case of both. When you try to place a value in a row, sometimes it can only be placed in two columns in that row. If you have another row, and the same value can only be placed in the same two columns, then you know that the value in those two rows will be in those two columns, even though you don't know which row will place the value in which column. As a result, you know that the value cannot occur elsewhere in those two columns. The same situation applies if you switch the roles of rows and columns.

This is exactly like naked pairs. In a naked pair, you know that the first cell will hold one of two values, and you know that the second cell will hold one of the same two values, so you know that each value will be used once. In an x-wing, you know that the first row will place the value in one of two columns, and you know that the second row will place the value in one of the same two values, so you know that each column will be used once.

Just as naked pairs generalize to naked triplets and naked quadruplets, x-wings generates to swordfish (three rows and three columns) and jellyfish (four rows and four columns). We don't talk about naked quintuplets, because it automatically means that you have a hidden pair, triple or quadruple. In the same way, we don't bother to name any generalization beyond four rows restricted to the same four columns—because a generalization to more than four rows means that you have an x-wing, swordfish or jellyfish on the columns.

Any example of swordfish or jellyfish is a special case of Nishio, but not all examples of swordfish or jellyfish are special cases of coloring.

XY-Wings, XY-Chains and Forcing Chains

An XY-Wing is formed when we have three cells that neighbor each other in a chain like (12)(23)(31), where (12) indicates a cell that must hold either a one or a two, and cells that are adjacent in the list are neighbors in the puzzle. In this case, any cell that borders both the first cell and the last cell cannot hold the value one. If a cell neighboring the (12) holds the value one, then all of the cells in the chain are forced to hold the right-hand value. Because the chain ends with the same value, any cell that borders the beginning and the end of the chain cannot hold that value. An XY-Wing is just the shortest XY-Chain. (Although you can think of a naked pair as a one-link XY-Chain: (12)(21), no one uses the terminology that way.)

The concept of Forcing Chains is very similar, but it is exactly the same situation as an XY-Chain. Consider the XY-Chain (12)(23)(31)(24)(44)(51). Any cell bodering the (12) and the (51) cannot hold the value one. The idea is that you do a limited fork on one of the cells in the chain, such as the (24). If that cell has the value two, then you'll force the left side of the XY-Chain and the head of the chain will take the value one. If the (24) cell has the value four, then you'll force the right side of the XY-Chain and the tail of the chain will take the value one. If a cell borders both the head and the tail, then it cannot hold the value one, because either choice for the (24) causes the same elimination.

XY-Chains and Forcing Chains are exactly the same. If you have one, then you have the other. It seems silly to have two names for the same method, but the concept of forcing chains generalizes nicely when you are considering trial and error methods. In fact, the generalization of forcing chains goes a long way toward showing why trial and error is a poor name for the open-ended trial and elimination methods.

Mixed Chains

This technique combines Color Chains with XY-Chains. It is similar to a technique called multi-coloring, but it is more general. In the section above, we wrote an XY-Chain as (xy)(yz)(zu)(ux), causing an elimination of x from any cell neighboring both ends of the chain. We didn't write any notation for Color Chains, but I'll introduce that now. If two cells with candidates (xy) and (xz) form a strong link on x, then we can write that link as (xy)-(zx). The reason for writing it this way is that it now behaves just like a doublet in an XY-Chain. Any cell with value x that borders the left side of the link will force the cell on the right side of the link to take the value x. So we can drop one of these right into an XY-Chain and let the XY-Chain have a strong link in the middle: (xy)(yz)(zuv)-(wz)(zx) causes an elimination of x from any cell neighboring both ends of the chain. Notice that there can be cells with more than two candidate values when a strong link is involved.

The notation rules are as follows:

Sometimes I write chains including the cell location. In that case, I only write the value between the cell locations for a weak link, and I just write a hyphen for a strong link. For example: (8,3)1(9,1)6(1,1)-(1,5)6(2,5)9(2,3)1(8,3) –> (8,3)≠1. Without the explicit cell locations, I would write: (16)(62)-(236)(69)(91) –> (8,3)≠1. You can read this full notation as If (8,3) is one, then (9,1) is six, then (1,1) is not six, then (1,5) is six, then (2,5) is nine, then (2,3) is one, so (8,3) is not one. Note that you can read a chain backward, too. If (8,3) is one, then (2,3) is nine, then…(9,1) is one, so (8,3) is not one.

Unique Rectangles

If you know that the puzzle you are solving has a unique solution, then you can sometimes use this to eliminate some candidates. This occurs most often in a rectangle, although I have occasionally recognized it in other shapes. Suppose the candidates for the four corners of a rectangle are (12)(12)(12)(14), and (this is important) opposite sides of the rectangle are each within a box. (And none of the four cells are in an extra constraint region, such as the X in Sudoku-X.) Then you know that the fourth corner must hold a four. Why? Because if it held a one, then the corners of the rectangle would be (2)(1)(2)(1), and the any puzzle that was solved by that configuration would also be solved by the configuration (1)(2)(1)(2), because each row, column and box would still hold the values one and two. It is essential that you have two corners of the rectangle in each box—if the four corners are in four different boxes (or three different boxes for jigsaw sudoku), then the technique fails.

Any configuration that could be changed to leave the same values in each row, column and box would mean that the puzzle did not have a unique solution. Other arrangements are possible. For example, Suppose you have (12)(12)(1245)(1267), and you have a strong link on ones between (1245) and (1267), meaning that one of those cells must hold a one. Then you can eliminate two as a candidate from both of those cells.

You cannot use uniqueness in the following situations:

XYZ-Wings and Pseudo-Multiples

An XYZ-Wing is very much like a triple. If you have a configuration like (xz)(xyz)(yz), where being adjacent in the list means that the cells are neighbors, then you can eliminate z from any cell that borders all three of these cells. Even though the (xz) and (yz) cells do not border each other, this acts sort of like a triple. If you eliminate z from either (xz) or (yz), the three original cells must hold x, y and z in some combination. So any cell that borders all three cannot hold a z.

In Cube Sudoku, the Sudoku of the Day puzzles, and other configurations such as Jigsaw Sudoku or Sudoku-X, you can have other situations that act like triples or quadruples. A pure pseudo-triple occurs if three cells neighbor each other pairwise, and those three cells are restricted to the same three values, but the three cells are not all in the same block. When that occurs, then each of the three cells must hold a different value. Any cell that borders all three cannot hold any of the three values. In addition, when cells form a pseudo-multiple not all cells have to hold all of the values. Consider three cells with candidate values (123), (123) and (12). Each cell neighbors the other two, but there is no block that contains all three cells. However, we know that one of the first two cells holds the value three. So if a cell neighbors both of those cells, then it cannot hold a three.

It is possible to have a pseudo-multiple in a group of cells even if some cells do not neighbor each other, as long as those cells do not have any candidate values in common. For example, if A, B, C and D are cells with candidate values (12), (123), (1234) and (34) respectively, and all cells neighbor each other except that A does not neighbor D. In this case, the four cells still form a pseudo-multiple. You have a pseudo-multiple any time that n cells are restricted to the same n values, and no two cells can have the same value. In this case, A and D cannot have the same value because they do not have any candidate values in common. No other pair of cells can have the same value because they neighbor each other.

Finally, it is possible to have n cells restricted to n values, where no two cells can have the same value unless that value is z. That is, there are cells that have candidate value z but do not neighbor each other. For lack of a better term, we can call this a pseudo-pseudo-multiple. If a cell borders every cell of the pseudo-pseudo-multiple that has a candidate value z, then that cell cannot take the value z. An XYZ-Wing (or an XY-Wing) is the simplest case. This can happen more easily in Cube Sudoku, the Sudoku of the Day puzzles, Jigsaw Sudoku and Sudoku-X. I believe pseudo-pseudo-multiples beyond XYZ-Wings can also happen in classic sudoku, but I've never spotted it.

Trial and Error, Forking and Tabling

Sometimes you just have to say what if… and see what you can find out. In the simplest case, you are looking for a contradiction. This is properly called trial and error. Even cruder is trial and success—just take a promising path and rejoice when that guess lets you fill the board successfully. The methods that I want to talk about here are better termed Trial and Elimination.

Trial and Elimination starts with a fork. Now, a fork can just be an attempt to find either a contradiction or a completed puzzle. That's a little crude, and we can be much more subtle. Trial and Elimination explores two mutually exclusive paths, just like Forcing Chains. Any conclusion that you reach on both paths is known for the puzzle generally. In Trial and Elimination, you are not trying to find a contradiction or solve the puzzle (although that may happen). Instead, you are trying to find new deductions.

Here are some of the situations that you may encounter as you explore two paths:

In a hard puzzle, you can start by poking around without writing anything down. You may do this literally if you put fingers on different cells to keep track of your deductions. Pick any doublet (a cell with only two candidate values) or any strong link (a value that has only two locations in a block), then look at some of the deductions that you can make down each path. You may find some of the situations in the list above.

Not all forking points are equally promising. The best forking points have a significant number of deductions down each path. These are some things that tend to cause a lot of deductions:

At some point you may find that you just can't find enough deductions by following the paths inside your head. Then you need to follow the forks. At this point, you are basically using the tabling method, where you track complementary forks and find inferences from the two forks, like those listed above. The exhaustive form of tabling can only be done by a computer, but you can easily track two forks by hand. Here are three suggestions:

Personally, I usually start by listing deductions in the margin. If the grid is big enough, my next choice is to mark the deductions on the left and right. If the grid is smaller or if I already tried one fork and need to try another, then I circle the candidate values for one path and uses squares for the other. Printing out another copy of the puzzle is a last resort.

Finally, it may happen that you try more than one fork and find some overlap between forks. Specifically, you may find that one branch of a fork implies a branch of a different fork. Let one fork start with choices A and notA. The other fork starts with choices B and notB. The notation A–>B means A implies B. You may be able to combine the forks in the following circumstances:

Be careful not to assume anything when you find that A–>B and notB–>notA. Those are already equivalent statements and you cannot combine your forking points, although any deductions for B also apply for A, and any deductions for notA also apply for notB.

The Sudoku of the Day puzzles that are graded Hard to Very Hard often require some amount of forking, or a series of unusual techniques.


Please send responses to my email address is mathrec at this domain

Thanks,
Steve