Forming MUGs from BUG-Lite composites

Advanced methods and approaches for solving Sudoku puzzles

Postby Myth Jellies » Sat Feb 18, 2006 11:15 am

Nice find, Vidar. You ought to submit that one to the type 3 uniqueness post. It's a beauty.:)

Here are a couple more candidates for MUGs. Note that in and of themselves, they are not all that useful, but if you whittle them down by successive eliminations of all of a digit's candidates in a group, you may be able to tailor them into something you can use.

...Edit - Vidar and aeb have disproven all of the following MUGs. I thought I had a means of building them, but alas, no.

Here is a six-digit MUG candidate.

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

Solving for an 'f' outside the pattern in rows 1 and 2, and in column 4 gets you to a five-digit MUG.
Code: Select all
(f) .  abcde  | abcde  .  abcde  | abcde  .  .
 .  .  abcde  | abcde  .  abcde  | abcde  . (f)
 .  .  abcde  | abcde  .  f      | abcde  .  .
--------------+------------------+---------------
 .  .  .      | abcde  .  abcde  | .      .  .
 .  .  .      | .      .  .      | .      .  .
 .  .  .      | .      .  .      | .      .  .
--------------+------------------+---------------
 .  .  .      | .      .  .      | .      .  .
 .  .  .      | .      .  .      | .      .  .
 .  .  .      |(f)     .  .      | .      .  .


And, just for grins and giggles, here is a nine-digit MUG
Code: Select all
 .   .   .   | .   .   .   | .   .   .
 .   .   .   | 1-9 1-9 1-9 | .   .   .
 .   .   .   | .   .   .   | .   .   .
-------------+-------------+---------------
 1-9 .   .   | 1-9 1-9 1-9 | .   1-9 .
 1-9 .   .   | 1-9 1-9 1-9 | .   1-9 .
 1-9 .   .   | 1-9 1-9 1-9 | .   1-9 .
-------------+-------------+---------------
 .   .   .   | 1-9 1-9 1-9 | .   .   .
 .   .   .   | .   .   .   | .   .   .
 .   .   .   | .   .   .   | .   .   .

Note that the pattern in boxes 2 and 8 can move to whatever row in their box you wish. The same is true for the column patterns in boxes 4 and 6. I think the most interesting thing about this MUG is that it tells you that you can't create a puzzle with a unique solution if the center box is clueless along with one clueless row in box 2 and in box 8 and one clueless column in box 4 and in box 6.
Last edited by Myth Jellies on Sat Feb 18, 2006 8:00 pm, edited 1 time in total.
Myth Jellies
 
Posts: 593
Joined: 19 September 2005

Postby vidarino » Sat Feb 18, 2006 12:37 pm

Myth Jellies wrote:Nice find, Vidar. You ought to submit that one to the type 3 uniqueness post. It's a beauty.:)


Thanks. But I'll just assume the readers of that thread takes a peek in here, too, so I'll just let it sit here.:)

And, just for grins and giggles, here is a nine-digit MUG...

(...)

Take any solved grid and erase one row in box 2, one in box 8, one column in box 4 and another in box 6 and erase all of box 5. The best you will be able to do (don't use any uniqueness/BUG/BUG-Lite techniques) is end up with a BUG+0 grid. It makes a nice trial grid for practicing finding nice loops or using POM techniques.


Hmm, I wouldn't say *any* solved grid. This one is solvable with naked singles only: (Unless I've misunderstood something again, which might very well be the case. I'm getting pretty good at that. ;) )
Code: Select all
+-------+-------+-------+
| 7 2 6 | 5 4 3 | 1 8 9 |
| 4 9 8 | 1 7 2 | 5 3 6 |
| 5 1 3 | . . . | 4 2 7 |
+-------+-------+-------+
| 6 7 . | . . . | . 9 4 |
| 9 3 . | . . . | . 1 2 |
| 8 4 . | . . . | . 6 5 |
+-------+-------+-------+
| 1 8 4 | . . . | 9 5 3 |
| 2 5 7 | 3 1 9 | 6 4 8 |
| 3 6 9 | 4 8 5 | 2 7 1 |
+-------+-------+-------+


Any solved grid with a whole unavoidable set wiped out will make a good candidate, though.

Vidar
vidarino
 
Posts: 295
Joined: 02 January 2006

Postby ronk » Sat Feb 18, 2006 2:37 pm

vidarino wrote:Any solved grid with a whole unavoidable set wiped out will make a good candidate, though.

Like this (somewhat) inverse pattern?
Code: Select all
 *-----------*
 |72.|...|.89|
 |49.|...|.36|
 |...|896|...|
 |---+---+---|
 |..1|258|3..|
 |..5|764|8..|
 |..2|931|7..|
 |---+---+---|
 |...|627|...|
 |25.|...|.48|
 |36.|...|.71|
 *-----------*
It has two solutions.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby Myth Jellies » Sat Feb 18, 2006 6:48 pm

:(Well, rats. As Vidar pointed out with his counter example, the nine-digit candidate is not a deadly pattern after all. Another theory debunked.
Myth Jellies
 
Posts: 593
Joined: 19 September 2005

Postby aeb » Sat Feb 18, 2006 9:44 pm

Myth Jellies wrote:Here is a six-digit MUG candidate.
Code: Select all
 .  .  abcdef | abcdef .  abcdef | abcdef .  .
 .  .  abcdef | abcdef .  abcdef | abcdef .  .
 .  .  abcdef | abcdef .  abcdef | abcdef .  .
--------------+------------------+---------------
 .  .  .      | abcdef .  abcdef | .      .  .
 .  .  .      | .      .  .      | .      .  .
 .  .  .      | .      .  .      | .      .  .
--------------+------------------+---------------
 .  .  .      | .      .  .      | .      .  .
 .  .  .      | .      .  .      | .      .  .
 .  .  .      | .      .  .      | .      .  .


But did you ask the oracle? The Pythia tells me that perhaps the outside had
Code: Select all
 E  F  abcdef | abcdef .  abcdef | abcdef .  .
 D  .  abcdef | abcdef .  abcdef | abcdef .  F
 .  .  abcdef | abcdef .  abcdef | abcdef B  C
--------------+------------------+---------------
 .  .  .      | abcdef A  abcdef | .      C  .
 .  .  .      | .      E  .      | B      .  .
 .  .  .      | F      .  .      | .      .  .
--------------+------------------+---------------
 .  .  D      | E      .  A      | F      .  .
 .  .  E      | .      .  C      | .      .  .
 .  .  F      | .      .  .      | C      .  .

and if that happens, things are reduced to the unique solution
Code: Select all
 E  F  c | a . b | d . .
 D  .  b | c . e | a . F
 .  .  a | d . f | e B C
---------+-------+-------
 .  .  . | b A d | . C .
 .  .  . | . E . | B . .
 .  .  . | F . . | . . .
---------+-------+-------
 .  .  D | E . A | F . .
 .  .  E | . . C | . . .
 .  .  F | . . . | C . .


That also shows that your 5-digit candidate is no good. On the other hand, yesterday or the day before you came with a 4-digit one that is very nice and completely correct. Maybe the details were lost - let me at least repeat the shape.
Code: Select all
abcd | abcd abcd
abcd | abcd abcd
-----+----------
     | abcd abcd
aeb
 
Posts: 83
Joined: 29 January 2006

Postby Myth Jellies » Sun Feb 19, 2006 12:03 am

Yes, aeb, you are right. I thought I was on to something, but, as you have shown, it just did not pan out.... Apparently I need to be a bit more rigorous in applying the oracle tests.
Myth Jellies
 
Posts: 593
Joined: 19 September 2005

Postby ronk » Sat Feb 02, 2008 6:08 pm

This puzzle can be solved with only singles and one MUG -- a MUG with UR Type 1 uniqueness.
Code: Select all
.5...8.6.......9..9.8...13.5..4..6..4...2.....81....23......7...9..16......35...4

After opening singles only:

 1     5      3     | 9     4     8     | 2     6     7
*267  *267   *267   | 1256  367   12357 | 9     4     8
 9     4      8     | 26    67    27    | 1     3     5
--------------------+-------------------+------------------
 5     237    279   | 4     3789  1379  | 6     1789  19
 4     367    679   | 168   2     1379  | 5     1789  19
 67    8      1     | 56    679   579   | 4     2     3
--------------------+-------------------+------------------
 3     12     5     | 28    89    4     | 7     19    6
 8     9      4     | 7     1     6     | 3     5     2
*267  *267+1 *267   | 3     5     29    | 8     19    4

As for BUG+N patterns, the lone extra candidate of this MUG+1 pattern -- (267)r29c123 -- must be true. After r9c2<>267, singles follow.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby Myth Jellies » Sun Feb 24, 2008 7:58 am

Here is another. MM's Extreme 74 using basic methods and coloring gets you here...

Code: Select all
 *-----------*
 |...|..9|.4.|
 |1..|.4.|..6|
 |7..|..5|...|
 |---+---+---|
 |.2.|4.6|...|
 |..6|.5.|9..|
 |.1.|9.2|.8.|
 |---+---+---|
 |...|2..|..5|
 |9..|.3.|..7|
 |.8.|7..|...|
 *-----------*
 *--------------------------------------------------------------------*
 | 236    5      238    | 1368   128    9      | 7      4      128    |
 | 1      9      238    | 38     4      7      | 23     5      6      |
 | 7      346    2348   | 1368   128    5      |*123    1239   1289   |
 |----------------------+----------------------+----------------------|
 | 38     2      9      | 4      18     6      | 5      7      13     |
 | 48     7      6      | 18     5      3      | 9      12     124    |
 | 345    1      345    | 9      7      2      | 6      8      34     |
 |----------------------+----------------------+----------------------|
 | 346    346    7      | 2      69    *148    |*148    169    5      |
 | 9      46     12     | 5      3     *148    |*148+2  126    7      |
 | 25     8      125    | 7      69    *14     |*14+3   12369  129    |
 *--------------------------------------------------------------------*

Note the 148 MUG in r789c67. The only way to escape the deadly pattern in c67 is for the one in r3c7 to be true. It doesn't solve the puzzle, but it just takes simple AICs or URs from here. Useful MUGs are pretty rare, so this was a fun find.
Myth Jellies
 
Posts: 593
Joined: 19 September 2005

Postby ronk » Fri May 30, 2008 12:40 pm

Myth Jellies wrote:
Code: Select all
 .   abc  . | abc  abc  . | .   .   .
 .   abc  . | .    abc  . | .   .   .
 .   .    . | .    .    . | .   .   .
------------+-------------+-----------
 .   .    . | abc  abc  . | .   .   .
 .   .    . | .    .    . | .   .   .
 .   .    . | .    .    . | .   .   .
------------+-------------+-----------
 .   .    . | .    .    . | .   .   .
 .   .    . | .    .    . | .   .   .
 .   .    . | .    .    . | .   .   .

...is a deadly MUG pattern

Has anyone observed a UR Type 1, 2 or 3 uniqueness deduction using this pattern:?:
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby Myth Jellies » Sun Jun 01, 2008 5:48 am

I haven't seen that one in particular, but I have seen a couple of cases of ones like
Code: Select all
ab   | abcd abcd
ab   | abcd abcd
-----+----------
     | cd   cd   

Unfortunately, even though they were presented on one of the forums, I can't seem to find them.
Myth Jellies
 
Posts: 593
Joined: 19 September 2005

Re: Forming MUGs from BUG-Lite composites

Postby ronk » Sat Feb 25, 2012 9:33 pm

Code: Select all
 .  AB .  | AC .  BD | .  CD .
 .  .  .  | .  .  .  | .  .  .
 .  AB .  | AC .  BD | .  CD .
----------+----------+----------
 .  .  .  | .  .  .  | .  .  .

If for this BUG-Lite we overlay all 96 permutations of assignments of tokens <abcd> to <ABCD>, we have the following MUG:

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

1. Given that the BUG-Lite is a deadly pattern, how does one elegantly prove that the MUG is a deadly pattern?

2. How does one elegantly prove that any possible reduction or permeation of the MUG is also a deadly pattern?
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Re: Forming MUGs from BUG-Lite composites

Postby David P Bird » Sun Feb 26, 2012 12:55 am

Using the definition that a deadly pattern is one that either has no solutions or more than one solution, this is my first reaction:

In each of the pattern columns two member digits must be true in external cells.
1) If the same digit occurs twice in the external cells in stack 2, box 2 will be impossible to complete as there would be insufficient candidates to fill 4 cells.
2) If any digit occurs in the external cells in three columns, again the pattern will be impossible to complete as it would become be a hidden single in both rows in in the same column.
3) This leaves the case when each candidate occurs twice externally, once in stack 2 and once in one of the other stacks. This reduces the pattern to a BUG (either an 8-cell DP or two 4-cell DPs)
David P Bird
2010 Supporter
 
Posts: 957
Joined: 16 September 2008
Location: Middle England

Re: Forming MUGs from BUG-Lite composites

Postby ronk » Sun Feb 26, 2012 11:54 am

David P Bird wrote:Using the definition that a deadly pattern is one that either has no solutions or more than one solution, this is my first reaction:

In each of the pattern columns two member digits must be true in external cells.
1) If the same digit occurs twice in the external cells in stack 2, box 2 will be impossible to complete as there would be insufficient candidates to fill 4 cells.
2) If any digit occurs in the external cells in three columns, again the pattern will be impossible to complete as it would become be a hidden single in both rows in in the same column.
3) This leaves the case when each candidate occurs twice externally, once in stack 2 and once in one of the other stacks. This reduces the pattern to a BUG (either an 8-cell DP or two 4-cell DPs)

IMO that's quite good (except that 'hidden single' should be 'naked single.' It's interesting that a 6-cell deadly-pattern ("DP") is not a possibility.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Re: Forming MUGs from BUG-Lite composites

Postby David P Bird » Sun Feb 26, 2012 5:36 pm

ronk wrote: IMO that's quite good (except that 'hidden single' should be 'naked single.'

I can't see anything more elegant so I'll take the C grade. However the way I was trying to describe it was to consider the options for reducing every pattern cell to a bivalue where the only possibilities would be hidden singles or naked pairs – perhaps you read it another way.
David P Bird
2010 Supporter
 
Posts: 957
Joined: 16 September 2008
Location: Middle England

Re: Forming MUGs from BUG-Lite composites

Postby ronk » Sun Feb 26, 2012 7:24 pm

David P Bird wrote:
ronk wrote: IMO that's quite good (except that 'hidden single' should be 'naked single.'

I can't see anything more elegant so I'll take the C grade. However the way I was trying to describe it was to consider the options for reducing every pattern cell to a bivalue where the only possibilities would be hidden singles or naked pairs – perhaps you read it another way.

Unless one knows the contents of all cells in a unit (row, column, box), I don't believe there can be a hidden anything.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

PreviousNext

Return to Advanced solving techniques