Logical use of uniqueness technique in an uniqueness test

Advanced methods and approaches for solving Sudoku puzzles

Postby ronk » Fri Apr 28, 2006 2:22 pm

RW wrote: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.

Without PMs, you're not even looking at a pattern to be "outside of", you're looking at this ...
Code: Select all
 . 1 9 | . . . | . . .
 8 3 7 | 1 . 6 | 2 9 .
 . 5 4 | . 9 . | . 1 .
-------+-------+-------
 . 9 6 | 5 8 3 | 4 2 .
 3 . 8 | 4 6 . | 9 . .
 . 4 . | 9 . 7 | . 3 .
-------+-------+-------
 . 8 . | 6 3 . | . 4 .
 9 6 1 | 2 7 4 | 5 8 3
 4 . 3 | 8 . . | . 6 .

So would you please explain that step again ... in terms of the givens and placements shown?

[edit: added the following]
RW wrote:In the puzzle that I found the pattern above (posted by ocean, XY-chains #11) ...

Thanks for that link. For a topic where givens are important for some deductions, I think posting the starting grid -- in line format at times to save space -- should be standard procedure anyway.

TIA, Ron
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby RW » Sat Apr 29, 2006 3:49 pm

ronk wrote:Without PMs, you're not even looking at a pattern to be "outside of", you're looking at this ...

Code: Select all
 . 1 9 | . . . | . . .
 8 3 7 | 1 . 6 | 2 9 .
 . 5 4 | . 9 . | . 1 .
-------+-------+-------
 . 9 6 | 5 8 3 | 4 2 .
 3 . 8 | 4 6 . | 9 . .
 . 4 . | 9 . 7 | . 3 .
-------+-------+-------
 . 8 . | 6 3 . | . 4 .
 9 6 1 | 2 7 4 | 5 8 3
 4 . 3 | 8 . . | . 6 .


So would you please explain that step again ... in terms of the givens and placements shown?


As I mentioned the 6 in r9c8 wasn't there when I first spotted the pattern, and in this particular case (I had 17 puzzles to check for the effortless thread) I used Simple Sudoku with pms to save time. I have however found similar patterns several times without pms as well, so here's a short explanation of what I would look at in this grid:

Looking at rows 4-6 I can see the hidden 68 pair:

Code: Select all
 . x 6-|---8---|------
 x . 8-|---6---|------
 . x . | x . x | . x .


Whenever I spot a pair in the same row/column within a box, I look for possible uniqueness patterns. In the box below, both 6 and 8 are in the middle column, they don't interfere with the pair in any way. In the box above they have to go in the corner cells, knowing how a corner works in uniqueness patterns I can continue by examining the positioning of numbers 6 and 8 in boxes 1 and 2.

In box 1 it is not hard to see the 26 pair. If I'm looking at a possible uniqueness patterns with numbers 6 and 8, and I find it aligned with a 2-6 pair, that pair basically ties up the 6 and introduces a 2 to the pattern, so I can continue looking at numbers 2 and 8. According to my theory on uniqueness chains all links so far have been "strong", none of them has allowed me to place any numbers outside the pattern. As this is the case I don't even need to remember what I've been looking at, all I need to concentrate me on is numbers 2 and 8 in row 1 and 3.

Then I look at box 2 and see that number 8 has to go in r1c6 or r3c6 => If 2 went in any of those two cells the chain would be completed. I look for other possible placements for number 2 within the box and find one possible cell, r1c5.

This might sound complicated, but it's actually pretty simple. I just find one pair and continue reading one box at a time until I find either a reduction or that there is no uniqueness reduction to be made associated to that pattern.

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

Postby ravel » Sat Apr 29, 2006 7:38 pm

Its very straightforward for me now to follow your explanations also without pm's. What you did not mention is, that not every pair leads to a uniqueness pattern, so most of these tries will end up without fruits:)

[Edit: deleted the link to a sample, where i made an embarrassing mistake]
Last edited by ravel on Sun Apr 30, 2006 8:33 am, edited 2 times in total.
ravel
 
Posts: 998
Joined: 21 February 2006

Postby ronk » Sat Apr 29, 2006 8:45 pm

RW wrote:
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.:)

Without the placement in r9c8, I don't see it.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby RW » Sat Apr 29, 2006 10:03 pm

ravel wrote:What you did not mention is, that not every pair leads to a uniqueness pattern, so most of these tries will end up without fruits


RW wrote:I just find one pair and continue reading one box at a time until I find either a reduction or that there is no uniqueness reduction to be made associated to that pattern.


Need I say more..?

ronk wrote:
RW wrote:
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.

Without the placement in r9c8, I don't see it.


Only two numbers outside the pattern, 2 in r1c5 and 6 in r1c8:
If r1c6=2 => (r1c5<>2) => r1c1=6 => (r1c8<>6) => r1c6<>2

Sorry the very brief answers, but I really need to go to sleep now...

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

Postby RW » Sun Apr 30, 2006 9:31 am

RW wrote:Only two numbers outside the pattern, 2 in r1c5 and 6 in r1c8:
If r1c6=2 => (r1c5<>2) => r1c1=6 => (r1c8<>6) => r1c6<>2


As one of the "outside" numbers have to be true, you could also consider them "quantum cell" (like in UR type 3) that form a pair together with r1c1 and we can eliminate all other numbers 2 and 6 in the same unit => the pattern also allows us to eliminate candidate 6 from r1c7 and r1c9.

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

Postby ronk » Sun Apr 30, 2006 11:19 am

RW wrote:As one of the "outside" numbers have to be true ...

Thanks. That strong inference -- "if r1c5<>2, then r1c8=6" -- is what I wasn't seeing. Once seen, we have the continuous nice loop

-r1c1-2-r1c5=2|6=r1c8-6-r1c1-

for the eliminations of 2s and 6s elsewere in row 1 (as you pointed out).

RW wrote:... you could also consider them "quantum cell" (like in UR type 3) that form a pair together with r1c1 ...

So the same deduction can be made with both candidates 2 and 6 in either (or both) r1c5 and r1c8.
Code: Select all

 26   .    .    | .   26+R 28+S  | 68+W 26+Q 68+X
 .    .    .    | .    .    .    | .    .    .   
 26   .    .    | .    .   28    | 68+Y .    68+Z
----------------+----------------+----------------
 .    .    .    | .    .    .    | .    .    .   
 .    .    .    | .    .    .    | .    .    .   
 .    .    .    | .    .    .    | 68   .    68

-r1c1-2-r1c58=2|6=r1c58-6-r1c1-
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby RW » Mon May 01, 2006 9:27 am

ronk wrote:So the same deduction can be made with both candidates 2 and 6 in either (or both) r1c5 and r1c8.

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



Theoretically yes, but that situation would be impossible because of the locked candidates. In box 1 and 2 numer 2 has to go in either row 1 or 3 => in box 3 number 2 has to go in row 2. Same goes for number 6 in box 2. If the candidates weren't locked like this, then there would also be possible placements for the involved numbers outside the pattern in row 2 and we couldn't make any deductions.

In my experience, these patterns where we can make some deductions because of strong interference between the numbers outside the pattern are a lot more common than more obvious BUG-lite+1 or similar patterns. When the BUG-lite pattern grows, we might sometimes need to consider a lot of cells, but deductions can still be found. Here's something to practise on, deduce one candidate to solve one number:

Code: Select all
ab+Y.   .  | bc+Z.   .  | ac  .   . 
b+X .   .  | c+W .   .  | .   .   .
ab+V.   .  | bc  .   .  | .   .   ac
-------------------------------------
.   .   .  | .   .   .  | c+Q .   .
.   .   .  | .   .   .  | c+R .   .
.   .   .  | .   .   .  | ac+S.   ac


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

Postby ronk » Mon May 01, 2006 11:27 am

RW wrote:Theoretically yes, but that situation would be impossible because of the locked candidates.

Everyone doesn't always see all the simpler patterns, so I would argue it's a bit better than theoretical.

RW wrote:Here's something to practise on, deduce one candidate to solve one number:
Code: Select all
ab+Y.   .  | bc+Z.   .  | ac  .   . 
b+X .   .  | c+W .   .  | .   .   .
ab+V.   .  | bc  .   .  | .   .   ac
-------------------------------------
.   .   .  | .   .   .  | c+Q .   .
.   .   .  | .   .   .  | c+R .   .
.   .   .  | .   .   .  | ac+S.   ac

At least one of r2c1=b, r2c4=c, and r45c7=c must be true. All cause r3c1<>b. Therefore r3c4=b.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby RW » Tue May 02, 2006 1:06 pm

ronk wrote:
RW wrote:Theoretically yes, but that situation would be impossible because of the locked candidates.

Everyone doesn't always see all the simpler patterns, so I would argue it's a bit better than theoretical.


You are very right there, I should maybe have said that in this particular case it doesn't make it much easier, as the extra candidates 2 and 6 also can be easily eliminated by locked candidates.

ronk wrote:At least one of r2c1=b, r2c4=c, and r45c7=c must be true. All cause r3c1<>b. Therefore r3c4=b.


Very good! I understand that patterns like these are extremely hard to implement in any computer solver, but they are not that impossible for the human eye. There's endless variations that actually appear quite often in all kinds of (sudoku)puzzles.

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

Postby RW » Wed May 03, 2006 8:00 am

Just in case somebody wanted to go kwazy and start programming BUG-lites combined with strong links, my example above could also be solved without considering any cells outside the pattern (not all links in the example are neccessary to make the deduction):

Code: Select all
ab+Y     bc+Z===ac
 ||      ||   c ||
 ||a     ||b    ||a
 ||      ||     ||
ab+V=====bc============ac
      b         ||  c
                ||
                ||
                ac+S   ac


=> r3c1<>b:)

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

Re: Logical use of uniqueness technique in an uniqueness tes

Postby ChPicard » Sun Mar 09, 2008 1:03 pm

Hi
Could you tell me which type of unique rectangles is here because I don't see why the 9 can be removed from r2c6?

Thank you

RW wrote:
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.
RW
ChPicard
 
Posts: 16
Joined: 02 March 2008

Postby ab » Sun Mar 09, 2008 1:26 pm

you must have 5 in one of the four squares marked * . If r2c6 is 9 then r2c8 and r3c6 would be 5 so r3c8 would have to be 9. Assuming the uniqueness of the solution you can eliminate 9 from r2c6.
ab
 
Posts: 451
Joined: 06 September 2005

Re: Logical use of uniqueness technique in an uniqueness tes

Postby ronk » Sun Mar 09, 2008 1:41 pm

ChPicard wrote:Could you tell me which type of unique rectangles is here because I don't see why the 9 can be removed from r2c6?

It is helpful to illustrate this UR as a BUG-Lite+3, meaning 3 cells with extra candidates. To avoid the BUG, at least one of the four extra candidates in r23c68 must be true. Individually consider each candidate to be true and look for a common outcome, using the two strong links for digit 5 in r2 and c6.
Code: Select all
 5    2    9    | 168  18   3    | 7    4     168
 4    3    6    | 189  7   *59+1 | 2   *59+18 189
 1    8    7    | 2    4   *59+6 | 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

I've given up trying to remember the formal name for exotic UR patterns and just use the generic "UR+3 w/ 2SL".
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Previous

Return to Advanced solving techniques