The New Sudoku Players' Forum

by **Leren** » Fri May 31, 2019 5:55 am

You can learn a lot about MUGs by starting here. Eleven's 7 cell 3 digit MUG appears about half way down the first page.

Leren

by **pjb** » Fri May 31, 2019 11:35 am

Code: Select all: 1 345 2 |c45 358 b48 | 9 7 6 6 57 348 | 157 d157 9 | 348 2 348 9 347 348 | 467 367 2 | 348 5 1 ------------------------+----------------------+--------------------- 5 346 9 | 2 68-1 7 | 3468 146 348 2 8 1 | 56 4 3 | 7 69 59 7 346 34 | 9 568-1 a18 | 2 146 3458 ------------------------+----------------------+--------------------- 3 9 6 | 147 d17 5 | 14 8 2 4 2 5 | 8 9 16 | 16 3 7 8 1 7 | 3 2 46 | 5 469 49

(1=8)r6c6 - (8=4)r1c6 - (4=5)r1c4 - (5=17)r27c5 => -1 r46c5; stte

Phil

by **eleven** » Fri May 31, 2019 9:06 pm

SpAce wrote:Can you give some hints how to see/verify the MUG?

Leren already gave a good link. Years ago I generated puzzles called "Muggy 1" to " Muggy 6".

by **SpAce** » Fri May 31, 2019 9:58 pm

Leren wrote:You can learn a lot about MUGs by starting here. Eleven's 7 cell 3 digit MUG appears about half way down the first page.

Thanks for the link! I don't think I've seen it before, but I guess eleven has tried to explain those principles a couple of times before. I might understand them a bit better now, but the verification process still seems quite error-prone when done manually. Not finding a single-solution producing combo of outside candidates doesn't seem like a positive proof unless every case is definitely covered -- and it might be easy to miss some.

eleven wrote:Leren already gave a good link. Years ago I generated puzzles called "Muggy 1" to " Muggy 6".

Thanks, I found them! They'll probably be useful references!

--

Added. Let's see if I've understood something or not. To me it seems that if we're suspecting a (permeable) MUG with n digits, we should test external candidates on all houses involved which have fewer than n MUG cells (we can't have external MUG candidates in the others, obviously, as they're already full and thus impermeable). For example, in our current case:

Code: Select all: x x +-----------------+---+-----------------+ | | | | | #348 | | #348 #348 | | #348 | | #348 | x +-----------------+---+-----------------+ | | | #348 #348 | x | | | | | | | | +-----------------+---+-----------------+

The permeable houses that can have externals are: r3,r4,c3,c9 (and/or b1,b6 but I'm not sure if they're needed since they're covered by the rows/cols). Doesn't that mean we would need 3^4 tests to cover every possible external combination to have positive proof that none of them produces a valid single solution? That doesn't sound like a reasonable job for a manual solver, even though many of the combos can be easily discarded (or seen as symmetrically equivalent in this case).

What am I missing? It seems to me that it's much easier to disprove a potential permeable MUG than to prove one. Makes me think that the only practical solution for a manual solver is to memorize the common MUG patterns (with pre-generated proofs) instead of proving them on the fly. Tell me it's not so...

by **eleven** » Sat Jun 01, 2019 12:06 pm

SpAce wrote:What am I missing? It seems to me that it's much easier to disprove a potential permeable MUG than to prove one. Makes me think that the only practical solution for a manual solver is to memorize the common MUG patterns (with pre-generated proofs) instead of proving them on the fly. Tell me it's not so...

You are quite right. You can see in the old threads, that proving big MUGs manually is cumbersome.
On the other hand big MUGs are rare in real puzzles, and you will hardly find one, which is not already listed in the MUG threads. And they are not hard to remember.

by **SpAce** » Sat Jun 01, 2019 9:26 pm

eleven wrote:You are quite right. You can see in the old threads, that proving big MUGs manually is cumbersome.
On the other hand big MUGs are rare in real puzzles, and you will hardly find one, which is not already listed in the MUG threads. And they are not hard to remember.

Ok, thanks for confirming that suspicion! It's kind of disappointing, but at least there's no need to feel extremely dumb if one finds it hard to see if a pattern is truly a MUG or not

by **Leren** » Sat Jun 01, 2019 10:07 pm

Code: Select all: +-----------------+---+-----------------+ | | | | | a348 | | b348 c348 | | d348 | | e348 | +-----------------+---+-----------------+ | | | f348 g348 | | | | | | | | | +-----------------+---+-----------------+

I'll have a go at proving that the 7 cell pattern is deadly. I've relabelled the 7 cells for convenience.

Pick any two values for the "diagonal" cells e and c. So, for example, e = 3 and c = 4. You are then left with

Code: Select all: +-----------------+---+-----------------+ | | | | | a3 | | b8 c4 | | d48 | | e3 | +-----------------+---+-----------------+ | | | f4 g38 | | | | | | | | | +-----------------+---+-----------------+

To avoid a 4 cell DP (38) in abde d must be 4. Similarly to avoid a 4 cell DP (48) in bcfg g must be 3. So you are left with

Code: Select all: +-----------------+---+-----------------+ | | | | | a3 | | b8 c4 | | d4 | | e3 | +-----------------+---+-----------------+ | | | f4 g3 | | | | | | | | | +-----------------+---+-----------------+

but then you are left with a 6 cell DP (34) in acdefg. So you can't avoid one of three overlapping DP's. That's a proof, isn't it ?

In any event, re-discovering the proofs of all the MUGs is just re-inventing the wheel. Just remember the keyword "impermeable" and you can easily re-locate the MUG thread and check out all the MUGs.

Leren

PS = found link to the 6 cell DP here although it's clearly not the first reference. Maybe eleven can find that.

Leren

by **SpAce** » Sun Jun 02, 2019 1:07 am

Leren wrote:I'll have a go at proving that the 7 cell pattern is deadly.
...
but then you are left with a 6 cell DP (34) in acdefg. So you can't avoid one of three overlapping DP's. That's a proof, isn't it ?

Yes, that works nicely in this case. What about more complex cases, like this:

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

Assigning a,b,c,d in box 5 gives us:

Code: Select all: +-----------------+-----------------+ | | bd ac | | | | | | | +-----------------+-----------------+ | cd | a b | | | | | ab | c d | +-----------------+-----------------+

From that we can deduce a couple of things (I think):

r1c46 <> ba | dc (URs) => r1c46 = bc | da
r46c3 <> ca | db (URs) => r46c3 = cb | da
r1c46,r46c3 <> (bc & cb) | (da & da) (6-cell BUG-Lites) => r1c46,r46c3 = (bc & da) | (da & cb)

So, we have two possible arrangements left for r1 and c3:

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 | +-----------------+-----------------+

Both look valid to me, as far as basic URs or BUG-Lites are concerned (or am I missing something?). However, it seems that those arrangements are impossible to produce from the original pattern with any external assignments.

For the first case (bc & da), the closest I can get is this:

Code: Select all: +-----------------+-----------------+ | | bc bc | ad | | | | | | +-----------------+-----------------+ | ad | ab bd | c | | | | ad | ac cd | b +-----------------+-----------------+ bc d a

And for the second case (da & cb) this:

Code: Select all: +-----------------+-----------------+ | | ad ad | bc | | | | | | +-----------------+-----------------+ | bc | ac ab | d | | | | bc | cd bd | a +-----------------+-----------------+ ad b c

Both of them are impermeable. So, unless I made mistakes or missed something, does that prove that the original pattern is a MUG? If so, then it seems that basic URs and BUG-Lites can (at least sometimes) help in reducing the pattern, but at the end you may still need the externals check (possibly with a more manageable number of cases, though). Am I on the right track?

In any event, re-discovering the proofs of all the MUGs is just re-inventing the wheel.

Not at all. It's about understanding, which is all that matters to me. I don't see the point in solving puzzles with patterns and techniques I don't fully get.

Just remember the keyword "impermeable" and you can easily re-locate the MUG thread and check out all the MUGs.

I will remember it as a good reference, thanks, but like I said, I don't feel like using any patterns unless I can understand them. Once I do, then I can either memorize or look them up when needed, because I know I could also derive them myself if needed.

by **Leren** » Sun Jun 02, 2019 9:17 am

I've attached a draft of a constructive proof that the more complex 8 cell 16 digit pattern above is indeed a MUG.

Myth Jellies' earlier consideration of this pattern can be found here.

Comments on my "proof", are welcome. Leren

by **SpAce** » Sun Jun 02, 2019 11:01 am

Leren wrote:I've attached a draft of a constructive proof that the more complex 8 cell 16 digit pattern above is indeed a MUG.
...
Comments on my "proof", are welcome. Leren

A couple of quick comments.

The external digits in the rows and columns must be different. Why is this ? ...

You could shorten and simplify this part by just noting that the group in the middle box is a naked quad, and two of the same digit on the rows or columns would annihilate one of its digits leaving three digits for four cells. No need for so many steps to arrive at that conclusion, imho. Nothing wrong with it, of course.

This, however, is something I don't quite understand:

Case 2: Show

Code: Select all
Case 2: Four different external digits (wlog c & d in the rows and a & b in the columns). -------------------+-------------------+------------------- . . . | . . . | . . . . . abcd | abcd abcd . | d . . . . abcd | abcd abcd . | c . . -------------------+-------------------+------------------- . . . | abcd abcd . | . . . . . . | . . . | . . . . . . | . . . | . . . -------------------+-------------------+------------------- . . . | a b . | . . . . . . | . . . | . . . . . . | . . . | . . . -------------------+-------------------+------------------- Which reduces to the following: -------------------+-------------------+------------------- . . . | . . . | . . . . . abc | bc ac . | d . . . . abd | bd ad . | c . . -------------------+-------------------+------------------- . . . | bcd acd . | . . . . . . | . . . | . . . . . . | . . . | . . . -------------------+-------------------+------------------- . . . | a b . | . . . . . . | . . . | . . . . . . | . . . | . . . -------------------+-------------------+------------------- Set r2c5 = a: This gives rise to two 6 cell box bent DPs labelled 1 and 2. -------------------+-------------------+------------------- . . . | . . . | . . . . . b1 | c2 *a1 . | d2 . . . . a1 | b1 d2 . | c2 . . -------------------+-------------------+------------------- . . . | d2 c2 . | . . . . . . | . . . | . . . . . . | . . . | . . . -------------------+-------------------+------------------- . . . | a1 b1 . | . . . . . . | . . . | . . . . . . | . . . | . . . -------------------+-------------------+-------------------

It appears that you're using the externals as parts of the bent DPs in most of your cases (not just here). How can that be? As far as I understand, it would require them to be lined up exactly like you have depicted, but why would they be (unless they're part of the pattern, but then we have a different pattern and they're no longer externals)? What happens if they're like this:

Code: Select all: -------------------+-------------------+------------------- . . . | . . . | . . . . . b1 | c2 *a1 . | . d2 . . . a1 | b1 d2 . | c2 . . -------------------+-------------------+------------------- . . . | d2 c2 . | . . . . . . | . . . | . . . . . . | . . . | . . . -------------------+-------------------+------------------- . . . | . b1 . | . . . . . . | a1 . . | . . . . . . | . . . | . . . -------------------+-------------------+-------------------

Those shapes aren't DPs, right? What am I missing? (In general, it seems kind of weird that the externals are used in such an active role, but I don't know if that's ok or not.)

by **Leren** » Sun Jun 02, 2019 11:17 am

Hi SpAce, that last point was a good one, now you can see why my "proof" was in draft form. I'll think about it more tomorrow. Leren

by **eleven** » Sun Jun 02, 2019 1:04 pm

As you can see, probably the best way to prove big MUG's is to reduce them to smaller known MUG's.
Hopefully these 3 cases do the job:
[Edit:] Thanks to the comments of Space and Leren i edited my proof. Now 2 cases and the note about the quad in box 2 should be sufficient, and a typo corrected]

Hidden Text: Show

First note: there can't be a MUG digit outside in box 2 (therefore also not the same digit outside of both of the 2 rows or columns)

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

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 . | . . . . . . | . . . | . . . . . . | . . . | . . . -------------------+-------------------+------------------- . . . | . . . | . . . . . . | . . . | . . . . . . | c d . | . . . -------------------+-------------------+-------------------

Reduces to this MUG:

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

Has exactly 2 solutions (like a UR).

With a, b in box 1 and c, d in box 5 this does not change (same 2 solutions always):

Code: Select all: -------------------+-------------------+------------------- . . . | . . . | . . . a . cd | bd bc . | . . . b . cd | ad ac . | . . . -------------------+-------------------+------------------- . . . | ab ab . | . . . . . . | . . . | . . . . . . | c d . | . . . -------------------+-------------------+------------------- . . . | . . . | . . . . . . | . . . | . . . . . . | . . . | . . . -------------------+-------------------+-------------------

by **SpAce** » Sun Jun 02, 2019 1:47 pm

eleven wrote:As you can see, probably the best way to prove big MUG's is to reduce them to smaller known MUG's.
Hopefully these 3 cases do the job:

Thanks, eleven! Very helpful!

Added. Just one comment/question about this:

Case 1: Show
A digit outside in both rows (or both columns)
Code: Select all
-------------------+-------------------+------------------- . . . | . . . | . . . . . abcd | abcd abcd . | . . a a . abcd | abcd abcd . | . . -------------------+-------------------+------------------- . . . | abcd abcd . | . . . . . . | . . . | . . . . . . | . . . | . . . -------------------+-------------------+-------------------

Reduces to this MUG:
Code: Select all
-------------------+-------------------+------------------- . . . | . . . | . . . . . bcd | bcd bcd . | . . a a . bcd | bcd bcd . | . . . -------------------+-------------------+------------------

Isn't that the exact case that can't happen (as Leren also mentioned), because it completely removes a digit from the box 2 quad? Or did you just show it for completeness as a no-solution reduction?

by **eleven** » Sun Jun 02, 2019 7:48 pm

You are right, thanks.
I added it at the end, when i read Leren's text - and thought oops, a case i missed.
But it is covered by the note, that there can't be a MUG digit outside in box 2.

by **Leren** » Sun Jun 02, 2019 9:20 pm

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

The New Sudoku Players' Forum

May 30, 2019

Re: May 30, 2019

Re: May 30, 2019

Re: May 30, 2019

Re: May 30, 2019

Re: May 30, 2019

Re: May 30, 2019

Re: May 30, 2019

Re: May 30, 2019

Re: May 30, 2019

Re: May 30, 2019

Re: May 30, 2019

Re: May 30, 2019

Re: May 30, 2019

Re: May 30, 2019

Re: May 30, 2019