MUGs: Impermeable versus Permeable Deadly Patterns

Advanced methods and approaches for solving Sudoku puzzles

Postby coloin » Wed Jun 18, 2008 4:43 pm

Interesting the difference between here and "Eureka"
http://www.sudoku.org.uk/SudokuThread.asp?fid=4&sid=10218&p1=1&p2=11
.......
Code: Select all
+---+---+---+
|...|...|...|
|12.|34.|...|
|34.|12.|...|
+---+---+---+
|...|...|...|
|...|...|...|
|...|...|...|
+---+---+---+
|...|...|...|
|...|...|...|
|...|...|...|
+---+---+---+

This was one of the U-8 unavoidable sets which cant occur in a valid grid as outlined before.

I havent seen it in a puzzle but......it could still be used as a uniqeness method !

C
coloin
 
Posts: 1637
Joined: 05 May 2005

Postby RW » Wed Jun 18, 2008 9:29 pm

coloin wrote:
Code: Select all
+---+---+---+
|...|...|...|
|12.|34.|...|
|34.|12.|...|
+---+---+---+
|...|...|...|
|...|...|...|
|...|...|...|
+---+---+---+
|...|...|...|
|...|...|...|
|...|...|...|
+---+---+---+

This was one of the U-8 unavoidable sets which cant occur in a valid grid as outlined before.

I havent seen it in a puzzle but......it could still be used as a uniqeness method !

Not really. It is true that you could eliminate any candidate that would lead to that formation, or this in the pm grid:
Code: Select all
.    .    .    | .    .    .
abcd abcd .    | abcd abcd .
abcd abcd .    | abcd abcd .

But, this wouldn't technically be an uniqueness elimination. That pattern will always result in zero solutions, so it is a regular solving technique that can be used without assuming uniqueness.

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

Postby Myth Jellies » Thu Jun 19, 2008 7:20 am

But the following would work as a potential MUG uniqueness pattern

Code: Select all
 .  abcd . | abcd abcd . | .   abcd .
 .  abcd . | abcd abcd . | .   abcd .
 .  .    . | .    .    . | .   .    .
-----------+-------------+------------
 .  .    . | .    .    . | .   .    .
 .  .    . | .    .    . | .   .    .
 .  .    . | .    .    . | .   .    .
-----------+-------------+------------
 .  .    . | .    .    . | .   .    .
 .  .    . | .    .    . | .   .    .
 .  .    . | .    .    . | .   .    .

which could reduce to...
Code: Select all
 .  ab   . | abcd abcd . | .   cd   .
 .  ab   . | abcd abcd . | .   cd   .
(c) .   (d)| .    .    . |(a)  .   (b)
-----------+-------------+------------
 . (c)   . | .    .    . | .  (a)   .
 . (d)   . | .    .    . | .  (b)   .
 .  .    . | .    .    . | .   .    .
-----------+-------------+------------
 .  .    . | .    .    . | .   .    .
 .  .    . | .    .    . | .   .    .
 .  .    . | .    .    . | .   .    .


or from an unavoidable set viewpoint, the U8...
Code: Select all
+---+---+---+
|...|...|...|
|.1.|23.|.4.|
|.2.|41.|.3.|
+---+---+---+
|...|...|...|
|...|...|...|
|...|...|...|
+---+---+---+
|...|...|...|
|...|...|...|
|...|...|...|
+---+---+---+

...along with the paired U4s like...
Code: Select all
+---+---+---+
|...|...|...|
|.1.|23.|.4.|
|.2.|14.|.3.|
+---+---+---+
|...|...|...|
|...|...|...|
|...|...|...|
+---+---+---+
|...|...|...|
|...|...|...|
|...|...|...|
+---+---+---+
Myth Jellies
 
Posts: 593
Joined: 19 September 2005

Postby coloin » Thu Jun 19, 2008 9:44 am

Thanks RW thats what I meant.

Have we any other [hard] examples of an elimination which is based on "validity" or gives zero solutions.

Of course every "wrong" PM gives zero solutions......

Code: Select all
+---+---+---+
|...|...|...|
|12.|3?.|...|
|34.|12.|...|
+---+---+---+
|...|...|...|
|...|...|...|
|...|...|...|
+---+---+---+
|...|...|...|
|...|...|...|
|...|...|...|
+---+---+---+

Assuming validity......we do this with every puzzle
we know r2c4 cant be 123 because it has zero solutions
we know r2c4 cant be a 4 because it has zero solutions
we know r2c4 has to be one of 56789 because of zero solutions

Actually this pattern always gives a hidden triplet [123] in r1c789 this rules out the 4 in r2c4 and r2c5.

So when does this go from non-assumptive to become assumptive ????

Is it when you can find it and see it for yourself ? [without computor aid ?]

Myth I dont think the U8 is complete. There are 3 other ways to represent the converse of this paired U4. [Which are paired U4s]

C
coloin
 
Posts: 1637
Joined: 05 May 2005

Postby ronk » Thu Jun 19, 2008 8:12 pm

RW wrote:
Code: Select all
*13469   *1349   5     | 8 *23679 *2369 |*1234679 *269  *1279
*13469+8 *1349+8 469-8 | 5 *23679 *2369 |*1234679 *269  *1279+8
 2        389    7     | 4  369    1    | 3569     569   589

(MUG on digits 1234679 in r78c1256789 solves the puzzle.)

These big MUGs have me scratching my head.

Would the most generalized pattern for this MUG have all 7 candidates at all 14 cells?

To what BUG-Lite pattern might this MUG reduce?

If a potential MUG is reducible to one BUG-Lite, is that sufficient to prove that all reductions lead to BUG-Lites?

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

Postby Myth Jellies » Fri Jun 20, 2008 7:10 am

coloin wrote:Thanks RW thats what I meant.

Have we any other [hard] examples of an elimination which is based on "validity" or gives zero solutions.

Of course every "wrong" PM gives zero solutions......

Code: Select all
+---+---+---+
|...|...|...|
|12.|3?.|...|
|34.|12.|...|
+---+---+---+
|...|...|...|
|...|...|...|
|...|...|...|
+---+---+---+
|...|...|...|
|...|...|...|
|...|...|...|
+---+---+---+

Assuming validity......we do this with every puzzle
we know r2c4 cant be 123 because it has zero solutions
we know r2c4 cant be a 4 because it has zero solutions
we know r2c4 has to be one of 56789 because of zero solutions

Actually this pattern always gives a hidden triplet [123] in r1c789 this rules out the 4 in r2c4 and r2c5.

So when does this go from non-assumptive to become assumptive ????

Is it when you can find it and see it for yourself ? [without computor aid ?]

Myth I dont think the U8 is complete. There are 3 other ways to represent the converse of this paired U4. [Which are paired U4s]

To my way of thinking, as long as you are building from some set of observable subpatterns, such as the hidden triple that eliminates all fours in row one except those in box 2 (locked candidates) or your impossible pattern to eliminate the 4 from r2c5; then you require no assumptions in making your deduction. If you in some way assume that the 4 in r2c5 is true and then work out that row 1 can not be completed, then you have made the deduction assumptively. The first cases imply that you have worked out a pattern that you can use on other puzzles. The last case implies that you haven't worked out a pattern that leads to the same deduction yet.

As for the U8 and U4+U4 pair, I thought that one was allowed to treat equivalent transformations as part of the same pattern. Thus one is allowed to substitute one digit for another. Also one should be allowed to swap two rows or two columns within a chute, as well as swap two chutes. Thus if you allow digits swaps and/or c4 and c5 to swap and/or r2 and r3 to swap, I think those two representations actually cover everything, though I have been wrong about this sort of thing before.

Your pattern (slightly modified)...
Code: Select all
+----+----+----+----+
|....|....|....|....|
|12..|34..|....|....|
|34..|21..|....|....|
+----+----+----+----+
|....|....|....|....|

...is a multi-solution unavoidable set on a 16x16 grid

I have seen something similar on a 9x9 though, this U12
Code: Select all
 abcd abcd . | abcd abcd . | .   .    .
 abcd abcd . | .    .    . | .   abcd abcd
 .    .    . | abcd abcd . | .   abcd abcd
-------------+-------------+------------
 .    .    . | .    .    . | .   .    .
 .    .    . | .    .    . | .   .    .
 .    .    . | .    .    . | .   .    .
-------------+-------------+------------
 .    .    . | .    .    . | .   .    .
 .    .    . | .    .    . | .   .    .
 .    .    . | .    .    . | .   .    .


which I didn't actually catch until it had become a BUG-Lite, something like
Code: Select all
 ab   cd   . | ac   bd   . | .   .    .
 ab   cd   . | .    .    . | .   ad   bc
 .    .    . | ac   bd   . | .   ad   bc
-------------+-------------+------------
 .    .    . | .    .    . | .   .    .
 .    .    . | .    .    . | .   .    .
 .    .    . | .    .    . | .   .    .
-------------+-------------+------------
 .    .    . | .    .    . | .   .    .
 .    .    . | .    .    . | .   .    .
 .    .    . | .    .    . | .   .    .

AU Tough for Feb. 22 presented at this stage on the daily sudoku forum
Code: Select all
+-----------+--------------+----------+
| 3  4 -158 | 9  *28+5 *17 |*12 6 *78 |
|*27 9 *18  | 6  *28   *17 | 3  5  4  |
|*27 6 *18+5|-25  4     3  |*12 9 *78 |
+-----------+--------------+----------+
| 5  3  6   | 4   7     9  | 8  1  2  |
| 9  2  4   | 3   1     8  | 5  7  6  |
| 1  8  7   | 25  25    6  | 9  4  3  |
+-----------+--------------+----------+
| 8  5  3   | 1   6     4  | 7  2  9  |
| 6  7  2   | 8   9     5  | 4  3  1  |
| 4  1  9   | 7   3     2  | 6  8  5  |
+-----------+--------------+----------+
Myth Jellies
 
Posts: 593
Joined: 19 September 2005

Postby Myth Jellies » Fri Jun 20, 2008 7:45 am

ronk wrote:
RW wrote:
Code: Select all
*13469   *1349   5     | 8 *23679 *2369 |*1234679 *269  *1279
*13469+8 *1349+8 469-8 | 5 *23679 *2369 |*1234679 *269  *1279+8
 2        389    7     | 4  369    1    | 3569     569   589

(MUG on digits 1234679 in r78c1256789 solves the puzzle.)

These big MUGs have me scratching my head.

Would the most generalized pattern for this MUG have all 7 candidates at all 14 cells?

Yes!

ronk wrote:To what BUG-Lite pattern might this MUG reduce?

Could be something like
Code: Select all
*13   *49   5     | 8 *27 *36 |*47 *26  *19
*13+8 *49+8 469-8 | 5 *27 *36 |*47 *26  *19+8


ronk wrote:If a potential MUG is reducible to one BUG-Lite, is that sufficient to prove that all reductions lead to BUG-Lites?

Unfortunately no. You have to prove that all possible external placements would result in a zero- or multi-solution state. Fortunately, depending on the pattern in question, the locations for these possible placements can be quite limited.
Myth Jellies
 
Posts: 593
Joined: 19 September 2005

Previous

Return to Advanced solving techniques