Logical use of uniqueness technique in an uniqueness test

Advanced methods and approaches for solving Sudoku puzzles

Logical use of uniqueness technique in an uniqueness test

Postby RW » Thu Apr 27, 2006 1:58 pm

Here's another interesting fact about uniqueness technique that I just discovered: you may in some cases use them logically even without the assurance of an unique solution. First, let's have a look at a basic uniqueness rectangle:

Code: Select all
. . ab|. . ab
. . ab|. . ab
. . . |. . .


I'd also like to call this a "closed system". Closed implies that no patterns outside this system could affect the numbers within the system, and no numbers within the system could affect any numbers outside the system. If you solve the rest of the puzzle, you are left with the rectangle and it doesn't matter what you do inside the rectangle, the rest of the puzzle remains the same.

Next, let's try to verify that this puzzle has an unique solution:

Code: Select all
 *-----------*
 |5..|..3|7..|
 |436|.7.|2..|
 |.87|.4.|3..|
 |---+---+---|
 |...|.62|...|
 |9..|...|..3|
 |...|43.|...|
 |---+---+---|
 |..4|.5.|83.|
 |..1|.2.|965|
 |..3|7..|..4|
 *-----------*


With basic techniques we would get this far:

Code: Select all
 *-----------------------------------------------------------*
 | 5     2     9     | 168   18    3     | 7     4     168   |
 | 4     3     6     | 189   7    *159   | 2    *1589  189   |
 | 1     8     7     | 2     4    *569   | 3    *59    69    |
 |-------------------+-------------------+-------------------|
 | 3     14    58    | 189   6     2     | 45    7     189   |
 | 9     46    2     | 5     18    7     | 46    18    3     |
 | 7     16    58    | 4     3     19    | 56    189   2     |
 |-------------------+-------------------+-------------------|
 | 2     9     4     | 16    5     16    | 8     3     7     |
 | 8     7     1     | 3     2     4     | 9     6     5     |
 | 6     5     3     | 7     9     8     | 1     2     4     |
 *-----------------------------------------------------------*


Here you can see an uniqueness rectangle in r23c68 that would let us remove candidate 9 from r2c6. However, we cannot use the uniqueness rectangle, as we don't know yet that this puzzle has only one solution.

There is also a possible reduction to be found by coloring the 9s:

Code: Select all
 *-----------------------------------------------------------*
 | 5     2     9     | 168   18    3     | 7     4     168   |
 | 4     3     6     |+189   7     159   | 2    *1589  189   |
 | 1     8     7     | 2     4     569   | 3     59    69    |
 |-------------------+-------------------+-------------------|
 | 3     14    58    |-189   6     2     | 45    7    +189   |
 | 9     46    2     | 5     18    7     | 46    18    3     |
 | 7     16    58    | 4     3    +19    | 56   -189   2     |
 |-------------------+-------------------+-------------------|
 | 2     9     4     | 16    5     16    | 8     3     7     |
 | 8     7     1     | 3     2     4     | 9     6     5     |
 | 6     5     3     | 7     9     8     | 1     2     4     |
 *-----------------------------------------------------------*


This let's us remove the 9 from r2c8. Now, remember what I said about closed systems: "no patterns outside this system could affect the numbers within the system" - but we just found a pattern that allowed us to remove candidate 9 from one of the involved cells...? This tell's us that, multiple solutions or not, these particular 4 cells can not form an deadly pattern => we may remove candidate 9 from r2c6 and proceed with the x-wing in r36c68 to eliminate 9 from r3c9.

The numerical proof for this reduction can be found in the coloring-grid:
If r2c6=9 (can see a +cell) => r3c6=5 => r3c8=9 (can see a -cell)

This rule applies to all almost-deadly patterns:

Code: Select all
If a reduction based on numeral logic prevents us from forming one solution of the deadly pattern, it will also prevent us from forming the other solution.


Let's have another look at the uniqueness rectangle:

Code: Select all
. . ab|. . ab
. . ab|. . ab
. . . |. . .


There is three different ways to interfere with the pattern from the outside:

1. Place an A somewhere else in one of the involved units, has to remove both candidates a in that unit and prevents both of the possible solutions in the deadly pattern.

2. Place an B somewhere else in one of the involved units, has to remove both candidates b in that unit and prevents both of the possible solutions in the deadly pattern.

3. Place a third number C on any of the four corners, removes both candidates a and b in that cell and prevents both of the possible solutions in the deadly pattern.

The real implication that the coloring grid gave us was:
either r2c4=9 => r2c6<>9 and r2c8<>9
or r6c8=9 => r2c8<>9 and r3c8<>9

Neither of these would allow us to construct the uniqueness pattern in any form.

There is of course one more way to remove candidates: T&E.

I'll quote myself again: "no numbers within the system could affect any numbers outside the system." => If an implication made by one of the numbers inside the possible deadly pattern causes a contradiction outside the pattern, it cannot be a deadly pattern. If you have a look at the uniqueness rectangle you will see that there is no way that any implication could end up with a contradiction. The definition of a deadly pattern is that it may end up in two possible correct solutions and may not end up in a contradiction.

To summarize:

-A uniqueness reduction is made because if that reduction was not true, a deadly pattern would form (multiple solutions).

-A uniqueness reduction cannot be made if you don't know that the puzzle has an unique solution, there might be a deadly pattern in the puzzle.

-If you are able to remove a candidate inside a possible deadly pattern by use of numeral logic, the deadly pattern cannot be there, and you may make uniqueness reduction assosiated to that particular deadly pattern, even if you don't know if the puzzle has an unique solution.

Long explanation for something that doesn't have any great effect on how we solve the puzzles... but I thought I'd share it with you anyway.

Comments?

RW
Last edited by RW on Thu Apr 27, 2006 1:27 pm, edited 1 time in total.
RW
2010 Supporter
 
Posts: 1000
Joined: 16 March 2006

Postby ravel » Thu Apr 27, 2006 2:53 pm

So in this sample you safely can also eliminate the 9 in r2c6, if the puzzle is unique or not. For solving puzzles this are good news for those, who only use methods that dont depend on uniqueness. Maybe you should call this thread "Unique rectangles for purists" ?:)
ravel
 
Posts: 998
Joined: 21 February 2006

Postby RW » Thu Apr 27, 2006 3:19 pm

ravel wrote:So in this sample you safely can also eliminate the 9 in r2c6, if the puzzle is unique or not.


Yes, I just wanted to prove that a uniqueness reduction is valid even if one of the candidates is already removed. Seemed to be some confusion about that here. Then I decided that why only prove that it is valid as normal, when I can also prove that it is valid in a multiple solution puzzle!:)

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

Postby Ocean » Thu Apr 27, 2006 5:03 pm

Interesting observation! In general this means:



Say we are "fearing" the two "deadly" patterns A and B:

Code: Select all
A: a  b      B:  b  a

   b  a          a  b

If the possibility of A is eliminated (by some logic), then B is also not possible.
[Edit - More correct is: If configuration A is proved/shown not to result in a valid solution, then also configuration B will not result in a valid solution.]


Thus:
Code: Select all
         a
   abX-------aZ
   |         
   |a       
   |         
   abY       ab

In a pattern of this kind (with strong link between the a's), b can be eliminated in the upper left corner. Because, if b was true, then we would end up with pattern B above, which cannot occur since its companion pattern A is impossible to reach.
Last edited by Ocean on Thu Apr 27, 2006 4:19 pm, edited 1 time in total.
Ocean
 
Posts: 442
Joined: 29 August 2005

Postby RW » Thu Apr 27, 2006 6:08 pm

Ocean wrote:If the possibility of A is eliminated (by some logic), then B is also not possible.


Yes, if it is eliminated by logic based on placements of numbers. If it was eliminated by uniqueness technique, then both A and B may still be possible if the puzzle has multiple solutions, as shown by Moschopulus here and more recently by myself here. But nobody would ever make such a reduction in a possible multiple solution grid, right?:)

Situations like these are in fact quite common, I've seen several examples. Here's another one for the "purists" to practise uniqueness reductions on:

Code: Select all
 *-----------*
 |.56|.7.|...|
 |8..|.9.|.7.|
 |4..|.68|.2.|
 |---+---+---|
 |56.|9..|2..|
 |...|.8.|...|
 |..3|..7|.46|
 |---+---+---|
 |.9.|82.|..4|
 |.4.|.5.|..2|
 |...|.3.|96.|
 *-----------*


Can be solved with xy-wing, coloring and one "safe" uniqueness reduction.

[Edit: and a BUG+1... sorry I forgot that when I posted it, see my post below how this can be done "safely"]

I shall also make one specification that I forgot to mention in my original post: The "safe" uniqueness reduction can only be made in a definite uniqueness pattern. These are the normal patterns, where we know which cells the possible deadly pattern would occupy. An indefinite uniqueness pattern is a pattern where we cannot tell exactly which cells would belong to the deadly pattern, such as a reverse BUG, hidden BUG or a BUG-lite with a "square" corner:

[edit: the terms "definite" and indefinite" are probably not the best to use here, but with my limited know the english speak, I couldn't come up with any better. Suggestions are welcome.]

Code: Select all
 *--------------------------------------------------------------------*
 |*26     1      9      | 37     245   -258    |*368    57    *45678  |
 | 8      3      7      | 1      45     6      | 2      9      45     |
 |*26     5      4      | 37     9     -28     |*368    1     *678    |
 |----------------------+----------------------+----------------------|
 | 17     9      6      | 5      8      3      | 4      2      17     |
 | 3      27     8      | 4      6      12     | 9      57     157    |
 | 15     4      25     | 9      12     7      |*68     3     *68     |
 |----------------------+----------------------+----------------------|
 | 57     8      25     | 6      3      19     | 17     4      29     |
 | 9      6      1      | 2      7      4      | 5      8      3      |
 | 4      27     3      | 8      15     159    | 17     6      29     |
 *--------------------------------------------------------------------*


If we know that this is a unique solution puzzle, we can safely eliminate candidates 2 from r13c6. But we could not make the elimination if we're not sure about the unique solution, even if we had removed candidate 6 from r1c9 with T&E. It could still be possible to form the deadly pattern with 68 in r1c7 and r3c9.

Hope I didn't confuse you too much with this last example...

Regards, RW
Last edited by RW on Tue May 09, 2006 12:09 pm, edited 2 times in total.
RW
2010 Supporter
 
Posts: 1000
Joined: 16 March 2006

Postby ronk » Thu Apr 27, 2006 6:55 pm

RW wrote:Seemed to be some confusion about that here.

RW, there are ways to make a point without putting other people down.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby ravel » Thu Apr 27, 2006 6:57 pm

RW wrote:Hope I didn't confuse you too much with this last example...

Eeh, me yes, can you explain the eliminations please ?

Ron, what makes us always posting at the same time ?:)
ravel
 
Posts: 998
Joined: 21 February 2006

Postby Ocean » Thu Apr 27, 2006 8:27 pm

RW wrote:
Ocean wrote:If the possibility of A is eliminated (by some logic), then B is also not possible.


Yes, if it is eliminated by logic based on placements of numbers. If it was eliminated by uniqueness technique, then both A and B may still be possible if the puzzle has multiple solutions, as shown by Moschopulus here and more recently by myself here. But nobody would ever make such a reduction in a possible multiple solution grid, right?:)



Sure. I edited the post above, so it should be clearer: If configuration A is proved/shown not to result in a valid solution, then also configuration B will not result in a valid solution.
Ocean
 
Posts: 442
Joined: 29 August 2005

Postby RW » Thu Apr 27, 2006 8:31 pm

ronk wrote:RW, there are ways to make a point without putting other people down.


I'm really sorry if I made you feel that way, that was absolutely not my intention. I've noticed that there is lots of uncertainty around this forum about uniqueness patterns in general, so I wanted to put in a post that explains the basic logical rules that govern these. Your post just happened to be the most recent example, and also the post that triggered my idea for this post; when I was thinking of how to answer that post I suddenly realised that uniqueness techniques can be used in non-unique puzzles like this. Thank you for making me think about that! No hard feelings I hope?:)

ravel wrote:Eeh, me yes, can you explain the eliminations please ?


(See ronk, there is a lot of uncertainty around here...)
(Sorry ravel, not my intention to put you down)

A more detailed explanation can be found in my very first post to this forum (which everybody seemed to know already at the time I posted it...). This is a very good example of what I called a "strong link" in a cornerblock in that post.

Code: Select all
 *--------------------------------------------------------------------*
 |*26     1      9      | 37     245   -258    |*368    57    *45678  |
 | 8      3      7      | 1      45     6      | 2      9      45     |
 |*26     5      4      | 37     9     -28     |*368    1     *678    |
 |----------------------+----------------------+----------------------|
 | 17     9      6      | 5      8      3      | 4      2      17     |
 | 3      27     8      | 4      6      12     | 9      57     157    |
 | 15     4      25     | 9      12     7      |*68     3     *68     |
 |----------------------+----------------------+----------------------|
 | 57     8      25     | 6      3      19     | 17     4      29     |
 | 9      6      1      | 2      7      4      | 5      8      3      |
 | 4      27     3      | 8      15     159    | 17     6      29     |
 *--------------------------------------------------------------------*


We don't know the exact location of numbers 6 and 8 yet in box 3, but no matter how we place them, they could not prevent a deadly pattern if number 2 was in r1c6 or r3c6. The different possibilities to place them would be:

-In the same row => UR with r6 (and two 2s in the row we choose)
-In the same column => BUG-lite with r1c16 and r3c16 (and empty cell in c6)
-On either diagonal => BUG-lite with r1c16, r3c16 and r6c79

Code: Select all
In the "corner" of a BUG-lite we do not need to strip down the candidates to a naked pair in two cells - the BUG-lite reduction can also be made if the candidates only appear in four cells that form a 2x2 square that coinsides with the other parts of the BUG-lite.


In my post on uniqueness chains I also explained how some deadly patterns may be found even if the candidates appear in six or even nine different cells of the box. Still confused?

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

Postby ravel » Thu Apr 27, 2006 9:31 pm

RW wrote:(Sorry ravel, not my intention to put you down)

Oh, no problem, i'm used to be down:)
A more detailed explanation can be found in my very first post to this forum

I remember that i did not read all of it. I was not that interested in hard-to-spot uniqueness patterns. and i admit, i am not still now.

But with your explanation i can understand now this very sophisticated sample and i like it, thanks.
ravel
 
Posts: 998
Joined: 21 February 2006

Postby ravel » Fri Apr 28, 2006 9:46 am

When i looked at it again today, it is not that hard to spot:
Code: Select all
 *--------------------------------------------------------------------*
 |*26     1      9      | 37     245   -258    |*368    57    *45678  | 68 28
 | 8      3      7      | 1      45     6      | 2      9      45     |
 |*26     5      4      | 37     9     -28     |*368    1     *678    | 68 28
 |----------------------+----------------------+----------------------|
 | 17     9      6      | 5      8      3      | 4      2      17     |
 | 3      27     8      | 4      6      12     | 9      57     157    |
 | 15     4      25     | 9      12     7      |*68     3     *68     |
 |----------------------+----------------------+----------------------|
 | 57     8      25     | 6      3      19     | 17     4      29     |
 | 9      6      1      | 2      7      4      | 5      8      3      |
 | 4      27     3      | 8      15     159    | 17     6      29     |
 *--------------------------------------------------------------------*
The 68 cross in box 3 together with the 68 pair in row 6 have an effect like a 68 pair in r13 for boxes 1 and 2.
This together with the 26 pair is like a 28 pair for box 2.
That gives an UR type 4, which allows the eliminations.

RW wrote:
Code: Select all
 *-----------*
 |.56|.7.|...|
 |8..|.9.|.7.|
 |4..|.68|.2.|
 |---+---+---|
 |56.|9..|2..|
 |...|.8.|...|
 |..3|..7|.46|
 |---+---+---|
 |.9.|82.|..4|
 |.4.|.5.|..2|
 |...|.3.|96.|
 *-----------*

Can be solved with xy-wing, coloring and one "safe" uniqueness reduction.

Seems that i missed something here also. I had a uniqueness pattern in r29c46, but i ended up with a BUG+1 or a 5 cell chain.
ravel
 
Posts: 998
Joined: 21 February 2006

Postby ronk » Fri Apr 28, 2006 10:56 am

ravel wrote:The 68 cross in box 3 together with the 68 pair in row 6 have an effect like a 68 pair in r13 for boxes 1 and 2.
This together with the 26 pair is like a 28 pair for box 2.
That gives an UR type 4, which allows the eliminations.

Thanks ravel. Your post got me to thinking ... and maybe I now understand RW's "corner" a lot better too.

The "2x2 corner" in 68 has the effect of reflecting the 68 pair in row 6 to rows 1 and 3 of box 3. The BUG-Lite ...
Code: Select all

 26   .    .    | .    .   28+5  | 68+W .    68+X
 .    .    .    | .    .    .    | .    .    .   
 26   .    .    | .    .   28    | 68+Y .    68+Z
----------------+----------------+----------------
 .    .    .    | .    .    .    | .    .    .   
 .    .    .    | .    .    .    | .    .    .   
 .    .    .    | .    .    .    | 68   .    68   
... is thus equivalent to ...
Code: Select all

 26   .    .    | .    .   28+5  | .   [68]  .   
 .    .    .    | .    .    .    | .    .    .   
 26   .    .    | .    .   28    | .   [68]  .   

... and the 28 may be eliminated from r1c6. However, this POV doesn't explain the r3c6<>2 elimination.
Last edited by ronk on Fri Apr 28, 2006 7:17 am, edited 1 time in total.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby ravel » Fri Apr 28, 2006 11:05 am

ronk wrote:However, this POV doesn't explain the r3c6<>2 elimination I recall in RW's post.

It comes from the conjugated 8's in col 6. (Other POV: there is a UR type 1 and type 4.)
ravel
 
Posts: 998
Joined: 21 February 2006

Postby ronk » Fri Apr 28, 2006 12:08 pm

ravel wrote:It comes from the conjugated 8's in col 6. (Other POV: there is a UR type 1 and type 4.)

But, of course. I'm sure you've seen the complexity caused by considering URs together with other strong links on the "UR Type 6" thread. With the larger BUG-Lite patterns, we could all go kwazy.:D
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby RW » Fri Apr 28, 2006 1:28 pm

ronk wrote:However, this POV doesn't explain the r3c6<>2 elimination.


When I use uniqueness technique, I usually don't think in terms of eliminating numbers from within the pattern (like UR type 1 - eliminate ab from the cell with extra candidates). As I usually don't use pms I don't keep track of which cells have extra candidates. I instead think "at least one number must be somewhere outside the pattern". What I would see in this case is:

Code: Select all
 26   .    .    | .    2   28    | .   [68]  .   
 .    .    .    | .    .    .    | .    .    .   
 26   .    .    | .    .   28    | .   [68]  .


only possibility to place an involved number outside the pattern is 2 in r1c5 => r13c6<>2. Then there is of course the strong link on the 8s in box 2 as you already noticed.

ronk wrote:I'm sure you've seen the complexity caused by considering URs together with other strong links on the "UR Type 6" thread. With the larger BUG-Lite patterns, we could all go kwazy.


Yes, and that's the fun part! Who can find the most wacko uniqueness reduction...

In the puzzle that I found the pattern above (posted by ocean, XY-chains #11) basic technique advanced the puzzle to something like this:

Code: Select all
 26   .    .    | .    2+R 28+S  | 68+W 6+Q  68+X
 .    .    .    | .    .    .    | .    .    .   
 26   .    .    | .    .   28    | 68+Y .    68+Z
----------------+----------------+----------------
 .    .    .    | .    .    .    | .    .    .   
 .    .    .    | .    .    .    | .    .    .   
 .    .    .    | .    .    .    | 68   .    68   


and I used the pattern to remove candidate 2 from r1c6 (can you see this reduction..?). I love doing stuff like that!! Then I just bruteforced the 6 into r9c8 before posting the example here to make it clearer, hope you don't mind.:)

ravel wrote:
Code: Select all
 *-----------*
 |.56|.7.|...|
 |8..|.9.|.7.|
 |4..|.68|.2.|
 |---+---+---|
 |56.|9..|2..|
 |...|.8.|...|
 |..3|..7|.46|
 |---+---+---|
 |.9.|82.|..4|
 |.4.|.5.|..2|
 |...|.3.|96.|
 *-----------*
 


Seems that i missed something here also. I had a uniqueness pattern in r29c46, but i ended up with a BUG+1 or a 5 cell chain.


You are not missing anything, I was missing something when I posted it. I pulled it out of a file where I saved lots of interesting puzzles and didn't remember the BUG. Bad example... But to save the situation, when you arrive at the BUG+1:

If r9c3=8 => r4c3=1 => r4c8=8 => r8c8=3 => two 5s in row 7 => r9c3<>8

That shows that one of the BUG solutions causes a contradiction and you can make the safe BUG reduction without assuming an unique soluton!:D

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

Next

Return to Advanced solving techniques