Uniqueness chains

Advanced methods and approaches for solving Sudoku puzzles

Postby RW » Tue Mar 28, 2006 6:44 pm

Jeff wrote:There are 3 types of instances, namely given, solved and unsolved. I am interested to know why the solved instances don't have to be included in the reverse BUG pattern for the technique to work properly.


To understand why, you have to understand the nature of a BUG-lite pattern. In any BUG-lite pattern all included cells can switch numbers and still give a valid solution. Example with three pairs:
Code: Select all
.  ab .  |.  .  ab |.  .  .
.  ab .  |.  .  .  |.  ab .
.  .  .  |.  .  ab |.  ab .

Gives two solutions:

.a.|..b|...     .b.|..a|...
.b.|...|.a.     .a.|...|.b.
...|..a|.b.     ...|..b|.a.

Here it doesn't matter if you have solved one of the included numbers in some way (T&E or uniqueness are the only possible), you will still have two solutions.

So in this case where A is a solved instance and the other are candidates you can still be sure that the cell below A holds number c if you know the puzzle has only one solution:
Code: Select all
.  A  .  |.  .  ab |.  .  .
bc bc .  |.  .  .  |.  ab .
.  .  .  |.  .  ab |.  ab .


In the case of a reverse BUG we know that the remaining instances of our numbers would form a BUG-lite pattern, if the reverse BUG was completed. Here the same rule applies. It doesn't matter if there is solved instances in the BUG-lite pattern, it will still have two valid solutions that satisfy the basic rule: all numbers appear once in every row, column and box.

Let's go back to the example I showed earlier in this thread. I filtered out all information except regarding numbers 1 and 2. The numbers marked with stars are Given or solved, all other are candidates.
Code: Select all
*--------------------------------------*
|    (12)(12)|        (12)|(12)        |
|        (12)| (2)        |(12)        |
|    (12)    |        (12)|            |
|--------------------------------------|
|            |    (2)  (2)|        *1  |
|*1          |            |    *2      |
|*2          |    *1      |            |
|--------------------------------------|
|    (12)    |(12)(2)     |            |
|            |            |    *1  *2  |
|    (12)(12)|(12)(2)     |            |
*--------------------------------------*

Now let's say we managed to solve r7c4 with T&E:
Code: Select all
*--------------------------------------*
|    (12)(12)|        (12)|(12)        |
|        (12)|(2)         |(12)        |
|    (12)    |        (12)|            |
|--------------------------------------|
|            |    (2)  (2)|        *1  |
|*1          |            |    *2      |
|*2          |    *1      |            |
|--------------------------------------|
|    (2)     | 1  (2)     |            |
|            |            |    *1  *2  |
|    (12)(12)|(2) (2)     |            |
*--------------------------------------*

Still if we completed the reverse BUG pattern with number 2 in r4c5 the closest we could ever get to a unique solution is something like this:
Code: Select all
*--------------------------------*
|          |       1  | 2        |
|       2  |          | 1        |
|    1     |       2  |          |
|--------------------------------|
|          |    2     |      *1  |
|*1        |          |   *2     |
|*2        |   *1     |          |
|--------------------------------|
|    2     | 1        |          |
|          |          |   *1 *2  |
|       1  | 2        |          |
*--------------------------------*

Which could be changed into this:
Code: Select all
*--------------------------------*
|          |       2  | 1        |
|       1  |          | 2        |
|    2     |       1  |          |
|--------------------------------|
|          |    2     |      *1  |
|*1        |          |   *2     |
|*2        |   *1     |          |
|--------------------------------|
|    1     | 2        |          |
|          |          |   *1 *2  |
|       2  | 1        |          |
*--------------------------------*

with the same two numbers, occupying the same cells, and still appearing only once each in every row, column and box => The double solution is a fact even if there is a solved number not included in the reverse BUG pattern.

As a basic rule when it comes to uniqueness patterns is that solved numbers are no stronger than unsolved numbers. If they are part in a BUG-lite pattern they can still be switched.

Did that clear things up for you?

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

Postby Jeff » Wed Mar 29, 2006 4:59 am

RW, thank you so much for the lengthy explanation.:D IOW, the 2 solutions in a 2-digit BUG pattern are generated by the 2 digits swapping places without affecting any placements in other cells of the grid. Since all given cells contain fixed digits and cannot swap places, they must not be included as part of the 2-digit BUG pattern. The only way to ensure that is to include all given cells in the 1-digit reverse BUG pattern.
Jeff
 
Posts: 708
Joined: 01 August 2005

Postby RW » Wed Mar 29, 2006 6:36 am

Jeff wrote:Since all given cells contain fixed digits and cannot swap places, they must not be included as part of the 2-digit BUG pattern.

Yes, if we are to make a reduction based on the fact that a puzzle otherwise would have two solutions.

This thread seems to have got a bit confusing as it discusses two different topics, or actually the same topic from two different points of view. My original post conserned identification of complex double-solution patterns by defining a chain with strong and weak links. Then I realised that if there is only two different numbers involved, the pattern might be easier to identify by looking at the already solved cells instead of the empty cells (reverse BUG), which has been discussed since that.

However, this doesn’t replace my original theory on uniqueness chains, the reverse BUG can only be applied if there is only two numbers involved. I wish to bring up the original topic once more, as I finally found a puzzle that can be solved with knowledge of advanced uniqueness chains:
Code: Select all
*-----------*
 |...|..4|.82|
 |.79|.8.|.4.|
 |.6.|7.5|.9.|
 |---+---+---|
 |...|...|...|
 |.31|2..|...|
 |.8.|43.|..7|
 |---+---+---|
 |...|6..|..5|
 |.4.|8..|.7.|
 |..3|...|9..|
 *-----------*

The basic techniques takes us this far:
Code: Select all
 
 *--------------------------------------------------------------------*
 | 3      1      5      | 9      6      4      | 7      8      2      |
 | 2      7      9      | 3      8      1      | 5      4      6      |
 | 48     6      48     | 7      2      5      | 13     9      13     |
 |----------------------+----------------------+----------------------|
 | 4679   259    47     | 15     179    6789   | 2368   236    489    |
 | 45679  3      1      | 2      579    6789   | 468    56     489    |
 | 569    8      26     | 4      3      69     | 126    125    7      |
 |----------------------+----------------------+----------------------|
 | 1789   29     78     | 6      1479   237    | 48     123    5      |
 | 1569   4      26     | 8      159    239    | 1236   7      13     |
 | 1678   25     3      | 15     147    27     | 9      126    48     |
 *--------------------------------------------------------------------*

Here we can make a simple uniqueness reduction and remove candidates 1 and 3 from R8C7 (uniqueness rectangle in R38C79). This reveals a pair, a x-wing and some other reductions that take us here:
Code: Select all
 *--------------------------------------------------------------------*
 | 3      1      5      | 9      6      4      | 7      8      2      |
 | 2      7      9      | 3      8      1      | 5      4      6      |
 | 48     6      48     | 7      2      5      | 13     9      13     |
 |----------------------+----------------------+----------------------|
 | 4679   259    47     | 15     179    6789   | 3468   236    489    |
 | 45679  3      1      | 2      579    6789   | 468    56     489    |
 | 569    8      26     | 4      3      69     | 126    15     7      |
 |----------------------+----------------------+----------------------|
 | 1789   29     78     | 6      1479   237    | 48     123    5      |
 | 159    4      26     | 8      159    39     | 26     7      13     |
 | 1678   25     3      | 15     147    27     | 9      126    48     |
 *--------------------------------------------------------------------*

To refresh your memory I’ll repeat the theory on strong weak links in an uniqueness chain:

A strong link is a link that cannot break the uniqueness chain, the candidates are already forced into place. A weak link has at least one optional solution.

At the end of the chain or in the middle of a straight three pair chain a strong link occurs when the two digits involved are forced into a pair in the same column/row.

In a cornerblock a strong link occurs when the two digits involved are forced into 2x2 cells that coinside with the chains on both sides.


[edit: Just noticed that I'm using the same terminology here (strong and weak link) that you use for other purposes in nice loops. Please do not mix up these totally different things. My strong link is a set of candidates that couldn't possibly give a unique solution if they are part of a uniqueness chain (all cells are included in the uniqueness pattern). A weak link is a set of candidates where at least one candidate is outside the uniqueness pattern. If anybody can come up with better names for these, that cannot be mixed up with another technique, please suggest.]

Having said this, let’s try to solve the puzzle. What we are dealing with here is a 7-link chain with candidates spread over 22 cells, so I think the best thing to do is hide all unneccessary information. When identifying patterns like these we usually don’t need to consider the numbers not involved, so I will remove everything that doesn’t concern numbers 4, 7 or 8:
Code: Select all
*-----------------------------------------*
|             |          4  | 7    8      |
|      7      |     8       |      4      |
|(48)     (48)| 7           |             |
|-------------+-------------+-------------|
|(47)     (47)|    (7)  (78)|(48)     (48)|
|(47)     (47)|    (7)  (78)|(48)     (48)|
|      8      | 4           |      7      |
|-------------+-------------+-------------|
|(78)     (78)|    (47) (7) |(48)     (48)|
|      4      | 8           |      7      |
|(78)     (78)|    (47) (7) |(48)     (48)|
*-----------------------------------------*

Now we can read the chain: Box 1 definitely holds a strong link (a pair in the same row). Looking down from there we can see that both boxes 4 and 7 hold strong links, if they turn out to be cornerblocks (two numbers forced into 2x2 cells). Looking right from box 4 we can see a weak link in box 5 (would be a strong link if number 7 went in column 6) and a strong cornerlink in box 6. Lookin right form box 7 we see the same thing, a weak link in box 8 (would be strong if number 7 went in column 5) and a strong cornerlink in box 9.

This is a 7-link chain with 5 strong links and 2 weak links. If number 7 went in R45C6 or R79C5 all links in the chain would be strong => double solution => we can remove candidate 7 from R45C6 and R79C5. This reveals a naked triplet and a single (R8C6=3) which solves the puzzle.

Questions? Please consult the original message of this thread. If that doesn’t give you an answer, feel free to ask.

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

Previous

Return to Advanced solving techniques