May 6, 2006: UR's and Coloring

[keith]

Today's puzzle is interesting. With possibilities, the starting point is:

Code: Select all

+----------------------+----------------------+----------------------+
| 5      29     289    | 4      6      1789   | 3      12     127    | 
| 7      4      2369   | 2359   19     159    | 1256   8      12     | 
| 238    1      2368   | 23578  8      578    | 9      2456   247    | 
+----------------------+----------------------+----------------------+
| 6      579    1589   | 89     3      2      | 1478   149    1479   | 
| 123489 2379   12389  | 689    5      4689   | 124678 12469  123479 | 
| 23489  239    2389   | 1      7      4689   | 2468   2469   5      | 
+----------------------+----------------------+----------------------+
| 1239   23569  4      | 5689   189    15689  | 125    7      129    | 
| 129    8      1259   | 579    149    14579  | 1245   3      6      | 
| 19     569    7      | 569    2      3      | 145    1459   8      | 
+----------------------+----------------------+----------------------+

After the usual, we get to:

Code: Select all

+----------------+----------------+----------------+
| 5    29   8    | 4    6    19   | 3    12   7    | 
| 7    4    239  | 23   19   5    | 6    8    12   | 
| 23   1    6    | 23   8    7    | 9    5    4    | 
+----------------+----------------+----------------+
| 6    579  159  | 89   3    2    | 1478 149  19   | 
| 48   279  129  | 689  5    468  | 1278 1269 3    | 
| 48   239  239  | 1    7    468  | 28   269  5    | 
+----------------+----------------+----------------+
| 1239 2356 4    | 568  19   68   | 125  7    129  | 
| 129  8    25   | 7    4    19   | 125  3    6    | 
| 19   56   7    | 56   2    3    | 14   149  8    | 
+----------------+----------------+----------------+
 

There is a Unique Rectangle on <48> in R56C16. There are two ways to look at the reductions:

One of R56C6 must be <6>. Therefore, R7C6 cannot be <6> and must be <8>. (Edit: Oops! I missed the elimination of <6> in R5C4!)

The only possibilities of <4> in C6 are in R56. Therefore, R56C6 cannot be <8>, and the only remaining possibility is R7C6 is <8>.

This reveals another UR on <56> in R79C24. R7C2 cannot be <56>. After further reductions, we get to:

Code: Select all

+----------------+----------------+----------------+
| 5    29b  8    | 4    6    19   | 3    12a  7    | 
| 7    4    239  | 23   19   5    | 6    8    12b  | 
| 23   1    6    | 23   8    7    | 9    5    4    | 
+----------------+----------------+----------------+
| 6    5    19   | 8    3    2    | 7    4    19   | 
| 48   7    12   | 9    5    46   | 128  126  3    | 
| 48   239  239  | 1    7    46   | 28   269  5    | 
+----------------+----------------+----------------+
| 1239 23   4    | 6    19   8    | 5    7    129a | 
| 129  8    5    | 7    4    19   | 12   3    6    | 
| 19   6    7    | 5    2    3    | 4    19   8    | 
+----------------+----------------+----------------+
 

Let's ignore the XYZ-wing on <128> which eliminates <2> in R5C8. Instead, there is a coloring chain on <2> that says R7C2 must be <3>. We get to here:

Code: Select all

+-------------+-------------+-------------+
| 5   29c 8   | 4   6   19  | 3   12d 7   | 
| 7   4   29b | 3   19a 5   | 6   8   12c | 
| 3   1   6   | 2   8   7   | 9   5   4   | 
+-------------+-------------+-------------+
| 6   5   19a | 8   3   2   | 7   4   19b | 
| 48  7   12  | 9   5   46  | 128 126 3   | 
| 48  29d 3   | 1   7   46  | 28  269 5   | 
+-------------+-------------+-------------+
| 129 3   4   | 6   19b 8   | 5   7  129ad| 
| 129 8   5   | 7   4   19  | 12c 3   6   | 
| 19  6   7   | 5   2   3   | 4   19  8   | 
+-------------+-------------+-------------+
 

and, coloring on <9> says that R7C1 cannot be <9>. (Actually, this is a swordfish on <9>.)

Also, coloring on <2>, eliminates <2> from R6C7, and we get to:

Code: Select all

+-------------+-------------+-------------+
| 5   29  8   | 4   6   19b | 3   12c 7   | 
| 7   4   29  | 3   19  5   | 6   8   12  | 
| 3   1   6   | 2   8   7   | 9   5   4   | 
+-------------+-------------+-------------+
| 6   5   19  | 8   3   2   | 7   4   19  | 
| 8   7   12  | 9   5   4   | 12  6   3   | 
| 4   29  3   | 1   7   6   | 8   29  5   | 
+-------------+-------------+-------------+
| 12  3   4   | 6   19  8   | 5   7   129 | 
| 129 8   5   | 7   4   19a | 12  3   6   | 
| 19  6   7   | 5   2   3   | 4   19d 8   | 
+-------------+-------------+-------------+

There is an XY-wing, but rather take a look at the possibilities for <1> in C6 and C8. This is a "fork": At least one of the cells labeled a and d is <1>. So, R8C7 is not <1>. (The XY-wing is <29-1> in R2C3, eliminating <1> in R4C9.)

This solves the puzzle.

Keith

[David Bryant]

Just to demonstrate (again) that useful "constellations" are often associated with "non-unique rectangles", here is another way to solve the 6 May, 2006 nightmare.

Here's the position at which Keith began his "UR" analysis.

Code: Select all

  5    29     8     4     6    19     3    12     7
  7     4    239   23    19     5     6     8    12
 23     1     6    23     8     7     9     5     4
  6    579   159   89     3     2   1478   149   19
 48    279   129   689    5    468  1278  1269    3
 48    239   239    1     7    468   28    269    5
1239  2356    4    568   19    68    125    7    129
 129    8    125    7     4    19    125    3     6
 19    56     7    56     2     3    14    149    8

The configuration of the pair {1, 2} in the top right 3x3 box alongside the pairs {1, 9} in columns 5 & 6 is inherently unstable:

r4c9 = 1 ==> r2c9 = 2 ==> r7c9 = 9 ==> r7c5 = 1 ==> r2c5 = 9 ==> r1c6 = 1 ==> r1c8 = 2

Since we can't have two "2"s in the top right 3x3 box we must have r4c9 = 9. This leads to a series of fairly obvious moves, ending in this position.

Code: Select all

  5    29     8     4     6    19     3    12     7
  7     4    39    23    19     5     6     8    12
 23     1     6    23     8     7     9     5     4
  6    57    15     8     3     2    17     4     9
 48    27    12     9     5    46   1278   126    3
 48    39    39     1     7    46    28    26     5
 239  2356    4    56    19     8    125    7    12
 29     8    25     7     4    19    125    3     6
  1    56     7    56     2     3     4     9     8

Now a double-implication chain from r6c2 is enough to finish it off.

A. r6c2 = 3 ==> r7c1 = 3 ==> r8c1 = 9
B. r6c2 = 9 ==> r1c6 = 9 ==> r8c1 = 9

With r8c1 = 9, the rest of the puzzle is singles all the way.

Now, why do I say these "constellations" are directly connected with the "UR"s in Keith's post? Let's examine each position a little more closely.

Code: Select all

  5    29     8     4     6    19     3    12     7
  7     4    239   23    19     5     6     8    12
 23     1     6    23     8     7     9     5     4
  6    579   159   89     3     2   1478   149   19
 48    279   129   689    5    468  1278  1269    3
 48    239   239    1     7    468   28    269    5
1239  2356    4    568   19    68    125    7    129
 129    8    125    7     4    19    125    3     6
 19    56     7    56     2     3    14    149    8

There are two "conjugate" positions for the "6" that the "UR" analysis says must appear at r5c6 or r6c6 -- these are at r5c4 and at r7c6.

A. r5c4 = 6 ==> r4c4 = 9 ==> r4c9 = 1 (leading to a contradiction).
B. r7c6 = 6 ==> {4, 8} pair in c6r5&6 ==> r4c4 = 9, etc.

Code: Select all

  5    29     8     4     6    19     3    12     7
  7     4    39    23    19     5     6     8    12
 23     1     6    23     8     7     9     5     4
  6    57    15     8     3     2    17     4     9
 48    27    12     9     5    46   1278   126    3
 48    39    39     1     7    46    28    26     5
 239  2356    4    56    19     8    125    7    12
 29     8    25     7     4    19    125    3     6
  1    56     7    56     2     3     4     9     8

From this second position, Keith's "UR" analysis showed that r7c2 = 3. The two "conjugate" cells are r7c1 and r6c2. We've already seen how a double-implication chain from one of those cells (r6c2) shows that r8c1 = 9. What happens if we start working from r7c1 instead?

A. r7c1 = 9 ==> r8c1 = 2
B. r7c1 = 9 ==> r2c5 = 9 ==> r2c3 = 3 ==> r3c1 = 2

So there' can't be a "9" at r7c1, and the "9" in the bottom left 3x3 box must lie at r8c1, just as before.

I think this connection between "non-unique rectangles" and double-implication chains is fascinating ... I'd like to understand what causes it to be so. dcb

[keith]

David said:

I think this connection between "non-unique rectangles" and double-implication chains is fascinating ... I'd like to understand what causes it to be so. dcb

Doubly so, because the UR's have the extra assumption of uniqueness. Or, is it that the UR pattern is useful even if uniqueness is not assumed?

(Actually, I think you will find that the UR pattern often comes with strong (conjugate) links that make it susceptible to other reductions.)

Keith

[David Bryant]

Some "non-unique rectangles" are more deeply embedded than others. This puzzle is a good example of a very tough UR.

Code: Select all

 *-----------*
 |91.|4..|2..|
 |8..|..6|...|
 |.3.|7..|.6.|
 |---+---+---|
 |...|..4|5..|
 |4..|.1.|..6|
 |..1|9..|...|
 |---+---+---|
 |.7.|..3|.9.|
 |...|6..|..3|
 |..5|..7|.84|
 *-----------*

After a series of mostly unexceptional moves (including a "fork" on the "2"s, and one XY-Wing from r8c6) I arrived at this position.

Code: Select all

  9     1     6     4    358   58     2    35     7
  8    245    7    12   2359    6    349  1345   159
 25     3    24     7    259   19    489    6   1589
 267  2689   389   38    67     4     5    12   1289
  4   2589  2389   358    1    258   89     7     6
2567  2568    1     9    67    258   34    34    28
 16     7    248   58    458    3    16     9    25
 12   2489  2489    6    458   19     7    25     3
  3    69     5    12    29     7    16     8     4

At this point, assuming the solution is unique, we easily see that r8c1 <> 2; if we set r8c1 = 2 we will have r3c1 = 5, and the "deadly pattern" will emerge at r4&6, c1&8. Can we also solve this puzzle without making the "uniquitous" assumption?

Yes, we can. But it's a bit more difficult than usual.

-- r1c5 <> 3. We can show this with a double-implication chain.
A. r1c5 = 3 ==> r1c8 = 5 ==> r8c8 = 2
B. r1c5 = 3 ==> {2, 5, 9} triplet in column 5 ==> r7c4 = 5 ==> r7c9 = 2

So we can set r1c8 = 3, r2c5 = 3, r6c8 = 4, and r6c7 = 3. We can also eliminate the "5" at r3c5 and the "9"s at r3c7&9, leaving the grid in this position.

Code: Select all

  9     1     6     4    58    58     2     3     7
  8    245    7    12     3     6    49    15    159
 25     3    24     7    29    19    48     6    158b
 267  2689   389   38    67     4     5    12   1289
  4   2589  2389   358    1    258   89     7     6
2567  2568    1     9    67    258    3     4    28a
 16     7    248   58    458    3    16     9    25
 12   2489  2489    6    458A  19     7    25     3
  3    69     5    12    29     7    16     8     4

-- r8c5 <> 4. The double-implication chain is fairly cute.
A. r8c5 = 4 ==> {5, 8} pair in row 7 ==> r7c9 = 2 ==> r6c9 = 8
B. r8c5 = 4 ==> r7c3 = 4 ==> r3c7 = 4 ==> r3c9 = 8

This doesn't lead to any more immediate eliminations, but it does leave us with a nice configuration in the {5, 8} pairs that allows us to crack the puzzle.

Code: Select all

  9     1     6     4    58*   58*    2     3     7
  8    245    7    12     3     6    49    15b   159
 25c    3    24     7    29    19    48     6    158d
 267  2689   389   38    67     4     5    12   1289
  4   2589B 2389   358    1    258   89     7     6
2567  2568    1     9    67    258A   3     4    28a
 16     7    28    58*    4     3    16     9    25
 12   2489  2489    6    58*   19     7    25B    3
  3    69     5    12    29     7    16     8     4

-- r6c6 <> 5. To make this deduction we must first observe the chain leading through the {5, 8} pairs, so that r6c6 = 5 ==> r7c4 = 5.
A. r6c6 = 5 ==> r7c4 = 5 ==> r7c9 = 2 ==> r6c9 = 8
B. r7c9 = 2 ==> r8c8 = 5 ==> r2c8 = 1
C. r6c6 = 5 ==> r5c2 = 5 ==> r3c1 = 5
D. (r2c8 = 1 & r3c1 = 5) ==> r3c9 = 8

Eliminating the "5" at r6c6 leaves the {2, 8} pair in row 6, leading to a few more or less obvious eliminations. Now the grid looks like this.

Code: Select all

  9     1     6     4    58    58     2     3     7
  8    245    7    12     3     6    49    15    159
 25     3    24     7    29    19    48     6    158
 267  2689   389   38    67     4     5    12   1289
  4   2589  2389   358A   1    258   89     7     6
 567   56     1     9    67    28     3     4    28
 16     7    28a   58     4     3    16     9    25
 12   2489  2489    6    58    19     7    25b    3
  3    69     5    12    29c    7    16     8     4

-- r5c4 <> 5. Setting r5c4 = 5 forces two "5"s into row 2, as follows.
A. r5c4 = 5 ==> r7c4 = 8 ==> r7c3 = 2
B. r7c3 = 2 ==> r8c8 = 2
C. r7c3 = 2 ==> r8c1 = 1 ==> r7c1 = 6 ==> r9c2 = 9 ==> r9c5 = 2
D. (r7c3 = 2 & r9c5 = 2) ==> r3c1 = 2 (only spot left open in row 3)
E. r8c8 = 2 ==> r2c8 = 5
F. r3c1 = 2 ==> r3c3 = 4 ==> r2c2 = 5

This leaves r5c6 as the only spot left for a "5" in the middle center 3x3 box, and the rest of the puzzle is singles all the way.

Oh -- one thing I find really fascinating about this procedure when compared to the "non-unique rectangle" is that the final forcing chain depends heavily on the positions of the digits "2" and "5". Not so coincidentally, the digits that might conceivably break up the "UR" on the pair {6, 7} at this point are -- you guessed it -- "2" and "5". dcb