dailysudoku.com :: View topic - MUGs: Impermeable and Permeable Deadly Patterns

dailysudoku.com
Discussion of Daily Sudoku puzzles

FAQ

Memberlist

Usergroups

Profile

MUGs: Impermeable and Permeable Deadly Patterns

dailysudoku.com Forum Index -> Solving techniques, and terminology

View previous topic :: View next topic

Author

Message

Myth Jellies

Joined: 27 Jun 2006
Posts: 64

Posted: Thu May 29, 2008 4:33 am Post subject: MUGs: Impermeable and Permeable Deadly Patterns

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:

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

Display posts from previous:

	dailysudoku.com Forum Index -> Solving techniques, and terminology	All times are GMT
Page 1 of 1

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