/* Wang tiles for Street Tilings Copyright (C) 2016 Frans Faase This program is used to analyze street tiling with Wang tiles. This program is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation; either version 2 of the License, or (at your option) any later version. This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details. You should have received a copy of the GNU General Public License along with this program; if not, write to the Free Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. GNU General Public License: http://www.iwriteiam.nl/GNU.txt Details: http://www.iwriteiam.nl/D1606.html#5 */ #include #include #include "insertonlymap.h" // http://www.iwriteiam.nl/insertonlymap3_cpp.txt int value(int w, int h) { return w + 3*h - 4; } int inverse(int x) { return 3*(x%3) + x/3; } bool st[9][9][9][9]; int st3[9][9][9]; struct { int top; int left; int right; int bottom; } stc[9][9]; bool debug_init = true; class DoubleLinesOutput { public: DoubleLinesOutput() : col(0), enable(false) {} void setEnable(bool v) { enable = v; } void add(int i1, int i2, int i3, int i4) { if (!enable) return; line1[col] = ' '; line2[col] = ' '; col++; line1[col] = i1+'A'; line1[col+1] = i2+'A'; line2[col] = i3+'A'; line2[col+1] = i4+'A'; col += 2; if (col > 64) { line1[col] = '\0'; line2[col] = '\0'; printf("%s\n%s\n\n", line1, line2); col = 0; } } void flush() { if (!enable) return; if (col > 0) { line1[col] = '\0'; line2[col] = '\0'; printf("%s\n%s\n", line1, line2); col = 0; } printf("\n"); } private: bool enable; int col; char line1[100]; char line2[100]; }; void initialize_st(int i1, int i2, int i3, int i4, DoubleLinesOutput &doubleLinesOutput) { doubleLinesOutput.add(i1, i2, i3, i4); st[i1][i2][i3][i4] = true; stc[i1][i2].top++; stc[i1][i3].left++; stc[i2][i4].right++; stc[i3][i4].bottom++; } void remove_st(int i1, int i2, int i3, int i4) { if (st[i1][i2][i3][i4]) { st[i1][i2][i3][i4] = false; stc[i1][i2].top--; stc[i1][i3].left--; stc[i2][i4].right--; stc[i3][i4].bottom--; } } struct { char tl, tr, bl, br; } squares[100]; int nr_squares = 0; class SquaresIterator { public: SquaresIterator() : _i(0) {} bool more() { return _i < nr_squares; } void next() { _i++; } char tl() { return squares[_i].tl; } char tr() { return squares[_i].tr; } char bl() { return squares[_i].bl; } char br() { return squares[_i].br; } private: int _i; }; struct Squares3 { char tl, tr, bl; bool br[9]; void init() { for (int i = 0; i < 9; i++) br[i] = false; } } squares3[100]; int nr_squares3 = 0; class Squares3Iterator { public: Squares3Iterator() : _i(0) {} bool more() { return _i < nr_squares3; } void next() { _i++; } char tl() { return squares3[_i].tl; } char tr() { return squares3[_i].tr; } char bl() { return squares3[_i].bl; } class brIterator { public: brIterator(const Squares3Iterator& it) : _i(it._i), _j(0) { while (_j < 9 && !squares3[_i].br[_j]) _j++; } bool more() { return _j < 9; } bool next() { _j++; while (_j < 9 && !squares3[_i].br[_j]) _j++; } int val() { return _j; } private: int _i; int _j; }; private: public: // for older gcc compiler int _i; }; int m[20][20]; char seq[40]; class Seq { public: Seq(char *n_seq) { strcpy(seq, n_seq); } char seq[40]; int compare(const Seq& rhs) const { return strcmp(seq, rhs.seq); } }; class VoidClass { public: VoidClass(const Seq& key) {} }; InsertOnlyMap impossibleSeq; bool check(int n, int x, int y) { int i1 = m[x][y]; int i2 = m[x+1][y]; int i3 = m[x][y+1]; for (int i4 = 0; i4 < 9; i4++) if (st[i1][i2][i3][i4]) { m[x+1][y+1] = i4; if (y == n-1) { if (x == n-1) return true; else if (check(n, x+1, n-1 - (x+1))) return true; } else if (check(n, x, y+1)) return true; } return false; } void check_count(int n, int x, int y, int &count) { int i1 = m[x][y]; int i2 = m[x+1][y]; int i3 = m[x][y+1]; for (int i4 = 0; i4 < 9; i4++) if (st[i1][i2][i3][i4]) { m[x+1][y+1] = i4; if (y == n-1) { if (x == n-1) { printf("A%c", m[0][n]+'A'); for (int i = 1; i <= n; i++) printf("%c%c", m[i][n-i+1]+'A', m[i][n-i]+'A'); printf("A"); for (int i = 0; i <= n; i++) printf(" %d", st3[m[i][n-i]][i==n?0:m[i+1][n-i]][i==0?0:m[i][n-i+1]]); printf("\n"); count++; } else check_count(n, x+1, n-1 - (x+1), count); } else check_count(n, x, y+1, count); } } int nr_impossible; int col; bool explore(int n, int x, int y, int sn) { if (x == 0) { if (y == 0) { if (!check(n, 0, n-1)) { if (col + sn >= 66) { printf("\n"); col = 0; } printf(" %s", seq); col += sn+1; impossibleSeq.findOrCreate(Seq(seq)); nr_impossible++; } if (strcmp(seq, "DAAHIFAAB") == 0) { printf("\nCheck DAAHIFAAB\n"); for (int i = 0; i <= n; i++) { for (int j = 0; j <= n; j++) printf("%c", m[j][i]+'A'); printf("\n"); } int count = 0; check_count(n, 0, n-1, count); printf("\nNumber solutions for DAAHIFAAB = %d\n\n", count); } } else { y--; x = n-1 - y; int i3 = m[x][y+1]; for (int i1 = 0; i1 < 9; i1++) for (int i2 = 0; i2 < 9; i2++) if (st3[i1][i2][i3] > 0) { m[x][y] = i1; seq[sn] = i1 + 'A'; m[x+1][y] = i2; seq[sn+1] = i2 + 'A'; seq[sn+2] = '\0'; bool impossible = false; for (int i = sn-3; i >= 0; i -= 2) if (impossibleSeq.contains(&seq[i])) { impossible = true; break; } if (!impossible) explore(n, x, y, sn+2); } } return true; } else { x--; int i2 = m[x+1][y]; int i3 = m[x][y+1]; int i4 = m[x+1][y+1]; for (int i1 = 0; i1 < 9; i1++) if (st[i1][i2][i3][i4]) { m[x][y] = i1; if (explore(n, x, y, sn)) return true; } return false; } } void impossible_sequences_from_corner() { for (int n = 2; n < 7; n++) { printf("\n\nn = %d\n", n); nr_impossible = 0; col = 0; for (int i1 = 0; i1 < 9; i1++) for (int i2 = 0; i2 < 9; i2++) for (int i3 = 0; i3 < 9; i3++) if (st3[i1][i2][i3] > 0) { m[0][n] = i3; seq[0] = i3 + 'A'; m[0][n-1] = i1; seq[1] = i1 + 'A'; m[1][n-1] = i2; seq[2] = i2 + 'A'; explore(n, 0, n-1, 3); } if (nr_impossible == 0) printf("No impossible sequences\n"); } } class CountFromTo { public: CountFromTo(const Seq& key) : from(0), to(0), count(0) {} long from; long to; long count; }; InsertOnlyMap possibleSeq[20]; bool seqIsPossible(char *seq, int l) { if (st3[seq[l-2]-'A'][seq[l-1]-'A'][seq[l-3]-'A'] == 0) { return false; } for (int i = l-5; i >= 0; i -= 2) if (impossibleSeq.contains(&seq[i])) return false; return true; } void explore2(int i, int n, const char *oldSeq, char *newSeq, CountFromTo &from) { int p = i * 2; if (i == n) { for (int i4 = 0; i4 < 3; i4++) { newSeq[p+2] = i4 + 'A'; newSeq[p+3] = '\0'; if (seqIsPossible(newSeq, p+3)) { CountFromTo *to = possibleSeq[n].findOrCreate(Seq(newSeq)); from.to++; to->from++; to->count += from.count; } } } else { for (int i4 = 0; i4 < 9; i4++) if (st[oldSeq[p+1]-'A'][oldSeq[p+2]-'A'][oldSeq[p]-'A'][i4]) { newSeq[p+2] = i4 + 'A'; newSeq[p+3] = '\0'; if (seqIsPossible(newSeq, p+3)) { newSeq[p+3] = oldSeq[p+2]; newSeq[p+4] = '\0'; explore2(i+1, n, oldSeq, newSeq, from); } } } } void check_inverse_are_equal(int n) { for (InsertOnlyMap::iterator it(possibleSeq[n]); it.more(); it.next()) { const char *seq = it.key().seq; char revSeq[30]; int len = strlen(seq); for (int i = 0; i < len; i++) revSeq[len-i-1] = inverse(seq[i]-'A')+'A'; revSeq[len] = '\0'; CountFromTo *rev = possibleSeq[n].findOrCreate(Seq(revSeq)); if (it.value().from != rev->from || it.value().count != rev->count) printf("Reverse has different counts: %d %d and %d %d\n", it.value().from, it.value().count, rev->from, rev->count); } } void find_possible_from_corner() { for (int i3 = 0; i3 <=3; i3 += 3) for (int i2 = 0; i2 <= 1; i2++) if (st3[0][i2][i3] > 0) { char seq[4]; seq[0] = i3 + 'A'; seq[1] = 'A'; seq[2] = i2 + 'A'; seq[3] = '\0'; CountFromTo* count = possibleSeq[0].findOrCreate(Seq(seq)); count->count = 1; } check_inverse_are_equal(0); printf("\n\n"); int till_n = 10; for (int n = 1; n < till_n; n++) { printf("n = %d\n", n); for (InsertOnlyMap::iterator it(possibleSeq[n-1]); it.more(); it.next()) { const char *oldSeq = it.key().seq; char newSeq[30]; for (int i1 = 0; i1 < 9; i1 += 3) { newSeq[0] = i1 + 'A'; newSeq[1] = oldSeq[0]; explore2(0, n, oldSeq, newSeq, it.value()); } } check_inverse_are_equal(n); } for (int n = 1; n < till_n; n++) { long count_dia = 0; long count = 0; long counts[50]; for (int i = 0; i < 50; i++) counts[i] = 0; for (InsertOnlyMap::iterator it(possibleSeq[n-1]); it.more(); it.next()) { if (n < 9 && it.value().to == 0) printf("%s %ld %ld %ld\n", it.key().seq, it.value().from, it.value().to, it.value().count); count_dia++; count += it.value().count; if (it.value().count < 50) counts[it.value().count]++; } for (InsertOnlyMap::iterator it(possibleSeq[n-1]); it.more(); it.next()) { if (n < 9 && it.value().to != 0 && strstr(it.key().seq, "DAAHIFAAB") != 0) printf("%s %ld %ld %ld\n", it.key().seq, it.value().from, it.value().to, it.value().count); } printf("%2d %5ld %5ld ", n*2+1, count_dia, count); for (int i = 0; i < 50; i++) printf("%7ld", counts[i]); printf("\n"); } } #define MAX_N 20 #define MAX_M 20 class State; class Transition { public: Transition(State* n_from, State* n_to); State* from; State* to; Transition* next_from; Transition* next_to; }; class State { public: State(const char *n_row, bool n_first, bool n_last) : first(n_first), last(n_last), from_states(0), to_states(0), next(0){ strcpy(row, n_row); } char row[MAX_M+1]; bool first; bool last; Transition* from_states; Transition* to_states; State* next; }; State* all_states; Transition::Transition(State* n_from, State* n_to) : from(n_from), to(n_to) { next_from = to->from_states; to->from_states = this; next_to = from->to_states; from->to_states = this; } State* find_or_create_state(const char *row, bool first, bool last) { State** ref = &all_states; for (;*ref != 0; ref = &(*ref)->next) if (strcmp((*ref)->row, row) == 0) return *ref; *ref = new State(row, first, last); return *ref; } bool is_last_row(const char* row, int m) { for (int i = 0; i+1 < m; i++) { if ( row[i+1] != row[i] + 1 && ( (row[i+1]-'A')%3 != 0 || (row[i]-'A')/3 == (row[i+1]-'A')/3)) return false; } for (int i = 2; i < m; i++) if (row[i] == 'C') return false; return true; } bool state_details = false; void find_start_states(int i, int m, char *row) { if (i == m) { row[m] = '\0'; bool last = is_last_row(row, m); if (state_details) printf("start: %s%s\n", row, last ? " *" : ""); find_or_create_state(row, true, last); return; } for (char ch = 'A'; ch <= 'C'; ch++) if (ch == 'A' || ch == row[i-1] + 1) { row[i] = ch; find_start_states(i+1, m, row); } } void find_next_states(State* from_state, char *to_row, int i, int m) { const char* from_row = from_state->row; if (i == m-1) { if ( ( to_row[i] == from_row[i] + 3 || ( to_row[i] <= 'C' && (from_row[i] - 'A') % 3 != (to_row[i] - 'A'))) && to_row[i] != 'G') { to_row[m] = '\0'; bool last = is_last_row(to_row, m); if (state_details) printf("%s -> %s%s\n", from_row, to_row, last ? " *" : ""); State* to_state = find_or_create_state(to_row, false, last); new Transition(from_state, to_state); } return; } for (char ch = 'A'; ch <= 'I'; ch++) if (st[from_row[i]-'A'][from_row[i+1]-'A'][to_row[i]-'A'][ch-'A']) { to_row[i+1] = ch; find_next_states(from_state, to_row, i+1, m); } } long nr_unique_rectangles = 0; long nr_rectangles = 0; long nr_rectangles_calc = 0; bool trace_is_smaller = false; bool is_smallers(char *rows[], int n, int &factor) { int m = strlen(rows[0]); int nr_cases = 1; int nr_equal = 1; char mat[MAX_N][MAX_M]; for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) mat[i][j] = rows[i][j]; if (trace_is_smaller) { printf("\n"); for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) printf("%c", mat[i][j]); printf("\n"); } printf("\n"); } for (int step = 1; step < 8; step++) { if (step % 2 == 1) { // flip vertical if (trace_is_smaller) printf("flip vertical\n"); for (int i = 0; i < n; i++) { for (int j = 0; j*2 < m; j++) { char h = mat[i][j]; mat[i][j] = mat[i][m-1-j]; mat[i][m-1-j] = h; } for (int j = 0; j < m;) { int v = (mat[i][j] - 'A') % 3; int h = (mat[i][j] - 'A') / 3; for (int k = 0; k <= v; k++, j++) mat[i][j] = k + 3*h + 'A'; } } } else if (step != 4) { // flip horizontal if (trace_is_smaller) printf("flip horizontal\n"); for (int j = 0; j < m; j++) { for (int i = 0; i*2 < n; i++) { char h = mat[i][j]; mat[i][j] = mat[n-1-i][j]; mat[n-1-i][j] = h; } for (int i = 0; i < n;) { int v = (mat[i][j] - 'A') % 3; int h = (mat[i][j] - 'A') / 3; for (int k = 0; k <= h; k++, i++) mat[i][j] = v + 3*k + 'A'; } } } else { // flip diagonal if (n != m) break; if (trace_is_smaller) printf("flip diagonal\n"); for (int i = 0; i < m-1; i++) for (int j = i+1; j < m; j++) { char h = mat[i][j]; mat[i][j] = mat[j][i]; mat[j][i] = h; } for (int i = 0; i < m; i++) for (int j = 0; j < m; j++) { int v = (mat[i][j] - 'A') % 3; int h = (mat[i][j] - 'A') / 3; mat[i][j] = h + 3*v + 'A'; } } if (trace_is_smaller) { for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) printf("%c", mat[i][j]); if (i+1 < n) printf("\n"); } } bool larger = false; for (int i = 0; i < n && !larger; i++) for (int j = 0; j < m && !larger; j++) if (mat[i][j] < rows[i][j]) { if (trace_is_smaller) printf(" smaller\n"); return false; } else if (mat[i][j] > rows[i][j]) { if (trace_is_smaller) printf(" larger\n"); larger = true; } nr_cases++; if (!larger) nr_equal++; if (trace_is_smaller && !larger) printf(" equal\n"); } factor = nr_cases / nr_equal; if (trace_is_smaller) printf("ok, factor = %d\n", nr_cases); return true; } bool horz_dash(char* rows[], int i, int j) { return (rows[i][j]-'A')%3 + 1 != (rows[i][j+1]-'A')%3; } bool vert_dash(char* rows[], int i, int j) { return (rows[i][j]-'A')/3 + 1 != (rows[i+1][j]-'A')/3; } bool trace_fill_next_row = false; bool print_rectangles = false; bool output_rectangles = false; void fill_next_row(char* rows[], State *s, int i, int n) { if (trace_fill_next_row) { for (int j = 0; j < i; j++) printf("%s ", rows[j]); printf("\n"); } if (i == n) { if (s->last) { nr_rectangles++; int factor; if (is_smallers(rows, n, factor)) { nr_unique_rectangles++; nr_rectangles_calc += factor; if (print_rectangles) { int m = strlen(rows[0]); printf("\n"); printf("+-"); for (int k = 0; k+1 < m; k++) printf("%c-", horz_dash(rows, 0, k) ? '+' : '-'); printf("+\n"); for (int j = 0; j < n; j++) { printf("|%c"/*);/*/, rows[j][0]); for (int k = 0; k+1 < m; k++) printf("%c%c", horz_dash(rows, j, k) ? '|' : ' '/*); /*/, rows[j][k+1]); printf("|\n"); if (j == n-1) break; printf("%s", rows[j][0] >= rows[j+1][0] ? "+-" : "| "); for (int k = 0; k+1 < m; k++) { bool vert = horz_dash(rows, j, k) || (j+1 < n && horz_dash(rows, j+1, k)); bool horz = vert_dash(rows, j, k) || vert_dash(rows, j, k+1); printf("%c%c", vert && horz ? '+' : vert ? '|' : horz ? '-' : ' ', vert_dash(rows, j, k+1) ? '-' : ' '); } printf("%c\n", vert_dash(rows, j, m-1) ? '+' : '|'); } printf("+-"); for (int k = 0; k+1 < m; k++) printf("%c-", horz_dash(rows, n-1, k) ? '+' : '-'); printf("+\n"); } if (output_rectangles) { int m = strlen(rows[0]); char buffer[MAX_N*MAX_M]; char *s = buffer; int c[5] = { 0, 0, 0, 0, 0 }; for (int j = 0; j < n; j++) for (int k = 0; k < m; k++) { if (rows[j][k] == 'A') { int j2 = 1; while (j2 < 3 && j + j2 < n && rows[j+j2][k] == 'A' + 3*j2) j2++; int k2 = 1; while (k2 < 3 && k + k2 < m && rows[j][k+k2] == 'A' + k2) k2++; if (j2 == 1 && k2 == 1 ) { *s++ = 'a'; c[0]++; } if (j2 == 1 && k2 == 2 ) { *s++ = 'b'; c[1]++; } if (j2 == 2 && k2 == 1 ) { *s++ = 'c'; c[1]++; } if (j2 == 2 && k2 == 2 ) { *s++ = 'd'; c[2]++; } if (j2 == 2 && k2 == 3 ) { *s++ = 'e'; c[3]++; } if (j2 == 3 && k2 == 2 ) { *s++ = 'f'; c[3]++; } if (j2 == 3 && k2 == 3 ) { *s++ = 'g'; c[4]++; } } } *s = '\0'; printf("\t{v:\"%d,%d,%d,%d,%d\",s:\"%s\"},\n", c[0], c[1], c[2], c[3], c[4], buffer); } } } return; } for (Transition* trans = s->to_states; trans != 0; trans = trans->next_to) { State* ns = trans->to; rows[i] = ns->row; fill_next_row(rows, ns, i+1, n); } } long uniq_results[MAX_N][MAX_M]; long all_results[MAX_N][MAX_M]; int error_n = -1; int error_m = -1; void find_in_rectangle(int n, int m) { printf("n = %d, m = %d\n\n", n, m); all_states = 0; char row[MAX_M+1]; row[0] = 'A'; find_start_states(1, m, row); for (State* s = all_states; s != 0; s = s->next) { for (char ch = 'A'; ch <= 'G'; ch += 3) if (ch == 'A' || ch == s->row[0] + 3) { row[0] = ch; find_next_states(s, row, 0, m); } } nr_unique_rectangles = 0; nr_rectangles = 0; nr_rectangles_calc = 0; char* rows[MAX_N]; for (State* s = all_states; s != 0 && s->first; s = s->next) { rows[0] = s->row; fill_next_row(rows, s, 1, n); } if (nr_rectangles != nr_rectangles_calc) { printf("ERROR: nr_rectangles = %ld, nr_rectangles_calc = %ld\n", nr_rectangles, nr_rectangles_calc); if (error_n == -1) { error_n = n; error_m = m; } } printf("\ntotal = %ld, unique = %ld\n", nr_rectangles, nr_unique_rectangles); uniq_results[n][m] = nr_unique_rectangles; all_results[n][m] = nr_rectangles; } int main(int argc, char* argv) { for (int i1 = 0; i1 < 9; i1++) for (int i2 = 0; i2 < 9; i2++) { for (int i3 = 0; i3 < 9; i3++) { for (int i4 = 0; i4 < 9; i4++) st[i1][i2][i3][i4] = false; st3[i1][i2][i3] = 0; } stc[i1][i2].top = 0; stc[i1][i2].left = 0; stc[i1][i2].right = 0; stc[i1][i2].bottom = 0; } DoubleLinesOutput doubleLinesOutput; doubleLinesOutput.setEnable(debug_init); // empty if (debug_init) printf("empty\n"); for (int a = 1; a+1 <= 3; a++) for (int b = 1; b+1 <= 3; b++) initialize_st(value(a, b), value(a+1, b), value(a, b+1), value(a+1, b+1), doubleLinesOutput); doubleLinesOutput.flush(); // horizontal if (debug_init) printf("\nhorizontal\n"); for (int a = 1; a+1 <= 3; a++) for (int b = 1; b <= 3; b++) for (int c = 1; c+1 <= 3; c++) if (a != 2 || c != 2) initialize_st(value(a, b), value(a+1, b), value(c, 1), value(c+1, 1), doubleLinesOutput); doubleLinesOutput.flush(); // vertical if (debug_init) printf("\nvertical\n"); for (int a = 1; a < 3; a++) for (int b = 1; b <= 3; b++) for (int c = 1; c+1 <= 3; c++) if (a != 2 || c != 2) initialize_st(value(b, a), value(1, c), value(b, a+1), value(1, c+1), doubleLinesOutput); doubleLinesOutput.flush(); // T if (debug_init) printf("\nT\n"); for (int a = 1; a+1 <= 3; a++) for (int b = 1; b <= 3; b++) for (int c = 1; c <= 3; c++) initialize_st(value(a, b), value(a+1, b), value(c, 1), value(1, 1), doubleLinesOutput); doubleLinesOutput.flush(); // T rotated to the left if (debug_init) printf("\nT rotated to the left\n"); for (int a = 1; a+1 <= 3; a++) for (int b = 1; b <= 3; b++) for (int c = 1; c <= 3; c++) initialize_st(value(b, a), value(1, c), value(b, a+1), value(1, 1), doubleLinesOutput); doubleLinesOutput.flush(); // T rotated to the right if (debug_init) printf("\nT rotated to the right\n"); for (int a = 1; a <= 3; a++) for (int b = 1; b <= 3; b++) if (!(a == 3 && b == 1) && !(a == 1 && b == 3)) for (int c = 1; c <= 3; c++) if (c != a) for (int d = 1; d+1 <= 3; d++) initialize_st(value(a, b), value(1, d), value(c, 1), value(1, d+1), doubleLinesOutput); doubleLinesOutput.flush(); // T upside-down if (debug_init) printf("\nT upside-down\n"); for (int a = 1; a <= 3; a++) for (int b = 1; b <= 3; b++) if (!(a == 3 && b == 1) && !(a == 1 && b == 3)) for (int c = 1; c <= 3; c++) if (c != a) for (int d = 1; d+1 <= 3; d++) initialize_st(value(b, a), value(1, c), value(d, 1), value(d+1, 1), doubleLinesOutput); doubleLinesOutput.flush(); if (debug_init) printf("\n-----\n\n"); doubleLinesOutput.setEnable(true); for (bool go = true; go; ) { for (int i1 = 0; i1 < 9; i1++) for (int i2 = 0; i2 < 9; i2++) for (int i3 = 0; i3 < 9; i3++) for (int i4 = 0; i4 < 9; i4++) if (st[i1][i2][i3][i4]) doubleLinesOutput.add(i1, i2, i3, i4); doubleLinesOutput.flush(); // Check top versus bottom go = false; for (int i1 = 0; i1 < 9; i1++) for (int i2 = 0; i2 < 9; i2++) { bool top = stc[i1][i2].top > 0; bool bottom = stc[i1][i2].bottom > 0; if (top != bottom) { printf("%c%c top = %d bottom = %d\n", i1+'A', i2+'A', stc[i1][i2].top, stc[i1][i2].bottom); go = true; } if (top && !bottom) { for (int i3 = 0; i3 < 9; i3++) for (int i4 = 0; i4 < 9; i4++) remove_st(i1, i2, i3, i4); } if (bottom && !top) { for (int i3 = 0; i3 < 9; i3++) for (int i4 = 0; i4 < 9; i4++) remove_st(i3, i4, i1, i2); } } // Check left versus right for (int i1 = 0; i1 < 9; i1++) for (int i2 = 0; i2 < 9; i2++) { bool left = stc[i1][i2].left > 0; bool right = stc[i1][i2].right > 0; if (left != right) { printf("%c%c left = %d right = %d\n", i1+'A', i2+'A', stc[i1][i2].left, stc[i1][i2].right); go = true; } if (left && !right) { for (int i3 = 0; i3 < 9; i3++) for (int i4 = 0; i4 < 9; i4++) remove_st(i1, i3, i2, i4); } if (right && !left) { for (int i3 = 0; i3 < 9; i3++) for (int i4 = 0; i4 < 9; i4++) remove_st(i3, i1, i4, i2); } } printf("\n"); } for (int i1 = 0; i1 < 9; i1++) for (int i2 = 0; i2 < 9; i2++) for (int i3 = 0; i3 < 9; i3++) for (int i4 = 0; i4 < 9; i4++) if (st[i1][i2][i3][i4]) st3[i1][i2][i3]++; // check if symmetric for (int i1 = 0; i1 < 9; i1++) for (int i2 = 0; i2 < 9; i2++) for (int i3 = 0; i3 < 9; i3++) { if (st3[i1][i2][i3] != st3[inverse(i1)][inverse(i3)][inverse(i2)]) { printf("Not symmetric for %c%c %c\n", i1+'A', i2+'A', i3+'A'); return 1; } for (int i4 = 0; i4 < 9; i4++) if (st[i1][i2][i3][i4] != st[inverse(i1)][inverse(i3)][inverse(i2)][inverse(i4)]) { printf("Not symmetric for %c%c %c%c\n", i1+'A', i2+'A', i3+'A', i4+'A'); return 1; } } impossible_sequences_from_corner(); find_possible_from_corner(); for (int n = 1; n <= MAX_N; n++) for (int m = 1; m <= MAX_M; m++) { uniq_results[n][m] = -1; all_results[n][m] = -1; } for (int n = 1; n <= 10; n++) for (int m = n; m <= 10; m++) { state_details = false; trace_fill_next_row = state_details; trace_is_smaller = state_details; find_in_rectangle(n, m); if (m != n) { find_in_rectangle(m, n); if ((uniq_results[n][m] != uniq_results[m][n] || all_results[n][m] != all_results[m][n]) && error_n == -1) { error_n = n; error_m = m; } } } for (int n = 1; n <= 10; n++) { printf("\n"); for (int m = 1; m <= 10; m++) if (uniq_results[n][m] == -1) printf(" "); else printf("%6ld", uniq_results[n][m]); } printf("\n"); for (int n = 1; n <= 10; n++) { printf("\n"); for (int m = 1; m <= 10; m++) if (all_results[n][m] == -1) printf(" "); else printf("%7ld", all_results[n][m]); } if (error_n > -1) printf("ERROR: n == %d && m == %d\n", error_n, error_m); output_rectangles = true; find_in_rectangle(8,8); return 0; }