Muggy 6

Post puzzles for others to solve here.

Re: Muggy 6

eleven wrote:
Luke wrote:I'd be interested in what eleven has to say...
Hm, i like the pattern, and i call it MUG like Myth, who has found it.
And i like the combination of "impossible" and "uniqueness" arguments.

As I mentioned earlier, XSUDO does not label the (169)r237c135 pattern below as a MUG. IMO time and effort would have been better expended finding out why.
Code: Select all
`*--------------------------------------------------------------*| 8     2     7      | 3     9     4      | 5     6     1      ||*169   3    *169    | 5    *16    2      | 7     8     4      || 5     4    *16     | 7    *16    8      | 3     2     9      ||--------------------+--------------------+--------------------|| 4     7     28     | 29    5     6      | 289   1     3      || 26    69    5      | 1     8     3      | 269   4     7      || 3     169   1268   | 29    4     7      | 2689  5     28     ||--------------------+--------------------+--------------------||*69+2  5    *69+2   | 68    3     1      | 4     7     8-2    || 7     16    4      | 68    2     9      | 18    3     5      || 1-2   8     3      | 4     7     5      | 12    9     6      |*--------------------------------------------------------------*`
ronk
2012 Supporter

Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Re: Muggy 6

Well i don't know XSUDO, and i don't have an official MUG definition at hand.
But in my eyes this is a flaw of the program, either from having a distinct definition for a MUG or from programming.

My definition is, that a MUG is a group of connected cells with candidates (pattern) - at least one having more than 2, which have at least 2 solutions inside this pattern, and no numbers placed outside can lead to a unique pattern solution.
Is there a different one?
eleven

Posts: 2381
Joined: 10 February 2008

Re: Muggy 6

eleven wrote:My definition is, that a MUG is a group of connected cells with candidates (pattern) - at least one having more than 2, which have at least 2 solutions inside this pattern, and no numbers placed outside can lead to a unique pattern solution.
Is there a different one?

An actual MUG definition? How revolutionary
I think it's a pretty damn good one.

"....which have at least 2 solutions inside this pattern...."

The only way I can make two solutions out of this pattern is to leave (1)r2c1 out of it, which is just good ole overlapping URs.

Here is the line that's getting blurred:
Is a pattern with "...at least 2 solutions PLUS a no solution" still a MUG in your definition?

The pattern:
Code: Select all
` .       .       .       | .       .  169     .       169     | .       16 .       .       16      | .       16-------------------------+------------ .       .       .       | .       .  .       .       .       | .       .  .       .       .       | .       . -------------------------+------------ 69      .       69      | .       .  .       .       .       | .       .  .       .       .       | .       . `

Two possible solutions:
Code: Select all
` .       .       .       | .       .  9       .       1       | .       6 .       .       6       | .       1-------------------------+------------ .       .       .       | .       .  .       .       .       | .       .  .       .       .       | .       . -------------------------+------------ 6      .        9       | .       .  .       .       .       | .       .  .       .       .       | .       . `

Code: Select all
` .       .       .       | .       .  9       .       6       | .       1 .       .       1       | .       6-------------------------+------------ .       .       .       | .       .  .       .       .       | .       .  .       .       .       | .       . -------------------------+------------ 6      .        9       | .       .  .       .       .       | .       .  .       .       .       | .       . `

...plus no solution:
Code: Select all
` .       .       .       | .       .  1       .       9       | .       6 .       .       6       | .       1-------------------------+------------ .       .       .       | .       .  .       .       .       | .       .  .       .       .       | .       . -------------------------+------------ 69      .       ?       | .       .  .       .       .       | .       .  .       .       .       | .       . `

Luke
2015 Supporter

Posts: 435
Joined: 06 August 2006
Location: Southern Northern California

Re: Muggy 6

[Withdrawn: the following posts demonstrate a MUG definition that I didn't expect.]
Last edited by daj95376 on Mon Jan 20, 2014 4:44 pm, edited 1 time in total.
daj95376
2014 Supporter

Posts: 2624
Joined: 15 May 2006

Re: Muggy 6

Since we know, that the uniqueness topic has many pitfalls, let us try to clarify some things.

When we look at a BUG pattern - each digit in the pattern twice in it's row, column and box, we can prove, that it is deadly by saying: "If it had one solution, it would have 2". This comes from the fact, that from one solution you would get another by taking the other digit in each cell.
However, having proved that, it turns out, that a BUG pattern in a unique puzzle never can have a solution. It cannot hold a (single) solution in the puzzle (as proved), and also not as stand-alone pattern. This is, because with the BUG property it is independent from the rest of the grid: No digit in the pattern can be outside in the same unit [Added: it would make it "no solution" by killing both possible solutions].

The same independence of the outside grid we have with UR's and BUG-Lites (as far as i know). Therefore we can verify them without looking at the rest of the grid. If the pattern has 2 solutions inside, it must be deadly, because also for a complete puzzle solution there would exist a second one.
I am not expert enough for BUG-Lites to exclude, that some have no pattern solutions, but i don't think so.

This is different with MUG's. There are units, where pattern digits still can be outside, and the pattern will change into this or that direction, depending which one it is.
Here the only way i know, to prove, that it is a valid MUG is to make all the possible placements outside and show for any case, that the pattern then either has no solution, or more than one.
eleven

Posts: 2381
Joined: 10 February 2008

Re: Muggy 6

Having said that, i wonder, if this is a MUG (not sure yet):
Code: Select all
` 1234  1234   .  |  1234  .  1234  |  1234    .    .  |   .    .  1234  |    .     .    .  |   .    .    .   |----------------------------------   .     .    .  |   .    .    .   | 1234    .    .  |   .    .  1234  | 1234  1234   .  |  1234  .  1234  |------------------------------------`
eleven

Posts: 2381
Joined: 10 February 2008

Re: Muggy 6

Luke wrote:Here is the line that's getting blurred:
Is a pattern with "...at least 2 solutions PLUS a no solution" still a MUG in your definition?
...
...plus no solution:
Code: Select all
` .       .       .       | .       .  1       .       9       | .       6 .       .       6       | .       1-------------------------+------------ .       .       .       | .       .  .       .       .       | .       .  .       .       .       | .       . -------------------------+------------ 69      .       ?       | .       .  .       .       .       | .       .  .       .       .       | .       . `

It can be argued that r2c1=1 implies r7c3=2 (or some other non-pattern digit), which would mean the pattern (with r2c1=1 as a pattern digit) is not a MUG.
ronk
2012 Supporter

Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Re: Muggy 6

[Withdrawn: the following posts demonstrate a MUG definition that I didn't expect.]
Last edited by daj95376 on Mon Jan 20, 2014 4:45 pm, edited 1 time in total.
daj95376
2014 Supporter

Posts: 2624
Joined: 15 May 2006

Re: Muggy 6

eleven wrote:I am not expert enough for BUG-Lites to exclude, that some have no pattern solutions, but i don't think so.

Here is an example of a BUG-Lite with no solutions.

eleven wrote:This is different with MUG's. There are units, where pattern digits still can be outside, and the pattern will change into this or that direction, depending which one it is.
Here the only way i know, to prove, that it is a valid MUG is to make all the possible placements outside and show for any case, that the pattern then either has no solution, or more than one.

An (apparent) alternative, that doesn't involve external placements, is to enumerate all of the pattern's solutions, and check that for each one, there is a second with the same footprint -- i.e. with same numbers occuring in each row, column and box.
If a footprint occured only once, then you could make some deductions about what would be required of external placements, by considering the complementary footprint and the PMs that it produces.

There's a possible issue: What if there is a solution with a footprint that only occurs once, but its complementary footprint has no solutions ? What if the complementary footprint doesn't have solutions, but the details have a lot to do with digits that don't actually occur in the potential MUG, and it's still possible to fill (just) some of the outside cells in a way that would reduce the pattern to the point where only the one solution remained ?

Those kinds of issues have tie-ins with an external placements definition, and the question of just how "realistic" they should be.

My worthless opinion: Stick with the "for each solution, a 2nd with the same footprint" idea, and don't worry about complementary footprints or external placements. It seems closest in spirit to the ideas behind BUGs, BUG-Lites, URs and DP's based on other kinds of unavoidable sets, and for all I know, it was the original definition (if there ever was one).
blue

Posts: 894
Joined: 11 March 2013

Re: Muggy 6

blue wrote:
eleven wrote:I am not expert enough for BUG-Lites to exclude, that some have no pattern solutions, but i don't think so.

Here is an example of a BUG-Lite with no solutions.

Ah, thanks. It's a BUG-Lite, where the 9 is both BUG and extra candidate.

An (apparent) alternative, that doesn't involve external placements, is to enumerate all of the pattern's solutions, and check that for each one, there is a second with the same footprint -- i.e. with same numbers occuring in each row, column and box.
...

Since i am not familiar with this "footprint" idea, i am not sure, that i understood this way to verify, if a pattern is a MUG.
The footprint consists of the numbers of a solution in each unit in arbitrary order, like 12 for all units (and both solutions) for a 12 UR ?
Would you be so kind to give an example for the possible MUG pattern i posted above ?

[Edit:] Now i guess, that it is clear to me (including a possible problem to find the outer placements with a complementary grid). But if you have the tools, it would be nice, when you could verify, if the above pattern is a MUG or not (I could not find a short way to do it manually). And give an example of a unique pattern solution, if there is one, or an example for a footprint with 2 solutions.
eleven

Posts: 2381
Joined: 10 February 2008

Re: Muggy 6

Two equivalent analyses of "Muggy 6" implying "incompatible patterns" ...

Number one :
Code: Select all
`+----------------------+-------------+--------------+| 8       2    7       | 3   9     4 | 5     6  1   || (16-9)  3    (+9-16) | 5   (16)  2 | 7     8  4   || 5       4    (16)    | 7   (16)  8 | 3     2  9   |+----------------------+-------------+--------------+| 4       7    28      | 29  5     6 | 289   1  3   || 26      69   5       | 1   8     3 | 269   4  7   || 3       169  1268    | 29  4     7 | 2689  5  28  |+----------------------+-------------+--------------+| (269)   5    (26-9)  | 68  3     1 | 4     7  8-2 || 7       16   4       | 68  2     9 | 18    3  5   || 1-2     8    3       | 4   7     5 | 12    9  6   |+----------------------+-------------+--------------+`
Kraken (269)r7c3 :=> [2r7c3==UA(69)r27c13==2r7c1==UR(16)r23c34]-2r7c9,r9c1 and 9r2c3=UR(16)r23c35
Code: Select all
`2r7c3OR6r7c3 ---------------------|6r3c3=1r3c3                |6r2c3=1r2c3=9r2c3 ---------|      1r2c1=9r2c1=6r2c1 ---|---> 1 solution of UA(69)r27c136r7c1===================9r7c1=2r7c1OR9r7c39r2c3=UR(16)r23c35`
7 Base Sets : r2c135 + r3c35 + r7c13 => Base-2r7c13="DP" ?

Number two:
Code: Select all
`+-----------------------+-------------+--------------+| 8        2    7       | 3   9     4 | 5     6  1   || (16-9)   3    (+9-16) | 5   (16)  2 | 7     8  4   || 5        4    (16)    | 7   (16)  8 | 3     2  9   |+-----------------------+-------------+--------------+| 4        7    8-2     | 29  5     6 | 289   1  3   || 26       69   5       | 1   8     3 | 269   4  7   || 3        169  168-2   | 29  4     7 | 2689  5  28  |+-----------------------+-------------+--------------+| -26(+9)  5    (+2-69) | 68  3     1 | 4     7  8-2 || 7        16   4       | 68  2     9 | 18    3  5   || 1-2      8    3       | 4   7     5 | 12    9  6   |+-----------------------+-------------+--------------+`
Kraken (269)r7c3 :=> [2r7c3==UA(69)r27c13==UR(16)r23c34] :=> r7c3=2 => r7c1=9=r2c3
Code: Select all
`2r7c3OR6r7c3 ---------------------------|6r3c3=1r3c3                      |6r2c3=1r2c3=9r2c3 ---------------|      1r2c1=9r2c1=6r2c1 ---------|9r7c3===================9r7c1 ---|---> 1 solution of UA(69)r27c13OR9r7c39r2c3=UR(16)r23c35`
7 Base Sets : r2c135 + r3c35 + r7c3 + 9r7c13 => Base-2r7c3="DP" ?
JC Van Hay

Posts: 719
Joined: 22 May 2010

Re: Muggy 6

Hi eleven,

Sorry I was so late on the reply -- football to watch.
Your pattern above, is indeed a MUG.

Most of what you asked for, I think ...

The main idea with footprints, is that if two ways of filling a set of cells, have the same footprint, then one fill can replace the other in any extension to a complete grid.
A 2nd solution to a footprint, is a solution that differs from the first in an unavoidable set that isn't necessarily minimal, and doesn't necessarily cover the entire pattern -- e.g. where the "difference cells" contain the two solutions to a UR pattern. The "vica-versa" is true as well.
A solution to a complementary footprint, amounts to a way to extend the first solution to a complete grid.

This is a short example of the idea "at work":
Code: Select all
`Your pattern:1234 1234 . | 1234 . 1234 |1234 .    . | .    . 1234 |.    .    . | .    . .    |------------+-------------+.    .    . | .    . .    |1234 .    . | .    . 1234 |1234 1234 . | 1234 . 1234 |------------+-------------+one of its solutions:1 2 . | 4 . 3 |3 . . | . . 2 |. . . | . . . |------+-------+. . . | . . . |2 . . | . . 4 |4 3 . | 2 . 1 |------+-------+The solution's footprint:    cell list: r1c1,..., r6c7 (the 12 cells of the pattern)    digits used in rows:        r1:1234        r2:23        r5:24          r6:1234    digits used in columns:        c1:1234        c2:23        c4:24        c6:1234    digits used in boxes:        b1: 123        b2: 234        b4: 234        b5: 124The original pattern, masked to allow only digits from the footprint lists:In this case, it's also the PM for the footprint itself.123 23 . | 24 . 234 |23  .  . | .  . 23  |.   .  . | .  . .   |---------+----------+.   .  . | .  . .   |24  .  . | .  . 24  |234 23 . | 24 . 124 |---------+----------+If that didn't have a solution that was distinct from the first, then the pattern would not be a MUG.It does have this solution, however:1 3 . | 2 . 4 |2 . . | . . 3 |. . . | . . . |------+-------+. . . | . . . |4 . . | . . 2 |3 2 . | 4 . 1 |------+-------+Similar things happen for all solutions to the original pattern.`

This is a quick and dirty C++ program, to read a pattern from file "input.txt", and check whether it's a MUG, using the "footprint based defintion" that doesn't worry about whether the solutions can be extended to a full grid. It doesn't actually try to produce 2nd solutions with the same footprint. Instead, it just collects the distinct footprints, one solution for each, and an count of solutions producing the given footprint.

C++:
Hidden Text: Show
Code: Select all
`#include <stdio.h>#include <stdlib.h>#include <string.h>int cellList[81];int cellCount;int masks[81];unsigned char grid[81];struct footprintdata { // sans cell list    int rowMasks[9];    int colMasks[9];    int boxMasks[9];};enum { MaxFootprintCount = 10000, };int solutionCount;int footprintCount;int counts[MaxFootprintCount];unsigned char solutions[MaxFootprintCount][81];footprintdata footprintList[MaxFootprintCount];void Solve(int index){    if (index == cellCount)    {        ++solutionCount;        footprintdata fp;        memset(&fp, 0, sizeof(fp));        for (int i = 0; i < cellCount; i++)        {            int cell = cellList[i];            int r = cell / 9;            int c = cell % 9;            int b = 3 * (r / 3) + (c / 3);            fp.rowMasks[r] |= (1 << grid[cell]);            fp.colMasks[c] |= (1 << grid[cell]);            fp.boxMasks[b] |= (1 << grid[cell]);        }        for (int n = 0; n < footprintCount; n++)        {            if (!memcmp(&fp, &footprintList[n], sizeof(fp)))            {                ++counts[n];                return;            }        }        if (footprintCount == MaxFootprintCount)        {            puts("MaxFootprintCount too small");            exit(-1);        }        counts[footprintCount] = 1;        memcpy(solutions[footprintCount], grid, 81);        memcpy(&footprintList[footprintCount], &fp, sizeof(fp));        ++footprintCount;        return;    }    int cell = cellList[index];    int mask = masks[cell];    int r = cell / 9;    int c = cell % 9;    int b = 3 * (r / 3) + (c / 3);    for (int i = 0; i < index; i++)    {        int cell2 = cellList[i];        if (mask & (1 << grid[cell2]))        {            int r2 = cell2 / 9;            int c2 = cell2 % 9;            int b2 = 3 * (r2 / 3) + (c2 / 3);            if (r2 == r || c2 == c || b2 == b)            {                mask &= ~(1 << grid[cell2]);                if (!mask)                    return;            }        }    }    for (int d = 1; d <= 9; d++)    {        if (mask & (1 << d))        {            grid[cell] = d;            Solve(index + 1);            grid[cell] = 0;        }    }}void ReadInput(){    char buf[256];    FILE *fp = fopen("input.txt", "rt");    if (!fp)    {        puts("input file");        exit(-1);    }    int r = 0;    while (fgets(buf, 256, fp))    {        char *s = buf;        int c = -1;        for (;;)        {            while (*s && !((*s >= '1' && *s <= '9') || *s == '0' || *s == '.'))                ++s;            if (!*s)                break;            int mask = 0;            while (*s && *s != ' ' && *s != '|')            {                if (*s >= '1' && *s <= '9')                    mask |= (1 << (*s - '0'));                ++s;            }            if (c < 0)                c = 0;            masks[9 * r + c] = mask;            if (mask)                cellList[cellCount++] = 9 * r + c;            if (++c >= 9)                break;        }        if (c >= 0)        {//          if (c < 9)//          {//              puts("input error");//              exit(-1);//          }            if (++r >= 9)                break;        }    }//  if (r < 9)//  {//      puts("input error");//      exit(-1);//  }    fclose(fp);}int main(int argc, char **argv){    ReadInput();    Solve(0);    printf("%d cells\n", cellCount);    printf("%d solutions\n", solutionCount);    printf("%d footprints\n", footprintCount);    for (int n = 0; n < footprintCount; n++)    {        if (counts[n] == 1)        {            printf("not a MUG\n");            memcpy(grid, solutions[n], 81);            for (int i = 0; i < 81; i++)                printf("%c%c", (grid[i] ? grid[i] + '0' : '.'), (((i + 1) % 9) ? ' ' : '\n'));            return 1;        }    }    printf("valid MUG\n");    return 0;}`

These are its results for your pattern, and the one here, that isn't a MUG.

Code: Select all
`input.txt:+---------------+---------------+| 1234  1234  . | 1234  .  1234 || 1234  .     . | .     .  1234 || .     .     . | .     .  .    |+---------------+---------------+| .     .     . | .     .  .    || 1234  .     . | .     .  1234 || 1234  1234  . | 1234  .  1234 |+---------------+---------------+output:12 cells288 solutions84 footprintsvalid MUG`

Code: Select all
`input.txt:+---------------+------------+---------------+| .  .     .    | .  .  1234 | .  .     1234 || .  1234  1234 | .  .  1234 | .  1234  .    || .  1234  1234 | .  .  .    | .  1234  1234 |+---------------+------------+---------------+output:10 cells288 solutions180 footprintsnot a MUG. . . . . 1 . . 2. 1 3 . . 2 . 4 .. 2 4 . . . . 1 3. . . . . . . . .. . . . . . . . .. . . . . . . . .. . . . . . . . .. . . . . . . . .. . . . . . . . .`

For the the 2nd pattern, the reported solution has a footprint with this PM diagram:

Code: Select all
`+-----------+----------+-----------+| .  .      | .  .  12 | .  .   2  || .  12  34 | .  .  12 | .  14  .  || .  12  34 | .  .  .  | .  14  23 |+-----------+----------+-----------+`

It doesn't change on Intersecting it with the pattern's PMs.
It's easy to check that it only has the one solution.

Edited: fixed the row order in a PM diagram, and made a "should be" insignificant change in the C++ code.
Last edited by blue on Mon Jan 20, 2014 8:38 pm, edited 3 times in total.
blue

Posts: 894
Joined: 11 March 2013

Re: Muggy 6

Hi blue,

many thanks for your elaborate answer and the MUG-verifying program, which is a kind of late Christmas present for me.
eleven

Posts: 2381
Joined: 10 February 2008

Previous