#include #define BIT(V,N) (((V) & (N)) != 0) bool possible_unfold(int a) { return a == 0 || (a >= 16 && a != 24 && a != 29); } bool straight_unfold(int a) { return a == 0 || a == 16 || a == 18 || a == 26; } int rotate_unfold(int a) { return ((a & 1) << 4) | (a & 2) | ((a & 4) << 1) | ((a & 8) >> 3) | ((a & 16) >> 2); } int bits_set(int a) { return (a & 1) + ((a >> 1) & 1) + ((a >> 2) & 1) + ((a >> 3) & 1) + ((a >> 4) & 1); } void print_unfold(int a) { printf(" %d%d%d%d%d", (a >> 4) & 1, a & 1, (a >> 1) & 1, (a >> 2) & 1, (a >> 3) & 1); } struct Tile { int i; int j; int k; int k_mode; int l; int l_mode; bool is_empty; Tile *next; Tile(int n_i, int n_j, int n_k, int n_k_mode, int n_l, int n_l_mode, Tile *n_next) : i(n_i), j(n_j), k(n_k), k_mode(n_k_mode), l(n_l), l_mode(n_l_mode), is_empty(i == 0 && j == 0 && k == 0 && l == 0), next(n_next) {} }; Tile *tiles[32][4][32][4]; int unfold_invert[32]; int nr_tiles = 0; void gen_tiles() { for (int i = 0; i < 16; i++) unfold_invert[i] = 0; for (int i = 16; i < 32; i++) unfold_invert[i] = (i & 16) | ((i & 1) ? 0 : 4) | ((i & 2) ? 0 : 8) | ((i & 4) ? 0 : 1) | ((i & 8) ? 0 : 2); for (int i = 0; i < 32; i++) for (int i_mode = 0; i_mode < 4; i_mode++) for (int j = 0; j < 32; j++) for (int j_mode = 0; j_mode < 4; j_mode++) tiles[i][i_mode][j][j_mode] = 0; tiles[0][0][0][0] = new Tile(0, 0, 0, 0, 0, 0, 0); for (int i = 0; i < 32; i++) if (possible_unfold(i)) { int i_rot = rotate_unfold(i); for (int j = 0; j < 32; j++) if (possible_unfold(j) && (i_rot & j) == 0) { int ij_rot = rotate_unfold(i_rot | j); for (int k = 0; k < 32; k++) if (possible_unfold(k) && (ij_rot & k) == 0) { int ijk_rot = rotate_unfold(ij_rot | k); int l = 31 & ~ijk_rot; if (possible_unfold(l)) { for (int i_mode = 0; i_mode < 4; i_mode++) { int k_mode = k == 0 ? 0 : i_mode | (j != 0 ? 1 : 0) | (l != 0 ? 2 : 0); if ( (i_mode != 0 || straight_unfold(i)) && (k_mode != 3 || straight_unfold(k)) && ((i_mode & 1) == 0 || j == 0) && ((i_mode & 2) == 0 || l == 0)) { for (int j_mode = 0; j_mode < 4; j_mode++) { int l_mode = l == 0 ? 0 : j_mode | (i != 0 ? 1 : 0) | (k != 0 ? 2 : 0); if ( (j_mode != 0 || straight_unfold(j)) && (l_mode != 3 || straight_unfold(l)) && ((j_mode & 1) == 0 || i == 0) && ((j_mode & 2) == 0 || k == 0)) { /* print_unfold(i); printf(" (%d)", i_mode); print_unfold(j); printf(" (%d)", j_mode); print_unfold(k); printf(" (%d)", k_mode); print_unfold(l); printf(" (%d)", l_mode); printf(" |"); print_unfold(unfold_invert[k]); print_unfold(unfold_invert[l]); printf("\n"); //*/ tiles[i][i_mode][j][j_mode] = new Tile(i, j, unfold_invert[k], k_mode, unfold_invert[l], l_mode, tiles[i][i_mode][j][j_mode]); nr_tiles++; } } } } } } } } } #define N 20 #define MAX_NR 1000 struct ColumnList; struct Column { int values[N]; int modes[N]; int min_nr_empty; bool empties[12]; bool reachable; ColumnList *next_columns; ColumnList *prev_columns; Column *next; Column() : min_nr_empty(MAX_NR), next_columns(0), prev_columns(0), reachable(false), next(0) { for (int i = 0; i < N; i++) values[i] = modes[i] = 0; for (int i = 0; i < 12; i++) empties[i] = 0; } }; struct ColumnList { Column* prev_column; Column* next_column; int nr_empty; ColumnList *next_columns; ColumnList *prev_columns; int values[N-1]; ColumnList(Column* n_prev_column, Column* n_next_column, int n_nr_empty) : prev_column(n_prev_column), next_column(n_next_column), nr_empty(n_nr_empty) { next_columns = prev_column->next_columns; prev_column->next_columns = this; prev_columns = next_column->prev_columns; next_column->prev_columns = this; } }; Column *columns = 0; int nr_columns = 1; int nr_transitions = 0; void expand_column(Column* column, int p, int n, int j, int j_mode, int nr_empty, Tile *sel_tiles[]) { if (p == n) { //printf("%d with ", p); //print_unfold(j); //printf("\n"); if (j == 0) { /* printf("--\n"); for (int q = 0; q < n; q++) { printf(" "); print_unfold(sel_tiles[q]->j); printf("\n"); print_unfold(column->values[p]); printf(" "); print_unfold(sel_tiles[q]->i); printf(" %d ", sel_tiles[q]->is_empty ? 0 : 1); print_unfold(unfold_invert[sel_tiles[q]->k]); printf(" "); print_unfold(sel_tiles[q]->k); printf("\n"); printf(" "); print_unfold(unfold_invert[sel_tiles[q]->l]); printf("\n"); } //*/ /* printf("--\n"); for (int q = 0; q < n; q++) { if (q > 0) printf("\n"); #define BITV(L,V) BIT(sel_tiles[q]->L,V) #define BITU(L,V) BIT(unfold_invert[sel_tiles[q]->L],V) printf(" %d\n", BITV(j, 8)); printf(" %d\n", BITV(j, 2)); printf(" %d%d%d\n", BITV(j, 4), BITV(j, 16), BITV(j, 1)); printf(" %d %d %d\n", BITV(i,1), BITU(k, 4), BITV(k, 1)); printf("%d %d%d%d %d %d%d%d %d%d%d %d\n", column->modes[q], BITV(i, 8), BITV(i, 2), BITV(i, 16), sel_tiles[q]->is_empty ? 0 : 1, BITU(k,16), BITU(k,2), BITU(k,8), BITV(k,8), BITV(k,2), BITV(k,16), sel_tiles[q]->k_mode); printf(" %d %d %d\n", BITV(i,4), BITU(k, 1), BITV(k, 4)); printf(" %d%d%d\n", BITU(l, 1), BITU(l, 16), BITU(l, 4)); printf(" %d\n", BITU(l, 2)); printf(" %d\n", BITU(l, 8)); } //*/ /* printf(" --> "); for (int q = 0; q < n; q++) print_unfold(sel_tiles[q]->k); printf("\n"); */ nr_transitions++; Column** ref_column = &columns; for (; *ref_column != 0; ref_column = &(*ref_column)->next) { bool equal = true; for (int q = 0; q < n; q++) if ( (*ref_column)->values[q] != sel_tiles[q]->k || (*ref_column)->modes[q] != sel_tiles[q]->k_mode) { equal = false; break; } if (equal) { //printf("equal\n"); break; } } if (*ref_column == 0) { //printf("New\n"); nr_columns++; (*ref_column) = new Column(); for (int q = 0; q < n; q++) { (*ref_column)->values[q] = sel_tiles[q]->k; (*ref_column)->modes[q] = sel_tiles[q]->k_mode; } } if ((*ref_column)->min_nr_empty > column->min_nr_empty + nr_empty) (*ref_column)->min_nr_empty = column->min_nr_empty + nr_empty; ColumnList *trans = new ColumnList(column, *ref_column, nr_empty); for (int q = 0; q < n - 1; q++) trans->values[q] = sel_tiles[q]->l; } return; } int i = column->values[p]; int i_mode = column->modes[p]; //printf("%*.*s", p * 2, p * 2, ""); //print_unfold(i); //print_unfold(j); //printf("\n"); for (Tile *tile = tiles[i][i_mode][j][j_mode]; tile != 0; tile = tile->next) { //printf("%*.*s", p * 2, p * 2, ""); //printf(" use "); //print_unfold(i); //print_unfold(j); //print_unfold(unfold_invert[tile->k]); //print_unfold(unfold_invert[tile->l]); //printf("\n"); sel_tiles[p] = tile; expand_column(column, p + 1, n, tile->l, tile->l_mode, nr_empty + (tile->is_empty ? 1 : 0), sel_tiles); } } void build_graph(int n) { columns = new Column(); columns->min_nr_empty = 0; columns->empties[0] = true; int nr = 0; for (Column *column = columns; column != 0; column = column->next) { /* printf("Processing "); for (int i = 0; i < n; i++) print_unfold(column->values[i]); printf("\n"); */ fprintf(stderr, "%c", column->min_nr_empty + 'a'); if (nr % 100 == 0) printf("%d %d %d\n", nr, nr_columns, nr_transitions); nr++; Tile *sel_tiles[N]; expand_column(column, 0, n, 0, 0, 0, sel_tiles); } } int height = 6; Column *sel_columns[30]; ColumnList *sel_trans[30]; int length = 10; void print_sols(Column *column, int depth, int nr_empty) { sel_columns[depth] = column; if (depth == length || (depth > 0 && column == columns)) { for (int d = 1; d <= depth; d++) printf("+--"); printf("+\n"); for (int h = 0; h < height; h++) { printf("|"); for (int d = 1; d <= depth; d++) printf(" %c", sel_columns[d]->values[h] == 0 ? '|' : ' '); printf("\n"); if (h < height - 1) { printf("+"); for (int d = 0; d < depth; d++) printf("%s+", sel_trans[d]->values[h] == 0 ? "--" : " "); printf("\n"); } } for (int d = 1; d <= depth; d++) printf("+--"); printf("+\n\n"); return; } if (nr_empty > 10) return; for (ColumnList *next_column = column->next_columns; next_column != 0; next_column = next_column->next_columns) if (next_column->next_column->reachable) { sel_trans[depth] = next_column; print_sols(next_column->next_column, depth + 1, nr_empty + next_column->nr_empty); } } int main(int argc, char *argv[]) { gen_tiles(); printf("%d\n", nr_tiles); build_graph(height); printf("%d %d\n", nr_columns, nr_transitions); int nr_reachable = 1; columns->reachable = true; for (bool more = true; more;) { more = false; for (Column *column = columns; column != 0; column = column->next) if (column->reachable) for (ColumnList *trans = column->prev_columns; trans != 0; trans = trans->prev_columns) if (!trans->prev_column->reachable) { trans->prev_column->reachable = true; nr_reachable++; more = true; } } printf("%d\n", nr_reachable); //for (Column *column = columns; column != 0; column = column->next) // printf("%4d %d\n", column->min_nr_empty, column->reachable); //print_sols(columns, 0, 0); return 0; }