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