/* 1991 ACM Finals Problem D The Domino Effect Ed Karrels, May. 1996 */ #include int bones[7][7]; int layout = 1; void Print(int board[7][8]) { int r, c; for (r=0; r<7; r++) { for (c=0; c<8; c++) printf("%4d", board[r][c]); putchar ('\n'); } putchar ('\n'); } int Place(int pips[7][8], int placed[7][8], int used[28], int n_used, int r1, int c1, int r2, int c2) { int b, soln=0, r, c; static int call=0; b = bones[pips[r1][c1]][pips[r2][c2]]; if (!used[b]) { used[b] = placed[r1][c1] = placed[r2][c2] = b; if (n_used == 28) { Print(placed); soln = 1; } else { r = r1; c = c1; while (placed[r][c] || (r<6 && placed[r+1][c]) && (c<7 && placed[r][c+1])) { if (++c > 7) { c = 0; if (++r > 6) break; } } if (r != 7) { if (r<6 && !placed[r+1][c]) soln += Place(pips, placed, used, n_used+1, r, c, r+1, c); if (c<7 && !placed[r][c+1]) soln += Place(pips, placed, used, n_used+1, r, c, r, c+1); } } placed[r1][c1] = placed[r2][c2] = used[b] = 0; } return soln; } int main() { int pips[7][8], placed[7][8], used[29]; int r, c, i, j, b, layout=1; for (b=1,i=0,j=0; b<29; b++) { bones[i][j] = bones[j][i] = b; if (++i == 7) { i = ++j; } } while (scanf("%d", &pips[0][0]) == 1) { for (r=0; r<7; r++) { for (c=0; c<8; c++) { if (r || c) scanf("%d", &pips[r][c]); placed[r][c] = 0; } } for (i=1; i<=28; i++) used[i] = 0; printf("Layout #%d:\n\n", layout); Print(pips); printf("Maps resulting from layout #%d are:\n\n", layout); i = Place(pips, placed, used, 1, 0, 0, 0, 1) + Place(pips, placed, used, 1, 0, 0, 1, 0); printf("There are %d solution(s) for layout #%d.\n\n\n", i, layout++); } return 0; }