Uniqueness Type 6 - UR meets X-Wing

Advanced methods and approaches for solving Sudoku puzzles

Uniqueness Type 6 - UR meets X-Wing

Postby Ruud » Fri Mar 31, 2006 2:06 pm

One of the regular players of the SudoCue Daily Nightmare posted this on my support forum here.

It sure looks like a new variant of the Uniqueness Test. I would like to introduce it as Uniqueness Test 6.

Look at this candidate list:
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  |
'------------'------------'------------'

An X-Wing for digit 9 coincides with a uniqueness rectangle. Placing a 9 in R7C5 or R9C3 would force a 9 in the opposite corner and form a deadly pattern.

So, to formulate uniqueness type 6:

When a rectangle can be found in a single floor or tower, with candidates a and b as the only possibilities in 2 of its corners, and candidates a and b are also present in the other 2 corners along with extra candidates, and the candidates for digit a form an X-Wing pattern, then candidate a can be removed from the 2 corners with extra candidates.

There must be somebody able to formulate this a bit more elegant.

Ruud.
Ruud
 
Posts: 664
Joined: 28 October 2005

Postby vidarino » Fri Mar 31, 2006 2:39 pm

I wrote about a similar trick in this article, which borrows an external conjugate pair.:)

Edit: Hmm, on second look, not that similar. However, it appears to be pretty similar to the type 4 Uniqueness Rectangle. I would say that type 6 is to type 4 what type 5 is to type 2.:D

Anyway, type 5 should be renamed to a subtype of type 2, IMHO. (ronk suggested type 2C, if I recall correctly.) So perhaps this one should be called type 4-something instead, since they're closely related?

Nevertheless, it's a nice trick, and not too uncommon either, it seems. Thanks for sharing.

Vidar
vidarino
 
Posts: 295
Joined: 02 January 2006

Re: Uniqueness Type 6 - UR meets X-Wing

Postby ronk » Fri Mar 31, 2006 6:24 pm

Ruud wrote:An X-Wing for digit 9 coincides with a uniqueness rectangle. Placing a 9 in R7C5 or R9C3 would force a 9 in the opposite corner and form a deadly pattern.

The two strong links of an x-wing aren't really required to make just one elimination, however. In addition to the "almost-unique-rectangle", one strong link is sufficient. For example, with only a strong link in row 7:

r9c3-9-r7c3=9=(ALS:r7c5=7|2=r9c3) implying r9c3<>9

The unique thing is that with a 2nd strong link (in row 9), a 2nd elimination may be made with "one step":

r7c5-9-r9c5=9=(ALS:r9c3=2|7=r7c5) implying r7c5<>9

Before baptizing the pattern as a UR instead of an AUR, however, I think it would be prudent to determine the relative frequency of the pattern. That begs the question "relative to what?"

Ron

P.S. vidarino, you *did* post this same pattern here.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby Myth Jellies » Fri Mar 31, 2006 11:28 pm

Though not quite as old as ronk's example, there is another good one illustrated in the BUG-Lite thread. I gave it a combo type 4-5 designation since it had elements of both.:)
Myth Jellies
 
Posts: 593
Joined: 19 September 2005

Postby Carcul » Sat Apr 01, 2006 11:25 am

Ruud wrote:Placing a 9 in R7C5 or R9C3 would force a 9 in the opposite corner and form a deadly pattern.


I don't understand this sentence, but for me the example is a very good one of an Almost Unique Rectangle (as Ronk as already pointed out):

[r9c3]=2|7=[r7c5]-7-[r8c5]-6-[r9c5]-9-[r9c3], => r9c3<>9.

Carcul
Carcul
 
Posts: 724
Joined: 04 November 2005

Diagonal UR

Postby Steve R » Mon Apr 03, 2006 5:29 pm

Does frequency matter so much?

Keith, who made the original observation, has since pointed out the path to some other eliminations. In fact, there seem to be diagonal versions of types 2, 3 and 4 unique rectangles. Why not call them just that?

Steve
Steve R
 
Posts: 74
Joined: 03 April 2006

Re: Diagonal UR

Postby ronk » Mon Apr 03, 2006 5:45 pm

Steve R wrote:Keith, who made the original observation, has since pointed out the path to some other eliminations.

Would you please provide a link or two to those posts? TIA, Ron
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Diagonal UR

Postby Steve R » Mon Apr 03, 2006 6:25 pm

Try here.

Steve
Steve R
 
Posts: 74
Joined: 03 April 2006

Taxonomy

Postby keith » Mon Apr 03, 2006 10:38 pm

Steve:


In fact, there seem to be diagonal versions of types 2, 3 and 4 unique rectangles. Why not call them just that?



Exactly! And then , this "Unique X-wing" is a special case when we have additional conjugate constraints.

By the way, I noticed the same pattern in Ruud's SudoCue Nightmare for today:

http://www.sudocue.net/forum/viewtopic.php?t=109


Best wishes,

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

Postby Havard » Sat Apr 08, 2006 4:32 pm

hi

I was thinking a bit about this, and what a general rule for this elimination might be. I am sure all this has been described many times before, and I do not claim it to be my invention, but I thought I would sum this up for myself, and maybe someone could benefit from it?:)

Let's first look at the UR type 4 rule...

Code: Select all
 ab------ab
  |       |
  |       |
  |   a   |
xabx====xabx

so here my symbols are:
Code: Select all
ab - the Unique Rectangle
xabx - to show that there are any number of more candidates present
=== - marks a strong link, here with the a's


So the logic for type 4 goes:
if you place a [b] in either of [xabx]
Code: Select all
 ab------ab
  |       |
  |       |
  |   a   |
  b=====xabx

then that forces the other [xabx] to become an [a] because they are stronly linked:
Code: Select all
 ab------ab
  |       |
  |       |
  |       |
  b-------a

But this means you get a deadly pattern:
Code: Select all
  a-------b
  |       |
  |       |
  |       |
  b-------a

and hence we can eliminate [b] from both [xabx]'s:
Code: Select all
 ab------ab
  |       |
  |       |
  |   a   |
xax=====xax


And this is the UR type 4 rule as we all know it!:)


If we now look at a scenario with the [xabx]'s in separate corners:
Code: Select all
 ab-----xabx
  |       |
  |       |
  |       |
xabx-----ab

it is now actually enough to have just one strong link between two of the cells to be able to make a elimination, lets link two and see:
Code: Select all
 ab-----xabx
  |       |
  |       |
  |   a   |
xabx=====ab

what would now happen if we put an [a] in the top right xabx:
Code: Select all
 ab-------a
  |       |
  |       |
  |   a   |
xabx=====ab

Then the bottom right [ab] would become a [b]:
Code: Select all
 ab-------a
  |       |
  |       |
  |   a   |
xabx======b

...and then, because of the strong link, the bottom left [xabx] would become a [a]:
Code: Select all
 ab-------a
  |       |
  |       |
  |   a   |
  a=======b

...and we would end up with a deadly pattern again:
Code: Select all
  b-------a
  |       |
  |       |
  |       |
  a-------b

Which means that [a] can NOT go there, and we can eliminate it:
Code: Select all
 ab------xbx
  |       |
  |       |
  |   a   |
xabx=====ab


And put in more general terms we could then say that:
Code: Select all
With a Unique Rectangle with the numbers [ab] that has two cells with "extra candidates" ([xabx]), and these cells are on a diagonal from each other, and you have a strong link between any two of the cells in the Rectangle for candidate [a], then you can eliminate candidate [a] from the cell with extra candidates that is not part of the strong link.


What is quite handy about this generalisation, is that you only need to concider one strong link. In cases where there are more than one, all the other candidates you might be able to eliminate, will follow as single candidates eliminations because of the strong links!

Let's look at the example given:
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  |
'------------'------------'------------'


It is now enough to notice that we have a uniqe rectangle for the 69's, the two cells with "other" candidates in them are diagonaly placed, and that for example the 9's in row 7 are strongly linked, to be able to say that r9c3<> 9. (we could also go: the 9's in column 3 are strongly linked, so r7c6<>9, or the 9's in column 5 are strongly linked, so r9c3<>9, or the 9's in row 9 are strongly linked, so r7c6<>9)
Now because of the other strong links that exists we then get that r7c3=6, and then again that r7c5=9 and then also r9c5=6 and then finally r9c3=9.

In other words no need for a rule that conciders the whole x-wing pattern!

This would also mean that I would disagree slightly with Vidar and call this a variation over the type 4, just because it eliminates the [b]same candidate that are strongly linked, rather then the opposite candidate of the type 4. Don't you think this would get confusing if you blended the two into one "type" ? However, they both only need one strong link, so there are of course a lot of similarities too...:) Any opinions?

Finally I would like to show this little freak:
Code: Select all
 ab=====xabx
  |  a   ||
  |     b||
  |      ||
xabx----xabx


where this:
Code: Select all
 ab=====xabx
  |  a   ||
  |     b||
  |      ||
  a-----xabx

leads to:
Code: Select all
  b=====xabx
  |  a   ||
  |     b||
  |      ||
  a-----xabx

Code: Select all
  b-------a
  |      ||
  |     b||
  |      ||
  a-----xabx

Code: Select all
  b-------a
  |       |
  |       |
  |       |
  a-------b


...and hence you can do this elimination:
Code: Select all
 ab=====xabx
  |  a   ||
  |     b||
  |      ||
 xbx----xabx


enjoy!:D

Havard
Havard
 
Posts: 377
Joined: 25 December 2005

Postby Havard » Sun Apr 09, 2006 2:42 pm

... and just to complete the madness:

if you have this:
Code: Select all
xabx====xabx
 ||   a  ||
 ||b    b||
 ||      ||
xabx----xabx


you can eliminate both a's in the bottom line:
Code: Select all
xabx----xabx
  |      |
  |      |
  |      |
 xbx----xbx


type 7 ?:)

Havard
Havard
 
Posts: 377
Joined: 25 December 2005

Postby ronk » Mon Apr 10, 2006 9:27 am

Havard wrote:This would also mean that I would disagree slightly with Vidar and call this a variation over the type 4, just because it eliminates the same candidate that are strongly linked, rather then the opposite candidate of the type 4. Don't you think this would get confusing if you blended the two into one "type" ? However, they both only need one strong link, so there are of course a lot of similarities too...:) Any opinions?

To me, it's not clear if you think the pattern -- the diagonal-UR and x-wing overlay -- should be considered a variation of type 4 or a new type 6. Please clarify.

My preference is to group most deductions using unique rectangles and one or more conjugate links into type 4. Then I can go to my little "UR Type 4 Reference Card":D to determine the appropriate subtype. An obvious exception would be this little 'gem':

Havard wrote:
Code: Select all
xabx====xabx
 ||   a  ||
 ||b    b||
 ||      ||
xabx----xabx

[edit: Color me surprised if that pattern even exists after the application of simpler techniques. However], I like the following:

Havard wrote:
Code: Select all
 ab=====xabx
  |  a   ||
  |     b||
  |      ||
xabx----xabx

It should occur much more frequently than the diagonal-UR and x-wing overlay, aka, the proposed 'type 6'.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby Havard » Mon Apr 10, 2006 1:56 pm

ronk wrote:
Havard wrote:This would also mean that I would disagree slightly with Vidar and call this a variation over the type 4, just because it eliminates the same candidate that are strongly linked, rather then the opposite candidate of the type 4. Don't you think this would get confusing if you blended the two into one "type" ? However, they both only need one strong link, so there are of course a lot of similarities too...:) Any opinions?

To me, it's not clear if you think the pattern -- the diagonal-UR and x-wing overlay -- should be considered a variation of type 4 or a new type 6. Please clarify.


Well I don't really know... I guess if I could have it the way I wanted it, I would go:

Type 1: UR with just one cell that does not have the UR-pair. Eliminate the UR-pair in that cell

Type 2: UR with one extra candidate in addition to the UR-pair. (can be attached to any of the UR-cells) Eliminate all other occurences of that candidate that can see all of the UR-ones.

Type 3: UR with two extra candidates in addition to the UR-pair. Can create a locked set with other cells, as long as all the UR-extra-candidates-cells are concidered one cell in the locked set, and of course all cells in the locked set can see eachother...

Type 4: UR with two cells that have extra candidates in addition to the UR-pair, and these two cells are on the same line, and have a strong link between one of the two UR-numbers in both those cells. You can then eliminate the other UR-number in both those cells.

Type 5: UR with two cells that have extra candidates in addition to the UR-pair, and these two cells are on a diagonal from each other, and you have a strong link between one of the two UR-numbers in any two cells. You can then eliminate that UR-number in the cell with extra candidates that are not part of the strong link.

Type 6: UR with three cells that have extra candidates in addition to the UR-pair, and with two strong links that are connected, and alternating between the two UR-numbers and that have to start from the one cell that does not have extra candidates. You can then eliminate the same candidate as the first strong link uses(going from the cell with no extra), in the one cell that does not have any strong links attached to it...

Type 7: UR where all four cells have extra candidates, and where you have three strong links alternating between the two UR-numbers. You can then eliminate both occurences of the candidate that are only linked once, in both opposite cells to that link.

This means that the old type 5 just becomes a Type 2.
It is of course tempting to make type 4 and 5 the same, but since they eliminate different candidates, I think they should have a type each...:)

And about the frequency:
In the first tests I have done, it looks like type 4,5 and 6 are just about equally common, and they all score much higher than 1,2 and 3. Have not tested type 7 yet...

Would be cool if anyone else wanted to check this!:)

Havard
Havard
 
Posts: 377
Joined: 25 December 2005

Postby ronk » Wed Apr 12, 2006 1:56 am

Havard wrote:This means that the old type 5 just becomes a Type 2.

While I agree with deprecating Type 5 to a Type 2 variant, specifically Type 2C, I don't agree with re-using the Type 5 name for another definition. Doing so will just cause unnecessary confusion.

And although my original reaction to Ruud's proposal for the Type 6 was similar to yours, I now think we should accept his proposal. That means your three proposals would be bumped up to Types 7, 8, and 9.

My solver produced the frequency results below. To make it easier to attach meaning to the numbers, I'll first list terse descriptions of the 9 UR types.

Code: Select all
Terse UR type descriptions:

Type 1: one UR cell with extra candidates
Type 2: two UR cells in a line, each with one identical extra candidate
Type 3: two UR cells in a line, each with at most two identical candidates
Type 4: strong link between two UR cells in a line, each with extra candidates
Type 5: two diagonal UR cells each with one identical extra candidate
Type 6: naked UR pair in diagonal cells, plus x-wing in one digit of UR pair
Type 7: two diagonal UR cells with extra candidates, plus one strong link
Type 8: three UR cells with extra candidates, plus two strong links
Type 9: all four UR cells with extra candidates, plus three strong links


Code: Select all
Exclusions from top1465:

Type 1: 120 exclusions in 60 cells
Type 2:  84 excl.
Type 3:  34 excl. (minimum) in 34 cells
Type 4: 110 excl.
Type 5:   0 (not implemented)
Type 6:   8 excl.
Type 7:  28 excl.
Type 8:  69 excl.
Type 9:   0 (implemented, but none detected)


[edit: revised Type 6 description, no change to Type 6 results]
Last edited by ronk on Mon Apr 17, 2006 11:42 am, edited 1 time in total.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Questions

Postby keith » Fri Apr 14, 2006 11:30 pm

Let me first say that I think this thread is fascinating! I like the way these uniqueness tests are being blended with "traditional" techniques to make new solving strategies.

I do have a couple of questions:

Question 1:

Is it possible for a UR to belong to more than one of the 9 types given by Havard? In other words, can I make eliminations based on a type 3 pattern, and then make type 4 eliminations on the same UR?

(I can post an example of my confusion, which is the SudoCue Nightmare for today, April 14.)

Question 2:

Havard wrote:
Type 3: UR with two extra candidates in addition to the UR-pair. Can create a locked set with other cells, as long as all the UR-extra-candidates-cells are concidered one cell in the locked set, and of course all cells in the locked set can see eachother...


Would it not be more accurate to say that the UR-pair is one cell in the locked set? Since the UR-pair can occupy only one of two cells in the UR. Then, the locked set of 2+N possibilities will only occupy 1+N cells?

To say it another way: The extra candidates will be fully represented in the solution of the locked set. Only one (of two) of the UR candidates will be there.

Thanks to all,

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

Next

Return to Advanced solving techniques