#include #include #define BIT(I) (1 << (I)) #define GETBIT(X,I) (((X) >> (I)) & 1) #define BITS2(X,Y) ((X) | ((Y) << 1)) #define BITS3(X,Y,Z) ((X) | ((Y) << 1) | ((Z) << 2)) #define FORALLTILE(I,X) for (int I = 0; I < 16; I++) if (GETBIT(X,I)) void print_qt_first(int qt) { FORALLTILE(i, qt) printf(" %c%c", i & 1 ? '1' : '0', i & 2 ? '1' : '0'); } void print_qt_second(int qt) { FORALLTILE(i, qt) printf(" %c%c", i & 4 ? '1' : '0', i & 8 ? '1' : '0'); } void print_qt(int qt) { printf("\n"); print_qt_first(qt); printf("\n"); print_qt_second(qt); printf("\n"); } class SetOfQT { public: SetOfQT() : nr(0) {} void add(int v) { for (int i = 0; i < nr; i++) if (values[i] == v) return; values[nr++] = v; } void print_first() { for (int i = 0; i < nr; i++) { if (i > 0) printf(" | "); print_qt_first(values[i]); } } void print_second() { for (int i = 0; i < nr; i++) { if (i > 0) printf(" "); print_qt_second(values[i]); } } int nr; int values[20]; }; int permutations[8][4] = { { 0, 1, 2, 3 }, { 2, 0, 3, 1 }, { 3, 2, 1, 0 }, { 1, 3, 0, 2 }, { 0, 2, 1, 3 }, { 1, 0, 3, 2 }, { 3, 1, 2, 0 }, { 2, 3, 0, 1 }, }; long permvectors[15][16]; void fill_permvectors() { for (int i = 1; i < 8; i++) { for (int v = 0; v < 16; v++) { int r = 0; for (int j = 0; j < 4; j++) if (GETBIT(v, j)) r |= BIT(permutations[i][j]); permvectors[i-1][v] = BIT(r); } } for (int i = 0; i < 8; i++) { for (int v = 0; v < 16; v++) { int r = 0; for (int j = 0; j < 4; j++) if (!(GETBIT(v, j))) r |= BIT(permutations[i][j]); permvectors[7+i][v] = BIT(r); } } } bool is_minimal(long qt) { for (int i = 0; i < 15; i++) { long aqt = 0; FORALLTILE(j, qt) aqt |= permvectors[i][j]; if (aqt < qt) return false; } return true; } bool has_unused_pieces(long qt) { int left = 0; int right = 0; int top = 0; int bottom = 0; FORALLTILE(i, qt) { int v0 = GETBIT(i,0); int v1 = GETBIT(i,1); int v2 = GETBIT(i,2); int v3 = GETBIT(i,3); left |= BIT(BITS2(v0, v2)); right |= BIT(BITS2(v1, v3)); top |= BIT(BITS2(v0, v1)); bottom |= BIT(BITS2(v2, v3)); } return left != right || top != bottom; } bool has_unused_pieces_in_cross(long qt) { int topleft = 0; int topright = 0; int bottomleft = 0; int bottomright = 0; FORALLTILE(i, qt) { int v0 = GETBIT(i,0); int v1 = GETBIT(i,1); int v2 = GETBIT(i,2); int v3 = GETBIT(i,3); topleft |= BIT(BITS3(v1,v3,v2)); topright |= BIT(BITS3(v3,v2,v0)); bottomright |= BIT(BITS3(v2,v0,v1)); bottomleft |= BIT(BITS3(v0,v1,v3)); } int poss_topleft = 0; int poss_topright = 0; int poss_bottomright = 0; int poss_bottomleft = 0; for (int i = 0; i < 32; i++) { int c0 = GETBIT(i,0); int c1 = GETBIT(i,1); int c2 = GETBIT(i,2); int c3 = GETBIT(i,3); int c4 = GETBIT(i,4); int v_tl = BITS3(c1,c0,c4); int v_tr = BITS3(c2,c0,c1); int v_br = BITS3(c3,c0,c2); int v_bl = BITS3(c4,c0,c3); bool tl = GETBIT(topleft, v_tl); bool tr = GETBIT(topright, v_tr); bool br = GETBIT(bottomright, v_br); bool bl = GETBIT(bottomleft, v_bl); if (tr && br && bl) { poss_topleft |= BIT(v_tl); } if (tl && br && bl) { poss_topright |= BIT(v_tr); } if (tl && tr && bl) { poss_bottomright |= BIT(v_br); } if (tl && tr && br) { poss_bottomleft |= BIT(v_bl); } } bool result; for (int r = 1; r <=2; r++) { result = false; FORALLTILE(i, qt) { int v0 = GETBIT(i,0); int v1 = GETBIT(i,1); int v2 = GETBIT(i,2); int v3 = GETBIT(i,3); int v_tl = BITS3(v1,v3,v2); int v_tr = BITS3(v3,v2,v0); int v_br = BITS3(v2,v0,v1); int v_bl = BITS3(v0,v1,v3); if ( !GETBIT(poss_topleft, v_tl) || !GETBIT(poss_topright, v_tr) || !GETBIT(poss_bottomright, v_br) || !GETBIT(poss_bottomleft, v_bl)) { if (!result) { if (r == 1) { printf("\n"); print_qt_first(qt); printf(" impossible"); } else { printf("\n"); print_qt_second(qt); printf(" "); } result = true; } if (r == 1) printf(" %c%d%d%c", GETBIT(poss_bottomright, v_br) ? ' ' : '~', v0, v1, GETBIT(poss_bottomleft, v_bl) ? ' ' : '~'); else { printf(" %c%d%d%c", GETBIT(poss_topright, v_tr) ? ' ' : '_', v2, v3, GETBIT(poss_topleft, v_tl) ? ' ' : '_'); } } } } if (result) printf("\n"); return result; } class Relation { public: Relation() { clear(); } void clear() { for (int i = 0; i < 16; i++) { for (int j = 0; j < 16; j++) rel[i][j] = ' '; } } void calculate_closure() { // Floyds algorithm for calculating closure for (int j = 0; j < 16; j++) for (int i = 0; i < 16; i++) for (int k = 0; k < 16; k++) { if (rel[i][j] != ' ' && rel[j][k] != ' ' && rel[i][k] == ' ') rel[i][k] = 'x'; } } char rel[16][16]; }; class SingleDirection : public Relation { public: SingleDirection(int new_qt) : Relation(), qt(new_qt) { for (int i = 0; i < 16; i++) { group[i] = i; size[i] = 0; } } void analyze() { calculate_closure(); // Calculate groups FORALLTILE(i, qt) if (rel[i][i] != ' ') { FORALLTILE(j, qt) if (rel[i][j] != ' ' && rel[j][i] != ' ' && rel[j][j] != ' ') { group[i] = j; break; } } // Calculate size FORALLTILE(i, qt) FORALLTILE(j,qt) if (rel[i][j] != ' ' || i == j) size[i]++; } #define FORALLGROUP(I,X) FORALLTILE(I,X) if (group[I] == I) bool smallerRel(int i, int j) { if (size[i] >= size[j]) return false; FORALLTILE(k, qt) if (rel[i][k] != ' ' && rel[j][k] == ' ') return false; return true; } void analyze_groups() { FORALLGROUP(i,qt) { FORALLGROUP(j,qt) { bool smaller = false; if (rel[i][j] != ' ' && smallerRel(j,i)) { smaller = true; FORALLGROUP(k, qt) if (smallerRel(j,k) && smallerRel(k,i)) { smaller = false; break; } } before[i][j] = smaller ? '<' : ' '; } } nr_groups = 0; nr_start = 0; nr_end = 0; FORALLGROUP(i,qt) { nr_groups++; bool is_start = true; bool is_end = true; FORALLGROUP(j,qt) { if (before[j][i] == '<') is_start = false; if (before[i][j] == '<') is_end = false; } startgroup[i] = is_start; endgroup[i] = is_end; if (is_start) nr_start++; if (is_end) nr_end++; } FORALLTILE(i,qt) if (i != group[i]) { startgroup[i] = startgroup[group[i]]; endgroup[i] = endgroup[group[i]]; } } void analyze_groups_print() { FORALLGROUP(i,qt) { FORALLGROUP(j,qt) printf("%c", before[i][j]); printf(" %3d %3d %d%d\n", group[i], size[i], startgroup[i], endgroup[i]); } printf("groups %d start %d end %d\n", nr_groups, nr_start, nr_end); } int group[16]; int size[16]; char before[16][16]; int qt; bool startgroup[16]; bool endgroup[16]; int nr_groups; int nr_start; int nr_end; }; bool has_unused_pieces_in_square(long qt, SingleDirection& left_to_right, SingleDirection& up_to_down, char squares[][17]) { long qt_1 = 0; long qt_2 = 0; long qt_3 = 0; long qt_5 = 0; long qt_6 = 0; long qt_7 = 0; long qt_9 = 0; long qt_10 = 0; long qt_11 = 0; long top_bottom_allowed = ~0L; long left_right_allowed = ~0L; long top; long bottom; long left; long right; bool above_allowed[16][16]; bool before_allowed[16][16]; for (int i = 0; i < 16; i++) for (int j = 0; j < 16; j++) above_allowed[i][j] = before_allowed[i][j] = true; int passes; for(passes = 1;; passes++) { top = 0; bottom = 0; left = 0; right = 0; qt_1 = 0; qt_2 = 0; qt_3 = 0; qt_5 = 0; qt_6 = 0; qt_7 = 0; qt_9 = 0; qt_10 = 0; qt_11 = 0; bool left_found[16][16]; bool right_found[16][16]; bool above_found[16][16]; bool below_found[16][16]; for (int i = 0; i < 16; i++) for (int j = 0; j < 16; j++) left_found[i][j] = right_found[i][j] = above_found[i][j] = below_found[i][j] = false; FORALLTILE(v6, qt) { int val[17]; for (int k = 1; k <= 16; k++) squares[v6][k] = '?'; val[6] = GETBIT(v6, 0); val[7] = GETBIT(v6, 1); val[10] = GETBIT(v6, 2); val[11] = GETBIT(v6, 3); for (int j = 0; j < 4096; j++) { val[1] = GETBIT(j, 0); val[2] = GETBIT(j, 1); val[3] = GETBIT(j, 2); val[4] = GETBIT(j, 3); val[5] = GETBIT(j, 4); val[8] = GETBIT(j, 5); val[9] = GETBIT(j, 6); val[12] = GETBIT(j, 7); val[13] = GETBIT(j, 8); val[14] = GETBIT(j, 9); val[15] = GETBIT(j, 10); val[16] = GETBIT(j, 11); #define FOURBITS(A,B,C,D) ((A) | ((B) << 1) | ((C) << 2) | ((D) << 3)) #define SQUARE(N) FOURBITS(val[N], val[N+1], val[N+4], val[N+5]) int v1 = SQUARE(1); int v2 = SQUARE(2); int v3 = SQUARE(3); int v5 = SQUARE(5); int v7 = SQUARE(7); int v9 = SQUARE(9); int v10 = SQUARE(10); int v11 = SQUARE(11); if ( GETBIT(qt, v1) && GETBIT(qt, v2) && GETBIT(qt, v3) && GETBIT(qt, v5) && GETBIT(qt, v7) && GETBIT(qt, v9) && GETBIT(qt, v10) && GETBIT(qt, v11) && GETBIT(top_bottom_allowed, FOURBITS(val[1], val[2], val[3], val[4])) && GETBIT(top_bottom_allowed, FOURBITS(val[13], val[14], val[15], val[16])) && GETBIT(left_right_allowed, FOURBITS(val[1], val[5], val[9], val[13])) && GETBIT(left_right_allowed, FOURBITS(val[4], val[8], val[12], val[16])) && before_allowed[v1][v2] && before_allowed[v2][v3] && before_allowed[v5][v6] && before_allowed[v6][v7] && before_allowed[v9][v10] && before_allowed[v10][v11] && above_allowed[v1][v5] && above_allowed[v5][v9] && above_allowed[v2][v6] && above_allowed[v6][v10] && above_allowed[v3][v7] && above_allowed[v7][v11] ) { qt_1 |= BIT(v1); qt_2 |= BIT(v2); qt_3 |= BIT(v3); qt_5 |= BIT(v5); qt_6 |= BIT(v6); qt_7 |= BIT(v7); qt_9 |= BIT(v9); qt_10 |= BIT(v10); qt_11 |= BIT(v11); top |= BIT(FOURBITS(val[1], val[2], val[3], val[4])); bottom |= BIT(FOURBITS(val[13], val[14], val[15], val[16])); left |= BIT(FOURBITS(val[1], val[5], val[9], val[13])); right |= BIT(FOURBITS(val[4], val[8], val[12], val[16])); left_found[v5][v6] = true; right_found[v6][v7] = true; above_found[v2][v6] = true; below_found[v6][v10] = true; for (int k = 1; k <= 16; k++) if (squares[v6][k] != 'x') squares[v6][k] = val[k] ? (squares[v6][k] == '0' ? 'x' : '1') : (squares[v6][k] == '1' ? 'x' : '0'); } } } int qt_possible = qt_1 & qt_2 & qt_3 & qt_5 & qt_6 & qt_7 & qt_9 & qt_10 & qt_11; if (qt_possible != qt) { printf("\n"); print_qt_first(qt); printf(" impossible 3x3 "); if (passes > 1) printf("(implied) "); print_qt_first(qt & ~qt_possible); printf("\n"); print_qt_second(qt); printf(" "); if (passes > 1) printf(" "); print_qt_second(qt & ~qt_possible); printf("\n"); return true; } top_bottom_allowed = top & bottom; left_right_allowed = left & right; bool same = true; for (int i = 0; i < 16; i++) for (int j = 0; j < 16; j++) { if (before_allowed[i][j] && (!left_found[i][j] || !right_found[i][j])) { before_allowed[i][j] = false; same = false; } if (above_allowed[i][j] && (!above_found[i][j] || !below_found[i][j])) { above_allowed[i][j] = false; same = false; } } if (same && bottom == top && left == right) break; } FORALLTILE(i, qt) FORALLTILE(j, qt) { if (before_allowed[i][j]) left_to_right.rel[i][j] = 'X'; if (above_allowed[i][j]) up_to_down.rel[i][j] = 'X'; } return false; } #define FIELD_SIZE 10 #define FIELD_SIZE_M1 (FIELD_SIZE-1) #define FIELD_CENTER (FIELD_SIZE/2-1) struct Transl { Transl(int (&nqtf)[FIELD_SIZE_M1][FIELD_SIZE_M1], int njx, int nkx, int njy, int nky) : qtf(nqtf), jx(njx), kx(nkx), jy(njy), ky(nky) {} int (&qtf)[FIELD_SIZE_M1][FIELD_SIZE_M1]; int jx, kx, jy, ky; int operator()(int j, int k) { return qtf[FIELD_CENTER + jx * j + kx * k][FIELD_CENTER + jy * j + ky * k]; } }; bool analyze_triangle(Transl transl, char &horz_line, char &result, char &dia_line) { bool inside_filled = true; bool inside_empty = true; long inside_qt = 0; int inside_qt_nr = 0; for (int j = 0; j <= FIELD_CENTER; j++) { for (int k = 0; k <= FIELD_CENTER; k++) if (k < j) printf(" "); else { printf("%3d", transl(j, k)); if (j > 0 && j < k) { if (transl(j, k) == -1) inside_filled = false; else if ((inside_qt & BIT(transl(j,k))) == 0) { inside_empty = false; inside_qt_nr++; inside_qt |= BIT(transl(j,k)); } } } printf("\n"); } bool horz_infinite = false; long horz_line_qt = 0; { bool horz_line1 = true; bool horz_line2 = true; for (int k = 1; k <= FIELD_CENTER; k++) { if (transl(0,k) != -1) horz_line_qt |= BIT(transl(0,k)); if (k >= 3 && transl(0,k) != transl(0,k-1)) horz_line1 = false; if (k >= 3 && (transl(0,k) != transl(0,k-2) || transl(0,k) == -1)) horz_line2 = false; } horz_infinite = horz_line1 || horz_line2; } horz_line = GETBIT(horz_line_qt, transl(0,0)) ? 'L' : (horz_infinite && transl(0, FIELD_CENTER) != -1) ? 'l' : ' '; bool dia_infinite = false; long dia_line_qt = 0; { bool dia_line1 = true; bool dia_line2 = true; for (int j = 1; j <= FIELD_CENTER; j++) { if (transl(j,j) != -1) dia_line_qt |= BIT(transl(j,j)); if (j >= 3 && transl(j,j) != transl(j-1,j-1)) dia_line1 = false; if (j >= 3 && (transl(j,j) != transl(j-2,j-2) || transl(j,j) == -1)) dia_line2 = false; } dia_infinite = dia_line1 || dia_line2; } dia_line = GETBIT(dia_line_qt, transl(0,0)) ? 'L' : (dia_infinite && transl(FIELD_CENTER, FIELD_CENTER) != -1) ? 'l' : ' '; result = ' '; printf("\ntria: "); if (inside_empty) { printf("empty\n\n"); return true; } printf("inside:%d ", inside_qt); if (!horz_infinite) { printf("horz not infinite\n"); return false; } printf("horz:%d ", horz_line_qt); if (!dia_infinite) { printf("dia not infinite\n"); return false; } printf("dia:%d ", dia_line_qt); if (inside_filled) { if (inside_qt_nr == 1) { printf("inside one type: infinite\n"); result = 'f'; return true; } int k1, k2; for (k1 = 1; k1 < FIELD_CENTER; k1++) if ( transl(FIELD_CENTER, k1) != -1 && transl(FIELD_CENTER, k1) != transl(FIELD_CENTER-1, k1)) break; for (k2 = FIELD_CENTER-1; k2 > 0; k2--) if ( transl(FIELD_CENTER, k2) != -1 && transl(FIELD_CENTER, k2) != transl(FIELD_CENTER-1, k2-1)) break; if (k2 < k1) { printf("border filled\n"); result = 'f'; return true; } } //printf("0,0: %d, 2,1: %d, 1,2: %d ", transl(0,0), transl(2,1), transl(1,2)); if (transl(0,0) == transl(1,2)) { printf("1,2\n"); result = 'L'; return true; } printf("\n"); int diagonal = 0; int orthogonal = 0; int vertical = 0; for (int j = 0; j <= FIELD_CENTER; j++) { for (int k = 0; k <= FIELD_CENTER; k++) if (k < j) printf(" "); else { printf("%3d", transl(j, k)); if (j >= 1 && k >=1) { printf("%c", transl(j,k) == transl(j-1,k-1) ? 'd' : '-'); if (transl(j,k) == transl(j-1,k-1)) diagonal++; } else printf("."); if (j >= 1 && k < FIELD_CENTER) { printf("%c", transl(j,k) == transl(j-1,k+1) ? 'o' : '-'); if (transl(j,k) == transl(j-1,k+1)) orthogonal++; } else printf("."); if (j >= 1) { printf("%c", transl(j,k) == transl(j-1,k) ? 'v' : '-'); if (transl(j,k) == transl(j-1,k)) vertical++; } else printf("."); } printf("\n"); } printf("diagonal:%d orthogonal:%d vertical:%d\n\n", diagonal, orthogonal, vertical); return false; } void analyze_quadrant(Transl transl, char &uses1, char &uses2, char &uses3, char &uses4, char &uses5) { Transl transl2(transl.qtf, transl.kx, transl.jx, transl.ky, transl.jy); bool solved1 = analyze_triangle(transl, uses1, uses2, uses3); bool solved2 = analyze_triangle(transl2, uses5, uses4, uses3); if (solved1 && solved2) { //if (uses2 == 'f' && uses4 == 'f') // uses3 = 'f'; return; } for (int j = 0; j <= FIELD_CENTER; j++) { for (int k = 0; k <= FIELD_CENTER; k++) printf("%3d", transl(j, k)); printf("\n"); } printf("\n"); if (uses1 != ' ' && uses5 != ' ') { { int k1; for (k1 = 1; k1 < FIELD_CENTER; k1++) if (transl(FIELD_CENTER-k1, k1) == -1 || transl(FIELD_CENTER-k1, k1) != transl(FIELD_CENTER-k1+1, k1)) break; int k2; for (k2 = FIELD_CENTER-2; k2 >= 0; k2--) if (transl(FIELD_CENTER-k2, k2) == -1 || transl(FIELD_CENTER-k2, k2) != transl(FIELD_CENTER-k2, k2+1)) break; if (k1 > k2) { printf("quad: border filed: infinite\n"); uses2 = 'f'; uses3 = 'f'; uses4 = 'f'; return; } } } bool diagonal1 = true; bool diagonal2 = true; for (int j = 0; j <= FIELD_CENTER; j++) for (int k = 0; k <= FIELD_CENTER; k++) { if (transl(j,k) == -1 || (j < FIELD_CENTER && k < FIELD_CENTER && transl(j,k) != transl(j+1,k+1))) diagonal1 = false; if (transl(j,k) == -1 || (j < FIELD_CENTER && k < FIELD_CENTER && transl(j,k+1) != transl(j+1,k))) diagonal2 = false; } if (diagonal1) { printf("quad: diagonal1: infinite\n"); uses2 = 'f'; uses3 = 'f'; uses4 = 'f'; return; } if (diagonal2) { printf("quad: diagonal2: infinite\n"); uses2 = 'f'; uses3 = 'f'; uses4 = 'f'; return; } printf("quad unresolved\n"); } class ImpossibleSquare { public: char field[FIELD_SIZE][FIELD_SIZE]; int qtf[FIELD_SIZE_M1][FIELD_SIZE_M1]; bool completely_filled; long qt_found; // grids struct { int x, y; } grid_coords[4]; int nr_grid_coords; int grid_dim; int half_grid_dim; // quadrants char uses[16]; //bool lines[8]; //bool line; //int x, y; bool selected; void fill(int i, long qt, char squares[][17]) { int v = 1; for (int j = 0; j < FIELD_SIZE; j++) for (int k = 0; k < FIELD_SIZE; k++) if (3 <= j && j <= 6 && 3 <= k && k <= 6) field[j][k] = squares[i][v++]; else field[j][k] = 'x'; for (bool more = true; more; ) { more = false; for (int k = 0; k < FIELD_SIZE-1; k++) for (int l = 0; l < FIELD_SIZE-1; l++) { if (field[k][l] != 'x' && field[k][l+1] != 'x' && field[k+1][l] != 'x' && field[k+1][l+1] != 'x') { int i2 = FOURBITS(field[k][l] == '1', field[k][l+1] == '1', field[k+1][l] == '1', field[k+1][l+1] == '1'); if (GETBIT(qt, i2) == 0) { printf("try %c%c%c%c\n", field[k][l], field[k][l+1], field[k+1][l], field[k+1][l+1]); printf("hit %d, %d\n", k, l); for (int x = 0; x < 4; x++) printf("%d", GETBIT(i2, x)); printf("\n"); return; } int v = 1; for (int m = k-1; m <= k+2; m++) for (int n = l-1; n <= l+2; n++) { if (0 <= m && m < 10 && 0 <= n && n < FIELD_SIZE) if (squares[i2][v] != 'x') if (field[m][n] == 'x') { more = true; field[m][n] = squares[i2][v]; } else if (field[m][n] != squares[i2][v]) { printf("CONFLICT\n"); return; } v++; } } } // Try complete further if (!more) { for (int k = 0; k < FIELD_SIZE-1; k++) for (int l = 0; l < FIELD_SIZE-1; l++) if (field[k][l] == 'x' || field[k][l+1] == 'x' || field[k+1][l] == 'x' || field[k+1][l+1] == 'x') { int c = 0; int fit_m; FORALLTILE(m, qt) { if ( (field[k ][l ] == 'x' || (field[k ][l ] == '1') == GETBIT(m, 0)) && (field[k ][l+1] == 'x' || (field[k ][l+1] == '1') == GETBIT(m, 1)) && (field[k+1][l ] == 'x' || (field[k+1][l ] == '1') == GETBIT(m, 2)) && (field[k+1][l+1] == 'x' || (field[k+1][l+1] == '1') == GETBIT(m, 3))) { fit_m = m; c++; } } if (c == 0) { printf("CONFLICT\n"); return; } if (c == 1) { field[k ][l ] = GETBIT(fit_m, 0) ? '1' : '0'; field[k ][l+1] = GETBIT(fit_m, 1) ? '1' : '0'; field[k+1][l ] = GETBIT(fit_m, 2) ? '1' : '0'; field[k+1][l+1] = GETBIT(fit_m, 3) ? '1' : '0'; more = true; } } } } // Test if field is completely filled completely_filled = true; qt_found = 0; for (int j = 0; j < FIELD_SIZE-1; j++) for (int k = 0; k < FIELD_SIZE-1; k++) if (field[j][k] != 'x' && field[j][k+1] != 'x' && field[j+1][k] != 'x' && field[j+1][k+1] != 'x') { int i2 = FOURBITS(field[j][k] == '1', field[j][k+1] == '1', field[j+1][k] == '1', field[j+1][k+1] == '1'); qtf[j][k] = i2; qt_found |= BIT(i2); } else { qtf[j][k] = -1; completely_filled = false; } if (qtf[FIELD_CENTER][FIELD_CENTER] != i) { printf("ASSERT %d %d\n", qtf[FIELD_CENTER][FIELD_CENTER], i); return; } // Analyze field analyze_quadrant(Transl(qtf, -1, 0, 0, -1), uses[0], uses[1], uses[2], uses[3], uses[4]); analyze_quadrant(Transl(qtf, 0, -1, 1, 0), uses[4], uses[5], uses[6], uses[7], uses[8]); analyze_quadrant(Transl(qtf, 1, 0, 0, 1), uses[8], uses[9], uses[10], uses[11], uses[12]); analyze_quadrant(Transl(qtf, 0, 1, -1, 0), uses[12], uses[13], uses[14], uses[15], uses[0]); // Find grids grid_dim = 0; half_grid_dim = 0; /* { nr_grid_coords = 0; int min_dist = 10000; for (int j = 0; j < FIELD_SIZE-1; j++) for (int k = 0; k < FIELD_SIZE-1; k++) if ((j != FIELD_CENTER || k != FIELD_CENTER) && qtf[j][k] == i) { int x = j-FIELD_CENTER; int y = k-FIELD_CENTER; int dist = x*x + y*y; if (dist < min_dist) { min_dist = dist; nr_grid_coords = 1; grid_coords[0].x = x; grid_coords[0].y = y; } else if (dist == min_dist && nr_grid_coords < 4) { grid_coords[nr_grid_coords].x = x; grid_coords[nr_grid_coords].y = y; nr_grid_coords++; } } for (int j = 0; j < nr_grid_coords; j++) printf("(%d,%d) ", grid_coords[j].x, grid_coords[j].y); bool is_grid = true; grid_dim = 0; for (int j = 0; j < nr_grid_coords; j++) for (int k = 0; k < nr_grid_coords; k++) { if (qtf[FIELD_CENTER + grid_coords[j].x + grid_coords[k].x] [FIELD_CENTER + grid_coords[j].y + grid_coords[k].y] != i) is_grid = false; if ( j < k && grid_coords[j].x + grid_coords[k].x == 0 && grid_coords[j].y + grid_coords[k].y == 0) grid_dim++; } if (!is_grid) { printf("not a grid\n"); grid_dim = 0; } else { half_grid_dim = nr_grid_coords - grid_dim*2; printf("dim = %d, half_dim = %d\n", grid_dim, half_grid_dim); } } */ printf("%c%c%c%c%c\n", uses[2], uses[3], uses[4], uses[5], uses[6]); printf("%c\\ /%c\n", uses[1], uses[7]); printf("%c * %c\n", uses[0], uses[8]); printf("%c/ \\%c\n", uses[15], uses[9]); printf("%c%c%c%c%c\n\n", uses[14], uses[13], uses[12], uses[11], uses[10]); for (int j = 0; j < 16; j++) if (uses[j] == 'L') for (int k = j+1; k < j+8; k++) if (uses[k%16] == 'L') for (int l = j+1; l < k; l++) uses[l%16] = 'f'; for (int j = 0; j < 16; j++) if ((uses[j] == 'l' || uses[j] == 'L') && uses[(j+15)%16] == 'f' && uses[(j+1)%16] == 'f') uses[j] = 'f'; print(i, qt); printf("%c%c%c%c%c\n", uses[2], uses[3], uses[4], uses[5], uses[6]); printf("%c\\ /%c\n", uses[1], uses[7]); printf("%c * %c\n", uses[0], uses[8]); printf("%c/ \\%c\n", uses[15], uses[9]); printf("%c%c%c%c%c\n\n", uses[14], uses[13], uses[12], uses[11], uses[10]); } void print(int i, long qt) { for (int j = 0; j < FIELD_SIZE; j++) { for (int k = 0; k < FIELD_SIZE; k++) printf("%c", field[j][k]); if (j < 2) printf(" "); if (j == 0) print_qt_first(qt_found); if (j == 1) print_qt_second(qt_found); if (j < 2) printf(" "); if (j == 0) print_qt_first(qt & ~qt_found); if (j == 1) print_qt_second(qt & ~qt_found); printf("\n"); } printf("\n"); } bool analyze(int i, long qt, int &c_solved_squares, int &c_impossible_squares) { bool all_trias = true; for (int j = 0; j < 16; j++) if (uses[j] != 'f') all_trias = false; if (all_trias)// || (grid_dim == 2 && half_grid_dim == 0)) { if (qt_found == qt) { printf("\n"); print_qt_first(qt); printf(" found solution\n"); print_qt_second(qt); printf("\n"); c_solved_squares++; return true; } else { printf("\n"); print_qt_first(qt); printf(" strong component "); print_qt_first(qt_found); printf("\n"); print_qt_second(qt); printf(" "); print_qt_second(qt_found); printf("\n"); c_impossible_squares++; return true; } } return false; } }; bool inside(char a[], char b[]) { bool empty = true; for (int i = 0; i < 16; i++) if (a[i] != ' ' && a[(i+1)%16] != 'f') { empty = false; int j = i+1; while (a[j%16] == ' ') j++; if ( !(a[i%16] == 'f' || b[i%16] == 'f') && !(a[j%16] == 'f' || b[j%16] == 'f')) { bool inside = true; for (int k = j+1; k < i+16; k++) if (b[k%16] != ' ') inside = false; if (inside) return true; } } return empty; } bool impossible_squares(long qt, char squares[][17], int &c_solved_squares, int &c_impossible_squares) { ImpossibleSquare impossibleSquares[16]; FORALLTILE(i, qt) { impossibleSquares[i].fill(i, qt, squares); //FORALLTILE(i, qt) if (impossibleSquares[i].analyze(i, qt, c_solved_squares, c_impossible_squares)) return true; } FORALLTILE(i, qt) impossibleSquares[i].selected = true; FORALLTILE(i, qt) FORALLTILE(j, qt) if ( impossibleSquares[i].qt_found != impossibleSquares[j].qt_found && (impossibleSquares[i].qt_found & impossibleSquares[j].qt_found) == impossibleSquares[i].qt_found) { bool smaller = true; for (int k = 0; k < 16; k++) if (impossibleSquares[i].uses[k] != ' ' && impossibleSquares[j].uses[k] == ' ') smaller = false; if (!smaller) { //printf("%d not smaller %d\n", i, j); //impossibleSquares[i].print(i, qt); //impossibleSquares[j].print(j, qt); } else impossibleSquares[i].selected = false; } printf("rows\n"); FORALLTILE(i, qt) { printf("%2d: %c ", i, impossibleSquares[i].selected ? '*' : ' '); FORALLTILE(j, qt) printf("%c", GETBIT(impossibleSquares[i].qt_found, j) ? 'x' : ' '); printf(" "); for (int j = 0; j < 16; j++) printf("%c", impossibleSquares[i].uses[j]); printf("\n"); } FORALLTILE(i, qt) if (impossibleSquares[i].selected) FORALLTILE(j, qt) if (impossibleSquares[j].selected) { long i_qt_found = impossibleSquares[i].qt_found; long j_qt_found = impossibleSquares[j].qt_found; if ( i_qt_found != j_qt_found && (i_qt_found & j_qt_found) != i_qt_found && (i_qt_found & j_qt_found) != j_qt_found) { if ( !inside(impossibleSquares[i].uses, impossibleSquares[j].uses) && !inside(impossibleSquares[j].uses, impossibleSquares[i].uses)) { printf("%d - %d impossible %d %d\n", i, j, inside(impossibleSquares[i].uses, impossibleSquares[j].uses), inside(impossibleSquares[j].uses, impossibleSquares[i].uses)); impossibleSquares[i].print(i, qt); impossibleSquares[j].print(j, qt); printf("\n"); print_qt_first(qt); printf(" strong components "); print_qt_first(i_qt_found); printf(" "); print_qt_first(j_qt_found); printf("\n"); print_qt_second(qt); printf(" "); print_qt_second(i_qt_found); printf(" "); print_qt_second(j_qt_found); printf("\n"); c_impossible_squares++; return true; } } } return false; } bool overlapping_components(Relation& rel1, Relation& rel2, int qt, char* dir, SetOfQT& overlap) { bool result = false; bool processed[16]; for (int i = 0; i < 16; i++) processed[i] = false; FORALLTILE(i, qt) if (!processed[i]) { bool all = true; FORALLTILE(j, qt) if (rel1.rel[i][j] == ' ') all = false; else processed[j] = true; if (!all) { bool used[16]; for (int j = 0; j < 16; j++) used[j] = false; FORALLTILE(j, qt) if (rel1.rel[i][j] != ' ') { FORALLTILE(k, qt) if (rel2.rel[j][k] != ' ') used[k] = true; } bool all_used = true; FORALLTILE(j, qt) if (!used[j]) all_used = false; if (!all_used) { result = true; int value = 0; FORALLTILE(j,qt) if (used[j]) value |= BIT(j); overlap.add(value); } } } return result; } #define MAX_LENGTH 7 // 10 #define MAX_DEPTH 10 #define MAX_SOLUTIONS 10000 class PartialSolutions { public: PartialSolutions() : nr_sols(0), empty(true) {} void add(int qt) { empty = false; int j = 0; bool found = false; for (int i = 0; i < nr_sols; i++) { if ((sols[i] | qt) == sols[i]) // qt subset of sols[i] { found = true; sols[j++] = sols[i]; } else if ((sols[i] | qt) == qt) // sols[i] subset of qt ; // remove sols[i] else sols[j++] = sols[i]; } if (!found && j < 50) { sols[j++] = qt; } nr_sols = j; } void print_first_row(int qt) { if (empty) printf("empty"); for (int i = 0; i < nr_sols; i++) { if (i > 0) printf(" "); print_qt_first(qt & ~sols[i]); } } void print_second_row(int qt) { for (int i = 0; i < nr_sols; i++) { if (i > 0) printf(" "); print_qt_second(qt & ~sols[i]); } } private: bool empty; int sols[50]; int nr_sols; }; class SearchRepeating { protected: SearchRepeating(SingleDirection& direction, bool top_bottom, PartialSolutions &partial_solutions) : _direction(direction), _top_bottom(top_bottom), _print(false), _partial_solutions(partial_solutions) {} void setPrint() { _print = true; } void insert_solution(int from, int to, int used) { int i; for (i = 0; i < _nr_solutions; i++) if (_solutions[i].from == from && _solutions[i].to == to && _solutions[i].qt_used == used) { break; } if (i == _nr_solutions && _nr_solutions < MAX_SOLUTIONS) { _solutions[i].from = from; _solutions[i].to = to; _solutions[i].qt_used = used; _nr_solutions++; } } bool find_path_in_solution() { if (_nr_solutions == MAX_SOLUTIONS) { //printf("length %d more than %d solutions\n", _length, _nr_solutions); } else { // Remove solutions that have no previous or next bool go; do { go = false; for (int i = 0; i < _nr_solutions; i++) { _solutions[i].prev = false; _solutions[i].next = false; } for (int i = 0; i < _nr_solutions; i++) for (int j = 0; j < _nr_solutions; j++) if (_solutions[i].to == _solutions[j].from) { _solutions[i].next = true; _solutions[j].prev = true; } int i; int j; for (i = 0, j = 0; i < _nr_solutions; i++) { if (_solutions[i].next && _solutions[i].prev) { _solutions[j].from = _solutions[i].from; _solutions[j].to = _solutions[i].to; _solutions[j].qt_used = _solutions[i].qt_used; j++; } else go = true; } _nr_solutions = j; } while (go && _nr_solutions > 0); if (_nr_solutions > 0) { // Calculate reachable states bool all_found = false; for (int i = 0; i < _nr_solutions; i++) _solutions[i].qt_cum = _solutions[i].qt_used; do { go = false; for (int i = 0; i < _nr_solutions; i++) for (int j = 0; j < _nr_solutions; j++) if (_solutions[i].to == _solutions[j].from) { int new_qt_cum = _solutions[i].qt_cum | _solutions[j].qt_cum; if (new_qt_cum != _solutions[j].qt_cum) { _solutions[j].qt_cum = new_qt_cum; go = true; } if (new_qt_cum == _direction.qt) all_found = true; } } while (go); if (all_found) { // Mark all paths leading to states reaching all tiles for (int i = 0; i < _nr_solutions; i++) _solutions[i].good = _solutions[i].qt_cum == _direction.qt; do { go = false; for (int i = 0; i < _nr_solutions; i++) if (!_solutions[i].good) for (int j = 0; j < _nr_solutions; j++) if ( _solutions[i].to == _solutions[j].from && _solutions[j].good) { _solutions[i].good = true; go = true; break; } } while (go); for (int i = 0; i < _size; i++) { if (search_down_path(0, i, 0)) return true; } //printf("Problem: %d not found\n", _length); } } } return false; } virtual void print_state(int state) { } virtual void print_found() { } bool search_down_path(int depth, int from, int qt_cum) { for (int i = 0; i < _nr_solutions; i++) if (_solutions[i].from == from && _solutions[i].good) { int to = _solutions[i].to; int qt_used = _solutions[i].qt_used; int new_qt_cum = qt_cum | qt_used; if (new_qt_cum == _direction.qt) { printf("\n"); print_qt_first(_direction.qt); print_found(); print_qt_second(_direction.qt); printf("\n"); if (_print) { printf("--\n"); for (int j = 0; j < depth; j++) { print_state(_steps[j].from); print_qt(_steps[j].qt); } print_state(from); print_qt(qt_used); print_state(to); printf("\n"); printf("--\n"); } return true; } _partial_solutions.add(new_qt_cum); if (depth < MAX_DEPTH) { _steps[depth].from = from; _steps[depth].to = to; _steps[depth].qt = qt_used; _steps[depth].qt_cum = new_qt_cum; // Check for cycle bool cycle = false; for (int i = 0; i < depth; i++) if (_steps[i].to == to && _steps[i].qt_cum == new_qt_cum) { cycle = true; break; } if (!cycle) { if (search_down_path(depth+1, to, new_qt_cum)) return true; } } } return false; } SingleDirection& _direction; bool _top_bottom; bool _print; PartialSolutions &_partial_solutions; struct { long from; long to; int qt_used; bool prev; bool next; int qt_cum; bool good; } _solutions[MAX_SOLUTIONS]; int _nr_solutions; int _length; int _size; struct { int from; int to; int qt; int qt_cum; } _steps[MAX_DEPTH+1]; }; class SearchRepeatingRectangle : public SearchRepeating { public: SearchRepeatingRectangle(SingleDirection& direction, bool top_bottom, PartialSolutions &partial_solutions) : SearchRepeating(direction, top_bottom, partial_solutions) {} bool search() { setPrint(); for (_length = 1; _length <= MAX_LENGTH; _length++) { _size = 1 << _length; _nr_solutions = 0; fflush(stdout); FORALLTILE(i,_direction.qt) find_solution(0, i); if (find_path_in_solution()) return true; } return false; } private: void find_solution(int l, int from) { if (l == _length) { if (from == _path[0]) { // found solution int from = 0; int to = 0; int used = 0; for (int i = 0; i < _length; i++) { used |= BIT(_path[i]); if (_top_bottom) { if (GETBIT(_path[i], 0)) from |= BIT(i); if (GETBIT(_path[i], 2)) to |= BIT(i); } else { if (GETBIT(_path[i], 0)) from |= BIT(i); if (GETBIT(_path[i], 1)) to |= BIT(i); } } from = normalize(from); to = normalize(to); insert_solution(from, to, used); } return; } _path[l++] = from; FORALLTILE(i,_direction.qt) if (_direction.rel[from][i] == 'X') find_solution(l, i); } int normalize(int v) { int r = v; for (int i = 0; i < _length; i++) { v = (v >> 1) | ((v&1) << (_length - 1)); if (v < r) r = v; } return r; } virtual void print_state(int state) { printf("("); for (int k = 0; k < _length; k++) printf("%d", GETBIT(state, k)); printf(")*"); } virtual void print_found() { printf(" found %s cyclic rectangle\n", _top_bottom ? "top-bottom" : "left-right"); } int _path[MAX_LENGTH]; }; class SearchRepeatingLines : public SearchRepeating { public: SearchRepeatingLines(SingleDirection& direction, bool top_bottom, PartialSolutions &partial_solutions) : SearchRepeating(direction, top_bottom, partial_solutions) {} bool search() { setPrint(); for (_length = 2; _length <= MAX_LENGTH; _length++) { _size = 1 << _length; for (int se_length = 2; se_length <= _length; se_length++) for (_start_length = 1, _end_length = se_length - _start_length; _end_length >= 1; _start_length++, _end_length--) { _end_pos = _length - _end_length; fflush(stdout); _nr_solutions = 0; FORALLTILE(i,_direction.qt) find_solution(0, i); if (find_path_in_solution()) return true; } } return false; } private: void find_solution(int l, int from) { bool trace = false; bool trace_n = false; if (trace_n) { printf("%*.*sfind_solution(%d, %d) ", l*2, l*2, "", l, from); for (int i = 0; i < l; i++) printf("%d%d%d%d%s ", GETBIT(_path[i], 0), GETBIT(_path[i], 1), GETBIT(_path[i], 2), GETBIT(_path[i], 3), _direction.startgroup[_path[i]] ? "s" : _direction.endgroup[_path[i]] ? "e" : ""); printf("f: %d%d%d%d%s |", GETBIT(from, 0), GETBIT(from, 1), GETBIT(from, 2), GETBIT(from, 3), _direction.startgroup[from] ? "s" : _direction.endgroup[from] ? "e" : ""); } if (l > _length+1) { if (trace_n) printf("l > _length\n"); return; } if (l == _start_length && _path[0] != from) { if (trace_n) printf("l == _start_length && _path[0] != from\n"); return; } if (l > _start_length + _end_length && from == _path[l - _end_length]) { // Found some solution int fromline[MAX_LENGTH]; int toline[MAX_LENGTH]; int used = 0; if (trace) printf("x %d %d-%d-%d:", _length, _start_length, _length - _start_length - _end_length, _end_length); for (int i = 0; i < l; i++) { used |= BIT(_path[i]); if (_top_bottom) { fromline[i] = GETBIT(_path[i], 1); toline[i] = GETBIT(_path[i], 3); } else { fromline[i] = GETBIT(_path[i], 2); toline[i] = GETBIT(_path[i], 3); } if (trace) printf(" %d%d%d%d%s", GETBIT(_path[i], 0), GETBIT(_path[i], 1), GETBIT(_path[i], 2), GETBIT(_path[i], 3), _direction.startgroup[_path[i]] ? "s" : _direction.endgroup[_path[i]] ? "e" : ""); } if (trace) printf(" : %d\n", used); int from = normalize(fromline, l-1); int to = normalize(toline, l-1); insert_solution(from, to, used); } //else??? { if (trace_n) printf("\n"); _path[l++] = from; FORALLTILE(i,_direction.qt) if (_direction.rel[from][i] == 'X') find_solution(l, i); } } int normalize(int line[], int length) { bool trace = false; bool trace_n = false; if (trace) { printf("%d: ", length); for (int i = 0; i < length; i++) { if (i == _start_length || i == length - _end_length) printf("*"); printf("%d", line[i]); } printf(" -> "); } int s = _start_length; int start = 0; for (int i = 0; i < _start_length; i++) if (line[i]) start |= BIT(i); int start_length; { int v = start; int f = 0; for (int i = 1; i <= _start_length; i++) { v = (v >> 1) | ((v&1) << (_start_length - 1)); if (v < start) { start = v; f = 1; s = i; if (trace_n) { printf("s:%d ", s); for (int l = 0; l < _start_length; l++) printf("%d", GETBIT(v, l)); printf(" "); } } else if (v == start) { s = i; if (trace_n) { printf("s:%d ", s); for (int l = 0; l < _start_length; l++) printf("%d", GETBIT(v, l)); printf(" "); } f++; } } start_length = _start_length / f; start &= (1 << start_length) - 1; } int e = length - _end_length; int end = 0; for (int i = 0; i < _end_length; i++) if (line[e+i]) end |= BIT(i); int end_length; { int v = end; int f = 1; for (int i = 1; i < _end_length; i++) { v = (v >> 1) | ((v&1) << (_end_length - 1)); if (v < end) { end = v; f = 1; e = length - _end_length + i; } else if (v == end) f++; } end_length = _end_length / f; end &= (1 << end_length) - 1; } if (trace) { for (int i = 0; i < start_length; i++) printf("%d", GETBIT(start, i)); printf("|"); for (int i = s; i < e; i++) printf("%d", line[i]); printf("|"); for (int i = 0; i < end_length; i++) printf("%d", GETBIT(end, i)); printf(" -> %d:%d", s, e); } int best_l = 100; int best_v; #define LINEBIT(X) \ ( (X) < s ? GETBIT(start, ((X) - s + start_length*10) % start_length) \ : (X) >= e ? GETBIT(end, ((X) - e) % end_length) \ : line[X] ) bool go = true; int a_s = s; for (; a_s <= e; a_s += start_length) { if (trace_n) printf(" a_s=%d", a_s); // process a_s to e for (int a_e = e, a2_s = a_s; a_e >= a_s - start_length; ) { if (trace_n) printf(" a_e=%d", a_e); while (a_e < a2_s) a2_s -= start_length; // check a_e int new_l = a_e - a2_s; int new_v = 0; for (int j = 0; j < new_l; j++) if (LINEBIT(a_s + j)) new_v |= BIT(j); if (trace_n) { printf(" %d:%d=", a2_s, a_e); for (int j = 0; j < new_l; j++) printf("%d", GETBIT(new_v, j)); } if (new_l < best_l || (new_l == best_l && new_v < best_v)) { best_l = new_l; best_v = new_v; } if (best_l == 0) break; // previous a_e -= end_length; int a_end = 0; for (int j = 0; j < end_length; j++) if (LINEBIT(a_e + j)) a_end |= BIT(j); if (a_end != end) { if (trace_n) printf(" e:%d!=%d", a_end, end); break; } } if (best_l == 0) break; if (a_s + start_length > e) break; // next int a_start = 0; for (int i = 0; i < start_length; i++) if (line[a_s + i]) a_start |= BIT(i); if (a_start != start) { if (trace_n) printf(" s:%d!=%d", a_start, start); go = false; break; } } if (go && best_l > 0) { int a_e = e; for (int i = 0; i < 10 /* just some number */; i++) { if (trace_n) printf(" i=%d %d:%d->", i, a_s, a_e); while (a_e < a_s) a_e += end_length; int new_l = a_e - a_s; int new_v = 0; for (int j = 0; j < new_l; j++) if (LINEBIT(a_s + j)) new_v |= BIT(j); if (trace_n) { printf("%d:%d=", a_s, a_e); for (int j = 0; j < new_l; j++) printf("%d", GETBIT(new_v, j)); } if (new_l < best_l || (new_l == best_l && new_v < best_v)) { best_l = new_l; best_v = new_v; } if (best_l == 0) break; int a_start = 0; for (int j = 0; j < start_length; j++) if (LINEBIT(a_s + j)) a_start |= BIT(j); if (trace_n) { printf(" a_s="); for (int j = 0; j < start_length; j++) printf("%d", GETBIT(a_start, j)); printf(" %d-%d", a_start, start); } if (a_start != start) break; a_s += start_length; } } if (best_l == 100) { //printf(" ERROR\n"); return 0; } int t = 0; int r = 0; if (trace) printf(" -> "); for (int i = 0; i < _start_length; i++, t++) { if (GETBIT(start, i % start_length)) r |= BIT(t); if (trace && i < start_length) printf("%d", GETBIT(start, i % start_length)); } if (trace) printf("|"); for (int i = 0; i < best_l; i++, t++) { if (GETBIT(best_v, i)) r |= BIT(t); if (trace) printf("%d", GETBIT(best_v, i)); } if (trace) printf("|"); for (int i = 0; i < _end_length; i++, t++) { if (GETBIT(end, i % end_length)) r |= BIT(t); if (trace && i < end_length) printf("%d", GETBIT(end, i)); } r |= BIT(t); if (trace) printf(" %d\n", r); return r; } virtual void print_state(int state) { int l = 0; for (int i = 0; i < 30; i++) if (GETBIT(state, i)) l = i; printf("("); for (int k = 0; k < l; k++) { if (k == _start_length) printf(")*"); if (k == l - _end_length) printf("("); printf("%d", GETBIT(state, k)); } printf(")*"); } virtual void print_found() { printf(" found %s cyclic lines\n", _top_bottom ? "top-bottom" : "left-right"); } int _path[MAX_LENGTH+2]; int _start_length; int _end_length; int _end_pos; }; class Results { public: Results() : _nr_results(0) {} void setSolved(long qt) { _results[_add(qt)].state = 's'; } void setUnsolved(long qt) { _results[_add(qt)].state = 'u'; } bool solved(long qt) { return _results[_add(qt)].state == 's'; } bool unsolved(long qt) { return _results[_add(qt)].state == 'u'; } private: int _add(long qt) { for (int i = 0; i < _nr_results; i++) if (_results[i].qt == qt) return i; _results[_nr_results].qt = qt; _results[_nr_results].state = ' '; return _nr_results++; } int _nr_results; struct { long qt; char state; } _results[6000]; }; int main(int argc, char *argv[]) { fill_permvectors(); Results results; FILE *f = fopen("results.txt", "rt"); if (f != 0) { char line1[1000]; char line2[1000]; fgets(line1, 999, f); while (fgets(line2, 999, f)) { int i = 0; long qt = 0; for (;; i += 3) { if ( line1[i] == ' ' && line2[i] == ' ' && (line1[i+1] == '0' || line1[i+1] == '1') && (line2[i+1] == '0' || line2[i+1] == '1') && (line1[i+2] == '0' || line1[i+2] == '1') && (line2[i+2] == '0' || line2[i+2] == '1')) { int b0 = line1[i+1] == '1'; int b1 = line1[i+2] == '1'; int b2 = line2[i+1] == '1'; int b3 = line2[i+2] == '1'; qt |= BIT((b0) | (b1 << 1) | (b2 << 2) | (b3 << 3)); } else break; } if (i > 0 && (line2[i] == '\n' || line2[i] == ' ') && line1[i] == ' ') { bool unsolved = strncmp(line1+i+1, "unsolved", 8) == 0; if (unsolved) results.setUnsolved(qt); else results.setSolved(qt); } strcpy(line1, line2); } fclose(f); } int c_not_minimal = 0; int c_has_unused_pieces = 0; int c_has_unused_pieces_in_cross = 0; int c_has_unused_pieces_in_square = 0; int c_several_components = 0; int c_overlap = 0; int c_cyclic_rectangle = 0; int c_cyclic_lines = 0; int c_solved_squares = 0; int c_impossible_squares = 0; int c_unsolved = 0; int c_unsolved_2dir = 0; for (long qt = 1; qt < (1L << 16) /*&& qt < 1000*/; qt++) //long qt = 38083; { if (!is_minimal(qt)) { c_not_minimal++; } else if (results.solved(qt)) { //printf("solved %d\n", qt); // already solved } else if (has_unused_pieces(qt)) { c_has_unused_pieces++; } else if (has_unused_pieces_in_cross(qt)) { c_has_unused_pieces_in_cross++; } else { SingleDirection left_to_right(qt); SingleDirection up_to_down(qt); char squares[16][17]; if (has_unused_pieces_in_square(qt, left_to_right, up_to_down, squares)) { c_has_unused_pieces_in_square++; } else { // 2115 Relation related; Relation horz_related; Relation vert_related; FORALLTILE(i,qt) FORALLTILE(j,qt) { if (left_to_right.rel[i][j] == 'X') { related.rel[i][j] = 'X'; related.rel[j][i] = 'X'; horz_related.rel[i][j] = 'X'; horz_related.rel[j][i] = 'X'; } if (up_to_down.rel[i][j] == 'X') { related.rel[i][j] = 'X'; related.rel[j][i] = 'X'; vert_related.rel[i][j] = 'X'; vert_related.rel[j][i] = 'X'; } } related.calculate_closure(); SetOfQT components; FORALLTILE(i,qt) { int value = 0; FORALLTILE(j,qt) if (related.rel[i][j] != ' ') value |= BIT(j); components.add(value); } if (components.nr > 1) { c_several_components++; printf("\n"); print_qt_first(qt); printf(" %d component ", components.nr); components.print_first(); printf("\n"); print_qt_second(qt); printf(" "); components.print_second(); printf("\n"); } else { // 2097 horz_related.calculate_closure(); vert_related.calculate_closure(); SetOfQT overlap; bool horz_over_comp = overlapping_components(horz_related, vert_related, qt, "x", overlap); bool vert_over_comp = overlapping_components(vert_related, horz_related, qt, "y", overlap); if (horz_over_comp || vert_over_comp) { c_overlap++; printf("\n"); print_qt_first(qt); printf(" %d overlap ", overlap.nr); overlap.print_first(); printf("\n"); print_qt_second(qt); printf(" "); overlap.print_second(); printf("\n"); } else { // 2085 left_to_right.analyze(); up_to_down.analyze(); left_to_right.analyze_groups(); up_to_down.analyze_groups(); PartialSolutions partial_solutions; bool found_cyclic = false; if (results.unsolved(qt) && 0) { printf("unsolved %d\n", qt); } else { if (left_to_right.nr_groups == 1) { SearchRepeatingRectangle searchRepeatingRectangle1(left_to_right, true, partial_solutions); if (searchRepeatingRectangle1.search()) { c_cyclic_rectangle++; found_cyclic = true; } } if (up_to_down.nr_groups == 1 && !found_cyclic) { SearchRepeatingRectangle searchRepeatingRectangle2(up_to_down, false, partial_solutions); if (searchRepeatingRectangle2.search()) { c_cyclic_rectangle++; found_cyclic = true; } } if (!found_cyclic) { SearchRepeatingLines searchRepeatingLines(left_to_right, true, partial_solutions); if (searchRepeatingLines.search()) { c_cyclic_lines++; found_cyclic = true; } } if (!found_cyclic) { SearchRepeatingLines searchRepeatingLines(up_to_down, false, partial_solutions); if (searchRepeatingLines.search()) { c_cyclic_lines++; found_cyclic = true; } } } if (!found_cyclic) { if (!impossible_squares(qt, squares, c_solved_squares, c_impossible_squares)) { c_unsolved++; if (left_to_right.nr_groups > 1 && up_to_down.nr_groups > 1) c_unsolved_2dir++; printf("\n"); print_qt_first(qt); printf(" unsolved "); partial_solutions.print_first_row(qt); printf("\n"); print_qt_second(qt); printf(" "); partial_solutions.print_second_row(qt); printf("\n\n"); printf("%d\n", qt); FORALLTILE(i,qt) { FORALLTILE(j,qt) printf("%c", left_to_right.rel[i][j]); printf(" %3d %3d ", left_to_right.group[i], left_to_right.size[i]); FORALLTILE(j,qt) printf("%c", up_to_down.rel[i][j]); printf("\n"); } printf("\n"); left_to_right.analyze_groups_print(); up_to_down.analyze_groups_print(); } } } } } } } long left = (1L << 16) - 1; left -= c_not_minimal; printf("Not minimal: %d (left %d)\n", c_not_minimal, left); left -= c_has_unused_pieces; printf("Has unused pieces: %d (left %d)\n", c_has_unused_pieces, left); left -= c_has_unused_pieces_in_cross; printf("Has unused pieces in cross: %d (left %d)\n", c_has_unused_pieces_in_cross, left); left -= c_has_unused_pieces_in_square; printf("Has unused pieces in square: %d (left %d)\n", c_has_unused_pieces_in_square, left); left -= c_several_components; printf("Has components : %d (left %d)\n", c_several_components, left); left -= c_overlap; printf("Has overlap : %d (left %d)\n", c_overlap, left); left -= c_cyclic_rectangle; printf("Found cyclic rectangle : %d (left %d)\n", c_cyclic_rectangle, left); left -= c_cyclic_lines; printf("Found cyclic lines : %d (left %d)\n", c_cyclic_lines, left); left -= c_solved_squares; printf("Found solved squares : %d (left %d)\n", c_solved_squares, left); left -= c_impossible_squares; printf("Found impossible squares : %d (left %d)\n", c_impossible_squares, left); printf("Unsolved : %d\n", c_unsolved); printf(" complex : %d\n", c_unsolved_2dir); return 0; }