| View previous topic :: View next topic |
| Author |
Message |
mturner
Joined: 02 Feb 2013
Posts: 7
Location: Fort Collins, Colorado
|
 Posted: Sat Feb 02, 2013 7:46 pm Post subject: Extended Unique Rectangles - Solving the 3,2,3,3 MUG |
 |
|
Unique Rectangles (URs) can be extended to structures larger than 2X2. In this post, I will explore how to use unique rectangles in 2X3 structures and various ways to approach candidate eliminations while avoiding a deadly pattern.
Extended Unique Rectangles are first mentioned in Andrew Stuart's website, http://www.sudokuwiki.org/Extended_Unique_Rectangles
Traditional unique rectangles depend on 4 cells located in 2 rows, 2 columns, and 2 boxes. In this post, Extended URs extend to either of:
3 boxes, 3 rows, 2 columns
3 boxes, 2 rows, 3 columns
In MUGs, this is the permeable deadly pattern MUG with 3 digits, 2 rows, 3 columns, 3 boxes.
Since rows and columns are interchangeable, I will only discuss the first case, leaving the second as an exercise for the reader.
A locked triple is any three cells with only 3 candidates. Examples include:
[1,2,3] + [1,2,3]+[1,2,3]
[1,2,3] + [1,2,3]+[1,2]
[1,2,3] + [1,3] +[1,2]
[1,2] + [1,3] + [2,3]
| Code: |
+---------+
|12 13 |
| |
| |
+---------+
|123 123 |
| |
| |
+---------+
| |
|23 123 |
| |
+---------+
|
Notice that the first column can be filled with [1,2,3], [1,3,2], and[2,1,3] and the second column can be filled with [3,1,2], [3,2,1], [1,2,3], and [1,3,2]. We can swap around the values and come up with multiple solutions. Thus we have a deadly pattern that must be avoided.
As in regular unique rectangles, there are a number of types. The types used here correspond to their regular UR types, but extended as appropriate.
Type 1
Suppose we have a partially solved puzzle with the following set of candidates:
| Code: |
+----------+
|123 123 |
| |
| |
+----------+
|123 123 |
| |
| |
+----------+
| |
|123 1234 |
| |
+----------+
|
The bottom right cell cannot be <1>, <2>, or<3>, because this would cause the deadly pattern. Since <4> is the only remaining candidate, the value for this cell must be <4>. After reduction, we have:
| Code: |
+----------+
|123 123 |
| |
| |
+----------+
|123 123 |
| |
| |
+----------+
| |
|123 4 |
| |
+----------+
|
If there are more candidates in the last cell, we still can remove all of the "deadly" candidates from the cell:
| Code: |
+-----------+
|123 123 |
| |
| |
+-----------+
|123 123 |
| |
| |
+-----------+
| |
|123 12345 |
| |
+-----------+
|
Resulting in:
| Code: |
+-----------+
|123 123 |
| |
| |
+-----------+
|123 123 |
| |
| |
+-----------+
| |
|123 45 |
| |
+-----------+
|
Type 2
If we have a single extra candidate value that occurs in a single row, one of them must be true in order to prevent the deadly pattern. Therefore, if any other cell in a column on this row outside the of the deadly patterns can have this candidate removed. In the diagram below, <4> occurs in the first row. In order to prevent the deadly pattern, one of them must be true. Therefore the cells marked with a # must not be <4> and can have it removed.
| Code: |
+-------------+-------+-------+
|1234 1234 # | # # # | # # # |
| # # # | | |
| # # # | | |
+-------------+-------+-------+
|123 123 | | |
| | | |
| | | |
+-------------+-------+-------+
| | | |
|123 123 | | |
| | | |
+-------------+-------+-------+
|
Type 2b
Similarly, if we have a single extra candidate value that occurs in a single column, one of them must be true in order to prevent the deadly pattern. Therefore, if any other cell in a row on this column outside the of the deadly patterns can have this candidate removed. In the diagram below, <4> occurs in the second column. In order to prevent the deadly pattern, one of them must be true. Therefore the cells marked with a # must not be <4> and can have it removed.
| Code: |
+-------------+-------+-------+
|123 1234 | | |
| # | | |
| # | | |
+-------------+-------+-------+
|123 1234 | | |
| # | | |
| # | | |
+-------------+-------+-------+
| # | | |
|123 1234 | | |
| # | | |
+-------------+-------+-------+
|
Type 3
If there is more than a single extra value in the column, at least one of them must be true. The extra cells can be thought of as a pseudo-cell that can be combined with other cells to produce reductions.
In this example, we have a two different extra values in the second column. One of them must be true. These can two extra values form a pseudo-cell. When combined with the bi-value cell containing these two values, they create a locked set on <4> and <5>. Therefore <4> and <5> can be removed from the cells marked with a #.
| Code: |
+------------+
|123 1234 |
| # |
| # |
+------------+
|123 1235 |
| 45 |
| # |
+------------+
| # |
|123 1234 |
| # |
+------------+
|
This method can be extended by considering that a bi-value cell can also be considered an Almost Locked Set (ALS). In general, we can combine the pseudo-cell with an ALS to create a locked set and create additional eliminations.
The pseudo-cell can contain more than 2 numbers. The ALS must contain all the values of the pseudo-cell and be comprised of enough cells to create a locked set. If there are 3 extra values, the ALS must be comprised of two cells. If the ALS contains values that are not part of the pseudo-cell, the ALS must be comprised of at least one more cell for each additional value.
In this example, we have three values in the pseudo-cell. Therefore the ALS must be in two cells and contain just these values.
| Code: |
+------------+
|123 1234 |
| # |
| # |
+------------+
|123 1235 |
| 45 |
| # |
+------------+
| 456 |
|123 1236 |
| # |
+------------+
|
In this example, the ALS contains an extra value of its own. Therefore it must contain an extra cell to create the locked set.
| Code: |
+------------+
|123 1234 |
| # |
| 46 |
+------------+
|123 1235 |
| 456 |
| # |
+------------+
| # |
|123 123 |
| # |
+------------+
|
Type 3b
In this case, the extra values are on a single row. Therefore the ALS must be in that row. The same limitations apply to the ALS as in the normal Type 3.
| Code: |
+--------------+-------+-------+
|1235 1234 # | 45 # # | # # # |
| | | |
| | | |
+-------------+--------+-------+
|123 123 | | |
| | | |
| | | |
+-------------+--------+-------+
| | | |
|123 123 | | |
| | | |
+-------------+--------+-------+
|
Type 3c
In this case, the ALS is located is the same box as the extra values. Rather than eliminations in a row or column, the eliminations are limited to the box. The same limitations on the ALS as in the normal Type 3.
| Code: |
+--------------+----+----+
|1235 1234 # | | |
| # # # | | |
| # # 45 | | |
+--------------+----+----+
|123 123 | | |
| | | |
| | | |
+--------------+----+----+
| | | |
|123 123 | | |
| | | |
+--------------+----+----+
|
Type 4
In a regular Unique Rectangle, if one of the values that make up deadly pattern are the are the only ones in the row, column, or box they reside in, then one of them must be true. This implies that the the other value of the deadly pair can be removed from these cells.
In Extended Unique Rectangles, since we are dealing with three candidates, the rule can be extended.
The rule is: If two of the values that make up the deadly pattern are the only ones in that row, column, or box, then the third deadly pattern value can be removed from these cells.
In this example, notice that the deadly pattern values <1> and <2> only occur within the possible deadly pattern cells and the are both in the same column. Therefore, to prevent the deadly pattern, <3> can be eliminated from those rows.
| Code: |
+----------+
|123 1234 |
| 7 |
| 8 |
+----------+
|123 1235 |
| 9 |
| 456 |
+----------+
| 456 |
|123 1236 |
| 3456 |
+----------+
|
Type 5
In standard Unique Rectangles, Type 5 refers to the case where there is a single extra value in opposite corners. One of these values must be true. Cells that can see both can have this candidate removed
| Code: |
+--------+
|123 12 |
| |
| |
+--------+
|12 123 |
| |
| |
+--------+
|
In extended Unique Rectangles, the same rule applies. When we have a single extra value that is in two columns and 2 or 3 rows.
In the diagram below, we see a single extra candidate in two cells that are not in the same row or column. The cells marked with a # are the only ones that can "see" all of them. They must not be <4> and can have it removed from them.
| Code: |
+----------+
|1234 123 |
| # |
| # |
+----------+
|123 1234 |
| # |
| # |
+----------+
| |
|123 123 |
| |
+----------+
|
In the diagram below, <4> occurs in the first row and the second column. In order to prevent the deadly pattern, one of them must be true. Therefore the cells marked with a # are the only ones that can "see" all of them. They must not be <4> and can have it removed from them.
Type 5b
In this case, the single extra value is in both a column and a single row. Only the cells in the same column and same area can have a candidate removed.
| Code: |
+-------------+-------+-------+
|1234 1234 | | |
| # | | |
| # | | |
+-------------+-------+-------+
|123 1234 | | |
| | | |
| | | |
+-------------+-------+-------+
| | | |
|123 1234 | | |
| | | |
+-------------+-------+-------+
|
Type 6
In regular Unique Rectangles, Type 6 refers to the case where there is differing extra values in opposite corners:
| Code: |
+--------+
|123 12 |
| # |
| # |
+--------+
|12 124 |
| @ |
| @ |
+--------+
|
As in Type 3, we can use an Almost Linked Set (ALS) to create eliminations. Because the extra values are in differing rows and columns, the ALS can only be 1 cell and is confined to the same box as one of the candidates and the column of the other. The ALS must be a bi-value cell. This leaves just one other cell that can have candidates removed. These locations are marked with <@> and <#> in the diagram.
In the simple case, Extended Unique Rectangles are similar:
| Code: |
+----------+
|1234 123 |
| 45 |
| # |
+----------+
|123 1235 |
| 45 |
| @ |
+----------+
| |
|123 123 |
| |
+----------+
|
Type 6b
Extended URs can also have one of the extra values in more that just the diagonal cells. Those cell must be in the same column as the 1 cell ALS (bi-value cell). As before, the ALS must be a bi-value cell. This leaves just one other cell that can have candidates removed.
| Code: |
+----------+
|1234 123 |
| |
| |
+----------+
|1234 1235 |
| 45 |
| # |
+----------+
| |
|1235 123 |
| |
+----------+
|
Hidden Unique Rectangles
Hidden Unique Rectangles use conjugate pairs (also known as Strong Links) to make additional eliminations.
I find that Hidden Unique Rectangles come in three types as shown below:
Hidden Unique Rectangle Type 1
The two bi-value cells with <1> are strongly linked. In addition, there is a strong link on 1's between the cell with <123> and the corresponding bi-value cell. In each of these cases, the <2> in the lower right corner can be removed.
| Code: |
+---------+
|12 12 |
| |
| |
+---------+
|123 124 |
| |
| |
+---------+
^ Strong link on 1
or
+---------+
|12 123 |< Strong link on 1
| |
| |
+---------+
|12 124 |
| |
| |
+---------+
|
Hidden Unique Rectangle Type 1b
A special case of Type 1 where each floor cell is a strong link to a different value. Two removals are possible. This is basically two Type 1's occurring at the same time.
| Code: |
+---------+
|12 12 |
| |
| |
+---------+
|123 124 |
| |
| |
+---------+
^ Strong link on 1
^ Strong link on 2
or
+---------+
|12 123 |< Strong link on 1
| |
| |
+---------+
|12 124 |< Strong link on 2
| |
| |
+---------+
|
Hidden Unique Rectangle Type 2
In this case, we have a bi-value cell in the upper left and strong links on <1> for the other 3 cells. The <2> in the lower right corner can be eliminated.
| Code: |
+---------+
|12 123 |
| |
| |
+---------+
|124 125 |< Strong link on 1's
| |
| |
+---------+
^ Strong link on 1's
|
Extended Hidden Unique Rectangles Type 1
In this example, the <12> in the second row, first column is bi-value cell. The <23> in the third row, first column is also a bi-value cell. It is not required that the cell in row one, column one be a bi-value cell.
There is a strong link on the second row on <1> and a second strong link in the third row on <2>.
If such a pattern exists, the <3> can be eliminated from the row 1, column 2.
| Code: |
+--------+
|134 123 |
| |
| |
+--------+
|12 123 |< Strong link on 1's
| |
| |
+--------+
| |
| 23 123 |< Strong link on 2's
| |
+--------+
^ Strong link on 1's
^ Strong link on 2's
^ Strong link on 3's
|
There are a number of other patterns that result in possible eliminations in Extended Hidden Unique Rectangles. I will leave those for a later post.[/code][/url]
Last edited by mturner on Fri Feb 08, 2013 7:01 am; edited 4 times in total |
|
| Back to top |
|
 |
Luke451
Joined: 20 Apr 2008
Posts: 310
Location: Southern Northern California
|
| Posted: Wed Feb 06, 2013 5:57 am Post subject: |
|
|
Wow, an impressive article you present! Is this new material or has it been published before?
The bulk of the non-UR deadly patterns you present are called MUGs these days. Multivalue Universal Graves.
Are you familiar some of the seminal MUG articles/threads, such as this? |
|
| Back to top |
|
|
mturner
Joined: 02 Feb 2013
Posts: 7
Location: Fort Collins, Colorado
|
| Posted: Wed Feb 06, 2013 8:35 pm Post subject: |
|
|
Thanks for your kind words.
To my knowledge this is new material, with the exception of Type 1 Extended Unique Rectangles and the introductory material on regular Unique Rectangles.
Thanks for the reference to MUGs. |
|
| Back to top |
|
|
Luke451
Joined: 20 Apr 2008
Posts: 310
Location: Southern Northern California
|
| Posted: Thu Feb 07, 2013 12:08 am Post subject: |
|
|
| mturner wrote: | | Code: | +---------+
|12 13 |
| |
| |
+---------+
|123 123 |
| |
| |
+---------+
| |
|23 123 |
| |
+---------+
|
|
I do not see this as a deadly pattern, sorry.
Also, with the MUG term in common usage, I would think it would be confusing to call them Extended Unique Rectangles. MUGs are not unique rectangles. I believe this term may have been in use at one time, maybe someone else remembers. Andrew's material has been around for a very long time and many things have evolved.
The link you provided at the top of your post seems to be dead, BTW. |
|
| Back to top |
|
|
mturner
Joined: 02 Feb 2013
Posts: 7
Location: Fort Collins, Colorado
|
| Posted: Thu Feb 07, 2013 12:31 am Post subject: |
|
|
I am open to renaming, although I don't think I have the power to change the topic name. I would guess that outside of this community, Unique Rectangles is still in common usage and is not unnecessarily confusing.
Link fixed. Thanks for bringing it to my attention. Andrew Stuart's posting on Extended Unique Rectangles first appeared on 24 August 2012.
For now, you'll have to take my word for it that it is a deadly pattern. |
|
| Back to top |
|
|
Marty R.
Joined: 12 Feb 2006
Posts: 5770
Location: Rochester, NY, USA
|
| Posted: Thu Feb 07, 2013 1:31 am Post subject: |
|
|
| Quote: | | I am open to renaming, although I don't think I have the power to change the topic name. |
You do. Just click Edit at the upper right of your message, make any changes in the subject and/or message and click Submit. |
|
| Back to top |
|
|
keith
Joined: 19 Sep 2005
Posts: 3355
Location: near Detroit, Michigan, USA
|
| Posted: Thu Feb 07, 2013 1:41 am Post subject: |
|
|
| Luke451 wrote: | | mturner wrote: | | Code: | +---------+
|12 13 |
| |
| |
+---------+
|123 123 |
| |
| |
+---------+
| |
|23 123 |
| |
+---------+
|
|
I do not see this as a deadly pattern, sorry.
Also, with the MUG term in common usage, I would think it would be confusing to call them Extended Unique Rectangles. MUGs are not unique rectangles. I believe this term may have been in use at one time, maybe someone else remembers. Andrew's material has been around for a very long time and many things have evolved.
The link you provided at the top of your post seems to be dead, BTW. |
I believe "deadly pattern" only applies to the solution, and is to be avoided. A solution here is
| Code: | +---------+
|1 3 |
| |
| |
+---------+
|2 1 |
| |
| |
+---------+
| |
|3 2 |
| |
+---------+
|
and is certainly deadly.
Keith |
|
| Back to top |
|
|
mturner
Joined: 02 Feb 2013
Posts: 7
Location: Fort Collins, Colorado
|
| Posted: Thu Feb 07, 2013 5:21 am Post subject: |
|
|
Marty,
Thanks for the tip for the newby.
I've updated the title to reflect the connections to MUGs (Multiple Universal Graves). I've kept the Universal Rectangle terminology. Here's why: A Google search of Sudoku Multiple Universal Grave only returns references to Binary Universal Graves. Sudoku MUGS returns links to purchase containers to drink coffee from. Sudoku Unique Rectangles is what got me to this forum. So it seems appropriate to keep that term in the title.
I also updated the first paragraph to show the connection to the MUG work done prior in this forum. A link to that topic is included. |
|
| Back to top |
|
|
ronk
Joined: 07 May 2006
Posts: 398
|
| Posted: Thu Feb 07, 2013 2:55 pm Post subject: |
|
|
| keith wrote: | I believe "deadly pattern" only applies to the solution, and is to be avoided. A solution here is
| Code: | +---------+
|1 3 |
| |
| |
+---------+
|2 1 |
| |
| |
+---------+
| |
|3 2 |
| |
+---------+
|
and is certainly deadly. |
For those who generate sudoku puzzles with unique solutions, I think the more common term is UnAvoidable Set (UAS) or simply UnAvoidable (UA). It is a pattern for which supplying at least one clue is unavoidable. |
|
| Back to top |
|
|
mturner
Joined: 02 Feb 2013
Posts: 7
Location: Fort Collins, Colorado
|
| Posted: Fri Feb 08, 2013 7:13 am Post subject: |
|
|
While doing some testing, I found a new Hidden Unique Rectangle type. It is a variant of Type 1, so I'm calling it Type 1b. I've added to the descriptions in the original post. Here's the example puzzle where I found my first one:
| Code: |
+------------+--------+-------------+
| 8 5 6 | 3 1 27 | 247 9 47 |
| 9 247 47 | 5 6 8 | 237 23 1 |
| 237 237 1 | 9 4 27 | 5 6 8 |
+------------+--------+-------------+
| 1 38 2 | 48 7 6 | 34 5 9 |
| 47 9 5 | 1 2 3 | 8 47 6 |
| 36 368 47 | 48 5 9 | 1 2347 23 |
+------------+--------+-------------+
| 467 467 3 | 2 8 5 | 9 1 47 |
| 5 24 3 | 7 9 1 | 6 234 23 |
| 27 1 9 | 6 3 4 | 27 8 5 |
+------------+--------+-------------+
|
The start for the puzzle is this.
My solving order is unorthodox, so you may not get to this point from the start given in the link.
The floor cells are <23> r6c9 and r8c9. The ceiling cells are r6c8 and r8c8. In row 6, notice the strong link on <2>, implying that we can eliminate <3> from r8c8.
But also notice that on row 8, there is also a strong link on <3>, implying that we can eliminate <2> from r6c8.
Thus two eliminations are possible.
Last edited by mturner on Sat Feb 09, 2013 7:55 pm; edited 1 time in total |
|
| Back to top |
|
|
Luke451
Joined: 20 Apr 2008
Posts: 310
Location: Southern Northern California
|
| Posted: Fri Feb 08, 2013 2:35 pm Post subject: |
|
|
Hi mturner! I hope all is well with you. Your example directly above has an error in the grid which will prevent folks from pasting it into their favorite front end. Still, the UR elimination you point out is valid. I used to like to call that one "Strong Elbow."
You may like to do some research on uniqueness classification. The work you are presenting here has already been exhaustively catalogued, particularly by guys like Mike Barker, Ruud, Ronk, Keith, Havard and many others. Just one example would be a thread like this. Check "Uniqueness Tests" for many other articles here.
Thank you for fixing the link to
Extended Unique Rectangles above. Of the last three examples, one and three are MUGs in my book and I have many examples of that exact pattern being called a MUG. The second is very clearly a BUG-Lite. Calling that second one anything but a BUG-Lite is not helpful whatsoever, in my humble, although many are happy with just "deadly pattern." |
|
| Back to top |
|
|
keith
Joined: 19 Sep 2005
Posts: 3355
Location: near Detroit, Michigan, USA
|
|
| Back to top |
|
|
mturner
Joined: 02 Feb 2013
Posts: 7
Location: Fort Collins, Colorado
|
| Posted: Sat Feb 09, 2013 2:38 am Post subject: |
|
|
I'll be spending some time doing more research. Thanks for the leads and links.
Luke451, can you give me more information about the difficulty you are having loading the puzzle? I've double checked the values and find that they are correct. |
|
| Back to top |
|
|
mturner
Joined: 02 Feb 2013
Posts: 7
Location: Fort Collins, Colorado
|
| Posted: Sat Feb 09, 2013 7:57 pm Post subject: |
|
|
| Error found and fixed. |
|
| 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
