The New Sudoku Players' Forum

[keith]

Type 3 Unique Rectangles - Hidden Subsets?

Most of us are familiar with Type 3 Unique Rectangles. Let me define them as being in the four cells:

A|C
B|D

which contain the pattern:

12|123
12|124

And, there are no conjugate constraints on <1> or <2> in C and D.

(Conjugate constraints lead to Type 4 reductions on the same pattern.)

<1> and <2> are the "deadly possibilities": At least one of C or D must not be one of these.

Now, the usual Type 3 reduction is this: One of C or D must be <3> or <4>. If there is another cell, "E", in the house(s) shared by C and D that has the possibilities <34>, then <3> and <4> can be eliminated as possibilities from all other cells in the house(s).

E is said to form a naked pair with the non-deadly possibilities in C and D.

There is an obvious extension to naked subsets when C and / or D contain extra possibilities. Also, in the above example, if we found two cells in the same house containing, say, <35> and <45>, we also have a naked subset, albeit involving a possibility that is not in A or B.

But, is this all?

I have found a few discussion threads that mention Type 3 reductions involving "hidden subsets", but they do not seem to come down to a clear definition of what this is, and what to do about it.

I do, though, have the following example from a real puzzle:

12|123
12|124

and there is another cell "E", in the same house as C and D, with possibilities E = <13>. It is immediately apparent that <1> can be excluded from D!

(OK, I confess: It is immediately apparent to me after thinking about it for a week. The solutions for {C,D,E} are {1,4,3}, {2,4,13}, or {3,2,1}.)

Sudoku Susser does not identify this pattern or reduction.

Questions:

1. Has someone figured this out? (Surely, someone must have?)

2. To me, this is Type 3, for it does not involve conjugate constraints on the deadly candidates. It is different, in that it eliminates a possibility in the UR corners, rather than their buddy cells. Can anyone send me to a thread on this? (Other than the UR threads in Mike Barker's sticky.)

3. Are you guys going to classify this as Type 19C-a?


Best wishes,

Keith

And, here is the example: Go for it!

Code: Select all


. . .|. . 1|. . 8
. 8 2|. . .|. . .
. . .|9 3 .|. . .
-----------------
. . .|8 9 7|. . .
. . .|1 . .|. 3 .
. . 5|. . .|2 . .
-----------------
3 . .|6 . .|. 1 .
9 . .|2 . .|. . 4
6 . 7|3 . .|. . .


[tarek]

Hi Keith,

This has been discussed before here.

[keith]

Tarek,

I took a quick look. I saw a discussion. I did not see a resolution.

Thank you.

Keith

[Havard]

Hi Keith!

I am a bit confused, because I looked at your pattern and instantly thought: "yup, that one is covered...", but then I started looking for where I had seen it, and it turned out that I could not find the exact same thing you are talking about...

The pattern I thought had it covered, was something like this from the exellent list Mike has put together:

Code: Select all

UR+3/1SL: two or three UR cells with extra candidates (Z is optional), plus one strong link and at least one extra cell
--- UR+3x/1SL: "Y" is a single candidate "y", the extra cell "(ab)y" consists of "ay", "by", or "aby" and shares a house with "abX" and "ab(Z)" or consists of "ay" and shares a line with "ab(Z)" => "b" can be removed from "abX".

 ab  |  abX
     |   |
     |   |a
     |   |
aby  |  ab(Z)  (ab)y


Now your pattern would look like this (I think):

Code: Select all

 ab  |  ab
     |     
     |     
     |     
aby  |  abX   ay
 
remove a from abX.


proof:

Code: Select all

if abX is "a":

 ab  |  ab
     |     
     |     
     |     
aby  |  a   ay


Code: Select all

...ay is "y", and aby is by:

 ab  |  ab
     |     
     |     
     |     
 by  |  a   y


Code: Select all

...and we get deadliness.

 a   |  b
     |     
     |     
     |     
 b   |  a   y


Let's try with both cells from the UR:

Code: Select all

 ab  |  ab
     |     
     |     
     |     
aby  |  abX   aby
 
remove ab from abX.


Code: Select all

if abX is "a":

 ab  |  ab
     |     
     |     
     |     
aby  |  a    aby


Code: Select all

...you get:

 a   |  b
     |     
     |     
     |     
 by  |  a    by


And I admit that I am a bit tired right now, but I can't see that there is any problems with this? (not leading to a deadly pattern) This again would make me question the:

consists of "ay", "by", or "aby"

. As far as I can see the "aby" case, ends up in the exact same position, and is hence not valid...? Should it not only be "ay" and "by"? Is really the elimination valid for "aby"?

However, if you use the subset construction rules on the matter, we could easily extend this to:

Code: Select all

 ab  |  ab
     |     
     |     
     |     
ab+xy|  abZ   ay   ax
 
remove a from abZ.


and hence also:

Code: Select all

 ab   |  ab
      |     
      |     
      |     
ab+wxy|  abZ   awxy   awxy   awxy
 
remove a from abZ.


And now for the general principle:

if you have a UR where two cells have extra candidates X and Z:

Code: Select all

 ab  |  ab
     |     
     |     
     |     
abX  |  abZ   


You can treat all the candidates X and one of a or b as one cell in a Locked Set. (So that you treat abX as either aX or bX) If you are able to construct this Locked Set, you can eliminate the candidate used (a or b) in abZ. (given that abZ can "see" all occurences of "a" in the Locked Set...of course)

Havard

[Mike Barker]

As near as I can tell Keith's pattern and Havard's extension are new:
--- UR+2b: two cells, not necessarily in a line, one with an extra candidate, "x", and one with at least one other extra different candidate, "Y" (if they are both x then this is just Type 2) plus a naked "ax" common to "abx" and "abY" => "a" can be removed "abY"

Code: Select all

ab     ab
abx    abY  ax

--- UR+2B: two cells, not necessarily in a line, with extra candidates "X" and "Y" plus extra cells common to "abX" and "abY" such that with "a" excluded the extra cells (not all of which must contain "a") form a locked set including "X" => "a" can be removed from "abY"

Code: Select all

 ab    ab
abX   abY (a)U (a)V ...

I'll add it to the list here. Note no stack divisions, because the eliminations are true regardless of whether the "ax" or "(a)U" is in the same box or not.

Havard, I think the issue is that the "consists of "ay", "by", or "aby" applies to a case with a strong link which this is not.

[ronk]

As near as I can tell Keith's pattern and Havard's extension are new:
--- UR+2b: two cells, not necessarily in a line, one with an extra candidate, "x", and one with at least one other extra different candidate, "Y"
(...)

Code: Select all

ab     ab
abx    abY  ax


(...)
Note no stack divisions, because the eliminations are true regardless of whether the "ax" or "(a)U" is in the same box or not.

Keith, great find. Mike, I added the highlighting above, as I think the not necessarily in a line means that stack division is important. For example ...

Code: Select all

ab   | abY
abc  | ab   ac

... is a valid elimination of 'a' from the abY cell, but the following is not.

Code: Select all

ab     abY
-----------------
abc    ab   ac

Also, with the extra candidates on a diagonal, the "hidden set" cells containing 'a' are restricted to the box containing abY (except for the other diagonal cell, of course). For example ...

Code: Select all

ab    | abY           |
abcde | ab  acde acde | cde

... is still a valid elimination of 'a' from the abY cell.

That was all just a long-winded way of saying the abY cell must see all (non-UR) a's of the "hidden set".

[tarek]

Having looked again, this thread deals with the hidden subset's target is one of the rectangles cells, different from what was thought before that the quantum cell forms part of a hidden subset (a type 3 pattern), here is a reminder of 2 examples why the type 3 pattern was not valid:

Code: Select all

*--------------------------------------------------------*
| 5     89    4    | 1     2     3    | 6     89    7    |
| 7     3     6    | 5     89    89   | 2     4     1    |
| 28    1     289  | 4     7     6    | 5     89    3    |
|------------------+------------------+------------------|
| 48    689   3    | 678   489   5    | 1     67    2    |
| 248   2568  7    | 68    3     1    | 9     56    48   |
| 1     5689  89   | 2     4689  789  | 3     567   48   |
|------------------+------------------+------------------|
| 6     278   28   | 9     1     78   | 4     3     5    |
| 3     4     5    | 678   68    2    | 78    1     9    |
| 9     78    1    | 3     5     4    | 78    2     6    |
*--------------------------------------------------------*
Candidates 467 form a Quantum cell as Candidates 89 in r2c5,r2c6,r6c5 & r6c6 form a unique quadrangle which leads to:
r6c2 Must only have 56 as valid Candidates (4567 is a Hidden Quad in Row 6)
r6c9 Must only have 4 as valid Candidates (4567 is a Hidden Quad in Row 6)
*-----------------------------------------------------------------*
| 79     3      48    | 2      6      45    | 1      57     89    |
| 1      6      5     | 8      79     79    | 3      2      4     |
| 79     28     24    | 345    34     1     | 89     57     6     |
|---------------------+---------------------+---------------------|
| 35     7      1     | 345    8      45    | 6      9      2     |
| 235    28     236   | 13579  13     679   | 48     134    17    |
| 4      9      368   | 137    2      67    | 5      13     178   |
|---------------------+---------------------+---------------------|
| 23     14     23    | 6      79     8     | 79     14     5     |
| 8      5      9     | 147    14     2     | 47     6      3     |
| 6      14     7     | 49     5      3     | 2      8      19    |
*-----------------------------------------------------------------*
Candidates 56 form a Quantum cell as Candidates 23 in r7c1,r7c3,r5c1 & r5c3 form a unique quadrangle which leads to:
r5c4 Must only have 59 as valid Candidates (569 is a Hidden Triple in Row 5)
r5c6 Must only have 69 as valid Candidates (569 is a Hidden Triple in Row 5)

These will lead to a contradiction

tarek

[Myth Jellies]

They look like nice short useful uniqueness chains to me...

Code: Select all

 ab   |^ab
%abx  |*abY $ax


Given the above, you have a strong inference between the x and Y in the abx and abY cells due to the deadly pattern. Thus you can construct the following Alternating Inference Chains (AICs)...

#1: *Y = %x - $x = $a
#2: *Y = %x - $x = $a - ^a = ^b

#1 means that Y is true in the abY-cell and/or 'a' is true in the ax-cell. Either one will eliminate 'a' from abY. #2 shows that b is removed from abY as well.

Code: Select all

 ab   | ab   .  . |
%abx  |*abY  .  . |$ax


In the above setup, only AIC #1 is valid, so you can only eliminate 'a' from abY.

With this one...

Code: Select all

ab     abY
-----------------
abc    ab   ac

...you don't have a #1 chain, but you do have the #2-like chain
Y = c - c = a - a = b
which will eliminate the 'b' from the abY-cell, even though you cannot remove the 'a'.

[Havard]

Havard, I think the issue is that the "consists of "ay", "by", or "aby" applies to a case with a strong link which this is not.

Well, I see this pattern:

Code: Select all

UR+3/1SL: two or three UR cells with extra candidates (Z is optional), plus one strong link and at least one extra cell
--- UR+3x/1SL: "Y" is a single candidate "y", the extra cell "(ab)y" consists of "ay", "by", or "aby" and shares a house with "abX" and "ab(Z)" or consists of "ay" and shares a line with "ab(Z)" => "b" can be removed from "abX".

 ab  |  abX
     |   |
     |   |a
     |   |
aby  |  ab(Z)  (ab)y


as an extension to what Keith has discovered. In other words that you can add one extra candidates to one cell, and make up for it with a strong link, and still end up with the same "deadliness" that Keith demonstrated. (That for this example is that "a" can't go in abZ. The strong link forces a to go there... ) Quite funny that the "extension" should be discovered before the "basic"...

But you say that the elimination is valid for "aby" with one strong link... Ley's try it:

Code: Select all

 ab  |  abX
     |   |
     |   |a
     |   |
aby  |  abZ  aby


setting abX to b:

Code: Select all

 ab  |   b 
     |   |
     |   |a
     |   |
aby  |  abZ  aby


because of strong link abZ is now a:

Code: Select all

 a   |   b 
     |   
     |   
     |   
aby  |   a   aby


removing a from the aby's:

Code: Select all

 a   |   b 
     |   
     |   
     |   
 by  |   a   by


And as I pointed out before, we end up with the same pattern that I could not see any progress with? Would you maybe like to explain to me how this elimination is valid, because I can't seem to grasp it...

Havard

[RW]

I like the pattern Keith found, and the other possibilities you are discussing. I'm just wondering how far we can go in calling things uniqueness rectangles. My opinion has always been that if I can cause the deadly pattern without including any steps in the chain outside the pattern, it's a UR, if I need to take a step outside the pattern, it's some sort of chain or trail.

Code: Select all

ab     ab 
abc    ab 


definitely a UR; if abc=ab => deadly pattern forms without considering any cells outside the pattern. The example that started this thread:

Code: Select all

ab     ab
abx    abY    ax


includes on step outside the pattern, which makes it questionable if it can be called a UR or if there should be another term for these. Problem is, if this is a UR then what are these (all allow elimination abY<>a):

Code: Select all

ab     abz    xz
abx    abY    ax


Code: Select all

ab     ab
abxw   abY    axw  axw


Code: Select all

abw    abz    xz   zw
abx    abY    ax


Code: Select all

abz    ab     wz
ab     abY    axw
              xw


This list could be infinitely extended if we deside to start looking for different patterns where interaction with extra cells let's us do uniqueness reductions.

RW

[ronk]

I like the pattern Keith found, and the other possibilities you are discussing. I'm just wondering how far we can go in calling things uniqueness rectangles. My opinion has always been that if I can cause the deadly pattern without including any steps in the chain outside the pattern, it's a UR, if I need to take a step outside the pattern, it's some sort of chain or trail.

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?

[ronk]

Code: Select all

ab   | abY
abc  | ab   ac

... is a valid elimination of 'a' from the abY cell, but the following is not.

If that's even a legal pattern, it looks different after some sleep. If the Y were excluded from the abY cell, the ab naked pair would place c in the ac cell, creating the deadly pattern. Or am I not awake yet?

[edit: I finally looked at the puzzle. The pattern there is the following.]

Code: Select all

ab   | abY
ab   | abc  ac

So apparently, the abY cell and the cells of the "hidden set" must all see each other, but they don't all need to be in one line. This probably means the UR cells with extra candidates cannot be on a diagonal.

[keith]

Credit where credit is due

I found this example in one of Mike's solver links, here:

http://forum.enjoysudoku.com/viewtopic.php?t=2000

(If someone can tell me how to link down to the actual message, I'll add the specific link here.) [ronk-moderator 4/01/2011 edit: Direct link to message.]

The contribution is by Lummox JR, and he/she says:

In this puzzle you can find uniqueness 3 twice. Once here:

Code: Select all

. . .|. . 1|. . 8
. 8 2|. . .|. . .
. . .|9 3 .|. . .
-----------------
. . .|8 9 7|. . .
. . .|1 . .|. 3 .
. . 5|. . .|2 . .
-----------------
3 . .|6 . .|. 1 .
9 . .|2 . .|. . 4
6 . 7|3 . .|. . .

+----------------+----------------+----------------+
| 457  39   39   | 57   2    1    | 6    457  8    |
| 157  8    2    | 57   4    6    | 1579 579  3    |
| 1457 467  16   | 9    3    8    | 1457 2457 257  |
+----------------+----------------+----------------+
| 2    346  136  | 8    9    7    | 45   45   16   |
| 478  4679 69   | 1    5    2    | 789  3    679  |
| 178  79   5    | 4    6    3    | 2    789  179  |
+----------------+----------------+----------------+
| 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  |
+----------------+----------------+----------------+


There the partial hidden pair is in column 9 …

For the life of me, I cannot find anything in column 9. So, I looked in Block 9. Let me spell it out.

The UR on <25> is in R79C29. The unsolved cells in block 9 and their possible solutions are:

Code: Select all

Soln.   259   257   2589   589   57
  a      2     7     89     89    5
  b      9     2     58     58    7
  c      9     5      2      8    7
  d      2     5     89     89    7
  e      5     2     89     89    7


The UR excludes Solutions d and e, so <259> is not <5>. The cells <2589> and <259> do not contribute to this elimination. <57> is the critical "extra" cell. (edited May 12 8:40 am ET.)

Let me state two obvious points:

1. This is a "simple" UR. Without the UR, <259> is possibly <5>.

2. There are no conjugate conditions from outside the house. (Maybe there is a Type 4 extension, but I'm having a hard enough time getting my head around this one! In another thread, Steve R has already observed there is a diagonal extension!)

What I am looking for is a simple statement, and a simple rule, that is similar to the statement about Type 3 eliminations with a naked subset.

Keith

(Now I am off to read all the new overnight contributions!)

[Mike Barker]

Ron, you are correct. When I eliminated the stack bar, the only types that had been considered had abX and abY in a line. I realized there were three types and modified the text but didn't show them (only for the original form is the stack bar not required). Also the diagonal type still seems valid, you just get a different elimination:

--- UR+2k: two cells, not necessarily in a line, one with an extra candidate, "x", and one with at least one other extra different candidate, "Y" plus "ax" common to "abx" and "abY" => "a" can be removed "abY" or in the UR+2kD case "b" can be removed from "abY" and "a" as well if "abY" and "ax" share a house (in this case they don't have to, but "ax" and the rightmost "ab" do).

Code: Select all

UR+2kA           ||   UR+2kB       ||   UR+2kD
ab     ab        ||   ab     ab    ||   ab   | abY       
abx    abY  ax   ||   ----------   ||   abx  | ab   ax   
                 ||   abx    abY   ||
                 ||   ax           ||

--- UR+2K: two cells, not necessarily in a line, with extra candidates "X" and "Y" plus extra cells common to "abX" and "abY" such that with "a" excluded the extra cells (not all of which must contain "a") form a locked set including "X" => "a" can be removed from "abY" or in the UR+2KD case "b" can be removed and "a" also if "abY" and "(a)U..." share a house (in this case they don't have to, but "aU..." and the rightmost "ab" do)

Code: Select all

UR+2KA                ||   UR+2KB       ||   UR+2KD
ab     ab             ||   ab     ab    ||   ab   | abY       
abX    abY  (a)U...   ||   ----------   ||   abx  | ab   (a)U...   
                      ||   abx    abY   ||
                      ||   (a)U...      ||

Havard, in this case, the original "abX" and the righthand "abY" share a box so you are left with:

Code: Select all

a   |   b 
by  |   a   y

If they don't then you are right only "ay" is possible, but I think I cover this. It is the same type of elimination as above only requiring the extra strong link which allows for the additional options on "aby"

RW, you are correct there are other forms which can be created with extra cells, but remember this is no different than Type 3, we just don't usually show them. Type 4 also places conditions on the other cells (they can't contain the candidate). I also agree that the list is getting long and at somepoint we may wish to separate UR's not requiring extra cell(s) and those that do (AUR's?). 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:

--- UR+3k: three cells, two with one extra candidate, "abx" and "abz", and one with at least one other extra candidate, "abY" plus "ax" common to "abx" and "abY" plus "(ax)z" common to "abz", "ax", and "abY" or "xz" if only common to "abz" and "ax" => "a" can be removed "abY"

Code: Select all

UR+3kA               ||   UR+3kB
ab   |  abz  (ax)z   ||   ab   |  abz  |  xz
abx  |  abY  ax      ||   abx  |  abY  |  ax

--- UR+4k: four cells, three with one extra candidate, "abx", "abz", and "abw", and one with at least one other extra candidate, "abY" plus "ax" common to "abx" and "abY" plus "(axw)z" and "(axz)w" common to "abz"", "abw", "ax, and "abY" or "(xw)z" and "(xz)w" if only common to "abz" , "abw" and "ax" => "a" can be removed "abY"

Code: Select all

UR+4kA                      ||   UR+4kB
abw  |  abz  (axw)z (axz)w  ||   abw  |  abz  |  (xw)z (xz)w
abx  |  abY  ax             ||   abx  |  abY  |  ax

[Carcul]

As far as I am concern, these are just examples of short nice loops involving AURs:

ab|abX
ab|abY aX

[abY]=Y|X=[abX]-X-[aX]-a-[abY], => abY<>a.

The cell "aX" can be substituted by any ALS, located in the same unit of C/D, and whose cells contain "a" and "X" (for example, acX/ac and so on).

The UR on <25> is in R79C29. The unsolved cells in block 9 and their possible solutions are:

Code:

Soln. 259 257 2589 589 57
a 2 7 89 89 5
b 9 2 58 58 7
c 9 5 2 8 7
d 2 5 89 89 7
e 5 2 89 89 7



The UR excludes Solutions d and e, so <259> is not <5>. The cells <2589> and <259> do not contribute to this elimination. <57> is the critical "extra" cell. (edited May 12 8:40 am ET.)

Again: [r9c9]=9|7=[r7c9]-7-[r7c7]-5-[r9c9], => r9c9<>5.

proof:
Code:
if abX is "a":

ab | ab
|
|
|
aby | a ay


Code:
...ay is "y", and aby is by:

ab | ab
|
|
|
by | a y


Code:
...and we get deadliness.

a | b
|
|
|
b | a y

Why is that deadly? I don't agree with that proof. Regarding the pattern

ab|abX
ab|abY aX

a better proof (for me) is: abY is or is not "Y" - if it is "Y" then is not "a"; if it is not "Y" then Uniqueness requires that abX is "X" which makes "aX" = a and so abY cannot be "a". In either case, abY is not "a" and so abY<>a.

Carcul