001: /***************************************************************************
002:                           solve.cpp  -  description
003:                              -------------------
004:     begin                : Fri Mar 28 2003
005:     copyright            : (C) 2003 by Dominik Raddatz
006:     email                : dom@wtal.de
007:  ***************************************************************************/
008: 
009: #include "solve.h"
010: #include <pthread.h>
011: #include <stdio.h>
012: 
013: long long allPieces[57*16*16];        // Array with all pieces sorted
014: int pieceCount[57*16];
015: 
016: pthread_mutex_t fastmutex = PTHREAD_MUTEX_INITIALIZER;
017: int globalThreadSync=0;                   // Requires Mutex
018: int numberOfSolutions=0;                  // Requires Mutex
019: 
020: long long andMasks[60];
021: long long equalsMasks[60];
022: 
023: int solve()
024: {
025:   pthread_t myThreadID=1;
026:   void *nothing;
027:   pthread_create(&myThreadID, NULL, &solve12, NULL);
028:   solve12(nothing);
029:   pthread_join(myThreadID, NULL);
030:   return numberOfSolutions;
031: }
032: 
033: void permute(const long long *source, long long *target)
034: {
035:   *target=0ull;
036:   for(int i=0; i<60; ++i)
037:   {
038:     *target|=(((*source)>>permutation13[i])&1)<<i;
039:   }
040: }
041: 
042: void insert(bool box[3][4][5], int pieceIndex)
043: {
044:   long long temp, temp2;
045:   convert(box, &temp2);
046:   permute(&temp2, &temp);
047:   int firstBit=findLowestBit(temp);
048:   if(pieceIndex==11)++pieceIndex;   // Hack for 16-Positions-Alignment; piece10 and piece 11 need more space than allocated
049:   allPieces[(firstBit<<8)+(pieceIndex<<4)+pieceCount[(firstBit<<4)+pieceIndex]]=temp;
050:   ++(*(pieceCount+((firstBit<<4)+pieceIndex)));
051: }
052: 
053: void insert(const long long &indexMask, const long long &andMask, const long long &equalsMask)
054: {
055:   long long temp;
056:   permute(&indexMask, &temp);
057:   int index=findLowestBit(temp);
058:   permute(&andMask, &temp);
059:   *(andMasks+index)=temp;
060:   permute(&equalsMask, &temp);
061:   *(equalsMasks+index)=temp;
062: }
063: 
064: void convert(bool source[3][4][5], long long *target)
065: {
066:   (*target)=0ull;
067:   for(int z=0; z<5; ++z)
068:   {
069:     for(int y=0; y<4; ++y)
070:     {
071:       for(int x=0; x<3; ++x)
072:       {
073:         (*target)<<=1;
074:         (*target)|=(long long)(source[x][y][z]);
075:       }
076:     }
077:   }
078: }
079: 
080: int findLowestBit(long long piece)
081: {
082:   int i=0;
083:   while(testBit(&piece, i)==false) ++i;
084:   return i;
085: }
086: 
087: inline bool testBit(const long long *piece, const int position)
088: {
089:   return(((*piece)&(1ull<<position))!=0);
090: }
091: 
092: void initializePC()
093: {
094:   for(int i=0; i<57; ++i)
095:   {
096:     for(int j=0; j<16; ++j)
097:     {
098:       *(pieceCount+((i<<4)+j))=0;
099:     }
100:   }
101: }
102: 
103: void *solve12(void *nothing)   // Here be 2 threads...
104: {
105:   int remainingPiecesList[13]={0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 0};  // Element#12 is # of found solutions, 1 and 3 are additional space for 0 and 2
106:   int localThreadSync=0;
107:   int i, j;
108:   int pieceNumber=*remainingPiecesList;
109:   const int *pC=pieceCount;                 // [0][0]
110:   const int last=*(remainingPiecesList+11);
111:   const long long *aP=allPieces;   // [0][0][0]
112:   const long long *cP=aP;
113:   int *rpl=remainingPiecesList;
114:   *rpl=last;
115:   for(j=0; j<*pC; ++j)
116:   {
117:     ++localThreadSync;
118:     pthread_mutex_lock(&fastmutex);    //mutexStart
119:     if(localThreadSync>globalThreadSync)
120:     {
121:       globalThreadSync=localThreadSync;
122:       pthread_mutex_unlock(&fastmutex);   //mutexEnd
123:       solve11(*cP, 0, remainingPiecesList);     // Does only work in first round
124:       printf("Thread's Solutions: %d\n", remainingPiecesList[12]);
125:       ++cP;
126:     }
127:     else 
128:     {
129:       pthread_mutex_unlock(&fastmutex);    //mutexEnd
130:       ++cP;
131:     }
132:   }
133:   *rpl++=pieceNumber;
134:   for(i=1; i<12; ++i)             // Leave out piece 0
135:   {
136:     aP+=16;
137:     cP=aP;
138:     ++pC;
139:     pieceNumber=*rpl;
140:     *rpl=last;
141:     for(j=0; j<*pC; ++j)
142:     {
143:       ++localThreadSync;
144:       pthread_mutex_lock(&fastmutex);    //mutexStart
145:       if(localThreadSync>globalThreadSync)
146:       {
147:         globalThreadSync=localThreadSync;
148:         pthread_mutex_unlock(&fastmutex);   //mutexEnd
149:         solve11(*cP, 0, remainingPiecesList);
150:         printf("Thread's Solutions: %d\n", remainingPiecesList[12]);
151:         ++cP;
152:       }
153:       else
154:       {
155:         pthread_mutex_unlock(&fastmutex);    //mutexEnd
156:         ++cP;
157:       }
158:     }
159:     *(rpl++)=pieceNumber;
160:   }
161:   pthread_mutex_lock(&fastmutex);    //mutexStart
162:   numberOfSolutions+=remainingPiecesList[12];   // += here
163:   pthread_mutex_unlock(&fastmutex);   //mutexEnd
164: }
165: 
166: void solve11(const long long puzzle , int fillPosition, int remainingPiecesList[13])
167: {
168:   while(((1ull<<(++fillPosition))&puzzle)!=0); // look for first 0 entry
169:   int i, j;
170:   int pieceNumber=*remainingPiecesList;
171:   const int lastPiece=*(remainingPiecesList+10);
172:   int *rpl=remainingPiecesList;
173:   const int offsetPart=fillPosition<<4;
174:   const int * const pCfP=pieceCount+offsetPart;       // Compute offset for pieceCount
175:   const int *pC=pCfP+(*rpl);                   // get number of elements there
176:   const long long * const aPfP=(allPieces+(offsetPart<<4));   // Compute offset for to be selected pieces
177:   const long long *currentPiece=aPfP+((*rpl)<<4);
178:   *rpl=lastPiece;
179:   for(j=0; j<*pC; ++j)
180:   {
181:     if((puzzle&(*currentPiece))==0ull)
182:     {
183:       solve10(puzzle|(*currentPiece), fillPosition, remainingPiecesList);
184:     }
185:     ++currentPiece;
186:   }
187:   *(rpl++)=pieceNumber;
188:   for(i=1; i<10; ++i)
189:   {
190:     pieceNumber=*rpl;               // Save to be tested pieceNumber
191:     *rpl=lastPiece;                 // Copy last (important) element to saved position
192:     pC=pCfP+pieceNumber;            // set pieceCount to next Piece
193:     currentPiece=aPfP+(pieceNumber<<4);
194:     for(j=0; j<*pC; ++j)
195:     {
196:       if((puzzle&(*currentPiece))==0ull)
197:       {
198:         solve10(puzzle|(*currentPiece), fillPosition, remainingPiecesList);
199:       }
200:       ++currentPiece;
201:     }
202:     *(rpl++)=pieceNumber;
203:   }
204:   pC=pCfP+(*rpl);
205:   currentPiece=aPfP+((*rpl)<<4);
206:   for(j=0; j<*pC; ++j)
207:   {
208:     if((puzzle&(*currentPiece))==0ull)
209:     {
210:       solve10(puzzle|(*currentPiece), fillPosition, remainingPiecesList);
211:     }
212:     ++currentPiece;
213:   }
214: }
215: 
216: void solve10(const long long puzzle , int fillPosition, int remainingPiecesList[13])
217: {
218:   while(((1ull<<(++fillPosition))&puzzle)!=0); // look for first 0 entry
219:   int i, j;
220:   const long long *currentPiece=andMasks+fillPosition;
221:   const long long *em=equalsMasks+fillPosition;
222:   for(j=fillPosition; j<60; ++j)
223:   {
224:     if((puzzle&(*(currentPiece++)))==(*(em++)))    // Check if puzzle contains pattern
225:     {
226:       return;
227:     }
228:   }
229:   int pieceNumber=*remainingPiecesList;
230:   const int lastPiece=*(remainingPiecesList+9);
231:   int *rpl=remainingPiecesList;
232:   const int offsetPart=fillPosition<<4;
233:   const int * const pCfP=pieceCount+offsetPart;       // Compute offset for pieceCount
234:   const int *pC=pCfP+(*rpl);                   // get number of elements there
235:   const long long * const aPfP=(allPieces+(offsetPart<<4));   // Compute offset for to be selected pieces
236:   currentPiece=aPfP+((*rpl)<<4);
237:   *rpl=lastPiece;
238:   for(j=0; j<*pC; ++j)
239:   {
240:     if((puzzle&(*currentPiece))==0ull)
241:     {
242:       solve9(puzzle|(*currentPiece), fillPosition, remainingPiecesList);
243:     }
244:     ++currentPiece;
245:   }
246:   *(rpl++)=pieceNumber;
247:   for(i=1; i<9; ++i)
248:   {
249:     pieceNumber=*rpl;               // Save to be tested pieceNumber
250:     *rpl=lastPiece;                 // Copy last (important) element to saved position
251:     pC=pCfP+pieceNumber;            // set pieceCount to next Piece
252:     currentPiece=aPfP+(pieceNumber<<4);
253:     for(j=0; j<*pC; ++j)
254:     {
255:       if((puzzle&(*currentPiece))==0ull)
256:       {
257:         solve9(puzzle|(*currentPiece), fillPosition, remainingPiecesList);
258:       }
259:       ++currentPiece;
260:     }
261:     *(rpl++)=pieceNumber;
262:   }
263:   pC=pCfP+(*rpl);
264:   currentPiece=aPfP+((*rpl)<<4);
265:   for(j=0; j<*pC; ++j)
266:   {
267:     if((puzzle&(*currentPiece))==0ull)
268:     {
269:       solve9(puzzle|(*currentPiece), fillPosition, remainingPiecesList);
270:     }
271:     ++currentPiece;
272:   }
273: }
274: 
275: void solve9(const long long puzzle , int fillPosition, int remainingPiecesList[13])
276: {
277:   while(((1ull<<(++fillPosition))&puzzle)!=0); // look for first 0 entry
278:   int i, j;
279:   const long long *currentPiece=andMasks+fillPosition;
280:   const long long *em=equalsMasks+fillPosition;
281:   for(j=fillPosition; j<60; ++j)
282:   {
283:     if((puzzle&(*(currentPiece++)))==(*(em++)))    // Check if puzzle contains pattern
284:     {
285:       return;
286:     }
287:   }
288:   int pieceNumber=*remainingPiecesList;
289:   const int lastPiece=*(remainingPiecesList+8);
290:   int *rpl=remainingPiecesList;
291:   const int offsetPart=fillPosition<<4;
292:   const int * const pCfP=pieceCount+offsetPart;       // Compute offset for pieceCount
293:   const int *pC=pCfP+(*rpl);                   // get number of elements there
294:   const long long * const aPfP=allPieces+(offsetPart<<4);   // Compute offset for to be selected pieces
295:   currentPiece=aPfP+((*rpl)<<4);
296:   *rpl=lastPiece;
297:   for(j=0; j<*pC; ++j)
298:   {
299:     if((puzzle&(*currentPiece))==0ull)
300:     {
301:       solve8(puzzle|(*currentPiece), fillPosition, remainingPiecesList);
302:     }
303:     ++currentPiece;
304:   }
305:   *(rpl++)=pieceNumber;
306:   for(i=1; i<8; ++i)
307:   {
308:     pieceNumber=*rpl;               // Save to be tested pieceNumber
309:     *rpl=lastPiece;                 // Copy last (important) element to saved position
310:     pC=pCfP+pieceNumber;            // set pieceCount to next Piece
311:     currentPiece=aPfP+(pieceNumber<<4);
312:     for(j=0; j<*pC; ++j)
313:     {
314:       if((puzzle&(*currentPiece))==0ull)
315:       {
316:         solve8(puzzle|(*currentPiece), fillPosition, remainingPiecesList);
317:       }
318:       ++currentPiece;
319:     }
320:     *(rpl++)=pieceNumber;
321:   }
322:   pC=pCfP+(*rpl);
323:   currentPiece=aPfP+((*rpl)<<4);
324:   for(j=0; j<*pC; ++j)
325:   {
326:     if((puzzle&(*currentPiece))==0ull)
327:     {
328:       solve8(puzzle|(*currentPiece), fillPosition, remainingPiecesList);
329:     }
330:     ++currentPiece;
331:   }
332: }
333: 
334: void solve8(const long long puzzle , int fillPosition, int remainingPiecesList[13])
335: {
336:   while(((1ull<<(++fillPosition))&puzzle)!=0); // look for first 0 entry
337:   int i, j;
338:   const long long *currentPiece=andMasks+fillPosition;
339:   const long long *em=equalsMasks+fillPosition;
340:   for(j=fillPosition; j<60; ++j)
341:   {
342:     if((puzzle&(*(currentPiece++)))==(*(em++)))    // Check if puzzle contains pattern
343:     {
344:       return;
345:     }
346:   }
347:   int pieceNumber=*remainingPiecesList;
348:   const int lastPiece=*(remainingPiecesList+7);
349:   int *rpl=remainingPiecesList;
350:   const int offsetPart=fillPosition<<4;
351:   const int * const pCfP=pieceCount+offsetPart;       // Compute offset for pieceCount
352:   const int *pC=pCfP+(*rpl);                   // get number of elements there
353:   const long long * const aPfP=allPieces+(offsetPart<<4);   // Compute offset for to be selected pieces
354:   currentPiece=aPfP+((*rpl)<<4);
355:   *rpl=lastPiece;
356:   for(j=0; j<*pC; ++j)
357:   {
358:     if((puzzle&(*currentPiece))==0ull)
359:     {
360:       solve7(puzzle|(*currentPiece), fillPosition, remainingPiecesList);
361:     }
362:     ++currentPiece;
363:   }
364:   *(rpl++)=pieceNumber;
365:   for(i=1; i<7; ++i)
366:   {
367:     pieceNumber=*rpl;               // Save to be tested pieceNumber
368:     *rpl=lastPiece;                 // Copy last (important) element to saved position
369:     pC=pCfP+pieceNumber;            // set pieceCount to next Piece
370:     currentPiece=aPfP+(pieceNumber<<4);
371:     for(j=0; j<*pC; ++j)
372:     {
373:       if((puzzle&(*currentPiece))==0ull)
374:       {
375:         solve7(puzzle|(*currentPiece), fillPosition, remainingPiecesList);
376:       }
377:       ++currentPiece;
378:     }
379:     *(rpl++)=pieceNumber;
380:   }
381:   pC=pCfP+(*rpl);
382:   currentPiece=aPfP+((*rpl)<<4);
383:   for(j=0; j<*pC; ++j)
384:   {
385:     if((puzzle&(*currentPiece))==0ull)
386:     {
387:       solve7(puzzle|(*currentPiece), fillPosition, remainingPiecesList);
388:     }
389:     ++currentPiece;
390:   }
391: }
392: 
393: void solve7(const long long puzzle , int fillPosition, int remainingPiecesList[13])
394: {
395:   while(((1ull<<(++fillPosition))&puzzle)!=0); // look for first 0 entry
396:   int i, j;
397:   const long long *currentPiece=andMasks+fillPosition;
398:   const long long *em=equalsMasks+fillPosition;
399:   for(j=fillPosition; j<60; ++j)
400:   {
401:     if((puzzle&(*(currentPiece++)))==(*(em++)))    // Check if puzzle contains pattern
402:     {
403:       return;
404:     }
405:   }
406:   int pieceNumber=*remainingPiecesList;
407:   const int lastPiece=*(remainingPiecesList+6);
408:   int *rpl=remainingPiecesList;
409:   const int offsetPart=fillPosition<<4;
410:   const int * const pCfP=pieceCount+offsetPart;       // Compute offset for pieceCount
411:   const int *pC=pCfP+(*rpl);                   // get number of elements there
412:   const long long * const aPfP=allPieces+(offsetPart<<4);   // Compute offset for to be selected pieces
413:   currentPiece=aPfP+((*rpl)<<4);
414:   *rpl=lastPiece;
415:   for(j=0; j<*pC; ++j)
416:   {
417:     if((puzzle&(*currentPiece))==0ull)
418:     {
419:       solve6(puzzle|(*currentPiece), fillPosition, remainingPiecesList);
420:     }
421:     ++currentPiece;
422:   }
423:   *(rpl++)=pieceNumber;
424:   for(i=1; i<6; ++i)
425:   {
426:     pieceNumber=*rpl;               // Save to be tested pieceNumber
427:     *rpl=lastPiece;                 // Copy last (important) element to saved position
428:     pC=pCfP+pieceNumber;            // set pieceCount to next Piece
429:     currentPiece=aPfP+(pieceNumber<<4);
430:     for(j=0; j<*pC; ++j)
431:     {
432:       if((puzzle&(*currentPiece))==0ull)
433:       {
434:         solve6(puzzle|(*currentPiece), fillPosition, remainingPiecesList);
435:       }
436:       ++currentPiece;
437:     }
438:     *(rpl++)=pieceNumber;
439:   }
440:   pC=pCfP+(*rpl);
441:   currentPiece=aPfP+((*rpl)<<4);
442:   for(j=0; j<*pC; ++j)
443:   {
444:     if((puzzle&(*currentPiece))==0ull)
445:     {
446:       solve6(puzzle|(*currentPiece), fillPosition, remainingPiecesList);
447:     }
448:     ++currentPiece;
449:   }
450: }
451: 
452: inline void solve6(const long long puzzle , int fillPosition, int remainingPiecesList[13])
453: {
454:   while(((1ull<<(++fillPosition))&puzzle)!=0); // look for first 0 entry
455:   int j;
456:   const long long *currentPiece=andMasks+fillPosition;
457:   const long long *em=equalsMasks+fillPosition;
458:   for(j=fillPosition; j<60; ++j)
459:   {
460:     if((puzzle&(*(currentPiece++)))==(*(em++)))    // Check if puzzle contains pattern
461:     {
462:       return;
463:     }
464:   }
465:   int *p234=remainingPiecesList;
466:   int pieceNumber=*(p234++);
467:   const int last=*(p234+4);
468:   const int offsetPart=fillPosition<<4;
469:   const int * const pCfP=pieceCount+offsetPart;       // Compute offset for pieceCount
470:   const int *pC=pCfP+pieceNumber;                   // get number of elements there
471:   const long long * const aPfP=(allPieces+(offsetPart<<4));   // Compute offset for to be selected pieces
472:   currentPiece=aPfP+(pieceNumber<<4);
473:   *remainingPiecesList=last;    // Replace 1st element
474:   for(j=0; j<*pC; ++j)
475:   {
476:     if((puzzle&(*currentPiece))==0ull)    // Use first Piece, call solve2 with pieces 2 and 3
477:     {
478:       solve5(puzzle|(*currentPiece), fillPosition, remainingPiecesList);
479:     }
480:     ++currentPiece;
481:   }
482:   *remainingPiecesList=pieceNumber;
483:   pieceNumber=*p234;
484:   *p234=last;        // Replace 2nd element
485:   pC=pCfP+pieceNumber;            // set pieceCount to next Piece
486:   currentPiece=aPfP+(pieceNumber<<4);
487:   for(j=0; j<*pC; ++j)
488:   {
489:     if((puzzle&(*currentPiece))==0ull)
490:     {
491:       solve5(puzzle|(*currentPiece), fillPosition, remainingPiecesList);
492:     }
493:     ++currentPiece;
494:   }
495:   *p234=pieceNumber;
496:   pieceNumber=*(++p234);
497:   *p234=last;              // Replace 3rd element
498:   pC=pCfP+pieceNumber;            // set pieceCount to next Piece
499:   currentPiece=aPfP+(pieceNumber<<4);
500:   for(j=0; j<*pC; ++j)
501:   {
502:     if((puzzle&(*currentPiece))==0ull)
503:     {
504:       solve5(puzzle|(*currentPiece), fillPosition, remainingPiecesList);
505:     }
506:     ++currentPiece;
507:   }
508:   *p234=pieceNumber;
509:   pieceNumber=*(++p234);
510:   *p234=last;
511:   pC=pCfP+pieceNumber;            // set pieceCount to next Piece
512:   currentPiece=aPfP+(pieceNumber<<4);
513:   for(j=0; j<*pC; ++j)
514:   {
515:     if((puzzle&(*currentPiece))==0ull)
516:     {
517:       solve5(puzzle|(*currentPiece), fillPosition, remainingPiecesList);
518:     }
519:     ++currentPiece;
520:   }
521:   *p234=pieceNumber;
522:   pieceNumber=*(++p234);
523:   *p234=last;
524:   pC=pCfP+pieceNumber;            // set pieceCount to next Piece
525:   currentPiece=aPfP+(pieceNumber<<4);
526:   for(j=0; j<*pC; ++j)
527:   {
528:     if((puzzle&(*currentPiece))==0ull)
529:     {
530:       solve5(puzzle|(*currentPiece), fillPosition, remainingPiecesList);
531:     }
532:     ++currentPiece;
533:   }
534:   *p234=pieceNumber;
535:   pC=pCfP+last;            // set pieceCount to next Piece
536:   currentPiece=aPfP+(last<<4);         // evtl tunable here
537:   for(j=0; j<*pC; ++j)
538:   {
539:     if((puzzle&(*currentPiece))==0ull)
540:     {
541:       solve5(puzzle|(*currentPiece), fillPosition, remainingPiecesList);
542:     }
543:     ++currentPiece;
544:   }
545: }
546: 
547: inline void solve5(const long long puzzle , int fillPosition, int remainingPiecesList[13])
548: {
549:   while(((1ull<<(++fillPosition))&puzzle)!=0); // look for first 0 entry
550:   int *p234=remainingPiecesList;
551:   int pieceNumber=*(p234++);
552:   const int last=*(p234+3);
553:   const int offsetPart=fillPosition<<4;
554:   const int * const pCfP=pieceCount+offsetPart;       // Compute offset for pieceCount
555:   const int *pC=pCfP+pieceNumber;                   // get number of elements there
556:   const long long * const aPfP=(allPieces+(offsetPart<<4));   // Compute offset for to be selected pieces
557:   const long long *currentPiece=aPfP+(pieceNumber<<4);
558:   int j;
559:   *remainingPiecesList=last;    // Replace 1st element
560:   for(j=0; j<*pC; ++j)
561:   {
562:     if((puzzle&(*currentPiece))==0ull)    // Use first Piece, call solve2 with pieces 2 and 3
563:     {
564:       solve4(puzzle|(*currentPiece), fillPosition, remainingPiecesList);
565:     }
566:     ++currentPiece;
567:   }
568:   *remainingPiecesList=pieceNumber;
569:   pieceNumber=*p234;
570:   *p234=last;        // Replace 2nd element
571:   pC=pCfP+pieceNumber;            // set pieceCount to next Piece
572:   currentPiece=aPfP+(pieceNumber<<4);
573:   for(j=0; j<*pC; ++j)
574:   {
575:     if((puzzle&(*currentPiece))==0ull)
576:     {
577:       solve4(puzzle|(*currentPiece), fillPosition, remainingPiecesList);
578:     }
579:     ++currentPiece;
580:   }
581:   *p234=pieceNumber;
582:   pieceNumber=*(++p234);
583:   *p234=last;              // Replace 3rd element
584:   pC=pCfP+pieceNumber;            // set pieceCount to next Piece
585:   currentPiece=aPfP+(pieceNumber<<4);
586:   for(j=0; j<*pC; ++j)
587:   {
588:     if((puzzle&(*currentPiece))==0ull)
589:     {
590:       solve4(puzzle|(*currentPiece), fillPosition, remainingPiecesList);
591:     }
592:     ++currentPiece;
593:   }
594:   *p234=pieceNumber;
595:   pieceNumber=*(++p234);
596:   *p234=last;
597:   pC=pCfP+pieceNumber;            // set pieceCount to next Piece
598:   currentPiece=aPfP+(pieceNumber<<4);
599:   for(j=0; j<*pC; ++j)
600:   {
601:     if((puzzle&(*currentPiece))==0ull)
602:     {
603:       solve4(puzzle|(*currentPiece), fillPosition, remainingPiecesList);
604:     }
605:     ++currentPiece;
606:   }
607:   *p234=pieceNumber;
608:   pC=pCfP+last;            // set pieceCount to next Piece
609:   currentPiece=aPfP+(last<<4);         // evtl tunable here
610:   for(j=0; j<*pC; ++j)
611:   {
612:     if((puzzle&(*currentPiece))==0ull)
613:     {
614:       solve4(puzzle|(*currentPiece), fillPosition, remainingPiecesList);
615:     }
616:     ++currentPiece;
617:   }
618: }
619: 
620: inline void solve4(const long long puzzle, int fillPosition, int remainingPiecesList[13])
621: {
622:   while(((1ull<<(++fillPosition))&puzzle)!=0); // look for first 0 entry
623:   int *p23_4=remainingPiecesList;
624:   int pieceNumber_4=*(p23_4++);
625:   const int last_4=*(p23_4+2);
626:   const int offsetPart_4=fillPosition<<4;
627:   const int * const pCfP_4=pieceCount+offsetPart_4;       // Compute offset for pieceCount
628:   const int *pC_4=pCfP_4+pieceNumber_4;                   // get number of elements there
629:   const long long * const aPfP_4=(allPieces+(offsetPart_4<<4));   // Compute offset for to be selected pieces
630:   const long long *currentPiece_4=aPfP_4+(pieceNumber_4<<4);
631:   int j_4;
632:   *remainingPiecesList=last_4;    // Replace 1st element
633:   for(j_4=0; j_4<*pC_4; ++j_4)
634:   {
635:     if((puzzle&(*currentPiece_4))==0ull)    // Use first Piece, call solve2 with pieces 2 and 3
636:     {
637:       solve3(puzzle|(*currentPiece_4), fillPosition, remainingPiecesList);
638:     }
639:     ++currentPiece_4;
640:   }
641:   *remainingPiecesList=pieceNumber_4;
642:   pieceNumber_4=*p23_4;
643:   *p23_4=last_4;        // Replace 2nd element
644:   pC_4=pCfP_4+pieceNumber_4;            // set pieceCount to next Piece
645:   currentPiece_4=aPfP_4+(pieceNumber_4<<4);
646:   for(j_4=0; j_4<*pC_4; ++j_4)
647:   {
648:     if((puzzle&(*currentPiece_4))==0ull)
649:     {
650:       solve3(puzzle|(*currentPiece_4), fillPosition, remainingPiecesList);
651:     }
652:     ++currentPiece_4;
653:   }
654:   *p23_4=pieceNumber_4;
655:   pieceNumber_4=*(++p23_4);
656:   *p23_4=last_4;              // Replace 3rd element
657:   pC_4=pCfP_4+pieceNumber_4;            // set pieceCount to next Piece
658:   currentPiece_4=aPfP_4+(pieceNumber_4<<4);
659:   for(j_4=0; j_4<*pC_4; ++j_4)
660:   {
661:     if((puzzle&(*currentPiece_4))==0ull)    // Use first Piece, call solve2 with pieces 2 and 3
662:     {
663:       solve3(puzzle|(*currentPiece_4), fillPosition, remainingPiecesList);
664:     }
665:     ++currentPiece_4;
666:   }
667:   *p23_4=pieceNumber_4;
668:   pC_4=pCfP_4+last_4;            // set pieceCount to next Piece
669:   currentPiece_4=aPfP_4+(last_4<<4);         // evtl tunable here
670:   for(j_4=0; j_4<*pC_4; ++j_4)
671:   {
672:     if((puzzle&(*currentPiece_4))==0ull)
673:     {
674:       solve3(puzzle|(*currentPiece_4), fillPosition, remainingPiecesList);
675:     }
676:     ++currentPiece_4;
677:   }
678: }
679: 
680: inline void solve3(const long long puzzle , int fillPosition, int remainingPiecesList[13])
681: {
682:   while(((1ull<<(++fillPosition))&puzzle)!=0); // look for first 0 entry
683:   int *p2=remainingPiecesList;
684:   int pieceNumber=*(p2++);
685:   const int last=*(p2+1);
686:   const int offsetPart=fillPosition<<4;
687:   const int * const pCfP=pieceCount+offsetPart;       // Compute offset for pieceCount
688:   const int *pC=pCfP+pieceNumber;                   // get number of elements there
689:   const long long * const aPfP=(allPieces+(offsetPart<<4));   // Compute offset for to be selected pieces
690:   const long long *currentPiece=aPfP+(pieceNumber<<4);
691:   int j;
692:   *remainingPiecesList=last;
693:   for(j=0; j<*pC; ++j)
694:   {
695:     if((puzzle&(*currentPiece))==0ull)    // Use first Piece, call solve2 with pieces 2 and 3
696:     {
697:       solve2(puzzle|(*currentPiece), fillPosition, remainingPiecesList);
698:     }
699:     ++currentPiece;
700:   }
701:   *remainingPiecesList=pieceNumber;
702:   pieceNumber=*p2;
703:   *p2=last;
704:   pC=pCfP+pieceNumber;            // set pieceCount to next Piece
705:   currentPiece=aPfP+(pieceNumber<<4);
706:   for(j=0; j<*pC; ++j)
707:   {
708:     if((puzzle&(*currentPiece))==0ull)
709:     {
710:       solve2(puzzle|(*currentPiece), fillPosition, remainingPiecesList);
711:     }
712:     ++currentPiece;
713:   }
714:   *p2=pieceNumber;
715:   pC=pCfP+last;            // set pieceCount to next Piece
716:   currentPiece=aPfP+(last<<4);
717:   for(j=0; j<*pC; ++j)
718:   {
719:     if((puzzle&(*currentPiece))==0ull)
720:     {
721:       solve2(puzzle|(*currentPiece), fillPosition, remainingPiecesList);
722:     }
723:     ++currentPiece;
724:   }
725: }
726: 
727: inline void solve2(const long long puzzle , int fillPosition, int remainingPiecesList[13])
728: {
729:   while(((1ull<<(++fillPosition))&puzzle)!=0); // look for first 0 entry
730:   int j;
731:   const int pieceNumber=*remainingPiecesList;
732:   const int last=*(remainingPiecesList+1);
733:   const int offsetPart=fillPosition<<4;
734:   const int * const pCfP=pieceCount+offsetPart;       // Compute offset for pieceCount
735:   const int *pC=pCfP+pieceNumber;                   // get number of elements there
736:   const long long * const aPfP=(allPieces+(offsetPart<<4));   // Compute offset for to be selected pieces
737:   const long long *currentPiece=aPfP+((pieceNumber)<<4);
738:   *remainingPiecesList=last;
739:   for(j=0; j<*pC; ++j)
740:   {
741:     if((puzzle&(*currentPiece))==0ull)    // Use first Piece, call solve2 with pieces 2 and 3
742:     {
743:       solve1(puzzle|(*currentPiece), fillPosition, remainingPiecesList);
744:     }
745:     ++currentPiece;
746:   }
747:   *remainingPiecesList=pieceNumber;
748:   pC=pCfP+last;
749:   currentPiece=aPfP+(last<<4);
750:   for(j=0; j<*pC; ++j)
751:   {
752:     if((puzzle&(*currentPiece))==0ull)    // Use first Piece, call solve2 with pieces 2 and 3
753:     {
754:       solve1(puzzle|(*currentPiece), fillPosition, remainingPiecesList);
755:     }
756:     ++currentPiece;
757:   }
758: }
759: 
760: inline void solve1(const long long puzzle, int fillPosition, int remainingPiecesList[13])
761: {
762:   while(((1ull<<(++fillPosition))&puzzle)!=0);
763:   const int offsetPart=(fillPosition<<4)+(*remainingPiecesList);
764:   const int pC=*(pieceCount+offsetPart);       // Compute offset for pieceCount
765:   const long long *currentPiece=allPieces+(offsetPart<<4);
766:   for(int j=0; j<pC; ++j)
767:   {
768:     if((puzzle&(*currentPiece))==0ull)
769:     {
770:       ++(*(remainingPiecesList+12));
771:       return;
772:     }
773:     ++currentPiece;
774:   }
775: }