Type 3 Unique Rectangles - Hidden Subsets?

Advanced methods and approaches for solving Sudoku puzzles

Another example

Postby keith » Fri May 26, 2006 2:01 am

Do you guys have this one cataloged? This fragment R6789 was posted on the Daily Sudoku site, by a human solver. From the initial puzzle, it is not a situation most would reach. Anyway:

Code: Select all
|1257  237   8     |1257  1267  4     |3679  39    26    |
----------------------------------------------------------
|6     12    259   |124   1234  1235  |8     29    7     |
|3     1278  27    |1278  9     1278  |46    5     46    |
|25789 278   4     |2578  2378  6     |39    239   1     |
----------------------------------------------------------

The UR / AUR <39> is in R69C78. The fifth cell is R7C8, <29>. My elimination would be R6C7 is not <3>. Myth Jellies pointed out the strong link on <9> in R6: R9C8 is not <9>.

(I think I have this right!)

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

Postby RW » Fri May 26, 2006 7:17 am

According to your candidate grid there would also be a strong link on <3> in box 9 and you could eliminate '3' from r6c7 without the fifth cell.

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

Postby Mike Barker » Thu Jun 01, 2006 3:12 am

My results with Kieth's techniques have been more favorable than Ron's. In the top1465, I'm able to solve 4 more puzzles with these techniques than without (#306, 447, 704, and 1145). Given that these puzzles were not solved even with grouped nice loops, that's pretty impressive. I did not see any puzzles that were previously solved, become unsolved with the addition of these techniques (that doesn't mean it can't happen - I just didn't see it happen). Of the four only in one case (#704) was the puzzle not solved without the techniques and then with the addition of the techniques solved (the other cases required the UR to occur prior to reaching a dead end). The PMs for the unsolved grid are shown below as well as the two UR's which lead to cracking the puzzle (both of which have 3 non-bivalued cells in the UR. The UR is indicated by the "*" and "-" where the elimination occurs at the "-". It requires 2 ALS indicated by the "#" and the "@". I'd be interested in other methods to advance the puzzle from the first grid.

Code: Select all
UR+3KX: r46c36, r5c123, r4c9 => r4c3<>6
+--------------------+--------------------+------------------+
|    69  2679    267 |     5   269      3 |   48  148     14 |
|  1389   349    348 |    79   489  14789 |    5    6      2 |
|   168  2456  24568 |    28  2468    148 |    9    7      3 |
+--------------------+--------------------+------------------+
|     5     1  -2369 |     4   239   *679 |  268   38    @67 |
|   #36 #2346  #2346 |  2378     5    678 |    1    9    467 |
|     7     8 *23469 |   239     1    *69 |  246  345     45 |
+--------------------+--------------------+------------------+
|     2   359      1 |     6   349     49 |    7   45      8 |
|     4    69     68 |    18     7      5 |    3    2    169 |
|  3689  3579   3578 |  1389  3489      2 |   46  145  14569 |
+--------------------+--------------------+------------------+


UR+3KX: r45c69, r6c6, r5c123 => r5c6<>6
+--------------------+--------------------+------------------+
|    69  2679    267 |     5   269      3 |   48  148     14 |
|  1389   349    348 |    79   489  14789 |    5    6      2 |
|   168  2456  24568 |    28  2468    148 |    9    7      3 |
+--------------------+--------------------+------------------+
|     5     1    239 |     4   239   *679 |  268   38    *67 |
|   @36 @2346  @2346 |  2378     5   -678 |    1    9   *467 |
|     7     8  23469 |   239     1    #69 |  246  345     45 |
+--------------------+--------------------+------------------+
|     2   359      1 |     6   349     49 |    7   45      8 |
|     4    69     68 |    18     7      5 |    3    2    169 |
|  3689  3579   3578 |  1389  3489      2 |   46  145  14569 |
+--------------------+--------------------+------------------+
Mike Barker
 
Posts: 458
Joined: 22 January 2006

Postby ronk » Thu Jun 01, 2006 11:48 am

Mike Barker wrote:In the top1465, I'm able to solve 4 more puzzles with these techniques than without (#306, 447, 704, and 1145).
(...)
Of the four only in one case (#704) was the puzzle not solved without the techniques and then with the addition of the techniques solved (the other cases required the UR to occur prior to reaching a dead end).

As those sentences appear contradictory, would you please clarify?
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby Mike Barker » Thu Jun 01, 2006 12:42 pm

Four more puzzles were solved with Keith's UR technique than without. Of the 4, 3 required the UR to occur in the middle of the solving steps. If the technique was not used, the puzzle was not solved. The UR could not be used at this point because it not longer existed. In the one shown, the puzzle was first solved without using the technique which allows a look at the unsolved puzzle. The puzzle was then solved, by first identifying the two UR's using Keith's technique and then the rest of my solver's techniques. I thought this was useful in that it shows a case where of the techniques my solver uses (naked sets, fish, strong links, XY cycles and other bivalue techniques, UR techniques, BUG-lite, basic and grouped nice loops, and ALS), the only one that seemed to work was Keith's UR. Now I could have an error in my solver, it could be I'm not using big enough ALS or nice loops, or I could be missing a technique and I'd love feedback on this. Barring a mistake, however, this is a great example that the technique is effective.
Mike Barker
 
Posts: 458
Joined: 22 January 2006

Postby ronk » Thu Jun 01, 2006 2:47 pm

Mike Barker wrote:Of the 4, 3 required the UR to occur in the middle of the solving steps. If the technique was not used, the puzzle was not solved. The UR could not be used at this point because it no longer existed.

Thanks for the clarification. When keith's technique is applied later to #704, is it possible to identify the key step that "destroys the UR"?
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby Mike Barker » Fri Jun 02, 2006 2:05 am

Actually the beauty of 704 is that of the 4 puzzles, it is the only one where the UR is not distroyed by effectively implementing Keith's techniques after everything else. This is the board after all other methods are exhausted showing one of the two UR+3KX which allow the puzzle to be solved:
Code: Select all
+--------------------+--------------------+------------------+
|    69  2679    267 |     5   269      3 |   48  148     14 |
|  1389   349    348 |    79   489  14789 |    5    6      2 |
|   168  2456  24568 |    28  2468    148 |    9    7      3 |
+--------------------+--------------------+------------------+
|     5     1  -2369 |     4   239   *679 |  268   38    @67 |
|   #36 #2346  #2346 |  2378     5    678 |    1    9    467 |
|     7     8 *23469 |   239     1    *69 |  246  345     45 |
+--------------------+--------------------+------------------+
|     2   359      1 |     6   349     49 |    7   45      8 |
|     4    69     68 |    18     7      5 |    3    2    169 |
|  3689  3579   3578 |  1389  3489      2 |   46  145  14569 |
+--------------------+--------------------+------------------+

I went back and looked at #306 where appling Keith's techniques after everything else doesn't lead to a solution, but allowing these eliminations prior to nice loops and ALS does. The two method summaries follow:
Code: Select all
Without Keith's Techniques:
Hidden Single: r1c1 => r1c1=9,r1c56<>9,r78c1<>9
Hidden Single: r6c3 => r6c3=2,r6c78<>2
Hidden Single: r7c3 => r7c3=8,r78c2<>8,r7c45<>8
Hidden Single: r1c9 => r1c9=8
Locked Row line/box: r2c12 => r2c4579<>1
Naked Single: r2c4 => r2c125<>4,r57c4<>4,r13c5<>4,r13c6<>4
Locked Column line/box: r78c2 => r2c2<>7
Naked Row Pair: r2c12 => r2c79<>5
Naked Block Pair: r2c12 => r1c3<>5
Naked Column Pair: r13c3 => r49c3<>4
Locked Column line/box: r13c5 => r789c5<>6
Locked Column box/box: r139c56 => r456c5<>1,r4c6<>1
Hidden Column Pair: r78c2 => r7c2=79,r8c2=79
Column X-Wing Fillet-o-Fish: r47c1|r479c6 => r7c5<>4
Column X-Wing Fillet-o-Fish: r49c3|r4789c6 => r9c5<>3
Column X-Wing Fillet-o-Fish: r49c3|r47c9 => r9c8<>5
Column X-Wing Fillet-o-Fish: r49c3|r47c9 => r7c1<>5
XYZ-wing: r6c1|r4c3, r2c1 => r4c1<>5
UR+2X/1SL: r13c38 => r13c8<>7
UR+3U/2SL: r56c24 => r5c2<>1
UR+4C/3SL: r37c56 => r7c6<>9
ALS xy-rule with B=2 cells: r9c2368-1-r2c5|r1c6-2-r78c4|r8c56|r7c5 => r9c5<>5
Locked Row box/box: r7c579|r8c58 => r8c1<>5
XY-wing: r8c16|r7c4 => r8c4<>6,r7c1<>6
Hidden Single: r7c4 => r7c4=6,r7c79<>6
Locked Column line/box: r89c8 => r135c8<>6
WXYZ-wing: r3c8|r2c79, r3c3 => r3c79<>7
*** UR+2B/1SL: r26c12 => r6c2<>1 ***
Nice Loop: r6c8=7=r8c8-7-r8c2-9-r8c4=9=r6c4-9-r6c7=9=r4c7~9~r6c8 => r4c7<>7
Nice Loop: r1c7=5=r1c8-5-r8c8=5=r8c5=8=r8c4=9=r6c4-9-r6c7=9=r4c7~9~r1c7 => r4c7<>5
Nice Loop: r5c7=2=r5c8-2-r3c8-4-r1c8-5-r8c8=5=r8c5=8=r8c4-8-r5c4~1~r5c7 => r5c7<>1
WXYZ-wing: r5c789, r3c9 => r4c9<>6
Nice Loop: r4c7=9=r6c7-9-r6c4=9=r8c4=8=r8c5=5=r7c5-5-r7c9=5=r4c9-5-r4c3~3~r4c7 => r4c7<>3
Grouped Nice Loop: ALS:r27c9-5-ALS:r8c12468-8-ALS:r5c4789~3~ => r4c9<>3
Grouped Nice Loop: r456c5=3=r4c6-3-r4c3-5-r4c9=5=r7c9-5-r7c5=5=r8c5~5~r456c5 => r8c5<>3
Incomplete solution

Code: Select all
With Keith's Techniques (the UR+2kx is highlighted), the UR which distroys the UR+2kx is highlighted in the previous list):
Hidden Single: r1c1 => r1c1=9,r1c56<>9,r78c1<>9
Hidden Single: r6c3 => r6c3=2,r6c78<>2
Hidden Single: r7c3 => r7c3=8,r78c2<>8,r7c45<>8
Hidden Single: r1c9 => r1c9=8
Locked Row line/box: r2c12 => r2c4579<>1
Naked Single: r2c4 => r2c125<>4,r57c4<>4,r13c5<>4,r13c6<>4
Locked Column line/box: r78c2 => r2c2<>7
Naked Row Pair: r2c12 => r2c79<>5
Naked Block Pair: r2c12 => r1c3<>5
Naked Column Pair: r13c3 => r49c3<>4
Locked Column line/box: r13c5 => r789c5<>6
Locked Column box/box: r139c56 => r456c5<>1,r4c6<>1
Hidden Column Pair: r78c2 => r7c2=79,r8c2=79
Column X-Wing Fillet-o-Fish: r47c1|r479c6 => r7c5<>4
Column X-Wing Fillet-o-Fish: r49c3|r4789c6 => r9c5<>3
Column X-Wing Fillet-o-Fish: r49c3|r47c9 => r9c8<>5
Column X-Wing Fillet-o-Fish: r49c3|r47c9 => r7c1<>5
XYZ-wing: r6c1|r4c3, r2c1 => r4c1<>5
*** UR+2kx: r26c12, r4c3 => r6c2<>5 ***
UR+2rd: r56c24 => r6c4<>8,r5c2<>1
UR+2X/1SL: r13c38 => r13c8<>7
UR+4C/3SL: r37c56 => r7c6<>9
Grouped Nice Loop: r4c12=1=r6c12-1-r6c4-9-r4c56=9=r4c7~9~r4c12 => r4c7<>1
Grouped Nice Loop: ALS:r9c2368-1-ALS:r1c6|r2c5-2-ALS:r78c5|r8c46|r7c4~5~ => r9c5<>5
Locked Row box/box: r7c579|r8c58 => r8c1<>5
XY-wing: r8c16|r7c4 => r8c4<>6,r7c1<>6
Hidden Single: r7c4 => r7c4=6,r7c79<>6
Locked Column line/box: r89c8 => r135c8<>6
WXYZ-wing: r3c8|r2c79, r3c3 => r3c79<>7
Nice Loop: r6c8=7=r8c8-7-r8c2-9-r8c4=9=r6c4-9-r6c7=9=r4c7~9~r6c8 => r4c7<>7
Nice Loop: r1c7=5=r1c8-5-r8c8=5=r8c5=8=r8c4=9=r6c4-9-r6c7=9=r4c7~9~r1c7 => r4c7<>5
Nice Loop: r5c7=2=r5c8-2-r3c8-4-r1c8-5-r8c8=5=r8c5=8=r8c4-8-r5c4~1~r5c7 => r5c7<>1
WXYZ-wing: r5c789, r3c9 => r4c9<>6
Nice Loop: r4c7=9=r6c7-9-r6c4=9=r8c4=8=r8c5=5=r7c5-5-r7c9=5=r4c9-5-r4c3~3~r4c7 => r4c7<>3
Grouped Nice Loop: ALS:r27c9-5-ALS:r8c12468-8-ALS:r5c4789~3~ => r4c9<>3
Grouped Nice Loop: r4c12=1=r4c9=5=r6c78-5-r6c1=5=r2c1=1=r2c2~1~ => r6c2<>1
Naked Single: r6c2 => r6c5<>8,r5c2<>8
Nice Loop: r7c6=2=r7c5=5=r8c5=8=r5c5=4=r5c2-4-r4c1=4=r7c1~4~r7c6 => r7c6<>4
Hidden Single: r7c1 => r7c1=4,r4c1<>4,r9c2<>4
Naked Row Triple: r9c238 => r9c6<>3
Nice Loop: r9c8=3=r9c3=5=r4c3-5-r4c9=5=r7c9~5~r9c8 => r7c9<>3
Nice Loop: r8c1=3=r9c3=5=r4c3-5-r4c9=5=r7c9-5-r7c5=5=r8c5~5~r8c1 => r8c5<>3
Nice Loop: r7c9=5=r4c9-5-r4c3=5=r9c3=3=r8c1=6=r8c8~6~r7c9 => r8c8<>5
Hidden Single: r8c5 => r8c5=5,r7c5<>5
Hidden Single: r8c4 => r8c4=8,r5c4<>8
Naked Single: r5c4 => r5c9<>1,r6c4<>1
Naked Single: r6c4 => r6c57<>9,r4c56<>9
Hidden Single: r5c5 => r5c5=8
Hidden Single: r5c2 => r5c2=4,r4c2<>4
Hidden Single: r4c7 => r4c7=9
Locked Row box/box: r4c1356|r6c15 => r6c78<>3
Nice Loop: r7c5=9=r8c6-9-r8c2-7-r8c8=7=r6c8-7-r6c5~3~r7c5 => r7c5<>3
Locked Column line/box: r78c6 => r4c6<>3
Naked Column Triple: r149c6 => r3c6<>17
Nice Loop: r2c7=2=r2c5-2-r3c6=2=r7c6=3=r7c7~3~r2c7 => r2c7<>3
Hidden Single: r2c9 => r2c9=3,r5c9<>3
Naked Single: r5c9 => r5c7<>6,r3c9<>6
Naked Single: r3c9 => r3c57<>1,r4c9<>1,r1c7<>1
Hidden Single: r6c7 => r6c7=1,r6c1<>1
Naked Block Pair: r6c1|r4c3 => r4c1<>3,r4c2<>5
Locked Column line/box: r12c7 => r7c7<>7
BUG+3C/2SL (2 buglets): r123c57 => r1c5<>7
Nice Loop: r8c1=3=r6c1=5=r6c8=7=r8c8~7~r8c1 => r8c8<>3
Nice Loop: r5c7-3-r7c7=3=r7c6=2=r3c6~2~ => r3c7<>2
The Solution is completed with singles
Mike Barker
 
Posts: 458
Joined: 22 January 2006

Postby ronk » Wed Jun 07, 2006 1:36 am

Mike Barker wrote:With Keith's Techniques (the UR+2kx is highlighted), the UR which distroys the UR+2kx is highlighted in the previous list) ...

That looks like the difference might be due to the relative order of Keith's technique with other uniqueness techniques ... and NOT necessarily with other non-uniqueness techniques.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

A claim

Postby keith » Wed Jun 07, 2006 3:28 am

I am going to make a claim which may be difficult for me to prove, if I am challenged to prove it:

I have posted at least two examples of overlapping Unique Rectangles: If you make the reductions for one of the rectangles, you destroy the pattern and reductions of the other. Sequence matters.

My claim: I have seen many examples of overlapping XY-wings, in which the reductions of one XY-wing destroy the other wings and their reductions. Sequence matters.

Sequence matters, for all techniques, not only for Uniqueness techniques.

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

Postby doduff » Fri Jun 09, 2006 9:20 am

keith wrote:
Code: Select all

|1257  237   8     |1257  1267  4     |3679  39    26    |
----------------------------------------------------------
|6     12    259   |124   1234  1235  |8     29    7     |
|3     1278  27    |1278  9     1278  |46    5     46    |
|25789 278   4     |2578  2378  6     |39    239   1     |
----------------------------------------------------------
 


The UR / AUR <39> is in R69C78. The fifth cell is R7C8, <29>. My elimination would be R6C7 is not <3>. Myth Jellies pointed out the strong link on <9> in R6: R9C8 is not <9>.


It took me awhile to see that 9 elimination, but wow, what a great deduction!

RW wrote:According to your candidate grid there would also be a strong link on <3> in box 9 and you could eliminate '3' from r6c7 without the fifth cell.


There doesn't appear to be a strong link on 3 in box 9(the lower right hand one right?).

keith wrote:My claim: I have seen many examples of overlapping XY-wings, in which the reductions of one XY-wing destroy the other wings and their reductions. Sequence matters.


I wouldn't think that sequence should matter. As long as an elimination is valid, it shouldn't matter when you do it. If you identify 2 xy-wings and one destroys the other, the conclusions of both should still be valid. An xy-wing is an xy-wing. I have another claim: The deduction from any solving method should be valid even if it uses 'destroyed' candidates. Now I may be jumping the gun on this, but it's just a gut feeling. We use incorrect candidates in chains all the time. In essence those candidates are not really there, so eliminating one may 'destroy' the loop, but just write it back in and the loop is there. Is there some proven rule that loops only work after all possible simpler reductions have been made... singles, pairs, etc? Hell, I think you should be able to use solved cells in loops, just write in some candidates, but this would probably not be fruitful.

Could you post an example of overlapping xy-wings where one destoys the other and its conclusions? I would be really curious to look into that.
doduff
 
Posts: 32
Joined: 29 May 2006

Postby ravel » Fri Jun 09, 2006 10:14 am

doduff wrote:There doesn't appear to be a strong link on 3 in box 9(the lower right hand one right?).

There is, you have only the 2 3's in box 9 (and the one in r9c5 can be eliminated).
ravel
 
Posts: 998
Joined: 21 February 2006

Postby doduff » Fri Jun 09, 2006 4:55 pm

Ah... I see... locked candidates. cool.

Can someone point me to a proof of why a unique puzzle cannot end up in this state:
Code: Select all
|1257  27    8     |1257  1267  4     |9     3     26    |
----------------------------------------------------------
|6     12    259   |124   1234  1235  |8     29    7     |
|3     1278  27    |1278  9     1278  |46    5     46    |
|25789 278   4     |2578  278   6     |3     29    1     |
----------------------------------------------------------


...fixing the 9 at r6c7.
Basically I want to know why

a b
----
b a

is deadly.

It seems like there could be a puzzle where you get to the state:
a b
----
b ax

and the you want to remove the a in ax by an AUR rule, but what says the x cannot be removed by some chain?
doduff
 
Posts: 32
Joined: 29 May 2006

Overlapping XY-wings

Postby keith » Sat Jun 10, 2006 2:31 am

doduff wrote:

Could you post an example of overlapping xy-wings where one destoys the other and its conclusions? I would be really curious to look into that.


Here is an example from this past week, in another thread:

http://www.dailysudoku.co.uk/sudoku/forums/viewtopic.php?t=935

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

Postby doduff » Sat Jun 10, 2006 2:59 am

That is an interesting example, along with the remote pairs that come afterward. I thought you meant that one of the xy-wings is actually invalid due to the presence of the other. Both conclusions are still true.

I still think it shouldn't matter what order you apply methods in.
doduff
 
Posts: 32
Joined: 29 May 2006

Re:

Postby ronk » Thu Mar 31, 2011 8:54 pm

In May 2006, Mike Barker here wrote: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

Since borders between boxes are not shown, that appears to be quite a mouthful. It presumably covers these six non-isomorphic cases.

Code: Select all
 .  ab . | ab  .  .  | .  .   .       . ab  . | abx .  .  | .  .  .   
 .  .  . | .   .  .  | .  .   .       .  .  . |  .  .  .  | .  .  .   
 . abx . | abY .  .  | .  ax  .       . ab  . | abY .  .  | .  .  .   
---------+-----------+-----------    ----- ---+-----------+----------
 .  .  . | .   .  .  | .  .   .       .  .  . | ax  .  .  | .  .  .   
Candidate "a" may be eliminated from the "abY" cell.
                               

 .  ab . | ab  .   .   | .  .  .      .  ab . | abY .   .   | .  .  . 
 .  .  . | .   .   .   | .  .  .      .  .  . | .   .   .   | .  .  . 
 . abY . | abx .   ax  | .  .  .      .  ab . | abx .   ax  | .  .  .   
---------+-------------+---------    ---------+-------------+---------
 .  .  . | .   .   .   | .  .  .      .  .  . | .   .   .   | .  .  . 
Candidate "a" may be eliminated from the "abY" cell.


 .  ab . | ab  .   .   | .  .  .      .  ab . | abx .   .   | .  .  . 
 .  .  . | .   .   .   | .  .  .      .  .  . | .   .   .   | .  .  . 
 . abx . | abY . a(b)x | .  .  .      .  ab . | abY . a(b)x | .  .  .   
---------+-------------+---------    ---------+-------------+---------
 .  .  . | .   .   .   | .  .  .      .  .  . | .   .   .   | .  .  . 
Candidates "a" and "b" may both be eliminated from the "abY" cell. Candidate "(b)" may be missing.

Before I continue with the others in that post, would someone please confirm? daj95376?
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

PreviousNext

Return to Advanced solving techniques