#include <stdlib.h>
#include <stdio.h>
#define S 7
#define M 4
#define N (S*S) / M
int cell(int grid[S][S], int x, int y)
{
if (x < 0 || x >= S) return 0;
if (y < 0 || y >= S) return 0;
return grid[y][x];
}
int solve(int *repo, int grid[S][S], int x, int y)
{
if (y == S) {
int i, j;
for (i = 0; i < 7; i++) {
for (j = 0; j < 7; j++) {
//putchar(".RGYB"[grid[j][i]]);
//putchar(".RGYB"[grid[j][i]]);
}
}
return 1;
} else {
int nextx = x + 1;
int nexty = y;
int res = 0;
int i;
if (nextx == 7) {
nextx = 0;
nexty++;
}
//Seeded part of the grid - see comments in main()
if((x < 2) && (y < 2)) {
res += solve(repo, grid, nextx, nexty);
}
else {
for (i = 0; i < M + 1; i++) {
if (repo[i] == 0) continue;
if (i && cell(grid, x - 1, y - 1) == i) continue;
if (i && cell(grid, x + 0, y - 1) == i) continue;
if (i && cell(grid, x + 1, y - 1) == i) continue;
if (i && cell(grid, x - 1, y + 0) == i) continue;
grid[y][x] = i;
repo[i]--;
res += solve(repo, grid, nextx, nexty);
grid[y][x] = 0;
repo[i]++;
}
}
return res;
}
}
//http://p...content-available-to-author-only...e.com/a/44681/13148
int main()
{
int repo[M + 1] = {1, N, N, N, N};
int grid[S][S] = {{0}};
int n;
//n = solve(repo, grid, 0, 0);
//Seed the grid to reduce color permutations and rotations/reflections:
// - There is only one empty cell, so at least three grid corners must be full of prisoners
// - Let's rotate the grid so that the top left corner is one of those corners
// - The upper left 2x2 cells must contain all 4 groups (colors) so no groups are in adjacent cells
grid[0][0] = 1;
grid[0][1] = 2;
grid[1][0] = 3;
grid[1][1] = 4;
repo[1]--;
repo[2]--;
repo[3]--;
repo[4]--;
n = solve(repo, grid, 2, 0);
printf("%d cells, %d groups of %d prisoners: %d\n", S
*S
, M
, N
, n
);
return 0;
}
CiNpbmNsdWRlIDxzdGRsaWIuaD4KI2luY2x1ZGUgPHN0ZGlvLmg+CgojZGVmaW5lIFMgNwojZGVmaW5lIE0gNAojZGVmaW5lIE4gKFMqUykgLyBNCgppbnQgY2VsbChpbnQgZ3JpZFtTXVtTXSwgaW50IHgsIGludCB5KQp7CiAgICBpZiAoeCA8IDAgfHwgeCA+PSBTKSByZXR1cm4gMDsKICAgIGlmICh5IDwgMCB8fCB5ID49IFMpIHJldHVybiAwOwogICAgCiAgICByZXR1cm4gZ3JpZFt5XVt4XTsKfQoKaW50IHNvbHZlKGludCAqcmVwbywgaW50IGdyaWRbU11bU10sIGludCB4LCBpbnQgeSkKewogICAgaWYgKHkgPT0gUykgeyAgCiAgICAgICAgaW50IGksIGo7CiAgICAgICAgCiAgICAgICAgZm9yIChpID0gMDsgaSA8IDc7IGkrKykgewogICAgICAgICAgICBmb3IgKGogPSAwOyBqIDwgNzsgaisrKSB7CiAgICAgICAgICAgICAgICAvL3B1dGNoYXIoIi5SR1lCIltncmlkW2pdW2ldXSk7CiAgICAgICAgICAgICAgICAvL3B1dGNoYXIoIi5SR1lCIltncmlkW2pdW2ldXSk7CiAgICAgICAgICAgICAgICBwdXRjaGFyKCIgWE8tWyJbZ3JpZFtqXVtpXV0pOwogICAgICAgICAgICAgICAgcHV0Y2hhcigiIFhPLV0iW2dyaWRbal1baV1dKTsKICAgICAgICAgICAgfQogICAgICAgICAgICBwdXRjaGFyKDEwKTsKICAgICAgICB9CiAgICAgICAgcHV0Y2hhcigxMCk7CiAgICAgICAgICAKICAgICAgICByZXR1cm4gMTsKICAgIH0gZWxzZSB7CiAgICAgICAgaW50IG5leHR4ID0geCArIDE7CiAgICAgICAgaW50IG5leHR5ID0geTsKICAgICAgICBpbnQgcmVzID0gMDsKICAgICAgICBpbnQgaTsKICAgICAgICAKICAgICAgICBpZiAobmV4dHggPT0gNykgewogICAgICAgICAgICBuZXh0eCA9IDA7CiAgICAgICAgICAgIG5leHR5Kys7CiAgICAgICAgfQogICAgICAgIAogICAgICAgIC8vU2VlZGVkIHBhcnQgb2YgdGhlIGdyaWQgLSBzZWUgY29tbWVudHMgaW4gbWFpbigpCiAgICAgICAgaWYoKHggPCAyKSAmJiAoeSA8IDIpKSB7CiAgICAgICAgICAgIHJlcyArPSBzb2x2ZShyZXBvLCBncmlkLCBuZXh0eCwgbmV4dHkpOwogICAgICAgIH0KICAgICAgICBlbHNlIHsKCSAgICAgICAgZm9yIChpID0gMDsgaSA8IE0gKyAxOyBpKyspIHsKCSAgICAgICAgICAgIGlmIChyZXBvW2ldID09IDApIGNvbnRpbnVlOwoJICAgICAgICAgICAgaWYgKGkgJiYgY2VsbChncmlkLCB4IC0gMSwgeSAtIDEpID09IGkpIGNvbnRpbnVlOwoJICAgICAgICAgICAgaWYgKGkgJiYgY2VsbChncmlkLCB4ICsgMCwgeSAtIDEpID09IGkpIGNvbnRpbnVlOwoJICAgICAgICAgICAgaWYgKGkgJiYgY2VsbChncmlkLCB4ICsgMSwgeSAtIDEpID09IGkpIGNvbnRpbnVlOwoJICAgICAgICAgICAgaWYgKGkgJiYgY2VsbChncmlkLCB4IC0gMSwgeSArIDApID09IGkpIGNvbnRpbnVlOwoJICAgICAgICAgICAgCgkgICAgICAgICAgICBncmlkW3ldW3hdID0gaTsKCSAgICAgICAgICAgIHJlcG9baV0tLTsKCSAgICAgICAgICAgIAoJICAgICAgICAgICAgcmVzICs9IHNvbHZlKHJlcG8sIGdyaWQsIG5leHR4LCBuZXh0eSk7CgkgICAgICAgICAgICAKCSAgICAgICAgICAgIGdyaWRbeV1beF0gPSAwOwoJICAgICAgICAgICAgcmVwb1tpXSsrOwoJICAgICAgICB9CiAgICAgICAgfQoKICAgICAgICByZXR1cm4gcmVzOwogICAgfQp9CgovL2h0dHA6Ly9wLi4uY29udGVudC1hdmFpbGFibGUtdG8tYXV0aG9yLW9ubHkuLi5lLmNvbS9hLzQ0NjgxLzEzMTQ4CmludCBtYWluKCkKewogICAgaW50IHJlcG9bTSArIDFdID0gezEsIE4sIE4sIE4sIE59OwogICAgaW50IGdyaWRbU11bU10gPSB7ezB9fTsKICAgIGludCBuOwogICAgCiAgICAvL24gPSBzb2x2ZShyZXBvLCBncmlkLCAwLCAwKTsKCiAgICAvL1NlZWQgdGhlIGdyaWQgdG8gcmVkdWNlIGNvbG9yIHBlcm11dGF0aW9ucyBhbmQgcm90YXRpb25zL3JlZmxlY3Rpb25zOgogICAgLy8gLSBUaGVyZSBpcyBvbmx5IG9uZSBlbXB0eSBjZWxsLCBzbyBhdCBsZWFzdCB0aHJlZSBncmlkIGNvcm5lcnMgbXVzdCBiZSBmdWxsIG9mIHByaXNvbmVycwogICAgLy8gLSBMZXQncyByb3RhdGUgdGhlIGdyaWQgc28gdGhhdCB0aGUgdG9wIGxlZnQgY29ybmVyIGlzIG9uZSBvZiB0aG9zZSBjb3JuZXJzCiAgICAvLyAtIFRoZSB1cHBlciBsZWZ0IDJ4MiBjZWxscyBtdXN0IGNvbnRhaW4gYWxsIDQgZ3JvdXBzIChjb2xvcnMpIHNvIG5vIGdyb3VwcyBhcmUgaW4gYWRqYWNlbnQgY2VsbHMKICAgIGdyaWRbMF1bMF0gPSAxOwogICAgZ3JpZFswXVsxXSA9IDI7CiAgICBncmlkWzFdWzBdID0gMzsKICAgIGdyaWRbMV1bMV0gPSA0OwogICAgcmVwb1sxXS0tOwogICAgcmVwb1syXS0tOwogICAgcmVwb1szXS0tOwogICAgcmVwb1s0XS0tOwogICAgbiA9IHNvbHZlKHJlcG8sIGdyaWQsIDIsIDApOwogICAgCiAgICBwcmludGYoIiVkIGNlbGxzLCAlZCBncm91cHMgb2YgJWQgcHJpc29uZXJzOiAlZFxuIiwgUypTLCBNLCBOLCBuKTsKCiAgICByZXR1cm4gMDsKfQo=