Unique Rectangles: The Essentials

Advanced methods and approaches for solving Sudoku puzzles

Unique Rectangles: The Essentials

Postby keith » Sun May 28, 2006 2:57 am

This thread is to summarize the basics about Unique Rectangles and the solution methods based on them.

The next message in this thread is a guide to the essentials of Unique Rectangles.

After that, the third message is a summary of other facts: The history of the discovery of UR's, the frequency of their occurrence in actual puzzles, and the people who deserve the credit.

Following that, messages in this thread are intended to provide real examples of how UR's occur and are used in actual puzzles.

It's been a great ride!

Keith
Last edited by keith on Mon Jun 12, 2006 6:58 pm, edited 1 time in total.
keith
2017 Supporter
 
Posts: 209
Joined: 03 April 2006

The Guide

Postby keith » Sun May 28, 2006 2:58 am

Unique Rectangles: The Essentials


1. Introduction

The 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 Rectangle

Suppose 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 Buddies

Each 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 Corners

Suppose 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 Corners

Next, 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 Set

You 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 Chains

If 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. Closure

Above 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#p21804

Other 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)
Last edited by keith on Wed Jun 07, 2006 7:33 pm, edited 11 times in total.
keith
2017 Supporter
 
Posts: 209
Joined: 03 April 2006

Unique Rectangles: The facts and the history

Postby keith » Sun May 28, 2006 3:04 am

This is a placeholder. Not written yet.

But, this will give credit to Lummox JR, MadOverlord and others before them who developed the basics of Unique Rectangles.

Also, I will add statistics where people have measured the frequency and effectiveness of these UR techniques.

Go Pistons!

Keith
keith
2017 Supporter
 
Posts: 209
Joined: 03 April 2006

Re: The Guide

Postby ronk » Sun May 28, 2006 4:04 am

keith wrote:
Code: Select all
+--------------+
|  -   -    -  |
|  1   -    2  |
|  -   -    -  |
+--------------+
|  2   -    1  |
|  -   -    -  |
|  -   -    -  |
+--------------+
(...)
+--------------+
|  -   -    -  |
| 12   -   12  |
|  -   -    -  |
+--------------+
| 12   -   12  |
|  -   -    -  |
|  -   -    -  |
+--------------+
(...)Either of the above is often called the "deadly pattern".

Strictly speaking, from a solver's point of view, only the second is a "deadly pattern." The first is one of two possible solutions from that deadly pattern.

But, as you say, people are also referring to the first as the deadly pattern, which I think is unfortunate.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby daj95376 » Sun May 28, 2006 5:47 pm

I have a long way to go on learning the terminology. However, a TYPE 1 UR sure looks like a special case of Remote Pairs. Am I right or wrong?
daj95376
2014 Supporter
 
Posts: 2624
Joined: 15 May 2006

Postby Mike Barker » Sun May 28, 2006 7:27 pm

In order for remote pairs to work there must be an even number of cells, see http://www.sadmansoftware.com/sudoku/technique15.htm. This has an odd number so, both "1" and "2" in the example are possible except that they result in a "deadly" pattern.
Mike Barker
 
Posts: 458
Joined: 22 January 2006

Postby doduff » Mon May 29, 2006 9:10 pm

I am curious, In the guide above, which I thorughly enjoyed reading, I think there may be some left out info.


Suppose we have an "incomplete X-Wing" on the following grid:

Code: Select all
+-------------+
|  -   -   -  |
| 12   -  123 |
|  -   -   -  |
+-------------+
| 123  -  12  |
|  -   -   -  |
|  -   -   -  |
+-------------+



I am not sure what is meant by an incomplete x-wing, but I think it might be this:

Code: Select all
+-------------+
|  -  2xx 3xx |
| 12   -  123 |
|  -   -   -  |
+-------------+
| 123  -  12  |
|  -  1xx 1xx |
|  -  3xx 2xx |
+-------------+


So the ones in the top box are the only possible ones in that row(and box) and the first column of ones are the only possible ones in that column, but the second row of ones is not conjugate, the may be some other possible ones elsewhere in that row. I have put in other 'possible' possibilities of 1, 2, and 3 for illustration.

What I get as the necessary reduction is:

Code: Select all
+-------------+
|  -  2xx 3xx |
|  1   -  23  |
|  -   -   -  |
+-------------+
| 23   -  12  |
|  -  1xx 1xx |
|  -  3xx 2xx |
+-------------+


I don't see why this would lead to the other 12 having to be a one also. Does that make sense, or am I misunderstanding something about the "incomplete X-wing"?

Peace.Joe
doduff
 
Posts: 32
Joined: 29 May 2006

Re: The Guide

Postby ronk » Mon May 29, 2006 9:45 pm

[edit: Subject edited by keith ... so this post no longer serves a purpose.]
Last edited by ronk on Tue May 30, 2006 5:20 pm, edited 1 time in total.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

My First Example

Postby keith » Mon May 29, 2006 10:07 pm

The following puzzle is the reason I wrote the Unique Rectangles guide. It is the Daily Sudoku puzzle of May 2, 2006.

Code: Select all
Puzzle: DS050206 Very hard
+-------+-------+-------+
| . 7 8 | . . . | . 1 . |
| 5 . . | . 4 . | . . . |
| . . 6 | . 7 2 | . . . |
+-------+-------+-------+
| 8 5 . | . . . | . . . |
| . . 4 | 5 . 7 | 9 . . |
| . . . | . . . | . 6 4 |
+-------+-------+-------+
| . . . | 1 8 . | 2 . . |
| . . . | . 6 . | . . 1 |
| . 1 . | . . . | 3 5 . |
+-------+-------+-------+

Up to that point, the Daily Sudoku had never required more than the basics: Naked and hidden singles, naked and hidden pairs, and line / block interactions. This one "needs" an X-wing or two. But, it also has unique rectangles.

The original discussion is here:
http://www.dailysudoku.co.uk/sudoku/forums/viewtopic.php?t=722

After the basics, you reach this point:
Code: Select all
+-------------+-------------+-------------+
| 249 7   8   | 369 5   39  | 46  1   29  |
| 5   239 239 | 68  4   1   | 68  27  279 |
| 1   49  6   | 89  7   2   | 48  3   5   |
+-------------+-------------+-------------+
| 8   5   239 | 4   239 6   | 1   27  237 |
| 23  6   4   | 5   1   7   | 9   8   23  |
| 7   239 1   | 29  239 8   | 5   6   4   |
+-------------+-------------+-------------+
| 349 349 7   | 1   8   5   | 2   49  6   |
| 249 8   5   | 239 6   39  | 7   49  1   |
| 6   1   29  | 7   29  4   | 3   5   8   |
+-------------+-------------+-------------+

You should be easily able to spot a Unique Rectangle, because there are three of them!


Type 3: <49> in R78C18
The "extra" values in C1 are <23>. They form a reduced set with <23> in R5C1. We can eliminate <2> and <3> in their shared buddies, who are all in C1: R1C1 cannot be <2>.


Type 4: <39> in R18C46

The only candidates for <3> in C4 are the corners of the rectangle. Thus, neither of R18C4 can be <9>.


Type 4: <27> in R24C89

The only candidates for <7> in C9 are the corners of the rectangle. Thus, neither of R24C9 can be <2>.


If you make these reductions, R1C9 is pinned to be <2>, and the puzzle falls apart.

Keith

PS: If you really don't want to be Unique, you might find:

An X-wing on <2> in R15,
An X-wing on <9> in R49,
and lots of other fishy patterns.
Last edited by keith on Tue May 30, 2006 4:25 pm, edited 1 time in total.
keith
2017 Supporter
 
Posts: 209
Joined: 03 April 2006

Re: My First Example

Postby re'born » Tue May 30, 2006 4:32 pm

keith wrote:
If you make these reductions, R1C9 is pinned to be <2>, and the puzzle falls apart.



Of course all of your reductions are correct and make nice examples, but only the first (removing 2 from r1c1) is needed to pin r1c9 to 2.
re'born
 
Posts: 551
Joined: 31 May 2007

Postby daj95376 » Tue May 30, 2006 5:45 pm

keith,

A very nice presentation on Unique Rectangles!

Unfortunately, the puzzle you mentioned as the reason for your presentation ... doesn't need them. It solvable with:

*) Naked/Hidden Singles
*) Naked Triple/Quad
*) Locked Candidates ( 1 & 2 )
*) X-Wing
daj95376
2014 Supporter
 
Posts: 2624
Joined: 15 May 2006

Miscellania / Mea culpa

Postby keith » Tue May 30, 2006 8:50 pm

ronk and doduff are correct. I have changed the parenthetical statement concerning type 6 rectangles. This will all become clearer (to me as well) as we post more examples.

rep'nA and daj95376 are correct. The example puzzle does not "need" Unique Rectangles. But, it is a nice example, since there are three of them.

Personally, I find UR's much easier to spot than X-wings.

Thanks for the feedback!

Keith
keith
2017 Supporter
 
Posts: 209
Joined: 03 April 2006

The Original Type 6 UR

Postby keith » Tue May 30, 2006 10:06 pm

This partially solved puzzle was posted by "Guest" on the Daily Sudoku forum on March 28, 2006:

Code: Select all
+-------------+-------------+-------------+
| 2   5   1   | 7   4   8   | 9   6   3   |
| 3   9   4   | 6   5   2   | 7   18  18  |
| 6   7   8   | 1   3   9   | 4   5   2   |
+-------------+-------------+-------------+
| 5   26  267 | 9   8   3   | 12  4   17  |
| 1   8   3   | 4   2   7   | 5   9   6   |
| 9   4   27  | 5   1   6   | 28  3   78  |
+-------------+-------------+-------------+
| 8   3   69  | 2   679 4   | 16  17  5   |
| 4   26  5   | 8   67  1   | 3   27  9   |
| 7   1   269 | 3   69  5   | 68  28  4   |
+-------------+-------------+-------------+

The thread is here:

http://www.dailysudoku.co.uk/sudoku/forums/viewtopic.php?p=2894#p2894

Unfortunately, Guest never returned, so we do not know the original puzzle.

READ NO FURTHER! How would you solve this? Or, at least, how would you make the next step?

Here is my original explanation:

First, there is an X-wing on <9>. The corners are R7C3, R7C5, R9C3, and R9C5. This does not lead to any eliminations, but note that either R7C3 and R9C5 are <9>, or R7C5 and R9C3 are <9>.

Second, there is a possible non-unique rectangle on <69> lurking in the same squares as the X-wing. So, R7C5 and R9C3 CANNOT be <9>, for then R7C3 and R9C5 must be <6>, and there will be a non-unique rectangle.

So, R7C3 and R9C5 must be <9>.


To complete the solution, there is an XY-wing. Or, you can use another uniqueness pattern, a "BUG+1".

Keith
keith
2017 Supporter
 
Posts: 209
Joined: 03 April 2006

Re: The Original Type 6 UR

Postby ronk » Tue May 30, 2006 11:45 pm

keith wrote:
Code: Select all
+-------------+-------------+-------------+
| 2   5   1   | 7   4   8   | 9   6   3   |
| 3   9   4   | 6   5   2   | 7   18  18  |
| 6   7   8   | 1   3   9   | 4   5   2   |
+-------------+-------------+-------------+
| 5   26  267 | 9   8   3   | 12  4   17  |
| 1   8   3   | 4   2   7   | 5   9   6   |
| 9   4   27  | 5   1   6   | 28  3   78  |
+-------------+-------------+-------------+
| 8   3   69  | 2   679 4   | 16  17  5   |
| 4   26  5   | 8   67  1   | 3   27  9   |
| 7   1   269 | 3   69  5   | 68  28  4   |
+-------------+-------------+-------------+

(...)
READ NO FURTHER! How would you solve this? Or, at least, how would you make the next step?

The "Type 5" UR(69) at r79c35 has extra diagonal candidates and is overlapped with a digit 9 x-wing. For a unique solution, at least one of r7c5=7 or r9c3=2 must be true. Either one being true causes exclusions r7c5<>9 and r9c3<>9.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

The rubber hits the road!

Postby keith » Wed May 31, 2006 2:28 am

Let's try this one.
Code: Select all
Puzzle: DSN051206
+-------+-------+-------+
| 1 . . | . 8 . | 3 . . |
| . 5 . | . . . | 7 . . |
| . . 8 | 9 . 1 | . . . |
+-------+-------+-------+
| . . 4 | 5 . . | . 6 . |
| 8 . . | . . . | . . 5 |
| . 7 . | . . 3 | 9 . . |
+-------+-------+-------+
| . . . | 6 . 2 | 1 . . |
| . . 3 | . . . | . 4 . |
| . . 6 | . 4 . | . . 9 |
+-------+-------+-------+


There is a Type 3 UR with two reductions based on two different sets of shared buddies. The UR is, by far, the simplest way to solve this puzzle.

Keith
keith
2017 Supporter
 
Posts: 209
Joined: 03 April 2006

Next

Return to Advanced solving techniques