dailysudoku.com Forum Index dailysudoku.com
Discussion of Daily Sudoku puzzles
 
 FAQFAQ   SearchSearch   MemberlistMemberlist   UsergroupsUsergroups   RegisterRegister 
 ProfileProfile   Log in to check your private messagesLog in to check your private messages   Log inLog in 

Extended Unique Rectangles - Solving the 3,2,3,3 MUG

 
Post new topic   Reply to topic    dailysudoku.com Forum Index -> Solving techniques, and terminology
View previous topic :: View next topic  
Author Message
mturner



Joined: 02 Feb 2013
Posts: 7
Location: Fort Collins, Colorado

PostPosted: Sat Feb 02, 2013 7:46 pm    Post subject: Extended Unique Rectangles - Solving the 3,2,3,3 MUG Reply with quote

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
View user's profile Send private message
Luke451



Joined: 20 Apr 2008
Posts: 310
Location: Southern Northern California

PostPosted: Wed Feb 06, 2013 5:57 am    Post subject: Reply with quote

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
View user's profile Send private message
mturner



Joined: 02 Feb 2013
Posts: 7
Location: Fort Collins, Colorado

PostPosted: Wed Feb 06, 2013 8:35 pm    Post subject: Reply with quote

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
View user's profile Send private message
Luke451



Joined: 20 Apr 2008
Posts: 310
Location: Southern Northern California

PostPosted: Thu Feb 07, 2013 12:08 am    Post subject: Reply with quote

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
View user's profile Send private message
mturner



Joined: 02 Feb 2013
Posts: 7
Location: Fort Collins, Colorado

PostPosted: Thu Feb 07, 2013 12:31 am    Post subject: Reply with quote

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
View user's profile Send private message
Marty R.



Joined: 12 Feb 2006
Posts: 5770
Location: Rochester, NY, USA

PostPosted: Thu Feb 07, 2013 1:31 am    Post subject: Reply with quote

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
View user's profile Send private message
keith



Joined: 19 Sep 2005
Posts: 3355
Location: near Detroit, Michigan, USA

PostPosted: Thu Feb 07, 2013 1:41 am    Post subject: Reply with quote

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
View user's profile Send private message
mturner



Joined: 02 Feb 2013
Posts: 7
Location: Fort Collins, Colorado

PostPosted: Thu Feb 07, 2013 5:21 am    Post subject: Reply with quote

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
View user's profile Send private message
ronk



Joined: 07 May 2006
Posts: 398

PostPosted: Thu Feb 07, 2013 2:55 pm    Post subject: Reply with quote

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
View user's profile Send private message
mturner



Joined: 02 Feb 2013
Posts: 7
Location: Fort Collins, Colorado

PostPosted: Fri Feb 08, 2013 7:13 am    Post subject: Reply with quote

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
View user's profile Send private message
Luke451



Joined: 20 Apr 2008
Posts: 310
Location: Southern Northern California

PostPosted: Fri Feb 08, 2013 2:35 pm    Post subject: Reply with quote

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
View user's profile Send private message
keith



Joined: 19 Sep 2005
Posts: 3355
Location: near Detroit, Michigan, USA

PostPosted: Fri Feb 08, 2013 10:02 pm    Post subject: Reply with quote

mturner,

While you're classifying URs, do you have this one?

http://www.dailysudoku.com/sudoku/forums/viewtopic.php?t=5672

Keith
Back to top
View user's profile Send private message
mturner



Joined: 02 Feb 2013
Posts: 7
Location: Fort Collins, Colorado

PostPosted: Sat Feb 09, 2013 2:38 am    Post subject: Reply with quote

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
View user's profile Send private message
mturner



Joined: 02 Feb 2013
Posts: 7
Location: Fort Collins, Colorado

PostPosted: Sat Feb 09, 2013 7:57 pm    Post subject: Reply with quote

Error found and fixed.
Back to top
View user's profile Send private message
Display posts from previous:   
Post new topic   Reply to topic    dailysudoku.com Forum Index -> Solving techniques, and terminology All times are GMT
Page 1 of 1

 
Jump to:  
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