Uniqueness Type 6 - UR meets X-Wing

Advanced methods and approaches for solving Sudoku puzzles

Postby tarek » Mon Apr 24, 2006 8:32 pm

Don't forget that the quantum cell can be used as an ALS.... simplest would be an xy wing........

tarek
User avatar
tarek
 
Posts: 2622
Joined: 05 January 2006

Postby ronk » Mon Apr 24, 2006 8:36 pm

gsf wrote:does the solution to this grid include r3c8=7?

The original posting has r3c8 as the tri-value 147 ... but the deduction r2c7<>4 is apparently still valid.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby gsf » Mon Apr 24, 2006 8:39 pm

ronk wrote:
gsf wrote:does the solution to this grid include r3c8=7?

The original posting has r3c8 as the tri-value 147 ... but the deduction r2c7<>4 is apparently still valid.

so its a typo -- r3c8 should have 7 because 7 is in the solution, right?
gsf
2014 Supporter
 
Posts: 7306
Joined: 21 September 2005
Location: NJ USA

Postby ronk » Mon Apr 24, 2006 9:07 pm

gsf wrote:r3c8 should have 7 because 7 is in the solution, right?
Yes, that's the way I see it.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby Havard » Mon Apr 24, 2006 10:09 pm

Great progress here. I thought I would add this:

--- UR+3C/2SL: both strong links share a node, have different labels and one link includes the bivalue cell => "a" can be removed from "abY"
Code: Select all
 ab-----abX
     a   |
        b|
         |
abY     abZ


since:
Code: Select all
 ab-----abX
     a   |
        b|
         |
ab      ab

can be concidered a "deadly pattern", the Y and Z can be used as a quantum cell in Locked and Almost locked sets.

in other words:
--- UR+3C/2SL: both strong links share a node, have different labels and one link includes the bivalue cell => "a" can be removed from "abY", and Y and Z makes a quantum cell.
Code: Select all
 ab-----abX
     a   |
        b|
         |
abY     abZ
Havard
 
Posts: 377
Joined: 25 December 2005

Postby Myth Jellies » Tue Apr 25, 2006 12:22 am

ravel wrote:
Code: Select all
 *--------------------------------------------------------------------*
 | 56     26     462    | 1458   7      9      | 3      4612   1248   |
 | 1      9      4627   | 45+8   3      48     | 45+278 4627   248    |
 | 357    37     8      | 45+1   2      6      | 45+7   #147    9      |
 |--------------------------------------------------------------------|
 | 4      2378   1      | 78     5      2378   | 289    239    6      |
 | 368    5      9      | 468    1468   12348  | 248    234    7      |
 | 3678   23678  2367   | 46789  4689   23478  | 1      5      2348   |
 |----------------------+----------------------+----------------------|
 | 2      178    5      | 3      1489   1478   | 6      1479   14     |
 | 36789  13678  367    | 2      14689  1478   | 479    13479  5      |
 | 3679   4      367    | 679    169    5      | 279    8      123    |
 *--------------------------------------------------------------------*

...since its going crazy anyway: what about the elimination rep'nA found in the grid MJ showed above? You have 2 strong links for the 5 and a "finned" strong link for the 4 to eliminate 4 in r2c7.


Hmmm. It is pretty easy to show that when you have just a "strong elbow" in a generic UR(+4, though it doesn't have to be +4)...
Code: Select all
abX-----abZ
     a  /|
         |
     /  a|
         |
  /      |
abY     abW

...the the 'b' candidate in the corner of the elbow is weakly linked to either the 'a' or 'b' candidates in the cell in the opposite corner. In other words, if either 'a' or 'b' are true in the abY-cell then b is false in the abZ-cell, and vice-versa. Any conjugate or strong link between the 'b' in the abY-cell and any grouping of 'b's sharing a house with the abZ-cell will thus kill the 'b' in the abZ-cell. This particular case is in the realm of an AUR, but it is quite obvious to see--probably as easy to spot as a type 3/UR assisted locked set deduction.
Myth Jellies
 
Posts: 593
Joined: 19 September 2005

Postby Mike Barker » Tue Apr 25, 2006 2:29 pm

I've updated the list based on Havard's and MJ's inputs. I'd be interested if there are other implementations of MJ's description. Also I agree with Ron, these later additions, which require more than 4 cells, probably exceed the charter of UR. I don't know if they fall under the heading of Almost Unique Rectangles (which I thought played a roll in nice loops, but didn't stand alone) or Pseudo Unique Rectangles, but until we get a thread going for these, I'll include them here.
Mike Barker
 
Posts: 458
Joined: 22 January 2006

Postby Steve R » Tue Apr 25, 2006 3:22 pm

Havard’s observation of earlier today about a quantum cell, now incorporated in UR+3C/2SL, seems to apply more generally. In particular a may be missing from the candidates of one cell:
Code: Select all
 
ab      abX
         |
        b|
         |
bY      abZ

Eliminations involving the candidates in the sets Y and Z may still be made from the bottom row.

Steve
Steve R
 
Posts: 74
Joined: 03 April 2006

Postby Havard » Tue Apr 25, 2006 6:02 pm

Steve R wrote:Havard’s observation of earlier today about a quantum cell, now incorporated in UR+3C/2SL, seems to apply more generally. In particular a may be missing from the candidates of one cell:
Code: Select all
 
ab      abX
         |
        b|
         |
bY      abZ

Eliminations involving the candidates in the sets Y and Z may still be made from the bottom row.

Steve


Hi Steve!

I can't quite get the "may still be...", because if the "a" was present, you would not be able to use Y and Z as a quantum cell. However I find your pattern quite interesting... A "broken" UR that allows (possible)eliminations that the "whole" one won't...:) Wonder if there are more of these?

Havard
Havard
 
Posts: 377
Joined: 25 December 2005

Postby ronk » Tue Apr 25, 2006 8:38 pm

Steve R wrote:In particular a may be missing from the candidates of one cell:
Code: Select all
 
ab      abX
         |
        b|
         |
bY      abZ

Eliminations involving the candidates in the sets Y and Z may still be made from the bottom row.

I'm not so sure about that. With the 'a' gone from the abY cell -- and not "freely inventible" -- the outcome ...
Code: Select all
a       b
           
         
         
b       a

... is not an indication of a deadly pattern. And there is neither a Y nor a Z in that.

If the 'a' is freely inventible, then the YZ quantum cell exclusion may be merely a delayed exclusion based on this original pattern:
Code: Select all
 ab-----abX
     a   |
        b|
         |
abY     abZ

Sort of like ... I'll exclude tha 'a' now ... and do the YZ quantum cell thingie later.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby Steve R » Tue Apr 25, 2006 10:02 pm

Ron

Thank you for pointing out the flaw: my previous note is nonsense and I apologise for it.

Steve
Steve R
 
Posts: 74
Joined: 03 April 2006

Postby Mike Barker » Thu Apr 27, 2006 4:02 am

Several of the nice loops identified in the summary of UR techniques are really X-wings including the Type 4 reduction. Presumably X-wings will occur prior to UR so these tests will be redundant. I've updated the summary to identify them. One for which this is not the case is UR+3X/2SL. Here's an example of one such reduction:

Code: Select all
465.27..1798.4126.2136....4342.6....6572.4.8.189..342652...6...93...26..876435912

UR+3X/2SL: r34c78 => r4c9<>5,r7c8<>7,r8c8<>7,r4c7<>7,r3c7=57,r3c8<>5

+-----------+-----------------+--------------+
|  4  6   5 |   389     2   7 |  38  39    1 |
|  7  9   8 |    35     4   1 |   2   6   35 |
|  2  1   3 |     6   589  89 | -578 -579  4 |
+-----------+-----------------+--------------+
|  3  4   2 |   189     6  89 | -157 *57 -579|
|  6  5   7 |     2    19   4 |  13   8   39 |
|  1  8   9 |    57    57   3 |   4   2    6 |
+-----------+-----------------+--------------+
|  5  2  14 |  1789  1789   6 |  37 -347 378 |
|  9  3  14 |   178   178   2 |   6 -457 578 |
|  8  7   6 |     4     3   5 |   9   1    2 |
+-----------+-----------------+--------------+


Obviously some of the reductions could also be done with nice loops, but this doesn't seem to be a bad way to get more bang for your buck.
Mike Barker
 
Posts: 458
Joined: 22 January 2006

Postby RW » Thu Apr 27, 2006 7:21 am

ronk wrote:I'm not so sure about that. With the 'a' gone from the abY cell -- and not "freely inventible" -- the outcome ...

Code: Select all
a       b
           
         
         
b       a


... is not an indication of a deadly pattern. And there is neither a Y nor a Z in that.


It seems you missed the point about uniqueness rectangles.

Code: Select all
..a|..b
...|...
..b|..a


is always invertible if none of the involved numbers were part of the initial clues. You could never obtain any row information for any of the involved numbers from the remaining grid. This means that if you have already removed the a from the abY cell:

Code: Select all
ab      abX
         |
        b|
         |
bY      abZ


it is even safer to make eliminations involving the candidates in the sets Y and Z in the bottom row. You do not even need to know that the puzzle has an unique solution. If the rectangle was a deadly pattern in a multiple solution puzzle, you would never have been able to remove the a.

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

Postby ronk » Thu Apr 27, 2006 11:34 am

RW wrote:
Code: Select all
..a|..b
...|...
..b|..a

is always invertible if none of the involved numbers were part of the initial clues. You could never obtain any row information for any of the involved numbers from the remaining grid.

I've twice coded algorithms trying to use that "not part of the initial clues" theory ... and they both failed. I suppose I could've had a bug both times, but after two failures I'm inclined to disbelieve the theory.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby ravel » Thu Apr 27, 2006 12:21 pm

No doubt that the "theory" is correct, Vidar's AUS is basically the same, but the pattern is very rare.

PS: To give a proof also (in more words than RW): Suppose in a unique solution you have a rectangle in 2 boxes with values
Code: Select all
a  b

b  a
then there cannot be an a or b elsewhere in one of the 6 units and
Code: Select all
b  a

a  b
is always possible from the initial clues, if none of the 4 is a given (the change does not influence other cells) - contradicting the uniqueness.
Last edited by ravel on Thu Apr 27, 2006 9:02 am, edited 1 time in total.
ravel
 
Posts: 998
Joined: 21 February 2006

PreviousNext

Return to Advanced solving techniques