Unique Rectangles: The Essentials1. IntroductionThe original techniques to solve classic Sudoku puzzles are based on the fundamental, simple rule: Each row, column and box contains only one occurrence of each of nine symbols.

It is quite possible for a Sudoku to have none or many solutions. But, most people consider a Sudoku puzzle to be "valid" only if it has a single solution. There are techniques that exploit this uniqueness condition.

In the past few months, the classic and the uniqueness techniques have been blended together, to create very interesting solution methods. These methods are based on patterns that are relatively (and sometimes very) easy for humans to recognize.

Consider the following fragment of a solved puzzle:

- Code: Select all
`+--------------+`

| - - - |

| 1 - 2 |

| - - - |

+--------------+

| 2 - 1 |

| - - - |

| - - - |

+--------------+

This is not a unique solution*: You can interchange the 1's and 2's in the above diagram to get a second solution. Each row, column and box still has one 1 and one 2.

(*Unless one of the values in the above diagram is given as an initial clue. Then, the solution is unique.)

Suppose that the candidate diagram leading to the solution is:

- Code: Select all
`+--------------+`

| - - - |

| 12 - 12 |

| - - - |

+--------------+

| 12 - 12 |

| - - - |

| - - - |

+--------------+

This cannot lead to a unique solution: The solution on each diagonal is either 1 or 2, and they can be interchanged.

Either of the above is often called the "deadly pattern". <1> and <2> are the "deadly candidates".

In the previous diagrams, the four cells define a rectangle, which must be, or must lead to, a non-unique solution. In an actual puzzle (where some corners have additional candidates), the goal is to avoid the deadly pattern by ensuring a "Unique Rectangle" (UR) in the solution.

This rectangle pattern obviously occupies only two rows and two columns. It also can occupy only

TWO boxes. If the rectangle occupies four boxes, the corners cannot be interchanged to get another solution. (Try it!)

2. The Simplest Unique RectangleSuppose we have a partially solved puzzle with the following set of candidates:

- Code: Select all
`+--------------+`

| - - - |

| 12 - 123 |

| - - - |

+--------------+

| 12 - 12 |

| - - - |

| - - - |

+--------------+

The top right cell cannot be <1> or <2>, because either would force the deadly pattern. So, it MUST be <3>. After reduction, the result is:

- Code: Select all
`+--------------+`

| - - - |

| 12 - 3 |

| - - - |

+--------------+

| 12 - 12 |

| - - - |

| - - - |

+--------------+

If three of the corner cells have only two candidates, it does not matter how many additional candidates are on the fourth cell. The "deadly" candidates can both be eliminated from the fourth cell.

So, if we have:

- Code: Select all
`+--------------+`

| - - - |

| 12 - 1234 |

| - - - |

+--------------+

| 12 - 12 |

| - - - |

| - - - |

+--------------+

the reduction is:

- Code: Select all
`+--------------+`

| - - - |

| 12 - 34 |

| - - - |

+--------------+

| 12 - 12 |

| - - - |

| - - - |

+--------------+

This is often called a

Type 1 Unique Rectangle. It is very easy for a human to spot.

3. Some Patterns: Shared BuddiesEach cell in a Sudoku puzzle has 20 "buddy" cells. These are the cells which are in the same row, column, or box as the original cell. These are the cells whose values directly affect, or are affected by, the value of the original cell. Two cells together have between 2 and 13 "shared buddies". If you are familiar with this concept, skip this section.

We will usually be concerned with two cells which are corners of the UR. Label them "*". They may be in the same row:

- Code: Select all
`+-------------+-------------+-------------+`

| * # * | # # # | # # # |

| - - - | - - - | - - - |

| - - - | - - - | - - - |

+-------------+-------------+-------------+

They need not be in the same box, but they may be. Their "shared buddies" (in the row) are labeled "#". Again, "buddies" are cells whose values directly influence each other.

The two cells, and their shared buddies, may be in the same column:

- Code: Select all
`+-------------+`

| - # - |

| - * - |

| - # - |

+-------------+

| - # - |

| - # - |

| - * - |

+-------------+

| - # - |

| - # - |

| - # - |

+-------------+

They may be in the same box:

- Code: Select all
`+-------------+-------------+-------------+`

| - - - | * # * | - - - |

| - - - | # # # | - - - |

| - - - | # # # | - - - |

+-------------+-------------+-------------+

Or, they may be on a diagonal:

- Code: Select all
`+-------------+-------------+-------------+`

| - - * | # # # | - - - |

| - - - | - - - | - - - |

| # # # | - * - | - - - |

+-------------+-------------+-------------+

4. One Extra Candidate on Two CornersSuppose we have the following:

- Code: Select all
`+-------------+`

| # - - |

| 12 - 123 |

| # - - |

+-------------+

| 123 - 12 |

| - - # |

| - - # |

+--------------+

One of the top right or bottom left cells must be <3>. Therefore, none of their shared buddies, the cells marked "#", can be <3>.

Above, the extra candidates are on a diagonal. This is a

Type 5 Unique Rectangle.

There are obvious variations when the extra candidates are in the same line (row or column). These variations are

Type 2 UR's.

5. Two or More Extra Candidates on Two CornersNext, suppose there is more than one additional candidate on two of the corners:

- Code: Select all
`+--------------+`

| - - - |

| 12 - 123 |

| - - - |

+--------------+

| 12 - 124 |

| - - - |

| - - - |

+--------------+

| - - - |

| - - - |

| - - - |

+--------------+

The cells on the right have candidates <1>, <2>, <3>, <4>. At least one of them is not <1> or <2>. Reductions cannot be made unless we bring in extra information from other cells.

5.1 A Reduced SetYou should examine the shared buddies of the cells with extra candidates, to see if any contain the extra candidates but not the deadly candidates. We might have the following:

- Code: Select all
`+--------------+`

| - - # |

| 12 - 123 |

| - - # |

+--------------+

| 12 - 124 |

| - - # |

| - - 34 |

+--------------+

| - - # |

| - - # |

| - - # |

+--------------+

In this case, we can eliminate <3> and <4> as candidates in any of the remaining shared buddies, the cells marked "#"!

Here is the explanation of this surprising result:

The cells with candidates <123>, <124>, and <34> are a "reduced set" of three cells containing four candidates. (Normally, we would need to find a full set of four cells to make eliminations in other cells.) However, the only two cells in the subset where the deadly values are candidates are on the corners of the rectangle.

Only one of the deadly candidates can occur in these two corner cells; The one "missing" candidate in the reduced set is one of the deadly values. Therefore, in the set of the "shared buddies", the reduced set contains all the occurrences of the "extra" candidates. Eliminations can be made in the remaining shared buddies.

There are obvious variations when the extra candidates are in the same row and / or the same box. This is usually called a

Type 3 Unique Rectangle. There is also a diagonal variant.

The reduced set may contain candidates which are not on the UR. For example,

- Code: Select all
`+-------------+`

| - - # |

| 12 - 123 |

| - - # |

+-------------+

| 12 - 124 |

| - - # |

| - - 345 |

+-------------+

| - - # |

| - - 45 |

| - - # |

+-------------+

allows elimination of <3>, <4>, and <5> from any of the cells marked "#".

5.2 Conjugate Pairs (Strong Links)If a candidate value occurs only twice in a row, column, or box, the two cells are called a "conjugate pair" and form a "strong link". In the solution, one of the two cells must be that candidate value.

Consider the diagram of Section 5, above. Suppose also that the only occurrences of the candidate <1> in the right hand column are on the corners of the rectangle. Then, one of these corner cells must have the value <1>. To avoid the deadly pattern, one of them must be <3> or <4>. So, neither of them can be <2>, and the reduction is:

- Code: Select all
`+--------------+`

| - - - |

| 12 - 13 |

| - - - |

+--------------+

| 12 - 14 |

| - - - |

| - - - |

+--------------+

This pattern and reduction is called a

Type 4 Unique Rectangle. Although this reduction "destroys" the UR, any reductions that could have been made as Type 2 and Type 3 UR's will still be available.

(Edit: This is true here, but it is very bad advice in general. You should look for all UR's, and for all reductions, before making any reductions.)There is an interesting diagonal variation, sometimes called a

Type 6 UR. It was first noticed as the overlay of an X-wing on a UR. Consider the pattern of Section 4, above, and suppose the rectangle is also an X-wing on <1>. The result must be:

- Code: Select all
`+--------------+`

| - - - |

| 1 - 23 |

| - - - |

+--------------+

| 23 - 1 |

| - - - |

| - - - |

+--------------+

The bottom right cell cannot be 2, because that would force the deadly pattern. (In fact, you do not need the full X-wing to make reductions. This will be explored in the examples.)

5.3 Short Forcing ChainsIf you encounter a possible Unique Rectangle it is worthwhile to consider the candidates of the cells in the set of shared buddies. For example, suppose we have

- Code: Select all
`+--------------+`

| - - - |

| 12 - 123 |

| - - - |

+--------------+

| 12 - 124 |

| - - - |

| - - 13 |

+--------------+

The extra cell contains one of the UR's extra candidates and one of the deadly candidates. It turns out the lower right corner of the UR cannot be <1>!

The easiest way to see this is to note that

- Code: Select all
`+--------------+`

| - - - |

| 12 - 123 |

| - - - |

+--------------+

| 12 - 1 |

| - - - |

| - - 13 |

+--------------+

forces the deadly pattern. This is a chain, in which a certain candidate value in one cell results in a contradiction. So, that candidate can be eliminated.

Another way to look at this: If the <13> cell is <1>, the <124> cell is not <1>. If the <13> cell is <3>, there is a Type 1 UR, and the <124> cell must be <4>. In either case, the <124> cell is not <1>. (This is an excellent technique: Tabulate the possible solutions.)

6. ClosureAbove is a summary of unique rectangles and solution strategies that are, I believe, most useful to human solvers using pencil and paper. There is much more on this subject. Take a look at

http://forum.enjoysudoku.com/viewtopic.php?p=21804#p21804Other messages in this thread will illustrate and expand on these principles with actual examples.

Keith

I'd like to thank those who reviewed earlier drafts. Their comments have, I think, much improved this guide.(Version 3.07: Last edit 053006 5:00 pm EDT)