Solution #16008 ********** *KKKLCCEE* *KGKLCCED* *GGGLLEED* *GHHHLJDD* *BIHMJJJD* *BIHMMJFF* *BIIIMMFF* *BBAAAAAF* ********** 223887 seconds Solution #16009 ********** *KKKLCCEE* *KMKLCCEI* *AMMLLEEI* *AGMMLIII* *AGGGBBBB* *AHGJBFFF* *AHJJJDFF* *HHHJDDDD* ********** 223892 secondsLet me share the source code with you, but if you want to improve your programming skills you should work on it yourself.
#include <iostream> #include <vector> #include <fstream> #include <time.h> #include <string> using namespace std; const int numPieces = 13; const int numTrans = 8; const int numRows = 5; const int numCols = 5; const int boardWidth = 10; const int boardHeight = 10; clock_t start = clock(); char board[boardHeight][boardWidth]; struct array { char acc[numRows][numCols]; }; void outputBoard(); void init(char[numRows][numCols]); bool allUnprintable(string s); void setEqual(char[numRows][numCols], char[numRows][numCols]); bool sameArray(array, char[numRows][numCols]); bool repeated(vector<array>, char[numRows][numCols]); void arrayInit(array&, char[numRows][numCols]); bool impasse(char[boardHeight][boardWidth]); void solve(int); class Trans { public: char pattern[numRows][numCols]; char id; Trans(); Trans(char[numRows][numCols]); bool place(int, int); void clear(); }; /* precondition: none postcondition: default constructor */ Trans::Trans() { init(pattern); id = \'@\'; } /* precondition: cc should contain the pattern postcondition: assign proper values to pattern[][] and id */ Trans::Trans(char cc[numRows][numCols]) { int r, c; for(r=0; r<numRows; r++) for(c=0; c<numCols; c++) { if(cc[r][c]!=\' \') id = cc[r][c]; pattern[r][c] = cc[r][c]; } } /* precondition: r and c must be >= 0 postcondition: do nothing and return false if the invoking pattern doesn\'t fit in the given position; place the invoking pattern in the given location and return true if the invoking pattern fits */ bool Trans::place(int r, int c) { int rr, cc; for(rr=0; rr<numRows; rr++) for(cc=0; cc<numCols; cc++) if(pattern[rr][cc] != \' \') if(rr+r>8 || cc+c>8 || board[rr+r][cc+c]!=\' \') return false; for(rr=0; rr<numRows; rr++) for(cc=0; cc<numCols; cc++) if(pattern[rr][cc] != \' \') board[rr+r][cc+c] = pattern[rr][cc]; return true; } /* precondition: none postcondition: clear out the spots occupied by the invoking pattern */ void Trans::clear() { int r, c, i = 0; for(r=boardHeight-1; r>=0; r--) for(c=boardWidth-1; c>=0; c--) if (board[r][c]==id) { board[r][c] = \' \'; if(++i==numRows) return; } } class Piece { public: Trans *patterns[numTrans]; int count; Piece(); Piece(char[numRows][numCols]); void transpose(char[numRows][numCols]); void rotate90(char[numRows][numCols]); }; Piece *pieces[numPieces]; /* precondition: none postcondition: default constructor */ Piece::Piece() { int i; for(i=0; i<numTrans; i++) patterns[i] = NULL; count = -1; } /* precondition: cc should contain the pattern postcondition: find and store all orientations of the pattern in Trans */ Piece::Piece(char cc[numRows][numCols]) { int i, currIndex; vector<array> va; array ar; va.clear(); arrayInit(ar, cc); va.push_back(ar); patterns[0] = new Trans(cc); currIndex = 1; for(i=0; i<3; i++) { rotate90(cc); if(!repeated(va, cc)) { arrayInit(ar, cc); va.push_back(ar); patterns[currIndex] = new Trans(cc); ++currIndex; } } rotate90(cc); transpose(cc); if(!repeated(va, cc)) { arrayInit(ar, cc); va.push_back(ar); patterns[currIndex] = new Trans(cc); ++currIndex; } for(i=0; i<3; i++) { rotate90(cc); if(!repeated(va, cc)) { arrayInit(ar, cc); va.push_back(ar); patterns[currIndex] = new Trans(cc); ++currIndex; } } count = currIndex; } /* precondition: cc may contain anything postcondition: transpose the pattern in cc */ void Piece::transpose(char cc[numRows][numCols]) { char tempcc[numRows][numCols]; int r, c; init(tempcc); for(r=0; r<numRows; r++) for(c=0; c<numCols; c++) tempcc[r][c] = cc[c][r]; setEqual(cc, tempcc); } /* precondition: cc may contain anything postcondition: rotate the pattern in cc by 90 degrees counterclockwise */ void Piece::rotate90(char cc[numRows][numCols]) { int r, c, offset; bool found = false; char tempcc[numRows][numCols]; offset = -1; for(c=numCols-1; c>=0 && !found; c--) for(r=numRows-1; r>=0; r--) if(cc[r][c]!=\' \') { offset = numCols - c - 1; found = true; break; } if(offset==-1) return; init(tempcc); for(r=0; r<numRows; r++) for(c=0; c<numCols; c++) if(numCols-c-1-offset>=0 && cc[r][c]!=\' \') tempcc[numCols-c-1-offset][r] = cc[r][c]; setEqual(cc, tempcc); } int main(int argc, char **argv) { if(argc!=2) { cout << 'usage: <exe> <file> '; cout << '<exe>: the executable of the program '; cout << '<file>: the file that contains all pieces '; exit(1); } int i, r, c; ifstream fin; char tempcc[numRows][numCols], letter; string temps; fin.open(argv[1]); if(!fin.is_open()) { cout << argv[1] << ' cannot be opened, forced exit '; exit(2); } init(tempcc); letter = \'A\'; for(i=0; i<numPieces; i++) { r = 0; while(true) { getline(fin, temps, \' \'); if(!fin) break; if(allUnprintable(temps)) break; for (c=0; c<numCols; c++) { if(temps[c]==\'\') break; else if(temps[c]==\'#\') tempcc[r][c] = letter; } r++; } pieces[i] = new Piece(tempcc); init(tempcc); letter++; } fin.close(); for(r=0; r<boardHeight; r++) for (c=0; c<boardWidth; c++) board[r][c] = \' \'; for(c=0; c<boardWidth; c++) { board[0][c] = \'*\'; board[boardHeight-1][c] = \'*\'; } for(r=1; r<boardHeight-1; r++) { board[r][0] = \'*\'; board[r][boardWidth-1] = \'*\'; } solve(0); return 0; } /* precondition: none postcondition: displays the current board onscreen */ void outputBoard() { int r, c; for(r=0; r<boardHeight; r++) { for(c=0; c<boardWidth; c++) cout << board[r][c]; cout << endl; } } /* precondition: none postcondition: make every element in the array a space */ void init(char cc[numRows][numCols]) { int r, c; for(r=0; r<numRows; r++) for(c=0; c<numCols; c++) cc[r][c] = \' \'; } /* precondition: none postcondition: return true if s doesn\'t contain \'#\'; return false otherwise */ bool allUnprintable(string s) { int i; for(i=0; i<s.length(); i++) if(s[i]==\'#\') return false; return true; } /* precondition: none postcondition: set the contents of cc equal to those of cc2 */ void setEqual(char cc[numRows][numCols], char cc2[numRows][numCols]) { int r, c; for(r=0; r<numRows; r++) for(c=0; c<numCols; c++) cc[r][c] = cc2[r][c]; } /* precondition: none postcondition: return true if the contents of a are identical to cc; return false otherwise */ bool sameArray(array a, char cc[numRows][numCols]) { int r, c; for(r=0; r<numRows; r++) for(c=0; c<numCols; c++) if(a.acc[r][c]!=cc[r][c]) return false; return true; } /* precondition: none postcondition: return true if cc exists in va; return false otherwise */ bool repeated(vector<array> va, char cc[numRows][numCols]) { int i; for(i=0; i<va.size(); i++) if(sameArray(va[i], cc)) return true; return false; } /* precondition: none postcondition: make the contents of ar equal to cc */ void arrayInit(array & ar, char cc[numRows][numCols]) { int r, c; for(r=0; r<numRows; r++) for(c=0; c<numCols; c++) ar.acc[r][c] = cc[r][c]; } /* precondition: boardHeight and boardWidth must both be 10 postcondition: return true if current board must lead to an impasse; return false otherwise */ bool impasse(char b[boardHeight][boardWidth]) { for (int i = 1; i < 9; i++) { for (int j = 1; j < 9; j++) { //cases where there\'s one unfillable pocket if (b[i-1][j]!=\' \'&&b[i][j-1]!=\' \'&&b[i][j+1]!=\' \'&&b[i+1][j]!=\' \') if (b[i][j] == \' \') return true; //cases where there\'s two unfillable pockets, horizontally if (j < 8) if (b[i-1][j]!=\' \'&&b[i-1][j+1]!=\' \'&&b[i][j+2]!=\' \'&&b[i+1][j+1]!=\' \' &&b[i+1][j]!=\' \'&&b[i][j-1]!=\' \') if (b[i][j]==\' \'&&b[i][j+1]==\' \') return true; //cases where there\'s three unfillable pockets, horizontally if (j < 7) if (b[i-1][j]!=\' \'&&b[i-1][j+1]!=\' \'&&b[i-1][j+2]!=\' \'&&b[i][j+3]!=\' \' &&b[i+1][j+2]!=\' \'&&b[i+1][j+1]!=\' \'&&b[i+1][j]!=\' \'&&b[i][j-1]!=\' \') if (b[i][j]==\' \'&&b[i][j+1]==\' \'&&b[i][j+2]==\' \') return true; //cases where there\'s four unfillable pockets, horizontally if (j < 6) if (b[i-1][j]!=\' \'&&b[i-1][j+1]!=\' \'&&b[i-1][j+2]!=\' \'&&b[i-1][j+3]!=\' \' &&b[i][j+4]!=\' \'&&b[i+1][j+3]!=\' \'&&b[i+1][j+2]!=\' \'&&b[i+1][j+1]!=\' \' &&b[i+1][j]!=\' \'&&b[i][j-1]!=\' \') if (b[i][j]==\' \'&&b[i][j+1]==\' \'&&b[i][j+2]==\' \'&&b[i][j+3]==\' \') return true; //cases where there\'s two unfillable pockets, vertically if (i < 8) if (b[i-1][j]!=\' \'&&b[i][j+1]!=\' \'&&b[i+1][j+1]!=\' \'&&b[i+2][j]!=\' \' &&b[i][j-1]!=\' \'&&b[i+1][j-1]!=\' \') if (b[i][j]==\' \'&&b[i+1][j]==\' \') return true; //cases where there\'s three unfillable pockets, vertically if (i < 7) if (b[i-1][j]!=\' \'&&b[i][j+1]!=\' \'&&b[i+1][j+1]!=\' \'&&b[i+2][j+1]!=\' \' &&b[i+3][j]!=\' \'&&b[i][j-1]!=\' \'&&b[i+1][j-1]!=\' \'&&b[i+2][j-1]!=\' \') if (b[i][j]==\' \'&&b[i+1][j]==\' \'&&b[i+2][j]==\' \') return true; //cases where there\'s four unfillable pockets, vertically if (i < 6) if (b[i-1][j]!=\' \'&&b[i][j+1]!=\' \'&&b[i+1][j+1]!=\' \'&&b[i+2][j+1]!=\' \' &&b[i+3][j+1]!=\' \'&&b[i+4][j]!=\' \'&&b[i][j-1]!=\' \'&&b[i+1][j-1]!=\' \' &&b[i+2][j-1]!=\' \'&&b[i+3][j-1]!=\' \') if (b[i][j]==\' \'&&b[i+1][j]==\' \'&&b[i+2][j]==\' \'&&b[i+3][j]==\' \') return true; } } return false; } /* precondition: n must be initially 0 postcondition: searches and displays solutions until all solutions are found */ void solve(int n) { if (n==numPieces) { outputBoard(); cout << (float)(clock() - start) / CLOCKS_PER_SEC << ' seconds' << endl; return; } Piece* temp = pieces[n]; int r, c, counter; for (counter=0; counter<temp->count; ++counter) for (r=1; r<boardHeight-1; r++) for (c=1; c<boardWidth-1; c++) if (temp->patterns[counter]->place(r, c)) { if (!impasse(board)) solve(n+1); temp->patterns[counter]->clear(); } }I thought only a couple of solutions existed because it seems so difficult to find one.