dailysudoku.com Forum Index dailysudoku.com
Discussion of Daily Sudoku puzzles
 
 FAQFAQ   SearchSearch   MemberlistMemberlist   UsergroupsUsergroups   RegisterRegister 
 ProfileProfile   Log in to check your private messagesLog in to check your private messages   Log inLog in 

MUGs: Impermeable and Permeable Deadly Patterns

 
Post new topic   Reply to topic    dailysudoku.com Forum Index -> Solving techniques, and terminology
View previous topic :: View next topic  
Author Message
Myth Jellies



Joined: 27 Jun 2006
Posts: 64

PostPosted: Thu May 29, 2008 4:33 am    Post subject: MUGs: Impermeable and Permeable Deadly Patterns Reply with quote

Impermeable versus Permeable Deadly Patterns

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:

 .   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:

 .   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:

 .   abc . | .   abc . | .   abc .
 .   abc . | .   abc . | .   abc .
 .   abc . | .   abc . | .   abc .
-----------+-----------+-----------
 .   .   . | .   .   . | .   .   .
 .   .   . | .   .   . | .   .   .
 .   .   . | .   .   . | .   .   .
-----------+-----------+-----------
 .   .   . | .   .   . | .   .   .
 .   .   . | .   .   . | .   .   .
 .   .   . | .   .   . | .   .   .

Code:

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

Code:

 .     .     . | .     .     . | .     .     .
 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:

 .   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:

 .   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:

 ab  cd  . | .   abcd  . | .   .   .
 .   .   . | .   .     . | .   .   .
 ab  cd  . | .   abcd  . | .   .   .
-----------+-------------+-----------
 .   .   . | .   .     . | .   .   .
 .   .   . | .   .     . | .   .   .
 .   .   . | .   .     . | .   .   .
-----------+-------------+-----------
 .   .   . | .   .     . | .   .   .
 .   .   . | .   .     . | .   .   .
 .   .   . | .   .     . | .   .   .

Now say r1c4 solves to "a". Then we get...
Code:

 b   cd  . |(a)  cd    . | .   .   .
 .   .   . | .   .     . | .   .   .
 a   cd  . | .   bcd   . | .   .   .
-----------+-------------+-----------
 .   .   . | .   .     . | .   .   .
 .   .   . | .   .     . | .   .   .
 .   .   . | .   .     . | .   .   .
-----------+-------------+-----------
 .   .   . | .   .     . | .   .   .
 .   .   . | .   .     . | .   .   .
 .   .   . | .   .     . | .   .   .

If r4c5 then solves to "d" then we end up with...
Code:

 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:

 .   abc . | .   abc . | .   .   .
 .   abc . | .   abc . | .   .   .
 .   abc . | .   abc . | .   .   .
-----------+-----------+-----------
 .   .   . | .   .   . | .   .   .
 .   .   . | .   .   . | .   .   .
 .   .   . | .   .   . | .   .   .
-----------+-----------+-----------
 .   .   . | .   .   . | .   .   .
 .   .   . | .   .   . | .   .   .
 .   .   . | .   .   . | .   .   .

3-digit 2-row 3-column 3-box
Code:

 .   abc . | .   abc . | .   abc .
 .   abc . | .   abc . | .   abc .
 .   .   . | .   .   . | .   .   .
-----------+-----------+-----------
 .   .   . | .   .   . | .   .   .
 .   .   . | .   .   . | .   .   .
 .   .   . | .   .   . | .   .   .
-----------+-----------+-----------
 .   .   . | .   .   . | .   .   .
 .   .   . | .   .   . | .   .   .
 .   .   . | .   .   . | .   .   .

4-digit 2-row 4-column 3-box
Code:

 .   abcd . | abcd abcd . | abcd .   .
 .   abcd . | abcd abcd . | abcd .   .
 .   .    . | .    .    . | .    .   .
------------+-------------+------------
 .   .    . | .    .    . | .    .   .
 .   .    . | .    .    . | .    .   .
 .   .    . | .    .    . | .    .   .
------------+-------------+------------
 .   .    . | .    .    . | .    .   .
 .   .    . | .    .    . | .    .   .
 .   .    . | .    .    . | .    .   .

4-digit 3-row 3-column 3-box L-shape
Code:

 .   abcd . | abcd abcd . | .   .   .
 .   abcd . | abcd abcd . | .   .   .
 .   .    . | .    .    . | .   .   .
------------+-------------+-----------
 .   .    . | abcd abcd . | .   .   .
 .   .    . | .    .    . | .   .   .
 .   .    . | .    .    . | .   .   .
------------+-------------+-----------
 .   .    . | .    .    . | .   .   .
 .   .    . | .    .    . | .   .   .
 .   .    . | .    .    . | .   .   .

4-digit 3-row 3-column 3-box ???
Code:

 .   abcd . | .   abcd . | abcd .   .
 .   abcd . | .   abcd . | abcd .   .
 .   abcd . | .   abcd . | abcd .   .
------------+------------+------------
 .   .    . | .   .    . | .    .   .
 .   .    . | .   .    . | .    .   .
 .   .    . | .   .    . | .    .   .
------------+------------+------------
 .   .    . | .   .    . | .    .   .
 .   .    . | .   .    . | .    .   .
 .   .    . | .   .    . | .    .   .

5-digit 5-row 5-column 5-box
Code:

 .   .     . | .     .     .     | .     .   .
 .   .     . | 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:

 .   abc  . | abc  abc  . | .   .   .
 .   abc  . | .    abc  . | .   .   .
 .   .    . | .    .    . | .   .   .
------------+-------------+-----------
 .   .    . | abc  abc  . | .   .   .
 .   .    . | .    .    . | .   .   .
 .   .    . | .    .    . | .   .   .
------------+-------------+-----------
 .   .    . | .    .    . | .   .   .
 .   .    . | .    .    . | .   .   .
 .   .    . | .    .    . | .   .   .

...is a deadly MUG pattern derived from...
Code:

(d)  abcd . | abcd abcd . | .   .   .
 .   abcd . | abcd abcd . | .   .   .
 .   .    . | .    .    . | .   .   .
------------+-------------+-----------
 .   .    . | abcd abcd . | .   .   .
 .   .    . | .    .    . | .   .   .
 .   .    . | .   (d)   . | .   .   .
------------+-------------+-----------
 .   .    . | .    .    . | .   .   .
 .   .    . | .    .    . | .   .   .
 .   .    . | .    .    . | .   .   .


For reference, here is the original MUG thread
Back to top
View user's profile Send private message
Display posts from previous:   
Post new topic   Reply to topic    dailysudoku.com Forum Index -> Solving techniques, and terminology All times are GMT
Page 1 of 1

 
Jump to:  
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum


Powered by phpBB © 2001, 2005 phpBB Group