/* Copyright Laurent Dami, CUI, U. of Geneva, Jan 1996. This is free software: any uses and modifications are allowed, provided this notice remains, and no money is charged. This programs finds solutions to the pentomino puzzle. A pentomino is a piece formed from 5 adjacent squares; there are exactly 12 such pieces. The puzzle is to fit them all in a 10X6 rectangle, as for example: _____________________ |_________| |__ _| | | _| _|__ _| | | | |__ |__ |_| |_|___| |___|_| |__ |____ | | | |_______|_| _|_| | |_______|_____|_____| The program uses BSD system calls for some interactive options. These can be removed using the -DNO_INTERACTION compiler flag; then it should compile on any platform. */ #include #ifndef NO_INTERACTION #include #include #include #endif #ifndef FALSE #define FALSE 0 #define TRUE 1 #endif int place_next_piece(), remove_top_piece(), check_connect(int, int); void print_board(), find_solutions(), clean_connect(); /* Data structure for the board. Each cell holds the id of the pentomino filling it, or 0 if empty. Real board is 10X6; one additional line and col, full of -1, to simplify the algorithm for print_solution() */ const COLUMNS = 10, ROWS = 6; int board[11][7] = { {0, 0, 0, 0, 0, 0, -1}, {0, 0, 0, 0, 0, 0, -1}, {0, 0, 0, 0, 0, 0, -1}, {0, 0, 0, 0, 0, 0, -1}, {0, 0, 0, 0, 0, 0, -1}, {0, 0, 0, 0, 0, 0, -1}, {0, 0, 0, 0, 0, 0, -1}, {0, 0, 0, 0, 0, 0, -1}, {0, 0, 0, 0, 0, 0, -1}, {0, 0, 0, 0, 0, 0, -1}, {-1, -1, -1, -1, -1, -1, -1}}; /* pentominos are numbered from 1 to 12. Each of them holds an array of 1 to 8 permutations, where each permutation is an array of 4 XY offsets from the (0, 0) position. */ typedef struct {int x, y;} Loc; typedef struct { int on_board; /* boolean flag */ int perm_count; Loc perm[8][4]; } Pentomino; Pentomino pentomino[13] = { {FALSE, 0, {0}}, /* fake pentomino */ {FALSE, 1, {{{-1, 1}, {0, 1}, {1, 1}, {0, 2}}}}, /* "X" pentomino */ {FALSE, 2, {{{1, 0}, {2, 0}, {3, 0}, {4, 0}}, /* "I" pentomino */ {{0, 1}, {0, 2}, {0, 3}, {0, 4}}}}, {FALSE, 4, {{{1, 0}, {2, 0}, {1, 1}, {1, 2}}, /* "T" pentomino */ {{-2, 1}, {-1, 1}, {0, 1}, {0, 2}}, {{0, 1}, {0, 2}, {-1, 2}, {1, 2}}, {{0, 1}, {0, 2}, {1, 1}, {2, 1}}}}, {FALSE, 4, {{{1, 0}, {2, 0}, {0, 1}, {0, 2}}, /* "V" pentomino */ {{1, 0}, {2, 0}, {2, 1}, {2, 2}}, {{0, 1}, {0, 2}, {-1, 2}, {-2, 2}}, {{0, 1}, {0, 2}, {1, 2}, {2, 2}}}}, {FALSE, 4, {{{-1, 2}, {-1, 1}, {0, 1}, {1, 0}}, /* "W" pentomino */ {{1, 0}, {1, 1}, {2, 1}, {2, 2}}, {{0, 1}, {-1, 1}, {-1, 2}, {-2, 2}}, {{0, 1}, {1, 1}, {1, 2}, {2, 2}}}}, {FALSE, 4, {{{0, 1}, {1, 0}, {2, 0}, {2, 1}}, /* "U" pentomino */ {{1, 0}, {1, 1}, {1, 2}, {0, 2}}, {{0, 1}, {1, 1}, {2, 1}, {2, 0}}, {{0, 1}, {0, 2}, {1, 2}, {1, 0}}}}, {FALSE, 8, {{{0, 1}, {0, 2}, {-1, 1}, {-1, 2}}, /* "P" pentomino */ {{0, 1}, {1, 0}, {1, 1}, {2, 1}}, {{0, 1}, {0, 2}, {1, 0}, {1, 1}}, {{1, 0}, {1, 1}, {2, 0}, {2, 1}}, {{0, 1}, {0, 2}, {1, 1}, {1, 2}}, {{0, 1}, {1, 0}, {1, 1}, {2, 0}}, {{0, 1}, {1, 0}, {1, 1}, {1, 2}}, {{0, 1}, {-1, 1}, {1, 0}, {1, 1}}}}, {FALSE, 8, {{{0, 1}, {-1, 1}, {0, 2}, {1, 2}}, /* "F" pentomino */ {{0, 1}, {-1, 1}, {-1, 2}, {-2, 1}}, {{1, 0}, {1, 1}, {1, 2}, {2, 1}}, {{0, 1}, {1, 1}, {-1, 1}, {-1, 2}}, {{0, 1}, {0, 2}, {-1, 2}, {1, 1}}, {{0, 1}, {1, 1}, {1, 2}, {2, 1}}, {{0, 1}, {-1, 1}, {0, 2}, {1, 0}}, {{0, 1}, {-1, 1}, {1, 1}, {1, 2}}}}, {FALSE, 8, {{{0, 1}, {0, 2}, {1, 2}, {0, 3}}, /* "Y" pentomino */ {{1, 0}, {1, 1}, {2, 0}, {3, 0}}, {{0, 1}, {-1, 1}, {0, 2}, {0, 3}}, {{0, 1}, {-1, 1}, {-2, 1}, {1, 1}}, {{0, 1}, {0, 2}, {-1, 2}, {0, 3}}, {{0, 1}, {-1, 1}, {1, 1}, {2, 1}}, {{0, 1}, {1, 1}, {0, 2}, {0, 3}}, {{1, 0}, {2, 0}, {2, 1}, {3, 0}}}}, {FALSE, 8, {{{0, 1}, {0, 2}, {0, 3}, {1, 0}}, /* "L" pentomino */ {{1, 0}, {2, 0}, {3, 0}, {3, 1}}, {{0, 1}, {0, 2}, {0, 3}, {-1, 3}}, {{0, 1}, {1, 1}, {2, 1}, {3, 1}}, {{1, 0}, {1, 1}, {1, 2}, {1, 3}}, {{0, 1}, {-1, 1}, {-2, 1}, {-3, 1}}, {{0, 1}, {0, 2}, {0, 3}, {1, 3}}, {{0, 1}, {1, 0}, {2, 0}, {3, 0}}}}, {FALSE, 4, {{{1, 0}, {1, 1}, {1, 2}, {2, 2}}, /* "Z" pentomino */ {{0, 1}, {-1, 1}, {-2, 1}, {-2, 2}}, {{0, 1}, {0, 2}, {-1, 2}, {1, 0}}, {{0, 1}, {1, 1}, {2, 1}, {2, 2}}}}, {FALSE, 8, {{{0, 1}, {0, 2}, {-1, 2}, {-1, 3}}, /* "S" pentomino */ {{1, 0}, {1, 1}, {2, 1}, {3, 1}}, {{0, 1}, {-1, 1}, {-1, 2}, {-1, 3}}, {{1, 0}, {2, 0}, {2, 1}, {3, 1}}, {{0, 1}, {0, 2}, {1, 2}, {1, 3}}, {{0, 1}, {-1, 1}, {1, 0}, {2, 0}}, {{0, 1}, {1, 1}, {1, 2}, {1, 3}}, {{0, 1}, {-1, 1}, {-2, 1}, {1, 0}}}} }; /* so pentomino[i].perm[j][k].x gives the x location of the kth square of the ith pentomino in permutation j NOTE: pentomino[0] is a fake pentomino, with perm_count==0; used to init the place_next_piece() loop */ /* Stack to remember which pentominos were placed on board so far */ struct placed_info { int pentomino_id; int perm_no; int loc_x; int loc_y; } placed_stack[12] = {{0, 0, 0, 0}}; int nplaced = 0; int nsolutions = 0; int monitoring = FALSE; void print_board() { int x, y, i; static char* borders[] = {" ", " |", "__", "_|"}; printf("\n"); for (x=0; x= COLUMNS) x = 0, y++; } while (board[x][y]); /* while cell not empty */ c = check_connect(x, y); clean_connect(); if ((c % 5) != 0) /* remaining connected cells are not */ break; /* a multiple of 5; so abort this try */ placed_stack[nplaced].loc_x = x; placed_stack[nplaced].loc_y = y; placed_stack[nplaced].pentomino_id = 0; } } } while (remove_top_piece()); } int remove_top_piece() { int i; struct placed_info *p; Loc *perm; if (nplaced == 0) return FALSE; /* no more pieces to be removed */ nplaced--; p = &placed_stack[nplaced]; perm = pentomino[p->pentomino_id].perm[p->perm_no]; board[p->loc_x][p->loc_y] = 0; /* remove from board */ for (i=0; i<4; i++) board[p->loc_x + perm[i].x] [p->loc_y + perm[i].y] = 0; pentomino[p->pentomino_id].on_board = FALSE; if (monitoring) { printf("\b\b\b\b\b\b \b\b\b\b\b\b"); fflush(stdout); } return TRUE; } int place_next_piece() /* permute current pentomino, or find a new pentomino, to be placed at current location (placed_stack[nplaced].loc_x/y). Tries permutations and pentominos in increasing order from current perm_no and pentomino_id. Returns FALSE if no pentomino could be placed. */ { int i; struct placed_info *p = &placed_stack[nplaced]; Loc *perm; NEXT_PERMUTATION: p->perm_no++; if (p->perm_no >= pentomino[p->pentomino_id].perm_count) { /* no next permutation, try to find new pentomino */ p->perm_no = 0; do { if (++p->pentomino_id > 12) return FALSE; /* no more pentomino to be tried */ } while (pentomino[p->pentomino_id].on_board); } perm = pentomino[p->pentomino_id].perm[p->perm_no]; /* try to fit current pentomino in current permutation at current location */ for (i=0; i<4; i++) { int x = p->loc_x + perm[i].x; int y = p->loc_y + perm[i].y; if ((x < 0) || (x >= COLUMNS) || (y < 0) || (y >= ROWS)) goto NEXT_PERMUTATION; /* failed, out of bounds */ else if (board[x][y]) goto NEXT_PERMUTATION; /* failed, cell not empty */ } /* succeeded, update board */ board[p->loc_x][p->loc_y] = p->pentomino_id; for (i=0; i<4; i++) board[p->loc_x + perm[i].x] [p->loc_y + perm[i].y] = p->pentomino_id; pentomino[p->pentomino_id].on_board = TRUE; if (monitoring) { printf("%3d(%1d)", p->pentomino_id, p->perm_no);fflush(stdout); } return ++nplaced; } const MARK = -2; int check_connect(int x, int y) { if (x < 0) return 0; if (y < 0) return 0; if (board[x][y]) return 0; board[x][y] = MARK; return 1 + check_connect(x-1, y) + check_connect(x, y-1) + check_connect(x+1, y) + check_connect(x, y+1); } void clean_connect() { int x, y; for (x = 0; x < COLUMNS; x++) for (y = 0; y < ROWS; y++) if (board[x][y] == MARK) board[x][y] = 0; } #ifndef NO_INTERACTION struct sgttyb initial_sgttyb; int initial_flags; void handler(), setup(), byebye(); void byebye() { ioctl(0, TIOCSETP, &initial_sgttyb); fcntl(0, F_SETFL, initial_flags); printf("\n"); exit(0); } void setup() { struct sgttyb sgttyb; ioctl(0, TIOCGETP, &sgttyb); initial_sgttyb = sgttyb; /* remember initial settings */ sgttyb.sg_flags |= CBREAK; /* process input chars before */ sgttyb.sg_flags &= ~ECHO; /* no echo */ ioctl(0, TIOCSETP, &sgttyb); initial_flags = fcntl(0, F_GETFL); fcntl(0, F_SETFL, initial_flags | FASYNC); /* enable SIGIO */ signal(SIGIO, handler); /* handle input chars */ signal(SIGINT, byebye); signal(SIGQUIT, byebye); } void handler() { char c; read(0, &c, 1); switch (c) { case 'h': case 'H': case '?': printf("\nI am computing solutions for the pentomino puzzle\n"); printf("Commands: P(rint current board, T(oggle monitoring, E(xit\n"); break; case 'b': case 'B': case 'p': case 'P': print_board(); break; case 'q': case 'Q': case 'e': case 'E': byebye(); case 'm': case 'M': case 't': case 'T': monitoring = ! monitoring; printf("\nMonitoring is %s\n", monitoring? "ON" : "OFF"); break; default: putchar('\07'); fflush(stdout); break; } if (monitoring) { int i; for (i = 0; i < nplaced; i++) printf("%3d(%1d)", placed_stack[i].pentomino_id, placed_stack[i].perm_no); fflush(stdout); } }; main() { setup(); find_solutions(); byebye(); } #else main() { find_solutions(); } #endif