001: /*
002: 
003:   File: Piece.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: 
027: #define NUM_PCS 12
028: #define START 4
029: #define NUM_BITS 60
030: #define NUM_HI_BITS 32
031: #define NUM_LO_BITS 32
032: #include "piecePositions.h"
033: 
034: 
035: int partMask[] = {
036:   1, 1<<1, 1<<2, 1<<3, 1<<4, 1<<5, 1<<6, 1<<7, 1<<8, 1<<9, 1<<10, 1<<11, 1<<11
037: };
038: int allParts = (1<<12)-1;
039: 
040: int partsUsed = 0;
041: int numSolutions = 0;
042: 
043: int counter = 0;
044: int percent = 0;
045: 
046: clock_t startTime;
047: 
048: 
049: extern void doSolve(int start, long long startMask, long long puzzle, int partsUsed);
050: extern void altDoSolve(int start, long long startMask, long long puzzle, int partsUsed);
051: 
052: extern void doSolve32(int start, int startMask, int puzzle, int partsUsed);
053: extern void altDoSolve32(int start, int startMask, int puzzle, int partsUsed);
054: 
055: 
056: #define placePiece(pieceNo, start, startMask, puzzle, partsUsed, size)                            \
057: {                                                                                                 \
058:   for (j= 0; j < positionIndex##size[pieceNo][start]; j++) {                                  \
059:     if(!(puzzle & positions##size[pieceNo][start][j]))                                            \
060:       doSolve##size(start+1, startMask<<1, puzzle | positions##size[pieceNo][start][j],           \
061:                     partsUsed | partMask[pieceNo]);                                               \
062:   }                                                                                               \
063: }
064: 
065: 
066: 
067: void doSolve(int start, long long startMask, long long puzzle, int partsUsed)
068: {
069:   int j;
070: 
071:   for (;(puzzle & startMask) && start < NUM_LO_BITS; start++, startMask <<= 1);
072: 
073:   if(start == NUM_LO_BITS) {
074:     doSolve32(0, 1, puzzle>>NUM_LO_BITS, partsUsed);
075:     return;
076:   }
077: 
078: /*   counter++; */
079: 
080:  piece1:
081:   if (partsUsed & partMask[1]) goto piece2;
082:   placePiece(1, start, startMask, puzzle, partsUsed,);
083:  piece2:
084:   if (partsUsed & partMask[2]) goto piece3;
085:   placePiece(2, start, startMask, puzzle, partsUsed,);
086:  piece3:
087:   if (partsUsed & partMask[3]) goto piece4;
088:   placePiece(3, start, startMask, puzzle, partsUsed,);
089:  piece4:
090:   if (partsUsed & partMask[4]) goto piece5;
091:   placePiece(4, start, startMask, puzzle, partsUsed,);
092:  piece5:
093:   if (partsUsed & partMask[5]) goto piece6;
094:   placePiece(5, start, startMask, puzzle, partsUsed,);
095:  piece6:
096:   if (partsUsed & partMask[6]) goto piece7;
097:   placePiece(6, start, startMask, puzzle, partsUsed,);
098:  piece7:
099:   if (partsUsed & partMask[7]) goto piece8;
100:   placePiece(7, start, startMask, puzzle, partsUsed,);
101:  piece8:
102:   if (partsUsed & partMask[8]) goto piece9;
103:   placePiece(8, start, startMask, puzzle, partsUsed,);
104:  piece9:
105:   if (partsUsed & partMask[9]) goto piece10;
106:   placePiece(9, start, startMask, puzzle, partsUsed,);
107:  piece10:
108:   if (partsUsed & partMask[10]) goto piece11;
109:   placePiece(10, start, startMask, puzzle, partsUsed,);
110:  piece11:
111:   if(!(partsUsed & partMask[11]))
112:     placePiece(11, start, startMask, puzzle, partsUsed,);
113:      
114: }
115: 
116: 
117: 
118: 
119: void doSolve32(int start, int startMask, int puzzle, int partsUsed)
120: {
121:   int j;
122: 
123:   if(partsUsed == allParts) {
124:     if(!(++numSolutions%4099)) { write(0, ".", 1); }
125:     if(!((numSolutions) % (409963/10))) {
126:       percent++;
127:       printf("\r%d%% done, %ld seconds so far; expecting %ld seconds.\n", 
128:              percent*10, (clock()-startTime)/1000000, (clock()-startTime)/100000/percent);
129:       fflush(stdout);
130:     }
131:     return;
132:   }
133: 
134:   for (;(puzzle & startMask) && start < NUM_BITS; start++, startMask <<= 1);
135: 
136: /*   counter++; */
137: 
138:  piece32_1:
139:   if (partsUsed & partMask[1]) goto piece32_2;
140:   placePiece(1, start, startMask, puzzle, partsUsed, 32);
141:  piece32_2:
142:   if (partsUsed & partMask[2]) goto piece32_3;
143:   placePiece(2, start, startMask, puzzle, partsUsed, 32);
144:  piece32_3:
145:   if (partsUsed & partMask[3]) goto piece32_4;
146:   placePiece(3, start, startMask, puzzle, partsUsed, 32);
147:  piece32_4:
148:   if (partsUsed & partMask[4]) goto piece32_5;
149:   placePiece(4, start, startMask, puzzle, partsUsed, 32);
150:  piece32_5:
151:   if (partsUsed & partMask[5]) goto piece32_6;
152:   placePiece(5, start, startMask, puzzle, partsUsed, 32);
153:  piece32_6:
154:   if (partsUsed & partMask[6]) goto piece32_7;
155:   placePiece(6, start, startMask, puzzle, partsUsed, 32);
156:  piece32_7:
157:   if (partsUsed & partMask[7]) goto piece32_8;
158:   placePiece(7, start, startMask, puzzle, partsUsed, 32);
159:  piece32_8:
160:   if (partsUsed & partMask[8]) goto piece32_9;
161:   placePiece(8, start, startMask, puzzle, partsUsed, 32);
162:  piece32_9:
163:   if (partsUsed & partMask[9]) goto piece32_10;
164:   placePiece(9, start, startMask, puzzle, partsUsed, 32);
165:  piece32_10:
166:   if (partsUsed & partMask[10]) goto piece32_11;
167:   placePiece(10, start, startMask, puzzle, partsUsed, 32);
168:  piece32_11:
169:   if(!(partsUsed & partMask[11]))
170:     placePiece(11, start, startMask, puzzle, partsUsed, 32);
171:      
172: }
173: 
174: 
175: 
176: #define placeAltPiece(pieceNo, start, startMask, puzzle, partsUsed, size)                    \
177: {                                                                                            \
178:   for (j= 0; j < positionIndex##size[pieceNo][start]; j++) {                                 \
179:     if(!(puzzle & positions##size[pieceNo][start][j]))                                       \
180:       altDoSolve##size(start+1, startMask<<1, puzzle | positions##size[pieceNo][start][j],   \
181:                  partsUsed | partMask[pieceNo]);                                             \
182:   }                                                                                          \
183: }
184: 
185: 
186: 
187: void altDoSolve32(int start, int startMask, int puzzle, int partsUsed)
188: {
189:   int j;
190:   if(partsUsed == allParts) {
191:     if(!(++numSolutions%4099))  { write(0, ".", 1); }
192:     if(!((numSolutions) % (409963/10))) {
193:       percent++;
194:       printf("\r%d%% done, %ld seconds so far; expecting %ld seconds.\n", 
195:              percent*10, (clock()-startTime)/1000000, (clock()-startTime)/100000/percent);
196:       fflush(stdout);
197:     }
198:     return;
199:   }
200: 
201:   for (;(puzzle & startMask) && start < NUM_BITS; start++, startMask <<= 1);
202: 
203: /*   counter++; */
204: 
205:  altPiece32_1:
206:   if (partsUsed & partMask[1]) goto altPiece32_2;
207:   placeAltPiece(1, start, startMask, puzzle, partsUsed, 32);
208:  altPiece32_2:
209:   if (partsUsed & partMask[2]) goto altPiece32_3;
210:   placeAltPiece(2, start, startMask, puzzle, partsUsed, 32);
211:  altPiece32_3:
212:   if (partsUsed & partMask[3]) goto altPiece32_4;
213:   placeAltPiece(3, start, startMask, puzzle, partsUsed, 32);
214:  altPiece32_4:
215:   if (partsUsed & partMask[4]) goto altPiece32_5;
216:   placeAltPiece(4, start, startMask, puzzle, partsUsed, 32);
217:  altPiece32_5:
218:   if (partsUsed & partMask[5]) goto altPiece32_6;
219:   placeAltPiece(5, start, startMask, puzzle, partsUsed, 32);
220:  altPiece32_6:
221:   if (partsUsed & partMask[6]) goto altPiece32_7;
222:   placeAltPiece(6, start, startMask, puzzle, partsUsed, 32);
223:  altPiece32_7:
224:   if (partsUsed & partMask[7]) goto altPiece32_8;
225:   placeAltPiece(7, start, startMask, puzzle, partsUsed, 32);
226:  altPiece32_8:
227:   if (partsUsed & partMask[8]) goto altPiece32_9;
228:   placeAltPiece(8, start, startMask, puzzle, partsUsed, 32);
229:  altPiece32_9:
230:   if (partsUsed & partMask[9]) goto altPiece32_10;
231:   placeAltPiece(9, start, startMask, puzzle, partsUsed, 32);
232:  altPiece32_10:
233:   if (partsUsed & partMask[10]) goto altPiece32_12;
234:   placeAltPiece(10, start, startMask, puzzle, partsUsed, 32);
235:  altPiece32_12:
236:   if(!(partsUsed & partMask[12]))
237:     placeAltPiece(12, start, startMask, puzzle, partsUsed, 32);
238:      
239: }
240: 
241: 
242: 
243: void altDoSolve(int start, long long startMask, long long puzzle, int partsUsed)
244: {
245:   int j;
246: 
247:   for (;(puzzle & startMask) && start < NUM_LO_BITS; start++, startMask <<= 1);
248: 
249:   if(start == NUM_LO_BITS){
250:     altDoSolve32(0, 1, puzzle>>NUM_LO_BITS, partsUsed);
251:     return;
252:   }
253: 
254: /*   counter++; */
255: 
256:  altPiece1:
257:   if (partsUsed & partMask[1]) goto altPiece2;
258:   placeAltPiece(1, start, startMask, puzzle, partsUsed,);
259:  altPiece2:
260:   if (partsUsed & partMask[2]) goto altPiece3;
261:   placeAltPiece(2, start, startMask, puzzle, partsUsed,);
262:  altPiece3:
263:   if (partsUsed & partMask[3]) goto altPiece4;
264:   placeAltPiece(3, start, startMask, puzzle, partsUsed,);
265:  altPiece4:
266:   if (partsUsed & partMask[4]) goto altPiece5;
267:   placeAltPiece(4, start, startMask, puzzle, partsUsed,);
268:  altPiece5:
269:   if (partsUsed & partMask[5]) goto altPiece6;
270:   placeAltPiece(5, start, startMask, puzzle, partsUsed,);
271:  altPiece6:
272:   if (partsUsed & partMask[6]) goto altPiece7;
273:   placeAltPiece(6, start, startMask, puzzle, partsUsed,);
274:  altPiece7:
275:   if (partsUsed & partMask[7]) goto altPiece8;
276:   placeAltPiece(7, start, startMask, puzzle, partsUsed,);
277:  altPiece8:
278:   if (partsUsed & partMask[8]) goto altPiece9;
279:   placeAltPiece(8, start, startMask, puzzle, partsUsed,);
280:  altPiece9:
281:   if (partsUsed & partMask[9]) goto altPiece10;
282:   placeAltPiece(9, start, startMask, puzzle, partsUsed,);
283:  altPiece10:
284:   if (partsUsed & partMask[10]) goto altPiece12;
285:   placeAltPiece(10, start, startMask, puzzle, partsUsed,);
286:  altPiece12:
287:   if(!(partsUsed & partMask[12]))
288:     placeAltPiece(12, start, startMask, puzzle, partsUsed,);
289:      
290: }
291: 
292: 
293: 
294: int solve()
295: {
296:   int usePiece = 0;
297:   int i;
298: 
299:   for(i=0; i < 8; i++)
300:     doSolve(4, 1<<4, piece0Positions[i] << 4, partMask[usePiece]);
301:   
302:   for(i=8; i < piece0NumPositions; i++)
303:     altDoSolve(4, 1<<4, piece0Positions[i] << 4, partMask[usePiece]);
304: 
305:   return 0;
306: }
307: 
308: 
309: 
310: 
311: 
312: 
313: 
314: int main(int argc, char**argv)
315: {
316:   clock_t startTime = clock();
317: 
318:   solve();
319: 
320:   printf("\ndone. %ld seconds, %ld solutions.\n", 
321:          (clock()-startTime)/1000000, numSolutions);
322: 
323: /*   printf("\ndone. %ld seconds, %ld solutions, %ld tries.\n",  */
324: /* 	 (clock()-startTime)/1000000, numSolutions, counter); */
325: 
326: }