001: /*
002: 
003:   File: Solver.cpp
004: 
005:   (c) 2003 by Oliver Ehli
006: 
007:      This program is free software; you can redistribute it and/or modify
008:      it under the terms of the GNU General Public License as published by
009:      the Free Software Foundation; either version 2 of the License, or
010:      (at your option) any later version.
011: 
012:      This program is distributed in the hope that it will be useful,
013:      but WITHOUT ANY WARRANTY; without even the implied warranty of
014:      MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
015:      GNU General Public License for more details.
016: 
017:      You should have received a copy of the GNU General Public License
018:      along with this program; if not, write to the Free Software
019:      Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
020: 
021:      See File LICENSE for more Information.
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: