The New Sudoku Players' Forum

[eleven]

Perhaps one final comment is a typo. In eleven's Case 2 diagram as posted r3c3 can't have an a. Leren

Thanks, i edited my post above.

[Leren]

Two more pieces of finessing.

1. A corollary of the "not the same digit outside of both of the 2 rows or columns" thing is that in eleven's Case 2 first reduction diagram

Code: Select all

-------------------+-------------------+-------------------
 .     .     .     | .     .     .     | .     .     .     
 .     .     bcd   | bd    bc    .     | .     .     a     
 .     .     acd   | ad    ac    .     | .     .     b     
-------------------+-------------------+-------------------
 .     .     .     | abd   abc   .     | .     .     .     
 .     .     .     | .     .     .     | .     .     .     
 .     .     .     | .     .     .     | .     .     .     
-------------------+-------------------+-------------------
 .     .     .     | .     .     .     | .     .     .     
 .     .     .     | .     .     .     | .     .     .     
 .     .     .     | c     d     .     | .     .     .     
-------------------+-------------------+-------------------

should actually reduce to this :

Code: Select all

-------------------+-------------------+-------------------
 .     .     .     | .     .     .     | .     .     .     
 .     .     cd    | bd    bc    .     | .     .     a     
 .     .     cd    | ad    ac    .     | .     .     b     
-------------------+-------------------+-------------------
 .     .     .     | ab    ab    .     | .     .     .     
 .     .     .     | .     .     .     | .     .     .     
 .     .     .     | .     .     .     | .     .     .     
-------------------+-------------------+-------------------
 .     .     .     | .     .     .     | .     .     .     
 .     .     .     | .     .     .     | .     .     .     
 .     .     .     | c     d     .     | .     .     .     
-------------------+-------------------+-------------------

which is the same for a and b on the other side. In fact a and b don't have to be on the same side anyway, so I think you can remove a diagram in Case 2 and merely point out that it doesn't matter which side of the pattern the a and b are, the reduced MUG is exactly the same.

2. The second piece of finessing is that it's probably not a good idea to have the a & b depicted in the same column, and the c & d in the same row, otherwise someone might ask why they are shown that way.

Leren

[eleven]

Good observation. So the proof becomes quite short with the help of you and SpAce.

Proof, that this pattern is a MUG:

Code: Select all

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

Note: Because of the quad there can't be a MUG digit outside in box 2 (and also not the same digit outside in both of the rows r34 or both columns c45)

Case 1:
The same digit is outside in both a row and a column: This reduces it to the 3 digit MUG:

Code: Select all

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

a is forced to r3c5, leaving

Code: Select all

    -------------------+-------------------+-------------------
     .     .     .     | .     .     .     | .     .     .     
     .     .     bcd   | bcd   bcd   .     | .     .     a     
     .     .     bcd   | bcd   a     .     | .     .     .     
    -------------------+-------------------+-------------------
     .     .     .     | bcd   bcd   .     | .     .     .     
     .     .     .     | .     .     .     | .     .     .     
     .     .     .     | .     .     .     | .     .     .     
    -------------------+-------------------+-------------------
     .     .     .     | .     .     .     | .     .     .     
     .     .     .     | .     .     .     | .     .     .     
     .     .     .     | a     .     .     | .     .     .     
    -------------------+-------------------+-------------------

Case 2:
4 different digits outside:

Code: Select all

    -------------------+-------------------+-------------------
     .     .     .     | .     .     .     | .     .     .     
     .     .     abcd  | abcd  abcd  .     | .     .     a     
     .     .     abcd  | abcd  abcd  .     | .     b     .     
    -------------------+-------------------+-------------------
     .     .     .     | abcd  abcd  .     | .     .     .     
     .     .     .     | .     .     .     | .     .     .     
     .     .     .     | .     .     .     | .     .     .     
    -------------------+-------------------+-------------------
     .     .     .     | .     d     .     | .     .     .     
     .     .     .     | .     .     .     | .     .     .     
     .     .     .     | c     .     .     | .     .     .     
    -------------------+-------------------+-------------------

Here b becomes locked to r2c45, a to r3c45, d to r34c4, c to r34c5, leaving

Code: Select all

    -------------------+-------------------+-------------------
     .     .     .     | .     .     .     | .     .     .     
     .     .     cd    | bd    bc    .     | .     .     a     
     .     .     cd    | ad    ac    .     | .     b     .     
    -------------------+-------------------+-------------------
     .     .     .     | ab    ab    .     | .     .     .     
     .     .     .     | .     .     .     | .     .     .     
     .     .     .     | .     .     .     | .     .     .     
    -------------------+-------------------+-------------------
     .     .     .     | .     .     .     | .     .     .     
     .     .     .     | .     d     .     | .     .     .     
     .     .     .     | c     .     .     | .     .     .     
    -------------------+-------------------+-------------------

Note, that a or b in box 1 and c or d in box 5 lead to the same pattern.
Has exactly 2 solutions (like a UR).

[SpAce]

Thank you very much, eleven and Leren! This has been very helpful. Hopefully it hasn't been a total waste of time for you guys either! Even if one knows something very well, at least I find it helpful to dive into the details every now and then. There's almost always some new nuance to pick up that provides some deeper understanding.

[Leren]

eleven wrote : Has exactly 2 solutions (like a UR).

First of all, let me congratulate you on a brilliant solution, which I gather is the first time this pattern is constructively proven to be a MUG.

In Myth Jellies' original post on the pattern here he says that he was "pretty sure" it was a MUG based on "testing", and I'm unaware that any further work was done on the subject.

One, hopefully, final piece of pedantry. Perhaps you could change the above wording to something like : "Has exactly 2 internal arrangements (like a UR). The reason being, of course, that the solution status of one arrangement will be the same as the solution status of the other arrangement ie if the pattern is fully exposed the puzzle will have either 0 or 2 solutions that do no conflict with the clues. In a well constructed puzzle with exactly one solution to the clues, there will be at least one other guard digit, call it e, that will disrupt the pattern and form part of the unique solution.

[SpAce]

What about my stab at it? I don't know what kind of proof it is, if any, but is my logic valid?

If it holds, that the possible arrangements can be reduced to these two options with basic UR and BUG-Lite operations:

1. bc & da:

Code: Select all

+-----------------+-----------------+
|                 | b          c    |
|                 |                 |
|                 |                 |
+-----------------+-----------------+
|               d | a          b    |
|                 |                 |
|               a | c          d    |
+-----------------+-----------------+

2. da & cb:

Code: Select all

+-----------------+-----------------+
|                 | d          a    |
|                 |                 |
|                 |                 |
+-----------------+-----------------+
|              c  | a          b    |
|                 |                 |
|              b  | c          d    |
+-----------------+-----------------+

...can we make some direct conclusions based on that? Are they perhaps known unavoidable sets (btw, is there a catalog of those somewhere?)? If so, isn't it a sort of similar proof to reducing the pattern to known MUGs? Or, can we even more directly know (based on known UAs) that four digits simply can't be arranged into such six-cell pattern without at least one clue among them (in a valid puzzle)? In other words, if one knows the corresponding UA, can the MUG property be derived from that directly? (Of course that still leaves the question of how the UA is proved in the first place.)

[blue]

Hi SpAce,

Are they perhaps known unavoidable sets

They are, but I wouldn't say they're "well known".

Each has one alternative fill with the same "footprint" (http://sudopedia.enjoysudoku.com/Footprint.html).

1. bc & da:

Code: Select all

+-----------------+-----------------+       +-----------------+-----------------+
|                 | b          c    |       |                 | c          b    |
|                 |                 |       |                 |                 |
|                 |                 |       |                 |                 |
+-----------------+-----------------+  -->  +-----------------+-----------------+
|               d | a          b    |       |               a | b          d    |
|                 |                 |       |                 |                 |
|               a | c          d    |       |               d | a          c    |
+-----------------+-----------------+       +-----------------+-----------------+

2. da & cb:

Code: Select all

+-----------------+-----------------+       +-----------------+-----------------+
|                 | d          a    |       |                 | a          d    |
|                 |                 |       |                 |                 |
|                 |                 |       |                 |                 |
+-----------------+-----------------+  -->  +-----------------+-----------------+
|               c | a          b    |       |               b | c          a    |
|                 |                 |       |                 |                 |
|               b | c          d    |       |               c | d          b    |
+-----------------+-----------------+       +-----------------+-----------------+

(Of course that still leaves the question of how the UA is proved in the first place.)

Producing an alternate fill with the same footprint, is one way.
Showing that it is a solution to a BUG-Lite pattern would be another.
(You could have read off the alternates from the BUG-Lite's that you displayed in your original post).

Offhand, I can't think of any other proof method.

What about my stab at it? I don't know what kind of proof it is, if any, but is my logic valid?

It was good enough for me, since I recognized that (1) & (2) were "unavoidable sets" (and given that the alternate fills were compatible with the (prospective) MUG's pencilmarks).

Cheers,
Blue.

---

Aside: I'm always hesitant to call these kinds of things "unavoidable sets". To me, and according to an old definition, an unavoidable set is always a set of cells in a complete solution grid. These days, it's probably a "minority of one" opinion.
There's a slight tie in with that idea and MUGs, though: If a solution to a prospective MUG's pencilmarks, has no extension to a complete grid, then it isn't necessary for an alternate solution with the same footprint to exist, for the pattern to be a MUG.

[eleven]

Are they perhaps known unavoidable sets (btw, is there a catalog of those somewhere?)

In this old thread (2008) you can find the unavoidables of size 6, 8 and 9:
http://forum.enjoysudoku.com/post17837.html#p17837
http://forum.enjoysudoku.com/post18383.html#p18383
http://forum.enjoysudoku.com/post18398.html#p18398

[SpAce]

Thanks, blue! That was very clarifying!

Are they perhaps known unavoidable sets

They are, but I wouldn't say they're "well known".

Each has one alternative fill with the same "footprint" (http://sudopedia.enjoysudoku.com/Footprint.html).

A pattern whose footprint has more than one solution is unavoidable (and conversely).

I hadn't heard of (or registered) that concept before! Seems like a very significant piece of the puzzle I was missing!

1. bc & da:

Code: Select all

+-----------------+-----------------+       +-----------------+-----------------+
|                 | b          c    |       |                 | c          b    |
|                 |                 |       |                 |                 |
|                 |                 |       |                 |                 |
+-----------------+-----------------+  -->  +-----------------+-----------------+
|               d | a          b    |       |               a | b          d    |
|                 |                 |       |                 |                 |
|               a | c          d    |       |               d | a          c    |
+-----------------+-----------------+       +-----------------+-----------------+

So the common footprint here is:

Common footprint: Show

r1: {b,c}
r4: {a,b,d}
r6: {a,c,d}
c3: {a,d}
c4: {a,b,c}
c6: {b,c,d}
b2: {b,c}
b4: {a,d}
b5: {a,b,c,d}

...but, for example, this alternate arrangement has a different footprint so it wouldn't prove anything:

Code: Select all

+-----------------+-----------------+       +-----------------+-----------------+
|                 | b          c    |       |                 | c          b    |
|                 |                 |       |                 |                 |
|                 |                 |       |                 |                 |
+-----------------+-----------------+  -->  +-----------------+-----------------+
|               d | a          b    |       |               d | a          c    |
|                 |                 |       |                 |                 |
|               a | c          d    |       |               a | b          d    |
+-----------------+-----------------+       +-----------------+-----------------+


Different footprints: Show

r1: {b,c}
r4: {a,b,d} -> {a,c,d}
r6: {a,c,d} -> {a,b,d}
c3: {a,d}
c4: {a,b,c}
c6: {b,c,d}
b2: {b,c}
b4: {a,d}
b5: {a,b,c,d}

Right?

(Of course that still leaves the question of how the UA is proved in the first place.)

Producing an alternate fill with the same footprint, is one way.

That seems easy enough, at least here. So, if I'd just done that extra step for both cases, it would have been an acceptable proof?

Showing that it is a solution to a BUG-Lite pattern would be another.
(You could have read off the alternates from the BUG-Lite's that you displayed in your original post).

Not sure if I understand that part. Can you elaborate?

What about my stab at it? I don't know what kind of proof it is, if any, but is my logic valid?

It was good enough for me, since I recognized that (1) & (2) were "unavoidable sets" (and given that the alternate fills were compatible with the (prospective) MUG's pencilmarks).

Glad to hear that!

Aside: I'm always hesitant to call these kinds of things "unavoidable sets". To me, and according to an old definition, an unavoidable set is always a set of cells in a complete solution grid. These days, it's probably a "minority of one" opinion.
There's a slight tie in with that idea and MUGs, though: If a solution to a prospective MUG's pencilmarks, has no extension to a complete grid, then it isn't necessary for an alternate solution with the same footprint to exist, for the pattern to be a MUG.

Again, not sure if I understand what that means in practice. Can you give an example?

[SpAce]

In this old thread (2008) you can find the unavoidables of size 6, 8 and 9:
http://forum.enjoysudoku.com/post17837.html#p17837
http://forum.enjoysudoku.com/post18383.html#p18383
http://forum.enjoysudoku.com/post18398.html#p18398

Thanks, eleven! So, I guess our example corresponds with this:

Code: Select all

T9
-----------
12.|4..|...
34.|1..|...
...|...|...
-----------
23.|
...|
...|
-----------

Or at least it matches with the first case. Does it also cover the second one? It would look like this to me:

Code: Select all

-----------
12.|3..|...
34.|2..|...
...|...|...
-----------
41.|
...|
...|
-----------

...but can we somehow see them as the same?

Code: Select all

T10 [Edit: This one should not be in the list, it cannot occur]
-----------
12.|34.|...
34.|21.|...
...|...|...
-----------

Probably a stupid question, but why can't that pattern occur in a real puzzle?

[eleven]

...but can we somehow see them as the same?

Yes, the second it is equivalent. Just swap the colums 12 and renumber 1<->2, 3<->4.

Probably a stupid question, but why can't that pattern occur in a real puzzle?

There is no place for the 3 digits in r1c789 in the other row 2.

[SpAce]

...but can we somehow see them as the same?

Yes, the second it is equivalent. Just swap the colums 12 and renumber 1<->2, 3<->4.

Ah, of course. I didn't consider the column swapping possibility. Thanks!

Probably a stupid question, but why can't that pattern occur in a real puzzle?

There is no place for the 3 digits in r1c789 in the other row 2.

So I was right. It was a very stupid question! I knew I was blind to something obvious. Thanks for that too!