Type 3 Unique Rectangles - Hidden Subsets?

Advanced methods and approaches for solving Sudoku puzzles

Postby RW » Sat May 13, 2006 6:49 pm

ronk wrote:Given the precedent set by the Type 3 UR, how would you word a definition to keep the Type 3 as a UR, but define keith's discovery as not a UR?


Well, I never really thought of the type 3 as a UR, to me it's a UR plus one pair (or whatever it takes to make the subset). But I don't see any point in trying to change the standard terminology around here, so I use the term "type 3" on this forum anyway.

Mike Barker wrote:For now we have one list and it is reasonable to include all types so that 1) others don't have to reinvent the wheel (although they are welcome to), 2) if they do is easy to show that they have, 3) we can build on and correct what has gone on before. That being said, I have no problem with these additional types and others which may come along


I must agree with Carcul that these should be thought of as short loops or chains involving AURs. Listing the possible patterns with one extra cell might still be reasonable, but adding more extra cells would make the list more intimidating than useful. Here's 10 more patterns with 2 extra cells that I came up with in a couple of minutes (eliminate a from abY):

Code: Select all
abz    abz    xz
ab     abY    abx
Code: Select all
abz    ab     bz
abx    abY    ax
Code: Select all
abx     ab     bxz    bxz
ab      abY
Code: Select all
abx    ab
----------
axz    abz
abx    abY
Code: Select all
abz    ab     bz
abx    abY    xz
Code: Select all
abz    ab     bxz
ab     abY    bx
Code: Select all
az
ab     ab
----------------
abxz   abY    ax
Code: Select all
ax   
abz    ab     bz
----------------
abx    abY   
Code: Select all
abxz   ab
----------
axz   
axz   
abxz   abY
Code: Select all
ab     abxz
-----------
       abxz
       abxz
ab     abY


There's most likely lots of other possibilities to add here. Allowing one strong link would probably double the possibilities and adding a third cell would make the list a nightmare.

Don't get me wrong, I think all of these are great patterns to use when you solve a puzzle. I just wanted to express my consern for the Unique Rectangle, it's purity and it's future.

RW
RW
2010 Supporter
 
Posts: 1000
Joined: 16 March 2006

Re: Credit where credit is due

Postby ravel » Sat May 13, 2006 7:56 pm

keith wrote:(If someone can tell me how to link down to the actual message, I'll add the specific link here.)

You have to add "&start=" to the link followed by the number of the posting. It is 0 for the first one, 15 for the first on page 2 and so on.

Concerning the UR-types i agree with Carcul and RW (also think of type 3 as an AUR). I neither will memorize all these types nor solve puzzles with a booklet containing them to be able to look for an appropriate pattern. So i am happy to see samples like this one from Keith, but i think the rest is mainly for programmers.
ravel
 
Posts: 998
Joined: 21 February 2006

Re: Credit where credit is due

Postby ronk » Sat May 13, 2006 9:38 pm

keith wrote:If someone can tell me how to link down to the actual message, I'll add the specific link here.

Although it's sometimes troublesome to get the absolute post number, I've always used the style used in email notifications. For example ... http://forum.enjoysudoku.com/viewtopic.php?p=28058#p28058 ... takes you to your post.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby ronk » Sat May 13, 2006 10:02 pm

Instead of discussing whether keith's find is a UR or an AUR, maybe we should be spending time figuring out whether occurrences of keith's find are rare, common, or frequent. Then, if it is just as common as the type 3 -- rightly or wrongly -- I believe it should be elevated to UR status.

But I think the definition should restrict the configuration to one locked set -- that includes one or two UR cells with extra candidates -- directly linked (chained) to another UR cell with extra candidates. That's effectively the donfiguration of the Type 3 UR.

And as for listing all the different subset sizes, forget it. We don't do that for the Type 3, do we?
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby RW » Sun May 14, 2006 12:52 pm

ronk wrote:Instead of discussing whether keith's find is a UR or an AUR, maybe we should be spending time figuring out whether occurrences of keith's find are rare, common, or frequent.


My guess is that it is common. I just had a look at the puzzle Keith presented in the beginning of this thread and found two of these:

Code: Select all
ab     ab
abx    abY    ax


and one
Code: Select all
ab     ab   
abxz   abY    ax    xz


plus a UR type 3, a BUG-lite and other nice patterns. Love the puzzle!:)

Finally I found one

Code: Select all
ab    ab
---------
axz   aw    wz
abx   abY


That advanced the puzzle to a BUG+2 that cracked it. Love the puzzle a lot!:D

RW
RW
2010 Supporter
 
Posts: 1000
Joined: 16 March 2006

Postby Mike Barker » Wed May 17, 2006 3:26 am

I like the idea of programming up at least some of the options to see what they buy, but before I do I want to make sure I'm not unnecessarily restricting possible elimination. I've updated the list of new eliminations based on previous posts and see some significant differences in how things are presented as well as adding some options which I knew were missing (UR+3K and UR+4K). Although I don't use the term ALS (the descriptions seemed easier by describing the key characteristics rather than using ALS terminology) clearly that is what is being used. Obviously the definitions can apply with "a" and "b" switched or with "x", "Y", etc switched.

--- UR+2kx: two cells in a line, one with an extra candidate, "x", and one with at least one other extra different candidate, "Y", plus "(b)(a)x" common to "abx" which can contain “a” and which can also contain "b" if common to the "ab" which is in line with "abY" => "a" can be removed from "abY".
Code: Select all
ab     ab         
abx    abY  (b)(a)x

--- UR+2kd: two diagonal cells one with an extra candidate, "x", and one with at least one other extra different candidate, "Y", plus "(a)(b)x" common to "abx" which can contain “b” and which can also contain "a" if common to "abY" => "a" can be removed "abY".
Code: Select all
ab     abY       
abx    ab   (a)(b)x

--- UR+2KX: two cells in a line, with extra candidates "X" and "Y" plus extra cells, "(b)(a)U...", which can contain “a”, such that U is a locked set which includes "X", "abX" is seen by all cells of "(b)(a)U..." which contain elements of "X", and "(b)(a)U..." can contain "b" if the "ab" which is in line with "abY" is seen by all of the cells of "(b)(a)U..." which contain "b" => "a" can be removed from "abY".
Code: Select all
ab     ab             
abX    abY  (b)(a)U...

--- UR+2KD: two diagonal cells, with extra candidates "X" and "Y" plus extra cells, "(a)(b)U...", which can contain “b”, such that U is a locked set which includes "X", "abX" is seen by all cells of "(a)(b)U..." which contain elements of "X", and "(a)(b)U..." can contain "a" if "abY" is seen by all cells of "(a)(b)U..." which contain "a" => "a" can be removed from "abY".
Code: Select all
ab     abY       
abX    ab   (a)(b)U...

--- UR+3kx: three cells, two with one extra candidate, "abx" and "abz", and one with at least one other extra candidate, "abY", plus "(a)(z)x" common to "abx" and which can contain "a" if common to "abY" and/or "z" if common to "abz" and "(a)(x)z", plus "(a)(x)z" common to "abz" and which can contain "a" if common to "abY" and "x" if common to "abx" and "(a)(z)x" => "a" can be removed "abY".
Code: Select all
ab      abz  (a)(x)z 
abx     abY  (a)(z)x

--- UR+3kd: three cells, two with one extra candidate, "abx" and "abz", and one with at least one other extra candidate, "abY", plus "(a)(b)(z)x" common to "abx" and which can contain "a" if common to "abY", "b" if common to "ab" and/or "z" if common to "abz" and "(a)(b)(x)z", plus "(a)(b)(x)z" common to "abz" and which can contain "a" if common to "abY", "b" if common to "ab", and/or "x" if common to "abx" and "(a)(b)(z)x" => "a" can be removed "abY".
Code: Select all
abz     ab   (a)(b)(x)z 
abx     abY  (a)(b)(z)x

--- UR+3KX: three cells with extra candidates "X", "Y", and "Z", plus extra cells, "aU...", such that U is a locked set which includes "X", "abX" is seen by all cells of "aU..." which contain elements of "X", and "abY" is seen by all cells of "aU..." which contain "a", plus additional extra cells "aV...", such that V is a locked set which includes "Z", "abZ" is seen by all cells of "aV..." which contain elements of "Z", and "abY" is seen by all cells of "aV..." which contain "a" => "a" can be removed from "abY". Note that "U", and "V" need not be disjoint.
Code: Select all
ab      abZ  aV... 
abX     abY  aU...

--- UR+3KD: three cells with extra candidates "X", "Y", and "Z", plus extra cells, "(a)(b)U...", such that U is a locked set which includes "X", "abX" is seen by all cells of "(a)(b)U..." which contain elements of "X", and "(a)(b)U..." can contain "a" if "abY" is seen by all cells of "(a)(b)U..." which contain "a" and/or "(a)(b)U..." can contain "b" if "ab" is seen by all cells of "(a)(b)U..." which contain "b", plus additional extra cells "(a)(b)V...", such that V is a locked set which includes "Z", "abZ" is seen by all cells of "(a)(b)V..." which contain elements of "Z", and "(a)(b)V..." can contain "a" if "abY" is seen by all cells of "(a)(b)V..." which contain "a" and/or can contain "b" if "ab" is seen by all cells of "(a)(b)V..." which contain "b" => "a" can be removed from "abY". Note that "U", and "V" need not be disjoint.
Code: Select all
abZ     ab   (a)(b)V... 
abX     abY  (a)(b)U...

--- UR+4kx: four cells, three with one extra candidate, "abx", "abz", and "abw", and one with at least one other extra candidate, "abY" similar to UR+4KX with U, V, and T some appropriate combination of {"(a)(w)(z)x", "(a)(x)(w)z", "(a)(x)(z)w"} => "a" can be removed "abY".
Code: Select all
abw     abz  (a)(x)(w)z (a)(x)(z)w
abx     abY  (a)(w)(z)x

--- UR+4KX: four cells with extra candidates "X", "Y", "Z", and "W", plus extra cells, "aU...", such that U is a locked set which includes "X", "abX" is seen by all cells of "aU..." which contain elements of "X", and "abY" is seen by all cells of "aU..." which contain "a", plus additional extra cells "aV...", such that V is a locked set which includes "Z", "abZ" is seen by all cells of "aV..." which contain elements of "Z", and "abY" is seen by all cells of "aV..." which contain "a", plus additional extra cells "aT...", such that "T" is a locked set which includes "W", "abW" is seen by all cells of "aT..." which contain elements of "W", and "abT" is seen by all cells of "abY" which contain "a" => "a" can be removed from "abY". Note that "U", "V", and "T" need not be disjoint.
Code: Select all
abW     abZ  aV... aT...
abX     abY  aU...

RW has also developed two techniques which use something like an Empty Rectangle.
--- UR+4rx: two cells in a line and box, with extra candidates, "X" and "Y", plus "b" only exists possibly in "abX" and in line with the rightmost "ab" and "abY" => "a" can be removed from "abY"
Code: Select all
ab    ab
----------
abX - abY
 -  - (b)...
 -  - (b)...

--- UR+4rd: two diagonal cells, with extra candidates, "X" and "Y", with "abX" and the rightmost "ab" in a box, plus "a" only exists possibly in "abX" and in line with the rightmost "ab" and "abY" => "a" can be removed from "abY"
Code: Select all
ab    abY
----------
abX - ab
 -  - (a)...
 -  - (a)...



Here are how RW's later set of ALS examples maps into the above definitions. There are a couple which, as far as I can tell, do not map into ALS and thus not into the definitions. I'm happy to let these go for now and deal with them later.
Code: Select all
UR+3KD: X=z, Z=z, U={xz,abx}, V=U
abz    abz    xz
ab     abY    abx
 
UR+3kd:
abz    ab     bz
abx    abY    ax
 
UR+2KD: U={"bxz", "bxz"}
abx     ab     bxz    bxz
ab      abY
 
UR+3KD: X=x, Z=x, U={axz,abz}, V=U
abx    ab
----------
axz    abz
abx    abY
 
UR+3KD: X=x, Z=z, U={bz,xz}, V={bz}
abz    ab     bz
abx    abY    xz
 
UR+2KD: X=z, U={bxz,bx}
abz    ab     bxz
ab     abY    bx
 
Non-ALS configuration:
az
ab     ab
----------------
abxz   abY    ax
 
Non-ALS configuration:
ax   
abz    ab     bz
----------------
abx    abY   
 
UR+3KD: X=xz, Z=xz, U={axz,axz}, V=U
abxz   ab
----------
axz   
axz   
abxz   abY
 
UR+2KX: X=xz, U={abxz,abxz}
ab     abxz
-----------
       abxz
       abxz
ab     abY

Although trying to figure out the general rules has been fun, its time to start programming and see what else I missed.
Last edited by Mike Barker on Fri May 26, 2006 9:13 am, edited 7 times in total.
Mike Barker
 
Posts: 458
Joined: 22 January 2006

Postby ronk » Wed May 17, 2006 11:35 am

Mike Barker wrote:
Code: Select all
ab   | abY       
abx  | ab   (a)(b)x

I assume the parenthesis for "(a)(b)x" stands for the possibility of either "ax" or "bx". If so, I see little gained over just writing ...
Code: Select all
ab   | abY       
abx  | ab   ax

It is understood -- or should be understood -- that 'a' represents either of the UR digits.

In the following ...
Code: Select all
ab   | ab       
abx  | abY   ax

... it is likewise "understood" that the "ax" can be anywhere in the "abx-ax" row, even though the stack line is shown, and which I think should always be shown [edit: in formal definitions].

My head is already spinning, so I'll retry understanding the more complex parts of your post later.:D
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby Mike Barker » Wed May 17, 2006 1:08 pm

The following all allow elimination of "a" in "abY"
Code: Select all
ab   | abY       
abx  | ab   ax  (ax is seen by "abx" and "abY")

ab   | abY       
abx  | ab   bx  (bx is seen by "abx" and "ab")

ab   | abY       
abx  | ab   abx  (abx is seen by "abx", "abY", and "ab")

plus all of the other permutations RW can come up with. Especially the second form is not just swapping the definitions of "a" and "b" and the last allows "abx" as the "key" cell - bad name, but it was late, I needed a letter for the identification and used "k" for Keith, but also decided it identified the need for the extra cell which was key to the technique. Also, because of the symmetry of the template, I no longer need to differentiate between patterns in which only one candidate can be eliminated and ones (like the last one here) which allow both.

Also I don't show the line stack, because then the template is more complicated because there are at least two (vertical and horizontal) which again complicates the template. IMO it was better to focus on which UR cells see the "(a)(b)x" cell which is equivalent.
Mike Barker
 
Posts: 458
Joined: 22 January 2006

Postby ronk » Wed May 17, 2006 6:00 pm

Mike, it appears your "(a)(b)x" meant either "abx" or "ax" or "bx"?

Mike Barker wrote:The following all allow elimination of "a" in "abY"
Code: Select all
ab   | abY       
abx  | ab   ax  (ax is seen by "abx" and "abY")

ab   | abY       
abx  | ab   bx  (bx is seen by "abx" and "ab")

ab   | abY       
abx  | ab   abx  (abx is seen by "abx", "abY", and "ab")

For the third, I think saying "abx is seen by (...) ab" is structurally redundant. For the second, "bx is seen by (...) ab" is also redundant. That makes the 1st and 3rd much alike, and can be covered by the single exemplar ...
Code: Select all
 
ab   | abY        |
abx  | ab   (ab)x | 

excludes both 'a' and 'b' from the abY cell
neither 'a' nor 'b' need exist in the "(ab)x" cell.

That leaves ...
Code: Select all
ab   | abY 
abx  | ab   bx

excludes 'a' from the abY cell

The lack of a 2nd stack line indicates "bx" can be anywhere in the "abx" row. No other notes should be required IMO.
Last edited by ronk on Wed May 17, 2006 2:30 pm, edited 2 times in total.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby gsf » Wed May 17, 2006 6:20 pm

are there any puzzle examples for the UR types being discussed?
gsf
2014 Supporter
 
Posts: 7306
Joined: 21 September 2005
Location: NJ USA

Postby RW » Wed May 17, 2006 6:40 pm

gsf wrote:are there any puzzle examples for the UR types being discussed?


The puzzle Keith posted in the first post on this thread, Simple Sudoku and one type 3 UR advances the puzzle here:

Code: Select all
.....1..8.82.........93.......897......1...3...5...2..3..6...1.9..2....46.73.....

 *-----------------------------------------------------------*
 | 457   9     3     | 57    2     1     | 6     457   8     |
 | 157   8     2     | 57    4     6     | 159   579   3     |
 | 57    46    16    | 9     3     8     | 145   2457  25    |
 |-------------------+-------------------+-------------------|
 | 2     3     16    | 8     9     7     | 45    45    16    |
 | 48    46    9     | 1     5     2     | 78    3     67    |
 | 18    7     5     | 4     6     3     | 2     89    19    |
 |-------------------+-------------------+-------------------|
 | 3     25    4     | 6     8     9     | 57    1     257   |
 | 9     1     8     | 2     7     5     | 3     6     4     |
 | 6     25    7     | 3     1     4     | 589   2589  259   |
 *-----------------------------------------------------------*


In r3c1789 and r4c78 there's a

[edit: fixed a typo in the pattern.]
Code: Select all
ab     ab   
abxz   abY    ax    az


a=5, b=4, x=2, z=7 - eliminate 5 from r3c7 (abY)
(if r3c7=5 => r3c9=2 => r3c1=7 => r3c8=4)

In r5c7, r7c279 and r9c279 there's also a

Code: Select all
ab    ab
---------
axz   aw    wz
abx   abY


a=5, b=2, w=7, z=8, x=9 - eliminate 5 from r7c9 (abY)
(if r7c9=5 => r7c7=7 => r5c7=8 => r9c7=9 => r9c9=2)

As you can see these are just short AUR loops, defined as specific patterns. Lot's of fun to play around with, probably found in almost any puzzle if you look hard enough.

RW
Last edited by RW on Wed May 17, 2006 3:06 pm, edited 1 time in total.
RW
2010 Supporter
 
Posts: 1000
Joined: 16 March 2006

Postby Mike Barker » Wed May 17, 2006 6:56 pm

Ron, good catch. I've simplified the descriptions accordingly. Actually I changed them back to what they were before my final mods - changing answers late at night is not a good thing! This is why I like to try to summarizes results - usually good things come from another set of eyes (or in this case another hundred). Also I should have said
plus hopefully all of the other permutations RW can come up with which conform to this basic UR/ALS technique (though I doubt it)

instead of
plus all of the other permutations RW can come up with
Mike Barker
 
Posts: 458
Joined: 22 January 2006

Postby ronk » Sat May 20, 2006 8:32 pm

I have been unable to find a real-life example of the following:
Code: Select all
abc  ab    .   | abY  .      .     
.    .     .   | .    .      .     
.    abc   .   | ab   .      .     

abc in the intersection of the AUR's abY row and the AUR's abc box
excludes 'a' and 'b' from abY

Has anyone else spotted one? Is there a fundamental reason they don't exist?
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby RW » Mon May 22, 2006 8:12 am

ronk wrote:
Code: Select all
abc  ab    .   | abY  .      .     
.    .     .   | .    .      .     
.    abc   .   | ab   .      .     

Is there a fundamental reason they don't exist?


They should exist, but they also ought to be very rare. The main problem is eliminatin the 'c' from the 'ab' cell in the left box. It can't have an C in the same unit, would eliminate the 'c' from at least one other 'abc' cell as well. Same goes for line box interaction. The 'ab' cell cannot be part of a hidden subset that eliminates 'c' either as long as there is 'ab' in both 'abc' cells. To create the pattern you would need at least an x-wing to eliminate the 'c'. Xy-wing, coloring or other advanced techinques could also do the trick.

RW
RW
2010 Supporter
 
Posts: 1000
Joined: 16 March 2006

Postby ronk » Thu May 25, 2006 8:44 pm

To anyone thinking about coding this technique ... there are greener pastures elsewhere !!!

Using the top1465 as source data, this technique yielded 104 exclusions in 97 cells, but my solver now solves -- using logic only -- one less puzzle than before. Incrementally, #652 is advanced to solution, but #606 and #1086 are now no longer being solved. (That's for chains with only one cell other than the UR, which in keeping with the thread title would be mostly "hidden pairs".)

Has anyone seen better results?
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

PreviousNext

Return to Advanced solving techniques