#include #include void swap(int &x, int &y) { int h = x; x = y; y = h; } class Permutations { public: Permutations(int val_n) : n(val_n), _more(true) { a = new int[n]; for (int i = 0; i < n; i++) a[i] = i; } ~Permutations() { delete []a; } bool more() { return _more; } void next() { _more = false; for (int i = n-2; i >= 0; i--) if (a[i] < a[i+1]) { _more = true; for (int j = n-1; j > i; j--) if (a[j] > a[i]) { swap(a[j], a[i]); break; } i++; for (int j = n-1; j > i; j--, i++) swap(a[j], a[i]); break; } } inline int operator[](int i) { return a[i]; } private: int n; int *a; bool _more; }; #define EMPTY 'x' char v[7][7]; int x[21]; int y[21]; bool f[7][3]; int otherside(const char *sol, int f, int v) { for (int p = 0; p < 21; p++) if (sol[p] == v + 'a') { if (x[p] == f) return y[p]; if (y[p] == f) return x[p]; } return -1; } int shape(const char *sol, int a, int b) { for (int i = 0; i < 7; i++) if (f[i][a] && !f[i][b]) { int n; n = otherside(sol, i, a); n = otherside(sol, n, b); n = otherside(sol, n, a); return (n == -1) ? 1 : 0; } return 2; } struct TriSol { TriSol() : next(0) {} char v[22]; int pattern[3]; int sym; TriSol* next; }; TriSol *all_tri_sols = 0; TriSol **ref_next_tri_sol = &all_tri_sols; bool pos_pattern[3][3][3]; void fill(char c, int p, int t) { if (p == 3) { c++; p = 0; t = 0; } if (c == 'd') { char sol[22]; char* s = sol; for (int i = 0; i < 6; i++) for (int j = i+1; j < 7; j++) *s++ = v[i][j]; *s = '\0'; bool smaller = false; int sym = 0; for (Permutations perms(7); perms.more(); perms.next()) { char alt_sol[22]; char *s = alt_sol; char rep[3] = { ' ', ' ', ' ' }; char cn = 'a'; for (int t = 0; t < 21; t++) { int i = perms[x[t]]; int j = perms[y[t]]; char ac = i < j ? v[i][j] : v[j][i]; if (ac == EMPTY) *s++ = EMPTY; else { if (rep[ac-'a'] == ' ') rep[ac-'a'] = cn++; *s++ = rep[ac-'a']; } } *s = '\0'; if (strcmp(alt_sol, sol) < 0) { smaller = true; break; } else if (strcmp(alt_sol, sol) == 0) sym++; } if (!smaller) { *ref_next_tri_sol = new TriSol; strcpy((*ref_next_tri_sol)->v, sol); (*ref_next_tri_sol)->pattern[0] = shape(sol, 0, 1); (*ref_next_tri_sol)->pattern[1] = shape(sol, 1, 2); (*ref_next_tri_sol)->pattern[2] = shape(sol, 2, 0); (*ref_next_tri_sol)->sym = sym; for (int r = 0; r < 3; r++) for (int s = 1; s <= 2; s++) pos_pattern[(*ref_next_tri_sol)->pattern[r]] [(*ref_next_tri_sol)->pattern[(r + s)%3]] [(*ref_next_tri_sol)->pattern[(r + 2*s)%3]] = true; ref_next_tri_sol = &(*ref_next_tri_sol)->next; } return; } for (; t < 21; t++) if (v[x[t]][y[t]] == EMPTY && !f[x[t]][c-'a'] && !f[y[t]][c-'a']) { v[x[t]][y[t]] = c; f[x[t]][c-'a'] = true; f[y[t]][c-'a'] = true; fill(c, p+1, t+1); f[x[t]][c-'a'] = false; f[y[t]][c-'a'] = false; v[x[t]][y[t]] = EMPTY; if (p == 0) break; } } class OctoGroup { public: OctoGroup() { for (int i = 0; i < 12; i++) elements[0][i] = i; for (int i = 0; i < 6; i++) vertices[0][i] = i; _nr = 1; for (int j = 0; j < 24; j++) { int element[12]; int vertex[6]; for (int r = 0; r < 2; r++) { for (int i = 0; i < 12; i++) element[_t[r][i]] = elements[j][i]; for (int i = 0; i < 6; i++) vertex[_v[r][i]] = vertices[j][i]; _insert(element, vertex); } } printf("%d\n", _nr); } int elements[24][12]; int vertices[24][6]; private: void _insert(int *element, int *vertex) { for (int j = 0; j < _nr; j++) { bool equal = true; for (int i = 0; i < 12; i++) if (elements[j][i] != element[i]) equal = false; for (int i = 0; i < 6; i++) if (vertices[j][i] != vertex[i]) equal = false; if (equal) return; } if (_nr == 24) { printf("Error\n"); return; } for (int i = 0; i < 12; i++) elements[_nr][i] = element[i]; for (int i = 0; i < 6; i++) vertices[_nr][i] = vertex[i]; _nr++; } int _nr; int _t[2][12] = { /* 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11 */ { 1, 2, 0, 5, 6, 7, 8, 3, 4, 10, 11, 9 }, { 3, 4, 1, 10, 5, 2, 0, 8, 9, 11, 6, 7 } }; int _v[2][6] = { /* 0, 1, 2, 3, 4, 5 */ { 1, 2, 0, 4, 5, 3 }, { 0, 2, 3, 4, 1, 5 } }; }; class OctoIterator { public: OctoIterator(const OctoGroup& group) : _group(group) { for (int i = 0; i < 12; i++) _value[i] = 3; _i = 1; next(); } bool more() { return _i == 12; } void next() { _i--; for (; _i >= 0 && _i < 12;) { if (_value[_i] == 2) { _value[_i] = 3; _i--; } else { if (_value[_i] == 3) _value[_i] = 0; else _value[_i]++; bool okay = true; switch (_i) { case 2: okay = pos_pattern[_value[ 0]][_value[ 1]][_value[ 2]]; break; case 4: okay = pos_pattern[_value[ 1]][_value[ 3]][_value[ 4]]; break; case 6: okay = pos_pattern[_value[ 2]][_value[ 5]][_value[ 6]]; break; case 8: okay = pos_pattern[_value[ 0]][_value[ 7]][_value[ 8]]; break; case 9: okay = pos_pattern[_value[ 3]][_value[ 8]][_value[ 9]]; break; case 10: okay = pos_pattern[_value[ 4]][_value[ 5]][_value[10]]; break; case 11: okay = pos_pattern[_value[ 7]][_value[ 7]][_value[11]] && pos_pattern[_value[ 9]][_value[10]][_value[11]]; break; } for (int s = 0; s < 24 && okay; s++) { sym[s] = true; for (int i = 0; i < 12; i++) if (_value[_group.elements[s][i]] != _value[i]) { okay = _value[_group.elements[s][i]] > _value[i]; sym[s] = false; break; } } if (okay) _i++; } } } int operator[](int i) { return _value[i]; } bool sym[24]; private: const OctoGroup& _group; int _i; int _value[12]; }; class Patterns { public: Patterns() { for (int i = 0; i < 3; i++) _used[i] = 0; _c = 0; _fill_pattern(0, 0, false); for (int i = 0; i < 105; i++) { int *p1 = all_patterns[i]; for (int j = 0; j < 105; j++) { match[i][j] = 2; int *p2 = all_patterns[j]; for (int k = 0; k < 7; k++) if (p1[k] != 3 && p2[k] != 3 && _pmatch(k, p1) == _pmatch(k, p2)) { match[i][j] = 3; break; } if (match[i][j] == 2) { for (int k = 0; k < 7; k++) if (p1[k] < 3 && p2[k] == 3) { k = _pmatch(k, p1); k = _pmatch(k, p2); k = _pmatch(k, p1); match[i][j] = k == -1 ? 1 : 0; break; } } } } } int all_patterns[105][7]; char match[105][105]; private: int _pattern[7]; int _used[3]; int _c; void _fill_pattern(int i, int j, bool e) { if (i == 7) { for (int k = 0; k < 7; k++) all_patterns[_c][k] = _pattern[k]; _c++; return; } for (int k = 0; k <= j && k < 3; k++) if (_used[k] < 2) { _used[k]++; _pattern[i] = k; _fill_pattern(i+1, k+1 > j ? k+1 : j, e); _used[k]--; } if (!e) { _pattern[i] = 3; _fill_pattern(i+1, j, true); } } int _pmatch(int k, int *p) { for (int i = 0; i < 7; i++) if (i != k && p[k] == p[i]) return i; return -1; } }; int main(int argc, char *argv[]) { int t = 0; for (int i = 0; i < 6; i++) for (int j = i+1; j < 7; j++) { v[i][j] = EMPTY; x[t] = i; y[t] = j; t++; } for (int i = 0; i < 7; i++) for (int j = 0; j < 3; j++) f[i][j] = false; for (int i = 0; i < 3; i++) for (int j = 0; j < 3; j++) for (int k = 0; k < 3; k++) pos_pattern[i][j][k] = false; fill('a', 0, 0); for (TriSol *triSol = all_tri_sols; triSol != 0; triSol = triSol->next) { printf("%d %d %d %s %d\n", triSol->pattern[0], triSol->pattern[1], triSol->pattern[2], triSol->v, triSol->sym); } Patterns patterns; OctoGroup octoGroup; for (int i = 0; i < 3; i++) { for (int j = 0; j < 3; j++) for (int k = 0; k < 3; k++) printf("%c", pos_pattern[i][j][k] ? 'T' : 'F'); printf("\n"); } FILE *fout = fopen("out2.txt","wt"); int c = 0; int c2 = 0; int c3 = 0; for (OctoIterator it(octoGroup); it.more(); it.next()) { for (int i = 0; i < 12; i++) printf("%2d", it[i]); printf("\n"); c++; int sol[8]; sol[0] = 0; for (sol[1] = 0; sol[1] < 105; sol[1]++) if (patterns.match[sol[0]][sol[1]] == it[2]) { for (sol[2] = 0; sol[2] < 105; sol[2]++) if ( patterns.match[sol[0]][sol[2]] == it[1] && patterns.match[sol[1]][sol[2]] == it[0]) for (sol[3] = 0; sol[3] < 105; sol[3]++) if ( patterns.match[sol[0]][sol[3]] == it[4] && patterns.match[sol[2]][sol[3]] == it[3]) for (sol[4] = 0; sol[4] < 105; sol[4]++) if ( patterns.match[sol[0]][sol[4]] == it[5] && patterns.match[sol[1]][sol[4]] == it[6] && patterns.match[sol[3]][sol[4]] == it[10]) for (sol[5] = 0; sol[5] < 105; sol[5]++) if ( patterns.match[sol[1]][sol[5]] == it[7] && patterns.match[sol[2]][sol[5]] == it[8] && patterns.match[sol[3]][sol[5]] == it[9] && patterns.match[sol[4]][sol[5]] == it[11]) { printf(" "); for(int i = 0; i < 6; i++) printf(" %3d", sol[i]); bool some_smaller = false; int symmetries = 1; for (int r = 1; r < 24; r++) if (it.sym[r]) { bool smaller = false; bool equal = true; for (int v = 0; v < 6; v++) if (sol[octoGroup.vertices[r][v]] != sol[v]) { smaller = sol[octoGroup.vertices[r][v]] < sol[v]; equal = false; break; } if (smaller) { some_smaller = true; printf(" (%d)", r); } if (equal) symmetries++; } for (int r = 0; r < 24; r++) if (it.sym[r]) { Permutations perm(7); for (perm.next(); perm.more() && !some_smaller; perm.next()) { bool smaller = false; bool equal = true; for (int v = 0; v < 6; v++) { int new_vector[7]; int map[3] = { -1, -1, -1 }; int nr = 0; for (int k = 0; k < 7; k++) { int m = patterns.all_patterns[sol[v]][perm[k]]; if (m < 3) { if (map[m] == -1) map[m] = nr++; m = map[m]; } new_vector[k] = m; } int new_sol; for (new_sol = 0; new_sol < 105; new_sol++) { bool equal = true; for (int k = 0; k < 7; k++) if (new_vector[k] != patterns.all_patterns[new_sol][k]) { equal = false; break; } if (equal) break; } if (new_sol == 105) { printf("\nError\n"); for (int k = 0; k < 7; k++) printf(" %d", perm[k]); printf("\n"); for (int k = 0; k < 7; k++) printf(" %d", patterns.all_patterns[sol[v]][k]); printf("\n"); for (int k = 0; k < 7; k++) printf(" %d", new_vector[k]); printf("\n"); return -1; } if (new_sol != sol[v]) { smaller = new_sol < sol[v]; equal = false; break; } } if (smaller) { some_smaller = true; printf(" (%d", r); for (int k = 0; k < 7; k++) printf("%c%d", k == 0 ? ':' : ',', perm[k]); printf(")"); } if (equal) symmetries++; } } printf(" = %d\n", symmetries); c2++; if (!some_smaller) { for (int k = 0; k < 6; k++) fprintf(fout, "%4d", sol[k]); fprintf(fout, "\n"); c3++; } } break; } } fclose(fout); printf("# = %d %d %d\n", c, c2, c3); }