Muggy 6

Post puzzles for others to solve here.

Re: Muggy 6

Postby ronk » Sat Jan 18, 2014 8:29 pm

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

Postby eleven » Sat Jan 18, 2014 9:48 pm

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: 2422
Joined: 10 February 2008

Re: Muggy 6

Postby Luke » Sun Jan 19, 2014 4:34 am

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 :twisted:
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      .       ?       | .       .
 .       .       .       | .       .
 .       .       .       | .       .
User avatar
Luke
2015 Supporter
 
Posts: 435
Joined: 06 August 2006
Location: Southern Northern California

Re: Muggy 6

Postby daj95376 » Sun Jan 19, 2014 10:56 am

[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

Postby eleven » Sun Jan 19, 2014 12:35 pm

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: 2422
Joined: 10 February 2008

Re: Muggy 6

Postby eleven » Sun Jan 19, 2014 3:25 pm

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: 2422
Joined: 10 February 2008

Re: Muggy 6

Postby ronk » Sun Jan 19, 2014 4:39 pm

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

Postby daj95376 » Sun Jan 19, 2014 6:13 pm

[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

Postby blue » Sun Jan 19, 2014 6:40 pm

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

Postby eleven » Sun Jan 19, 2014 8:06 pm

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: 2422
Joined: 10 February 2008

Re: Muggy 6

Postby JC Van Hay » Mon Jan 20, 2014 12:18 am

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
2r7c3
OR
6r7c3 ---------------------|
6r3c3=1r3c3                |
6r2c3=1r2c3=9r2c3 ---------|
      1r2c1=9r2c1=6r2c1 ---|---> 1 solution of UA(69)r27c13
6r7c1===================9r7c1=2r7c1
OR
9r7c3
9r2c3=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
2r7c3
OR
6r7c3 ---------------------------|
6r3c3=1r3c3                      |
6r2c3=1r2c3=9r2c3 ---------------|
      1r2c1=9r2c1=6r2c1 ---------|
9r7c3===================9r7c1 ---|---> 1 solution of UA(69)r27c13
OR
9r7c3
9r2c3=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

Postby blue » Mon Jan 20, 2014 5:55 am

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

The 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 cells
288 solutions
84 footprints
valid MUG


Code: Select all
input.txt:

+---------------+------------+---------------+
| .  .     .    | .  .  1234 | .  .     1234 |
| .  1234  1234 | .  .  1234 | .  1234  .    |
| .  1234  1234 | .  .  .    | .  1234  1234 |
+---------------+------------+---------------+

output:

10 cells
288 solutions
180 footprints
not 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

Postby eleven » Mon Jan 20, 2014 9:13 am

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: 2422
Joined: 10 February 2008

Previous

Return to Puzzles