MUGs: Impermeable versus Permeable Deadly Patterns

Advanced methods and approaches for solving Sudoku puzzles

MUGs: Impermeable versus Permeable Deadly Patterns

Postby Myth Jellies » Thu May 29, 2008 7:16 am

From a uniqueness-based Puzzle-solving point of view, what makes a candidate pattern deadly is the property that no matter what solved cells you place outside of the pattern, you still have multiple solutions (or no solution) represented inside the pattern.

There are essentially two types of deadly candidate patterns. The most common and most familiar kind are what I like to call "impermeable" deadly patterns. The hallmark of an impermeable deadly pattern is that no potentially solved outside digit can affect the pattern without forcing the pattern into a zero-solution state (i.e. forcing the pattern to be false). URs, BUGs, and BUG-Lites are all impermeable deadly patterns. As an example, consider a generic UR.

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

Note that if any cell sharing a house with the pattern (but outside the pattern) is determined to solve to an "a", then the pattern degenerates to something with two "b"s in the same house. This zero-solution state is the result whenever an outside entity solves that can affect the UR, and this is why a UR is a closed, or impermeable deadly pattern.
Code: Select all
 .   ab  . | .   ab  . | .   .   .
 .   .   . | .   .   . | .   .   .
 .   b   . | .   b   . | .  (a)  .
-----------+-----------+-----------
 .   .   . | .   .   . | .   .   .
 .   .   . | .   .   . | .   .   .
 .   .   . | .   .   . | .   .   .
-----------+-----------+-----------
 .   .   . | .   .   . | .   .   .
 .   .   . | .   .   . | .   .   .
 .   .   . | .   .   . | .   .   .

There are lots of impermeable deadly MUG patterns as well. Here are a few examples of some three- and four-candidate impermeable MUGs
Code: Select all
 .   abc . | .   abc . | .   abc .
 .   abc . | .   abc . | .   abc .
 .   abc . | .   abc . | .   abc .
-----------+-----------+-----------
 .   .   . | .   .   . | .   .   .
 .   .   . | .   .   . | .   .   .
 .   .   . | .   .   . | .   .   .
-----------+-----------+-----------
 .   .   . | .   .   . | .   .   .
 .   .   . | .   .   . | .   .   .
 .   .   . | .   .   . | .   .   .

Code: Select all
 .   abc . | .   ab  . | .   ac  .
 .   ab  . | .   abd . | .   ad  .
 .   ac  . | .   ad  . | .   acd .
-----------+-----------+-----------
 .   .   . | .   .   . | .   .   .
 .   .   . | .   .   . | .   .   .
 .   .   . | .   .   . | .   .   .
-----------+-----------+-----------
 .   .   . | .   .   . | .   .   .
 .   .   . | .   .   . | .   .   .
 .   .   . | .   .   . | .   .   .

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

Most impermeable MUGs take up too much space and are too constraining to be useful. Note that many of them represent a ton of extra solutions. The nine abc's deadly pattern represents 12 solutions, while the sixteen abcd's MUG represents 288 solutions. In effect, these patterns are overly deadly. Often they can be relaxed somewhat, adding extra degrees of freedom by either eliminating select cells or adding extra candidate digits. This results in what I like to call "permeable" deadly MUG patterns. These permeable MUGs will actually expect some interaction with solved outside cells, yet they still retain the deadly property that no matter how many of these potential external solution interactions there are, the pattern never reduces to a single solution state.

Let's look at one of the simplest permeable MUGs.
Code: Select all
 .   abc . | .   abc . | .   .   .
 .   abc . | .   abc . | .   .   .
 .   abc . | .   abc . | .   .   .
-----------+-----------+-----------
 .   .   . | .   .   . | .   .   .
 .   .   . | .   .   . | .   .   .
 .   .   . | .   .   . | .   .   .
-----------+-----------+-----------
 .   .   . | .   .   . | .   .   .
 .   .   . | .   .   . | .   .   .
 .   .   . | .   .   . | .   .   .

Note that any external solution "a", "b", or "c" sharing a box or column with this pattern will result in a zero-solution state. The only other outside potential solution positions where an interaction can occur is in box 3. Since all potential outside solved cells are in the same box, you can only have one of each digit. Thus the maximum interaction we can have is something like the following...
Code: Select all
 .   ab  . | .   ab  . |(c)  .   .
 .   ac  . | .   ac  . | .  (b)  .
 .   bc  . | .   bc  . | .   .  (a)
-----------+-----------+-----------
 .   .   . | .   .   . | .   .   .
 .   .   . | .   .   . | .   .   .
 .   .   . | .   .   . | .   .   .
-----------+-----------+-----------
 .   .   . | .   .   . | .   .   .
 .   .   . | .   .   . | .   .   .
 .   .   . | .   .   . | .   .   .

We cannot effectively add another interaction without pushing things into a zero-solution state. Note that this results in a multi-solution impermeable BUG-Lite pattern. No matter what happens in box 3, our permeable MUG either enters a zero-solution state (and can be dismissed as false) or it retains its multi-solution status. Thus the six abc's pattern is deadly, and has to be avoided just like any other deadly pattern.

Let's consider another pattern which you might suspect is deadly--two URs with four different digits that overlap in two cells.
Code: Select all
 ab  cd  . | .   abcd  . | .   .   .
 .   .   . | .   .     . | .   .   .
 ab  cd  . | .   abcd  . | .   .   .
-----------+-------------+-----------
 .   .   . | .   .     . | .   .   .
 .   .   . | .   .     . | .   .   .
 .   .   . | .   .     . | .   .   .
-----------+-------------+-----------
 .   .   . | .   .     . | .   .   .
 .   .   . | .   .     . | .   .   .
 .   .   . | .   .     . | .   .   .

Now say r1c4 solves to "a". Then we get...
Code: Select all
 b   cd  . |(a)  cd    . | .   .   .
 .   .   . | .   .     . | .   .   .
 a   cd  . | .   bcd   . | .   .   .
-----------+-------------+-----------
 .   .   . | .   .     . | .   .   .
 .   .   . | .   .     . | .   .   .
 .   .   . | .   .     . | .   .   .
-----------+-------------+-----------
 .   .   . | .   .     . | .   .   .
 .   .   . | .   .     . | .   .   .
 .   .   . | .   .     . | .   .   .

If r4c5 then solves to "d" then we end up with...
Code: Select all
 b   d   . |(a)  c     . | .   .   .
 .   .   . | .   .     . | .   .   .
 a   c   . | .   b     . | .   .   .
-----------+-------------+-----------
 .   .   . | .  (d)    . | .   .   .
 .   .   . | .   .     . | .   .   .
 .   .   . | .   .     . | .   .   .
-----------+-------------+-----------
 .   .   . | .   .     . | .   .   .
 .   .   . | .   .     . | .   .   .
 .   .   . | .   .     . | .   .   .

Note that the entire pattern through outside interaction can be reduced to a single solution state. Thus this pattern does not qualify as a deadly pattern.

Here is a short list of some permeable deadly pattern MUGs.

3-digit 3-row 2-column 2-box
Code: Select all
 .   abc . | .   abc . | .   .   .
 .   abc . | .   abc . | .   .   .
 .   abc . | .   abc . | .   .   .
-----------+-----------+-----------
 .   .   . | .   .   . | .   .   .
 .   .   . | .   .   . | .   .   .
 .   .   . | .   .   . | .   .   .
-----------+-----------+-----------
 .   .   . | .   .   . | .   .   .
 .   .   . | .   .   . | .   .   .
 .   .   . | .   .   . | .   .   .

3-digit 2-row 3-column 3-box
Code: Select all
 .   abc . | .   abc . | .   abc .
 .   abc . | .   abc . | .   abc .
 .   .   . | .   .   . | .   .   .
-----------+-----------+-----------
 .   .   . | .   .   . | .   .   .
 .   .   . | .   .   . | .   .   .
 .   .   . | .   .   . | .   .   .
-----------+-----------+-----------
 .   .   . | .   .   . | .   .   .
 .   .   . | .   .   . | .   .   .
 .   .   . | .   .   . | .   .   .

4-digit 2-row 4-column 3-box
Code: Select all
 .   abcd . | abcd abcd . | abcd .   .
 .   abcd . | abcd abcd . | abcd .   .
 .   .    . | .    .    . | .    .   .
------------+-------------+------------
 .   .    . | .    .    . | .    .   .
 .   .    . | .    .    . | .    .   .
 .   .    . | .    .    . | .    .   .
------------+-------------+------------
 .   .    . | .    .    . | .    .   .
 .   .    . | .    .    . | .    .   .
 .   .    . | .    .    . | .    .   .

4-digit 3-row 3-column 3-box L-shape
Code: Select all
 .   abcd . | abcd abcd . | .   .   .
 .   abcd . | abcd abcd . | .   .   .
 .   .    . | .    .    . | .   .   .
------------+-------------+-----------
 .   .    . | abcd abcd . | .   .   .
 .   .    . | .    .    . | .   .   .
 .   .    . | .    .    . | .   .   .
------------+-------------+-----------
 .   .    . | .    .    . | .   .   .
 .   .    . | .    .    . | .   .   .
 .   .    . | .    .    . | .   .   .

4-digit 3-row 3-column 3-box ???
Code: Select all
 .   abcd . | .   abcd . | abcd .   .
 .   abcd . | .   abcd . | abcd .   .
 .   abcd . | .   abcd . | abcd .   .
------------+------------+------------
 .   .    . | .   .    . | .    .   .
 .   .    . | .   .    . | .    .   .
 .   .    . | .   .    . | .    .   .
------------+------------+------------
 .   .    . | .   .    . | .    .   .
 .   .    . | .   .    . | .    .   .
 .   .    . | .   .    . | .    .   .

5-digit 5-row 5-column 5-box
Code: Select all
 .   .     . | .     .     .     | .     .   .
 .   .     . | abcde abcde abcde | .     .   .
 .   .     . | .     .     .     | .     .   .
-------------+-------------------+-------------
 .   abcde . | abcde .     abcde | abcde .   .
 .   abcde . | .     abcde .     | abcde .   .
 .   abcde . | abcde .     abcde | abcde .   .
-------------+-------------------+-------------
 .   .     . | .     .     .     | .     .   .
 .   .     . | abcde abcde abcde | .     .   .
 .   .     . | .     .     .     | .     .   .

This five-digit MUG might occasionally fit in with our symmetric puzzles.

Note that any deadly pattern that you come up with when reducing a deadly pattern also qualifies as a deadly pattern. Thus...
Code: Select all
 .   abc  . | abc  abc  . | .   .   .
 .   abc  . | .    abc  . | .   .   .
 .   .    . | .    .    . | .   .   .
------------+-------------+-----------
 .   .    . | abc  abc  . | .   .   .
 .   .    . | .    .    . | .   .   .
 .   .    . | .    .    . | .   .   .
------------+-------------+-----------
 .   .    . | .    .    . | .   .   .
 .   .    . | .    .    . | .   .   .
 .   .    . | .    .    . | .   .   .

...is a deadly MUG pattern derived from...
Code: Select all
(d)  abcd . | abcd abcd . | .   .   .
 .   abcd . | abcd abcd . | .   .   .
 .   .    . | .    .    . | .   .   .
------------+-------------+-----------
 .   .    . | abcd abcd . | .   .   .
 .   .    . | .    .    . | .   .   .
 .   .    . | .   (d)   . | .   .   .
------------+-------------+-----------
 .   .    . | .    .    . | .   .   .
 .   .    . | .    .    . | .   .   .
 .   .    . | .    .    . | .   .   .


For reference, here is the original MUG thread
Myth Jellies
 
Posts: 593
Joined: 19 September 2005

Postby Carcul » Thu May 29, 2008 7:36 pm

Interesting how your terminology continues to be quite chemical.:D
Carcul
 
Posts: 724
Joined: 04 November 2005

Postby wintder » Fri May 30, 2008 7:03 am

Carcul wrote:Interesting how your terminology continues to be quite chemical.:D


If impermeable is your thought, geologists are quite aware of this word.

Oops, as are ship builders.
wintder
 
Posts: 297
Joined: 24 April 2007

Postby Myth Jellies » Fri May 30, 2008 7:43 am

Carcul, nice to see that you are still occasionally checking in here. You would be correct in assuming that my background is scientific. When my Filet-O-Fish term flopped way back when, I went back to my roots:)
Myth Jellies
 
Posts: 593
Joined: 19 September 2005

Postby Myth Jellies » Fri May 30, 2008 7:59 am

An interesting Permeable MUG observation.

It turns out that for any N > 2, there is an N-digit 2-row N-column 3-box MUG pattern. If you consider N = 9, then this tells you that if you have two empty rows in the same chute, then the puzzle must have multiple solutions. It is something that we already knew, but it is nice to see that MUG logic bears this relationship out.

There looks to be a relationship between valid puzzle transformations and MUG patterns.
Myth Jellies
 
Posts: 593
Joined: 19 September 2005

Postby coloin » Fri May 30, 2008 11:08 am

Myth.....what you are describing is the myriad of different "unavoidable sets" which exist in every puzzle. If a sudoku puzzle and therefore solution grid is defined by all the unavoidable sets it possibly means that many puzzle characteristics could be explained by the "intersection" of the unavoidable sets solely covered by a given clue.

When a BUG or UR gives you an elimination - you are eliminating the grid solution which has this unavoidable set. It cant have it in the grid solution relevant to the puzzle.

Whenever a "subpuzzle" has 2 or 3 [or more] grid solutions this means that there is one or more unavoidable set which arnt "covered".

The unavoidable sets which are uniquely covered by an individual clue in a Hard puzzles tend to be big.

The unavoidable sets in the "other" solution grids of the n-1 subpuzzles from our puzzle with n clues are multiple and smaller. If we knew them we would have many UR eliminations. !!!!!!

I have often wondered if analysis of the n-1 solution grids would give us an insight into solving or rating our "hardest puzzles". I have no idea how though.

I will pick a hard puzzle - remove a clue and then study the URs in the other solution grids which would cause a conflict with the removed clue.

C

For stats, definitions on minimality.
http://forum.enjoysudoku.com/viewtopic.php?t=2747&postdays=0&postorder=asc&start=11

You need two at least 2 clues in a box and always 2 or more of a particular clue value.

To show how many unavoidable sets there are !
http://forum.enjoysudoku.com/viewtopic.php?t=4882&start=15
coloin
 
Posts: 2493
Joined: 05 May 2005
Location: Devon

Postby Myth Jellies » Sat May 31, 2008 8:07 am

coloin wrote:Myth.....what you are describing is the myriad of different "unavoidable sets" which exist in every puzzle. If a sudoku puzzle and therefore solution grid is defined by all the unavoidable sets it possibly means that many puzzle characteristics could be explained by the "intersection" of the unavoidable sets solely covered by a given clue.


Actually, unavoidable sets approaches the same problem from the point of view of an already solved puzzle. They seem to be much more useful to a puzzle-maker who has access to the solutions and needs to cover all of the unavoidable sets to come up with a unique solution puzzle. The puzzle-solver only has access to his candidate list. Knowing that the puzzle-maker has covered all the unavoidable sets with his clues, the solver knows that all UR, BUG, and MUG candidate patterns that he can pick out of his candidate list must be false.

There is a correlation, of course, but it is not exactly one-to-one. For example, the unavoidable set represented by
Code: Select all
123......
.........
.........
231......
.........
.........
.........
.........
.........

can be represented by the BUG-Lite pattern
Code: Select all
 ab  bc  ca| .   .   . | .   .   .
 .   .   . | .   .   . | .   .   .
 .   .   . | .   .   . | .   .   .
-----------+-----------+-----------
 ab  bc  ca| .   .   . | .   .   .
 .   .   . | .   .   . | .   .   .
 .   .   . | .   .   . | .   .   .
-----------+-----------+-----------
 .   .   . | .   .   . | .   .   .
 .   .   . | .   .   . | .   .   .
 .   .   . | .   .   . | .   .   .

but it can also be represented by the permeable MUG pattern
Code: Select all
 abc abc abc| .   .   . | .   .   .
 .   .   .  | .   .   . | .   .   .
 .   .   .  | .   .   . | .   .   .
-----------+-----------+-----------
 abc abc abc| .   .   . | .   .   .
 .   .   .  | .   .   . | .   .   .
 .   .   .  | .   .   . | .   .   .
-----------+-----------+-----------
 .   .   .  | .   .   . | .   .   .
 .   .   .  | .   .   . | .   .   .
 .   .   .  | .   .   . | .   .   .

and the MUG candidate pattern may be more potent because you can derive the BUG-Lite pattern from it (shown below), thus it encompasses the BUG-Lite pattern.
Code: Select all
 abc abc abc| .   .   . | .   .   .
 .   .   .  | .   .   . | .   .   .
 .   .   .  | .   .   . | .   .   .
-----------+-----------+-----------
 abc abc abc| .   .   . | .   .   .
 .   .   .  | .   .   . | .   .   .
 .   .   .  | .   .   . | .   .   .
-----------+-----------+-----------
 (c) (a) (b)| .   .   . | .   .   .
 .   .   .  | .   .   . | .   .   .
 .   .   .  | .   .   . | .   .   .
Myth Jellies
 
Posts: 593
Joined: 19 September 2005

Postby coloin » Sat May 31, 2008 3:47 pm

Yes all true, knowing the unavoidable sets isnt an easy way to pick out a UR.
The puzzle making programs [that I use] arnt that clever. Removing clues and adding clues are verified if the solution =1. Mapping out the unavoidables would be difficult. In any case, the unavoidable sets are only all definable [if that is possible] when you have a valid puzzle / complete solution grid.

Myth Jellies wrote:....the solver knows that all UR, BUG, and MUG candidate patterns that he can pick out of his candidate list must be false.

YES
these could be patterns in one of the solution grids of the n-1 clues [n=clues in puzzle]

Picking these unavoidable set /UR patterns of course is not straight forward.

Myth Jellies wrote:There is a correlation, of course, but it is not exactly one-to-one.

Is it not ?

this subpuzzle has two solutions
Code: Select all
+---+---+---+
|...|457|698|
|468|139|752|
|579|268|143|
+---+---+---+
|...|574|869|
|684|391|527|
|795|682|431|
+---+---+---+
|231|745|986|
|846|913|275|
|957|826|314|
+---+---+---+ it needs a clue in one of the spaces to define the solution grid.

+---+---+---+
|123|...|...|
|...|...|...|
|...|...|...|
+---+---+---+
|312|...|...|
|...|...|...|
|...|...|...|
+---+---+---+
|...|...|...|
|...|...|...|
|...|...|...|
+---+---+---+  U6

+---+---+---+
|312|...|...|
|...|...|...|
|...|...|...|
+---+---+---+
|123|...|...|
|...|...|...|
|...|...|...|
+---+---+---+
|...|...|...|
|...|...|...|
|...|...|...|
+---+---+---+  U6'



Most commonly these "maximal" subpuzzles have 2 grid solutions. They vary only by the unavoidable set and its converse.

Getting back on topic I think you are describing the way U4s and U6s can switch from solution grid to solution grid. And the U6 to the U9 in your BUG-Lite example.

I will try again to pick out a largish unavoidable and present it as a UR reduction !

C
coloin
 
Posts: 2493
Joined: 05 May 2005
Location: Devon

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

Your invalid puzzle (due to multiple solutions)
Code: Select all
+---+---+---+
|...|457|698|
|468|139|752|
|579|268|143|
+---+---+---+
|...|574|869|
|684|391|527|
|795|682|431|
+---+---+---+
|231|745|986|
|846|913|275|
|957|826|314|
+---+---+---+

indicates that the BUG-lite
Code: Select all
 13  12  23| .   .   . | .   .   .
 .   .   . | .   .   . | .   .   .
 .   .   . | .   .   . | .   .   .
-----------+-----------+-----------
 13  12  23| .   .   . | .   .   .
 .   .   . | .   .   . | .   .   .
 .   .   . | .   .   . | .   .   .
-----------+-----------+-----------
 .   .   . | .   .   . | .   .   .
 .   .   . | .   .   . | .   .   .
 .   .   . | .   .   . | .   .   .

is a deadly pattern, but so is the permeable MUG
Code: Select all
 123 123 123| .   .   . | .   .   .
 .   .   .  | .   .   . | .   .   .
 .   .   .  | .   .   . | .   .   .
------------+-----------+-----------
 123 123 123| .   .   . | .   .   .
 .   .   .  | .   .   . | .   .   .
 .   .   .  | .   .   . | .   .   .
------------+-----------+-----------
 .   .   .  | .   .   . | .   .   .
 .   .   .  | .   .   . | .   .   .
 .   .   .  | .   .   . | .   .   .

Furthermore, the permeable MUG deadly pattern will also catch the extra multi-solution puzzles represented by
Code: Select all
+---+---+---+
|...|457|698|
|468|139|752|
|579|268|143|
+---+---+---+
|...|574|869|
|684|391|527|
|795|682|431|
+---+---+---+
|123|745|986|
|846|913|275|
|957|826|314|
+---+---+---+

+---+---+---+
|...|457|698|
|468|139|752|
|579|268|143|
+---+---+---+
|...|574|869|
|684|391|527|
|795|682|431|
+---+---+---+
|312|745|986|
|846|913|275|
|957|826|314|
+---+---+---+

...and every other permutation of the digits 1, 2, and 3 in box 7. Handy if you haven't gotten around to solving them yet.

Perhaps that is the key, that permable MUGs represent multi-solution puzzles that need more than one clue to define a unique solution grid. Or in other words, a superposition of multiple 2-solution puzzles.

You are quite likely right in your U6 U9 assessment.
Last edited by Myth Jellies on Sun Jun 01, 2008 1:41 am, edited 1 time in total.
Myth Jellies
 
Posts: 593
Joined: 19 September 2005

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

Just realized that this pattern
Code: Select all
 .     .     . | .     .     . | .     .     .
 abcd  abcd  . | abcd  abcd  . | .     .     .
 abcd  abcd  . | abcd  abcd  . | .     .     .
---------------+---------------+---------------
 abcd  abcd  . | abcd  abcd  . | .     .     .
 abcd  abcd  . | abcd  abcd  . | .     .     .
 .     .     . | .     .     . | .     .     .
---------------+---------------+---------------
 .     .     . | .     .     . | .     .     .
 .     .     . | .     .     . | .     .     .
 .     .     . | .     .     . | .     .     .
 

Can't really exist in a 9x9 sudoku since you have 6 cells in r123456c3 and only 5 digits that you are allowed to put in them. Doesn't change things, but you can take that pattern off of the impermeable MUG list.
Myth Jellies
 
Posts: 593
Joined: 19 September 2005

Postby ronk » Sun Jun 01, 2008 1:29 pm

Myth Jellies wrote:indicates that the BUG-lite [...] is a deadly pattern, but so is the permeable MUG
Code: Select all
 123 123 123| .   .   . | .   .   .
 .   .   .  | .   .   . | .   .   .
 .   .   .  | .   .   . | .   .   .
------------+-----------+-----------
 123 123 123| .   .   . | .   .   .
 .   .   .  | .   .   . | .   .   .
 .   .   .  | .   .   . | .   .   .
------------+-----------+-----------
 .   .   .  | .   .   . | .   .   .
 .   .   .  | .   .   . | .   .   .
 .   .   .  | .   .   . | .   .   .

And (obviously) so is any "partially permeated" MUG, for example ...

Ruud50k #1747
Code: Select all
..6..2....1..98....75.....6...8.51...4..6..7...24.7...9.....58....57..3....2..4..

After SSTS
 348  9    6    | 7    5    2    | 38   14   1348
 234  1    34   | 6    9    8    | 7    245  345
 28   7    5    |*13  *134 *134  | 89   29   6
----------------+----------------+---------------
 7    36   9    | 8    2    5    | 1    46   34
 135  4    138  | 9    6    13   | 238  7    2358
 1356 3568 2    | 4    13   7    | 3689 569  3589
----------------+----------------+---------------
 9    236  1347 |*13  *134 *6-134| 5    8    127
 146  28   148  | 5    7    1469 | 269  3    129
 1356 356  137  | 2    8    1369 | 4    169  179

Type 1 MUG(134+6)r37c456: ==> r7c6<>134

A common marker is the triplet in a box-row intersection. Other markers probably exist for Type 2 and Type 3.

Can't really exist in a 9x9 sudoku since you have 6 cells in r123456c3 and only 5 digits that you are allowed to put in them. Doesn't change things, but you can take that pattern off of the impermeable MUG list.

You could edit your opening post.:)
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Re: MUGs: Impermeable versus Permeable Deadly Patterns

Postby eleven » Mon Jun 02, 2008 5:28 pm

Myth Jellies wrote:4-digit 3-row 3-column 3-box ???
Code: Select all
 .   abcd . | .   abcd . | abcd .   .
 .   abcd . | .   abcd . | abcd .   .
 .   abcd . | .   abcd . | abcd .   .
------------+------------+------------
 .   .    . | .   .    . | .    .   .
 .   .    . | .   .    . | .    .   .
 .   .    . | .   .    . | .    .   .
------------+------------+------------
 .   .    . | .   .    . | .    .   .
 .   .    . | .   .    . | .    .   .
 .   .    . | .   .    . | .    .   .

What about this pattern now ? I couldn't figure out so far, if it is a MUG or not.

Added: I am rather sure that it is. In the 3 columns one of the 4 digits have to be in rows 4-9. If one digit is in two of the columns there, you have a MUG like above. Otherwise you get something like this:
Code: Select all
 .   abc  . | .   abd  . | acd  .   .
 .   abc  . | .   abd  . | acd  .   .
 .   abc  . | .   abd  . | acd  .   .
------------+------------+------------
 .   .    . | .   .    . | .    .   .
 .   .    . | .   .    . | .    .   .
 .   .    . | .   .    . | .    .   .
------------+------------+------------
 .   .    . | .   .    . | .    .   .
 .   .    . | .   .    . | .    .   .
 .   .    . | .   .    . | .    .   .

If it's correct, the second puzzle here can be easily solved: http://forum.enjoysudoku.com/viewtopic.php?p=57361#p57361
eleven
 
Posts: 3150
Joined: 10 February 2008

Postby Myth Jellies » Mon Jun 02, 2008 11:05 pm

Nice find, Eleven

Yes it is a MUG. You can also add potentials inside b123 to get something like...
Code: Select all
(d)  abcd . | .   abcd . | abcd .   .
 .   abcd . |(c)  abcd . | abcd .   .
 .   abcd . | .   abcd . | abcd .  (b)
------------+------------+------------
 .   .    . | .   .    . | .    .   .
 .   .    . | .   .    . | .    .   .
 .   .    . | .   .    . | .    .   .
------------+------------+------------
 .   .    . | .   .    . | .    .   .
 .   .    . | .   .    . | .    .   .
 .   .    . | .   .    . | .    .   .

 .   abc  . | .   ab   . | ac   .   .
 .   ab   . | .   abd  . | ad   .   .
 .   ac   . | .   ad   . | acd  .   .
------------+------------+------------
 .   .    . | .   .    . | .    .   .
 .   .    . | .   .    . | .    .   .
 .   .    . | .   .    . | .    .   .
------------+------------+------------
 .   .    . | .   .    . | .    .   .
 .   .    . | .   .    . | .    .   .
 .   .    . | .   .    . | .    .   .

which is actually how I came up with that impermeable pattern above

Code: Select all
.7....4.82...9........3.6...6.7..5.........92..1......9......1....8.....3........ #47505

 +-----------------------------------------------------------------------+
 |  156    7      9      |  1256   256    256    |  4      3      8      |
 |  2      34     346    |  46     9      8      |  7      5      1      |
 |  145    18     458    |  145    3      7      |  6      2      9      |
 |-----------------------+-----------------------+-----------------------|
 |  8      6      2      |  7      1      9      |  5      4      3      |
 |  457    345    3457   |  56     8      456    |  1      9      2      |
 |  45     9      1      |  3      245    245    |  8      67     67     |
 |-----------------------+-----------------------+-----------------------|
 |  9     #28    *4567+8 |  256   *4567+2 2456   |  3      1     *4567   |
 |  14567  12    *4567   |  8     *4567+2 3      |  9      67    *45(67)  |
 |  3      45    *4567   |  9     *4567   1      |  2      8     *4567   |
 +-----------------------------------------------------------------------+


Using the 28 in r7c2 as a helper, we have
(2=8)r7c2 - (8)r7c3 =MUG= (2)r78c5 => r7c46 <> 2 => r16c5 <> 2, etc.

Eleven, you currently have the record for the biggest useful MUG found to date!
Myth Jellies
 
Posts: 593
Joined: 19 September 2005

Postby RW » Sat Jun 14, 2008 6:32 am

Thanks for the thread, some interesting patterns there. Is there any difference to the layered BUG-lite, or are these patterns just an extension to those few patterns I presented in that thread?

MJ wrote:Eleven, you currently have the record for the biggest useful MUG found to date!

What's the measure? Number of cells, number of deadly candidates or amount of different digits? If any of the last two, this should take the lead:
Code: Select all
 *--------------------------------------------------------------------------------------*
 | 4569     4579     469      | 2679     12679    24569    | 2579     8        3        |
 | 59       579      1        | 3        8        259      | 2579     4        6        |
 | 45689    2        3        | 679      679      4569     | 579      1        579      |
 |----------------------------+----------------------------+----------------------------|
 | 7        89       289      | 1        5        2689     | 269      3        4        |
 | 13459    13459    249      | 269      2369     7        | 8        2569     1259     |
 | 13589    6        289      | 29       4        2389     | 1259     7        1259     |
 |----------------------------+----------------------------+----------------------------|
 |*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.)

Though in this case there is of course an easier way to spot the elimination...

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

Postby Myth Jellies » Mon Jun 16, 2008 9:53 am

RW, your example nicely points out a relationship between reverse uniqueness and certain permeable MUGs (perhaps all MUGs). The difference (if one exists) between layered BUG-lites and MUGs was offered in the layered BUG-lite thread.

Sure you can have the biggest MUG noted to date. I bet you have the inside track on all the reversible uniqueness examples for conversions:)
Myth Jellies
 
Posts: 593
Joined: 19 September 2005

Next

Return to Advanced solving techniques