001:
002:
003:
004:
005:
006:
007:
008:
009:
010:
011:
012:
013:
014:
015:
016:
017:
018:
019:
020:
021:
022:
023:
024: #include <stdio.h>
025: #include <time.h>
026: #include <stdlib.h>
027: #include <unistd.h>
028: #include <string.h>
029:
030: #include "Puzzle.h"
031: #include "Piece.h"
032: #include "Solver.h"
033:
034: #include "InventorWriter.h"
035:
036:
037:
038: int levelCounter[NUM_PCS] = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 };
039:
040: int Solver::partMask[] = {
041: 1, 1<<1, 1<<2, 1<<3, 1<<4, 1<<5, 1<<6, 1<<7, 1<<8, 1<<9, 1<<10, 1<<11
042: };
043:
044: int Solver::allParts = (1<<12)-1;
045:
046: int ***positionsLeft;
047: int **positionsLeftIndex;
048:
049: #define MAX_POS 32
050: #define MAX_POS_32 28
051:
052: Solver::Solver(Piece **inPieces) : partsUsed(0), currentDepth(0), numSolutions(0)
053: {
054: for (int i=0; i< NUM_PCS; i++)
055: currentPositions[i] = 0;
056: pieces = inPieces;
057:
058: }
059:
060:
061:
062:
063:
064: double counter = 0;
065: int percent = 0;
066:
067: static clock_t startTime = clock();
068:
069:
070: int Solver::solve()
071: {
072: int usePiece = 0;
073:
074: for(int i=0; i < 8; i++)
075: doSolve(4, 1<<4, (pieces[usePiece]->getPosition(i)) << 4, partMask[usePiece]);
076:
077: Piece *tmp = pieces[11];
078: pieces[11] = pieces[12];
079:
080: for(int i=8; i < pieces[usePiece]->getNumPositions(); i++)
081: doSolve(4, 1<<4, (pieces[usePiece]->getPosition(i)) << 4, partMask[usePiece]);
082:
083:
084: cout << endl << "done. " << ((double)(clock()-startTime))/1000000.0 << " seconds for "
085: << numSolutions << " solutions and " << counter << " tries." << endl;
086:
087: return 0;
088: }
089:
090:
091:
092:
093:
094:
095: void Solver::placePiece(int pieceNo, int start, long long startMask, long long puzzle, int partsUsed)
096: {
097: long long *positionList = pieces[pieceNo]->getPositions(start);
098: for (int j= 0; j < pieces[pieceNo]->getNumPositions(start); j++, positionList++) {
099: if(!(puzzle & *positionList))
100: doSolve(start+1, startMask<<1, puzzle | *positionList, partsUsed | partMask[pieceNo]);
101: }
102: }
103:
104:
105: void Solver::doSolve(int start, long long startMask, long long puzzle, int partsUsed)
106: {
107:
108: if(partsUsed == allParts) {
109: if(!(++numSolutions%1000)) {cout << "."; fflush(stdout);}
110: if(!((numSolutions) % (409963/10))) {
111: percent++;
112: cout << endl << percent*10 << "% done, " << ((double)(clock()-startTime))/1000000.0
113: << " seconds so far." << endl << " expecting "
114: << ((double)(clock()-startTime))/1000000.0*10.0/((double)percent) << " seconds."
115: << endl;
116: }
117: return;
118: }
119:
120: for (;(puzzle & startMask) && start < MAX_POS+MAX_POS_32; start++, startMask <<= 1);
121:
122: piece1:
123: if (partsUsed & partMask[1]) goto piece2;
124: placePiece(1, start, startMask, puzzle, partsUsed);
125: piece2:
126: if (partsUsed & partMask[2]) goto piece3;
127: placePiece(2, start, startMask, puzzle, partsUsed);
128: piece3:
129: if (partsUsed & partMask[3]) goto piece4;
130: placePiece(3, start, startMask, puzzle, partsUsed);
131: piece4:
132: if (partsUsed & partMask[4]) goto piece5;
133: placePiece(4, start, startMask, puzzle, partsUsed);
134: piece5:
135: if (partsUsed & partMask[5]) goto piece6;
136: placePiece(5, start, startMask, puzzle, partsUsed);
137: piece6:
138: if (partsUsed & partMask[6]) goto piece7;
139: placePiece(6, start, startMask, puzzle, partsUsed);
140: piece7:
141: if (partsUsed & partMask[7]) goto piece8;
142: placePiece(7, start, startMask, puzzle, partsUsed);
143: piece8:
144: if (partsUsed & partMask[8]) goto piece9;
145: placePiece(8, start, startMask, puzzle, partsUsed);
146: piece9:
147: if (partsUsed & partMask[9]) goto piece10;
148: placePiece(9, start, startMask, puzzle, partsUsed);
149: piece10:
150: if (partsUsed & partMask[10]) goto piece11;
151: placePiece(10, start, startMask, puzzle, partsUsed);
152: piece11:
153: if(!(partsUsed & partMask[11]))
154: placePiece(11, start, startMask, puzzle, partsUsed);
155:
156:
157:
158: }
159:
160:
161:
162: