| View previous topic :: View next topic |
| Author |
Message |
keith
Joined: 19 Sep 2005
Posts: 3355
Location: near Detroit, Michigan, USA
|
 Posted: Sat May 16, 2009 7:06 pm Post subject: Unique Rectangles |
 |
|
(This is a copy of an article I wrote some time ago. I am posting it here just to be sure there is an extra copy.
The original is here: Broken link removed 18 Jul 2010
Keith: 15 May, 2009)
Edit 18 Jul, 2010:
The original was indeed lost, along with the entire Players' Forum. Much of the content has been recovered. In particular see this article at
http://Forum.EnjoySuDoku.com/viewtopic.php?t=4204
which was last edited on 7 Jun, 2006
end edit
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: |
+--------------+
| - - - |
| 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: |
+--------------+
| - - - |
| 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: |
+--------------+
| - - - |
| 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: |
+--------------+
| - - - |
| 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: |
+--------------+
| - - - |
| 12 - 1234 |
| - - - |
+--------------+
| 12 - 12 |
| - - - |
| - - - |
+--------------+
|
the reduction is:
| Code: |
+--------------+
| - - - |
| 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: |
+-------------+-------------+-------------+
| * # * | # # # | # # # |
| - - - | - - - | - - - |
| - - - | - - - | - - - |
+-------------+-------------+-------------+
|
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: |
+-------------+
| - # - |
| - * - |
| - # - |
+-------------+
| - # - |
| - # - |
| - * - |
+-------------+
| - # - |
| - # - |
| - # - |
+-------------+
|
They may be in the same box:
| Code: |
+-------------+-------------+-------------+
| - - - | * # * | - - - |
| - - - | # # # | - - - |
| - - - | # # # | - - - |
+-------------+-------------+-------------+
|
Or, they may be on a diagonal:
| Code: |
+-------------+-------------+-------------+
| - - * | # # # | - - - |
| - - - | - - - | - - - |
| # # # | - * - | - - - |
+-------------+-------------+-------------+
|
4. One Extra Candidate on Two Corners
Suppose we have the following:
| Code: |
+-------------+
| # - - |
| 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: |
+--------------+
| - - - |
| 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: |
+--------------+
| - - # |
| 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: |
+-------------+
| - - # |
| 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: |
+--------------+
| - - - |
| 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: |
+--------------+
| - - - |
| 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: |
+--------------+
| - - - |
| 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: |
+--------------+
| - - - |
| 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://www.sudoku.com/boards/viewtopic.php?p=21804#21804
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 Sun Jul 18, 2010 6:34 pm; edited 1 time in total |
|
| Back to top |
|
 |
daj95376
Joined: 23 Aug 2008
Posts: 3854
|
| Posted: Thu Jun 11, 2009 12:53 am Post subject: |
|
|
According to Sudopedia, the following pattern is a ...
| Code: | ===== ===== ===== ===== Hidden Unique Rectangle
(*) bivalue + 2x strong links in an "L" pattern
+--------------+
| . . . |
| 12x . 1y-2 |< strong link on <1>
| . . . |
+--------------+
|*12 . 12z |
| . . . |
| . . . |
+--------------+
^ strong link on <1>
|
However, I don't see an example in Sudopedia for this pattern. Does it have a name? I call it a ...
| Code: | ===== ===== ===== ===== template for Unique Rectangle Type 1/4
(*) bivalues + 2x strong links in an "L" pattern
+--------------+
| . . . |
| 1x-2 . 12y |
| . . . |
+--------------+
|*12 . *12 |< strong link on <1>
| . . . |
| . . . |
+--------------+
^ strong link on <1>
|
|
|
| Back to top |
|
|
keith
Joined: 19 Sep 2005
Posts: 3355
Location: near Detroit, Michigan, USA
|
| Posted: Thu Jun 11, 2009 2:14 am Post subject: |
|
|
| daj95376 wrote: | According to Sudopedia, the following pattern is a ...
| Code: | ===== ===== ===== ===== Hidden Unique Rectangle
(*) bivalue + 2x strong links in an "L" pattern
+--------------+
| . . . |
| 12x . 1y-2 |< strong link on <1>
| . . . |
+--------------+
|*12 . 12z |
| . . . |
| . . . |
+--------------+
^ strong link on <1>
|
However, I don't see an example in Sudopedia for this pattern. Does it have a name? I call it a ...
| Code: | ===== ===== ===== ===== template for Unique Rectangle Type 1/4
(*) bivalues + 2x strong links in an "L" pattern
+--------------+
| . . . |
| 1x-2 . 12y |
| . . . |
+--------------+
|*12 . *12 |< strong link on <1>
| . . . |
| . . . |
+--------------+
^ strong link on <1>
|
|
Danny,
Let's back up. My original observation, hijacked by the SudoPolice, was that of a UR (possible DP) overlaid on an X-wing. After a few messages, it became clear we were talking about possible DP's supplemented by strong links.
I am not a programmer - I have not laid out all the possibilities. You might ask Mike Barker, one of the few in that forum without an unmanageable ego.
In the case you cite, if there is an X-wing on <1>, the eliminations are clearly correct. I also believe you are correct in the eliminations of the patterns that you give, that are one link short of an X-wing.
(I would ask, like the mythical Type 5 UR, does it really occur?)
I don't have a name for them. other than UR (possible DP) supplemented by strong links. The SudoPolice have variously called them Type 6, Type 7, or Hidden UR's.
Best wishes,
Keith |
|
| Back to top |
|
|
daj95376
Joined: 23 Aug 2008
Posts: 3854
|
| Posted: Fri Sep 25, 2009 6:49 am Post subject: |
|
|
More rambling (by me) on Unique Rectangles.
The basic URs -- Types 1/2/3/4/5/6 -- all require that (at least) two of the four cells be equivalent bivalues. Two of the basic URs -- Types 4/6 -- require that one of the candidates exist in an X-Wing pattern. This makes the basic URs (relatively) easy to identify.
However, there are other URs. Mike Barker created an extensive list. Among those that have become popular is the Hidden UR (see my message above). It, and the other pattern in my message above, relies on a strong link in a row and a strong link in a column.
I recently ran across an example of a UR that I think is very easy to identify and use. Two of the cells form a Naked Pair, and there is a single strong link connecting each of these cells to its alternate companion cell.
| Code: | +-----------------------------------------------------+
| 6 45 14 | 15 7 9 | 3 8 2 |
| 15 8 2 | 145 3 14 | 9 7 6 |
| 3 7 9 | 6 2 8 | 1 5 4 |
|-----------------+-----------------+-----------------|
| 458 45 3 | 2 1 7 | 58 6 9 |< strong link on <8>
| 9 6 7 | 48 48 5 | 2 1 3 |
| 158 2 18 | 3 9 6 | 58 4 7 |< strong link on <5>
|-----------------+-----------------+-----------------|
| 7 9 5 | 18 6 2 | 4 3 18 |
| 2 3 48 | 7 5 14 | 6 9 18 |
| 48 1 6 | 9 48 3 | 7 2 5 |
+-----------------------------------------------------+
^ Naked Pair <58>
|
Now, you can analyze the relationships anyway you'd like, but here's the final upshot:
| Code: | *) The <58> cell in [r4 -- strong link on <8>] must be <8>, and
*) The <58> cell in [r6 -- strong link on <5>] must be <5>.
|
|
|
| Back to top |
|
|
keith
Joined: 19 Sep 2005
Posts: 3355
Location: near Detroit, Michigan, USA
|
| Posted: Sat Sep 26, 2009 1:44 am Post subject: |
|
|
| daj95376 wrote: | More rambling (by me) on Unique Rectangles.
The basic URs -- Types 1/2/3/4/5/6 -- all require that (at least) two of the four cells be equivalent bivalues. Two of the basic URs -- Types 4/6 -- require that one of the candidates exist in an X-Wing pattern. This makes the basic URs (relatively) easy to identify.
However, there are other URs. Mike Barker created an extensive list. Among those that have become popular is the Hidden UR (see my message above). It, and the other pattern in my message above, relies on a strong link in a row and a strong link in a column.
I recently ran across an example of a UR that I think is very easy to identify and use. Two of the cells form a Naked Pair, and there is a single strong link connecting each of these cells to its alternate companion cell.
| Code: | +-----------------------------------------------------+
| 6 45 14 | 15 7 9 | 3 8 2 |
| 15 8 2 | 145 3 14 | 9 7 6 |
| 3 7 9 | 6 2 8 | 1 5 4 |
|-----------------+-----------------+-----------------|
| 458 45 3 | 2 1 7 | 58 6 9 |< strong link on <8>
| 9 6 7 | 48 48 5 | 2 1 3 |
| 158 2 18 | 3 9 6 | 58 4 7 |< strong link on <5>
|-----------------+-----------------+-----------------|
| 7 9 5 | 18 6 2 | 4 3 18 |
| 2 3 48 | 7 5 14 | 6 9 18 |
| 48 1 6 | 9 48 3 | 7 2 5 |
+-----------------------------------------------------+
^ Naked Pair <58>
|
Now, you can analyze the relationships anyway you'd like, but here's the final upshot:
| Code: | *) The <58> cell in [r4 -- strong link on <8>] must be <8>, and
*) The <58> cell in [r6 -- strong link on <5>] must be <5>.
|
|
Danny,
Interesting logic!
Or, the UR makes a <14> pseudocell in B4C1 that makes a 14-8 XY-wing with R9C1 and R6C3, eliminating <8> in R8C3.
Keith. |
|
| Back to top |
|
|
Myth Jellies
Joined: 27 Jun 2006
Posts: 64
|
| Posted: Wed Sep 30, 2009 3:20 am Post subject: |
|
|
You've show what is essentially the "naked" patterns associated with URs. There is a whole complementary half of "hidden" patterns based on the question, "Where must the deadly pattern digits go if they are not in the deadly pattern?"
You can even have mixed cases, as in this recent offering
| Code: | *-----------------------------------------------------------*
| 7 246 1234 | 1346 36 9 | 236 8 5 |
| 139 269 123 | 136 8 5 | 236 4 7 |
| 34 5 8 | 7 236 24 | 1 9 36 |
|-------------------+-------------------+-------------------|
| 14 7 14 | 8 9 3 | 5 6 2 |
| 2 8 6 | 5 4 7 | 9 3 1 |
| 5 3 9 | 2 1 6 | 4 7 8 |
|-------------------+-------------------+-------------------|
| 349 49 7 | 346 5 1 | 8 2 346 |
| 6 1 234 | 9 *37+2 8 |*37 5 34 |
| 8 24 5 |#36 *37+6 24 |*37+6 1 9 |
*-----------------------------------------------------------*
|
If you consider the "naked" case in row 8, the only non-deadly digit option is a 2 in r8c5.
If you consider the "hidden" case in row 9, the only escape option for 37 in that row is a 3 in r9c4
So you can immediately determine that r8c5 cannot be a 3
(And if you also note that the sevens are locked in r89c5 so the first option can be rewritten as 2&7 in r89c5 you can eliminate the 3 in r9c5 as well.) |
|
| Back to top |
|
|
daj95376
Joined: 23 Aug 2008
Posts: 3854
|
| Posted: Tue Dec 08, 2009 1:02 pm Post subject: |
|
|
Normally, it's a good idea to find all URs before performing any eliminations for them. However, here is an example where that rule-of-thumb is ill-advised.
| Code: | +-----------------------+
| . . . | 2 . . | . 7 8 |
| . . . | . . 8 | 3 2 4 |
| . . . | . . . | . . . |
|-------+-------+-------|
| 7 . . | . . 4 | . . . |
| . . . | . 7 . | 1 3 9 |
| . 3 . | 1 . . | . 8 . |
|-------+-------+-------|
| . 1 . | . 8 . | . . 3 |
| 3 4 . | . 5 9 | . . . |
| 9 8 . | . 2 . | 7 . 5 |
+-----------------------+
|
After basics:
| Code: | r12c15 <16> UR Type 4 <> 6 r12c1
r34c78 <56> UR Type 6 <> 5 *r3c8,r4c7
r38c89 <16> UR Type 6 <> 1 *r3c8,r8c9
+--------------------------------------------------------------+
| 1456 56 34 | 2 16 35 | 9 7 8 |
| 156 567 9 | 57 16 8 | 3 2 4 |
| 28 27 38 | 9 4 37 | 56 156 16 |
|--------------------+--------------------+--------------------|
| 7 9 1 | 8 3 4 | 256 56 26 |
| 48 256 48 | 56 7 256 | 1 3 9 |
| 256 3 25 | 1 9 256 | 4 8 7 |
|--------------------+--------------------+--------------------|
| 25 1 257 | 4 8 67 | 26 9 3 |
| 3 4 27 | 67 5 9 | 8 16 126 |
| 9 8 6 | 3 2 1 | 7 4 5 |
+--------------------------------------------------------------+
# 47 eliminations remain
|
The UR Type 4 can be performed without affecting the outcome. However, concurrent application of the UR Type 6s hinder the puzzle from being cracked at this point. Ironically, only one should be performed.
Perform <56> UR Type 6 and it forces the <16> UR Type 6 to become a UR Type 1, and it cracks the puzzle.
Perform <16> UR Type 6 and it forces the <56> UR Type 6 to become a UR Type 1, and it cracks the puzzle.
What's not very obvious is this AIC forced by the concurrent UR Type 6s:
| Code: | (2)r4c7 = (1-5)r3c8 = (2)r8c8 => r4c9,r7c7<>2
|
|
|
| Back to top |
|
|
wapati
Joined: 10 Jun 2008
Posts: 472
Location: Brampton, Ontario, Canada.
|
| Posted: Tue Dec 08, 2009 6:00 pm Post subject: |
|
|
| daj95376 wrote: | Normally, it's a good idea to find all URs before performing any eliminations for them. However, here is an example where that rule-of-thumb is ill-advised.
| Code: | +-----------------------+
| . . . | 2 . . | . 7 8 |
| . . . | . . 8 | 3 2 4 |
| . . . | . . . | . . . |
|-------+-------+-------|
| 7 . . | . . 4 | . . . |
| . . . | . 7 . | 1 3 9 |
| . 3 . | 1 . . | . 8 . |
|-------+-------+-------|
| . 1 . | . 8 . | . . 3 |
| 3 4 . | . 5 9 | . . . |
| 9 8 . | . 2 . | 7 . 5 |
+-----------------------+
|
After basics:
| Code: | r12c15 <16> UR Type 4 <> 6 r12c1
r34c78 <56> UR Type 6 <> 5 *r3c8,r4c7
r38c89 <16> UR Type 6 <> 1 *r3c8,r8c9
+--------------------------------------------------------------+
| 1456 56 34 | 2 16 35 | 9 7 8 |
| 156 567 9 | 57 16 8 | 3 2 4 |
| 28 27 38 | 9 4 37 | 56 156 16 |
|--------------------+--------------------+--------------------|
| 7 9 1 | 8 3 4 | 256 56 26 |
| 48 256 48 | 56 7 256 | 1 3 9 |
| 256 3 25 | 1 9 256 | 4 8 7 |
|--------------------+--------------------+--------------------|
| 25 1 257 | 4 8 67 | 26 9 3 |
| 3 4 27 | 67 5 9 | 8 16 126 |
| 9 8 6 | 3 2 1 | 7 4 5 |
+--------------------------------------------------------------+
# 47 eliminations remain
|
The UR Type 4 can be performed without affecting the outcome. However, concurrent application of the UR Type 6s hinder the puzzle from being cracked at this point. Ironically, only one should be performed.
Perform <56> UR Type 6 and it forces the <16> UR Type 6 to become a UR Type 1, and it cracks the puzzle.
Perform <16> UR Type 6 and it forces the <56> UR Type 6 to become a UR Type 1, and it cracks the puzzle.
What's not very obvious is this AIC forced by the concurrent UR Type 6s:
| Code: | (2)r4c7 = (1-5)r3c8 = (2)r8c8 => r4c9,r7c7<>2
|
|
It is interesting. If you take a look at the grid after using both type 6 URs there is an avoidable DP (2 really) that leaves only one more step.
Note that r3c8 is NOT a given.
| Code: | .---------------.-------------.------------.
| 145 56 34 | 2 16 35 | 9 7 8 |
| 15 567 9 | 57 16 8 | 3 2 4 |
| 28 27 38 | 9 4 37 | 56 *6 *16 |
:---------------+-------------+------------:
| 7 9 1 | 8 3 4 | 26 56 26 |
| 48 256 48 | 56 7 256 | 1 3 9 |
| 6 3 25 | 1 9 256 | 4 8 7 |
:---------------+-------------+------------:
| 25 1 257 | 4 8 67 | 26 9 3 |
| 3 4 27 | 67 5 9 | 8 *16 *2-6|
| 9 8 6 | 3 2 1 | 7 4 5 |
'---------------'-------------'------------'
.----------------.-------------.------------.
| 1456 56 34 | 2 16 35 | 9 7 8 |
| 156 567 9 | 57 16 8 | 3 2 4 |
| 28 27 38 | 9 4 37 |*56 *6 16 |
:----------------+-------------+------------:
| 7 9 1 | 8 3 4 |*2-6*56 26 |
| 48 256 48 | 56 7 256 | 1 3 9 |
| 256 3 25 | 1 9 256 | 4 8 7 |
:----------------+-------------+------------:
| 25 1 257 | 4 8 67 | 26 9 3 |
| 3 4 27 | 67 5 9 | 8 16 26 |
| 9 8 6 | 3 2 1 | 7 4 5 |
'----------------'-------------'------------' |
|
|
| Back to top |
|
|
daj95376
Joined: 23 Aug 2008
Posts: 3854
|
| Posted: Thu Mar 25, 2010 7:47 pm Post subject: |
|
|
This pattern -- borrowed from ronk in another forum -- is the basis for a UR Type 1. Three of the cells contain ab and the fourth cell contains at least one value of the candidate pair. In this case, it eliminates a from a+X.
I could have also written:
As it turns out, the classic UR Type 1 is simply two concurrent applications of this pattern.
In addition, the first pattern can be reduced to:
and the elimination of a in a+X still holds true. This was recently explored by Keith in another thread. |
|
| Back to top |
|
|
daj95376
Joined: 23 Aug 2008
Posts: 3854
|
| Posted: Sun Jul 04, 2010 1:32 am Post subject: |
|
|
I have recently been confused by the use of AUR in a number of messages. So, I went to Sudopedia and checked its definition for Unique Rectangle.
| Sudopedia wrote: | A Unique Rectangle is a Deadly Pattern formed by 4 cells that share 2 rows, 2 columns and 2 boxes.
|
Sudopedia doesn't contain an entry for AUR. But it does use Uniqueness Test 1 through Uniqueness Test 6, among others.
Okay, then AUR makes sense as Almost a Unique Rectangle, and it's the general case that encompasses the Uniqueness Tests.
Hmmm!!! |
|
| Back to top |
|
|
keith
Joined: 19 Sep 2005
Posts: 3355
Location: near Detroit, Michigan, USA
|
| Posted: Sun Jul 04, 2010 5:31 am Post subject: |
|
|
Danny,
I have no idea what an AUR is. I think we should define an ADP. Almost Deadly Pattern.
A DP is any single-digit solution that has interchangeable candidates and, therefore, multiple solutions. An ADP is an unsolved situation that has a DP plus additional candidates.
By the way, I do not view Sudopedia as a hallowed scripture. The last time I looked, there was no description of a general remote pair, nor of an M-wing,
Keith |
|
| Back to top |
|
|
daj95376
Joined: 23 Aug 2008
Posts: 3854
|
| Posted: Sun Jul 04, 2010 2:57 pm Post subject: |
|
|
| keith wrote: | Danny,
I have no idea what an AUR is. I think we should define an ADP. Almost Deadly Pattern.
A DP is any single-digit solution that has interchangeable candidates and, therefore, multiple solutions. An ADP is an unsolved situation that has a DP plus additional candidates.
By the way, I do not view Sudopedia as a hallowed scripture. The last time I looked, there was no description of a general remote pair, nor of an M-wing,
|
Keith,
I agree that Sudopedia is not a hallowed scripture. However, since we are without a hallowed scripture (anywhere) for Sudoku, then I try to use any formalized reference that I can find. Sudopedia seems to be "right" a majority of the time.
I was surprised to see that Sudopedia defined Unique Rectangle as a specific Deadly Pattern. I'd always thought that a Unique Rectangle was a specific DP with additional candidates present.
I should have done this first. I searched through The New Sudoku Players' Forum for the first occurrance of "Unique Rectangle". It was a post by MadOverlord here that goes back to Oct 21, 2005. He talks about Uniqueness tests and how he's categorized them into Unique Rectangle types that have extra candidates present.
So, I guess AUR is used by those who follow the Sudopedia definition and wish to designate a UR with additional candidates. You and I can continue to merrily use Unique Rectangle using MadOverlord's definition. _ 
Regards, Danny |
|
| Back to top |
|
|
keith
Joined: 19 Sep 2005
Posts: 3355
Location: near Detroit, Michigan, USA
|
| Posted: Sun Jul 04, 2010 7:59 pm Post subject: |
|
|
Danny,
I took a look at what Sudopedia has to say on the subject, and I don't like it. I don't like the usual classification of URs into types either, but at least it is a common terminology. Sudopedia's discussion may be logical, but it is terminology no one uses.
By the way, all the links to the old Players' Forum from Sudopedia are now broken.
I agree that we may as well start with what Sudopedia says. It helps with common terminology.
By the way, Mad Overlord is Robert Woodhead. He wrote the Sudoku Susser.
Keith |
|
| Back to top |
|
|
keith
Joined: 19 Sep 2005
Posts: 3355
Location: near Detroit, Michigan, USA
|
| Posted: Mon Jul 05, 2010 3:31 am Post subject: |
|
|
Danny,
I think Sudopeida is simply incorrect. In 2006 I wrote (see the first post of my UR thread, the second post of this thread):
| Quote: | | ... 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. |
The Unique Rectangle is NOT the deadly pattern. It is NOT a set of candidates that may lead to a non-unique solution. It is what you need to eliminate the deadly pattern, or the potential of a non-unique solution.
I am not about to start editing Sudopedia, any more than I am prepared to rewrite the Encyclopedia Britannica.
There is a sidebar (and much less important) discussion as to whether the deadly pattern (DP) is a (particular) non-unique solution, or whether it is a collection of candidates that may lead to such a solution.
I would prefer we say a DP is a group of cells in a solved puzzle where values can be interchanged, so the solution is not unique.
In an unsolved puzzle, I would prefer to refer to a "possible DP" or a "potential DP".
By the way, I just happened to come along as Robert Woodhead and others were refining their ideas on uniqueness techniques.
Best wishes,
Keith |
|
| Back to top |
|
|
daj95376
Joined: 23 Aug 2008
Posts: 3854
|
| Posted: Mon Jul 05, 2010 3:54 am Post subject: |
|
|
| keith wrote: | I think Sudopedia is simply incorrect.
|
I agree ... but I don't think anyone else cares. So, I'll accept AUR from those who do follow the Sudopedia definition. |
|
| Back to top |
|
|
daj95376
Joined: 23 Aug 2008
Posts: 3854
|
| Posted: Sat Nov 20, 2010 7:32 am Post subject: |
|
|
While reviewing a collection of puzzles dedicated to URs, I happened on this puzzle.
| Code: | +-----------------------+
| . 2 . | . . 9 | . . 3 |
| 8 . . | . 4 2 | . . . |
| 7 . . | . . . | . . 2 |
|-------+-------+-------|
| . 8 . | 1 . . | . . . |
| . . . | . . . | . 3 1 |
| . . . | . 5 4 | 6 . . |
|-------+-------+-------|
| . . 5 | . 3 7 | . 4 . |
| . 9 . | . . . | . 6 . |
| . 6 . | 5 . . | . . . |
+-----------------------+
c3b1 Locked Candidate 1 <> 9 r456c3
<16> UR in r13c35
+-----------------------------------------------------------------------+
| 156 2 *16+4 | 78 *16 9 | 4578 1578 3 |
| 8 35 139 | 37 4 2 | 579 1579 6 |
| 7 34 *16+349 | 38 *16 5 | 489 189 2 |
|-----------------------+-----------------------+-----------------------|
| 569 8 26 | 1 7 3 | 259 59 4 |
| 59 457 24 | 29 8 6 | 2579 3 1 |
| 19 37 123 | 29 5 4 | 6 789 89 |
|-----------------------+-----------------------+-----------------------|
| 2 1 5 | 6 3 7 | 89 4 89 |
| 3 9 7 | 4 2 8 | 1 6 5 |
| 4 6 8 | 5 9 1 | 3 2 7 |
+-----------------------------------------------------------------------+
# 56 eliminations remain
|
Although a strong links analysis produces r1c3<>1, I noticed a finned-UR approach that I've used previously.
| Code: | r1c3=4 => r5c3=2 r4c3=6 ; r3c3<> 6 -or-
UR Type 1 ; r3c3<>16
|
|
|
| Back to top |
|
|
peterj
Joined: 26 Mar 2010
Posts: 974
Location: London, UK
|
| Posted: Sat Nov 20, 2010 9:27 am Post subject: |
|
|
Danny, that's an interesting approach I have never thought of using. Thanks
It led me to think again about the question of whether a UR move like this can be replicated by a "proof" move like a chain or net that does not rely on the setter uniquesness assumption - and so whether puzzles can always be solved without using uniqueness. What's the current thinking on this? (Sudopedia just notes it as a "controversy"!) I can often find equivalent moves especially if the UR move was "kraken"-like rather than just using internal logic, but they tend to be ugly brutes!
In this case quite a nice ALS move ..
| Code: | | ANQ(6=1345)b1q1358 - (3=7)r6c2 - r6c8=(7-2)r5c7=r4c7 - (2=6)r4c3 ; r3c3<>6 |
[Edited to clarify] |
|
| Back to top |
|
|
tlanglet
Joined: 17 Oct 2007
Posts: 2468
Location: Northern California Foothills
|
| Posted: Sat Nov 20, 2010 1:58 pm Post subject: |
|
|
| daj95376 wrote: | While reviewing a collection of puzzles dedicated to URs, I happened on this puzzle.
| Code: | +-----------------------+
| . 2 . | . . 9 | . . 3 |
| 8 . . | . 4 2 | . . . |
| 7 . . | . . . | . . 2 |
|-------+-------+-------|
| . 8 . | 1 . . | . . . |
| . . . | . . . | . 3 1 |
| . . . | . 5 4 | 6 . . |
|-------+-------+-------|
| . . 5 | . 3 7 | . 4 . |
| . 9 . | . . . | . 6 . |
| . 6 . | 5 . . | . . . |
+-----------------------+
c3b1 Locked Candidate 1 <> 9 r456c3
<16> UR in r13c35
+-----------------------------------------------------------------------+
| 156 2 *16+4 | 78 *16 9 | 4578 1578 3 |
| 8 35 139 | 37 4 2 | 579 1579 6 |
| 7 34 *16+349 | 38 *16 5 | 489 189 2 |
|-----------------------+-----------------------+-----------------------|
| 569 8 26 | 1 7 3 | 259 59 4 |
| 59 457 24 | 29 8 6 | 2579 3 1 |
| 19 37 123 | 29 5 4 | 6 789 89 |
|-----------------------+-----------------------+-----------------------|
| 2 1 5 | 6 3 7 | 89 4 89 |
| 3 9 7 | 4 2 8 | 1 6 5 |
| 4 6 8 | 5 9 1 | 3 2 7 |
+-----------------------------------------------------------------------+
# 56 eliminations remain
|
Although a strong links analysis produces r1c3<>1, I noticed a finned-UR approach that I've used previously.
| Code: | r1c3=4 => r5c3=2 r4c3=6 ; r3c3<> 6 -or-
UR Type 1 ; r3c3<>16
|
|
Danny,
I like your finned or almost approach, but do not see how it adds to viewing the pattern. To me the strong analysis that determined r1c3<>1 is correct but incomplete. The internal SIS is r1c3=4 & r3c3=349 which can also be used to perform an additional deletion:
(4)r1c3-(4=2)r5c3-(2=6)r4c3; r3c3<>6
||
(349)r3c3-(6)r3c3
Ted |
|
| Back to top |
|
|
daj95376
Joined: 23 Aug 2008
Posts: 3854
|
| Posted: Sat Nov 20, 2010 5:06 pm Post subject: |
|
|
| peterj wrote: | Danny, that's an interesting approach I have never thought of using. Thanks
It led me to think again about the question of whether a UR move like this can be replicated by a "proof" move like a chain or net that does not rely on the setter uniquesness assumption - and so whether puzzles can always be solved without using uniqueness. What's the current thinking on this? (Sudopedia just notes it as a "controversy"!) I can often find equivalent moves especially if the UR move was "kraken"-like rather than just using internal logic, but they tend to be ugly brutes!
In this case quite a nice ALS move ..
| Code: | | ANQ(6=1345)b1q1358 - (3=7)r6c2 - r6c8=(7-2)r5c7=r4c7 - (2=6)r4c3 ; r3c3<>6 |
|
Peter, an awful lot has been written about the uniqueness controversy. I doubt if there's a consensus on the topic.
My Position on Uniqueness:
There is nothing in the fundamental, newspaper-type description of a Sudoku puzzle that says it must have a unique solution from the clues provided. There are many solutions to the following Sudoku puzzle.
| Code: | +-----------------------+
| . . . | . . . | . . . |
| . . . | . . . | . . . |
| . . . | . . . | . . . |
|-------+-------+-------|
| . . . | . . . | . . . |
| . . . | . 1 . | . . . |
| . . . | . . . | . . . |
|-------+-------+-------|
| . . . | . . . | . . . |
| . . . | . . . | . . . |
| . . . | . . . | . . . |
+-----------------------+
|
If a Sudoku puzzle has only one solution, then I consider it an additional constraint that's fair game to utilize.
I've heard that using uniqueness might lead to a solution in a multi-solution puzzle, but I don't recall seeing it demonstrated. Even so, I have found a solution and the puzzle can be tossed. I don't care if someone else finds a different solution. That simply means that it's a multi-solution puzzle!!!
Finally, I doubt if a uniqueness step is ever the only way to advance a puzzle's solution. However, I think they are much more interesting to include in a solution than a boring 9-cell XY-Chain. (Your chain does not fall into this category.)
BTW, that's an impressive grouped 6=3 strong link you formed through the ANQ()!
Regards, Danny |
|
| Back to top |
|
|
daj95376
Joined: 23 Aug 2008
Posts: 3854
|
| Posted: Sat Nov 20, 2010 7:16 pm Post subject: |
|
|
| tlanglet wrote: | I like your finned or almost approach, but do not see how it adds to viewing the pattern. To me the strong analysis that determined r1c3<>1 is correct but incomplete. The internal SIS is r1c3=4 & r3c3=349 which can also be used to perform an additional deletion:
(4)r1c3-(4=2)r5c3-(2=6)r4c3; r3c3<>6
||
(349)r3c3-(6)r3c3
|
Yes Ted, what I described is essentially identical to what you described. The only difference is in motivation. I'm much more likely to examine URs that are almost a know pattern with known eliminations before examining URs for eliminations based on analyzing the internal SIS. Similar to a finned X-Wing where no one takes the time to analyze which eliminations are associated with the X-Wing.
As for the elimination r3c3<>6, it leads to r1c3<>1, which exposes a Naked Triple as the final step before Singles. The Naked Triple would have performed r3c3<>6 as well.
Regards, Danny |
|
| Back to top |
|
|
|
|
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
|
Powered by phpBB © 2001, 2005 phpBB Group
|
FAQ
Search
Memberlist
Usergroups
Register
Profile
Log in to check your private messages
Log in
