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