// See http://www.iwriteiam.nl/D1802.html#10 for explaination #include #include void generateExactCover() { for (int p = 0; p < 16; p++) { bool tl = (p & 8) != 0; bool tr = (p & 4) != 0; bool bl = (p & 2) != 0; bool br = (p & 1) != 0; for (int y = 0; y < 4; y++) for (int x = 0; x < 4; x++) if (p != 0 || (x == 0 && y == 0)) { for (int i = 0; i < 16; i++) printf("%c", p == i ? '1' : '0'); for (int i = 0; i < 16; i++) printf("%c", x + 4*y == i ? '1' : '0'); for (int y1 = 0; y1 < 4; y1++) for (int x1 = 1; x1 < 4; x1++) if (x1 == x + 1 && y1 == y) printf("%c%c", tr ? '0' : '1', br ? '0' : '1'); else if (x1 == x && y1 == y) printf("%c%c", tl ? '1' : '0', bl ? '1' : '0'); else printf("00"); for (int y1 = 1; y1 < 4; y1++) for (int x1 = 0; x1 < 4; x1++) if (x1 == x && y1 == y + 1) printf("%c%c", bl ? '0' : '1', br ? '0' : '1'); else if (x1 == x && y1 == y) printf("%c%c", tl ? '1' : '0', tr ? '1' : '0'); else printf("00"); printf(" %d at %d,%d\n", p, x, y); } } } #define ELEM(V,I) (((V) & (1 << (I))) != 0 ? 1 : 0) void tryAll(bool output_json) { int matching[17]; for (int i = 0; i < 17; i++) matching[i] = 0; int extra[16]; for (int i = 0; i < 16; i++) extra[i] = 0; for (int s = 0; s < (1 << 25); s++) if (ELEM(s,0) == 0 && ELEM(s,1) == 0 && ELEM(s,5) == 0 && ELEM(s,6) == 0) { int count[16]; for (int i = 0; i < 16; i++) count[i] = 0; for (int x = 0; x < 4; x++) for (int y = 0; y < 4; y++) { int p = x + 5*y; int v = (ELEM(s,p) ? 8 : 0) | (ELEM(s,p+1) ? 4 : 0) | (ELEM(s,p+5) ? 2 : 0) | (ELEM(s,p+6) ? 1 : 0); count[v]++; } int m = 0; for (int i = 0; i < 16; i++) if (count[i] > 0) m++; matching[m]++; if (m == 16) { if (output_json) { for (int y = 0; y < 4; y++) for (int x = 0; x < 4; x++) { int p = x + 5*y; if (p > 0) { int v = (ELEM(s,p) ? 8 : 0) | (ELEM(s,p+1) ? 4 : 0) | (ELEM(s,p+5) ? 2 : 0) | (ELEM(s,p+6) ? 1 : 0); printf("%s%d", p == 1 ? "\t[" : ",",v); } } printf("],"); } else { for (int y = 0; y < 5; y++) { for (int x = 0; x < 5; x++) printf("%d", ELEM(s, x + 5*y)); printf("\n"); } printf("\n"); for (int y = 0; y < 4; y++) { for (int x = 0; x < 4; x++) { int p = x + 5*y; int v = (ELEM(s,p) ? 8 : 0) | (ELEM(s,p+1) ? 4 : 0) | (ELEM(s,p+5) ? 2 : 0) | (ELEM(s,p+6) ? 1 : 0); printf("%x", v); } printf("\n"); } } printf("\n"); } } if (!output_json) for (int i = 1; i <= 16; i++) printf("%2d: %6d\n", i, matching[i]); } int main(int argc, char *argv[]) { if (argc >= 2 && strcmp(argv[1], "EC") == 0) generateExactCover(); else tryAll(argc >= 2 && strcmp(argv[1], "js") == 0); return 0; }