001: /*
002:  * Copyright (C) 2003, Jochen Hoenicke
003:  * 
004:  * Der Algorithmus ist wie folgt: Die rekursive play_piece-Methode such
005:  * zunächst mit Hilfe von merge die Auswahl (choice), die die
006:  * wenigsten Stellungen zulässt.  Eine Auswahl ist dabei entweder ein
007:  * Feld im Würfel, das belegt werden soll, oder eines der
008:  * verbleibenden Teile das abgelegt werden soll.
009:  *
010:  * Zu dieser Auswahl werden dann alle Teile, die sie erfüllen und die
011:  * nicht im Konflikt zu anderen bereits gelegten Teilen stehen,
012:  * ausprobiert, und play_piece wird rekursiv aufgerufen.
013:  *
014:  * Damit man nicht jedesmal neu ausrechnen muss, welche Teile passen,
015:  * werden die Teile die noch passen in dem BitVector posspiece mit 1
016:  * markiert und jedesmal wenn ein neues Teil abgelegt wird werden die
017:  * Teile die dazu im Konflikt stehen aus allen BitVectoren gelöscht.
018:  * Dazu wird das vorher berechnete array conflicts benutzt.
019:  *
020:  * Das erste Teil ist hart kodiert:  Es ist immer das x-Teil, da es nur
021:  * 12 Lagen (ohne Symmetrie) besitzt.  Dieses Teil wird daher auch nicht
022:  * bei den Auswahlen berücksichtigt.
023:  *
024:  * Die Hauptarbeit erledigt die merge routine (die in Assembler
025:  * kodiert ist). Sie kombiniert den conflicts-Vector mit den
026:  * posspiece-Vector und berechnet dabei die Anzahl der Teile für jede
027:  * Auswahl.  Als Rückgabewert gibt sie die Auswahl mit den wenigsten
028:  * Teilen zurück.
029:  *
030:  * Es gibt insgesamt 60 (Felder) + 12 (Teile) = 72 mögliche Auswahlen.
031:  * Weil die Mittelfelder über 512 Stellungen zulassen und das den
032:  * Bit-Vector unnötig aufbläht wurden diese Felder weggelassen.  Das
033:  * ist möglich weil in jeder noch nicht gelösten Stellung mind. 4
034:  * Felder frei sind und damit noch 2 andere Auswahlen möglich sind.
035:  * Ausserdem wurden die 6 Teile mit den wenigsten Rotationen
036:  * ausgewählt, sodass man auf runde 64 Auswahlen kommt.
037:  * 
038:  */
039: 
040: #include <stdlib.h>
041: #include <stdio.h>
042: #include <string.h>
043: 
044: 
045: #define NUM_CUBES      60
046: #define NUM_ROTATIONS  24
047: #define NUM_PIECES     12
048: #define MAX_PIECE_SIZE 6
049: 
050: /* Die maximale Anzahl der Teile die auf eine Auswahl passen
051:  * Dies ist gleichzeitig die Anzahl der bits pro BitVector.
052:  */
053: #define MAX_ROTATIONS  (16*32)
054: 
055: /* Die Anzahl von verschiedenen rotierten Teilen.
056:  */
057: #define NUM_ALL_ROTATIONS 4412
058: 
059: #define ASYMMETRIC_PIECE X_PIECE
060: #define ASYMMETRIC_PIECE2 6
061: 
062: #define X_PIECE 10
063: #define MAX_X_ROTATIONS  40
064: 
065: static int x2x[5] = {0,1,2,3,4};
066: static int y2y[4] = {0,1,2,3};
067: static int z2z[3] = {0,1,2};
068: 
069: #define coord2bit(x,y,z) (((x2x[x])*4*3 + (y2y[y])*3 + (z2z[z])))
070: 
071: /* We never place on the middle cubes as they have to many rotations */
072: #define OMIT_CUBE1 coord2bit(2,1,1)
073: #define OMIT_CUBE2 coord2bit(2,2,1)
074: 
075: #define CUBE_CHOICES     (NUM_CUBES - 2)
076: #define NUM_CHOICES      (64)
077: #define NUM_CHOICE_WORDS (2)
078: 
079: int cube2choice(int cube) {
080:     return cube == OMIT_CUBE1 || cube == OMIT_CUBE2 ? -1
081:         :  cube < OMIT_CUBE1 && cube < OMIT_CUBE2 ? cube
082:         :  cube < OMIT_CUBE1 || cube < OMIT_CUBE2 ? cube - 1
083:         :  cube - 2;
084: }
085: static int p2c[12] = { 
086:     -1, 
087:     CUBE_CHOICES + 0,
088:     CUBE_CHOICES + 1,
089:     CUBE_CHOICES + 2,
090:     -1, 
091:     CUBE_CHOICES + 3,
092:     -1, 
093:     CUBE_CHOICES + 4,
094:     -1, 
095:     -1, 
096:     -1, 
097:     CUBE_CHOICES + 5
098: };
099: #define piece2choice(pnr) (p2c[pnr])
100: 
101: 
102: typedef int coord[3];
103: typedef coord piece[MAX_PIECE_SIZE + 1];
104: 
105: piece ctpieces[NUM_PIECES] = {
106:   {
107:     {0,0,0}, {1,0,0}, {0,1,0}, {0,2,0}, {1,2,0}, {-1,-1,-1}
108:   }, {
109:     {1,0,0}, {2,0,0}, {1,1,0}, {0,2,0}, {1,2,0}, {-1,-1,-1}
110:   }, {
111:     {0,0,0}, {0,1,0}, {0,2,0}, {0,3,0}, {1,3,0}, {-1,-1,-1}
112:   }, {
113:     {0,0,0}, {0,1,0}, {1,1,0}, {0,2,0}, {0,3,0}, {-1,-1,-1}
114:   }, {
115:     {0,0,0}, {1,0,0}, {0,1,0}, {1,1,0}, {1,1,1}, {-1,-1,-1}
116:   }, {
117:     {0,0,0}, {1,0,0}, {2,0,0}, {1,1,0}, {1,2,0}, {-1,-1,-1}
118:   }, {
119:     {0,0,0}, {1,0,0}, {0,1,0}, {1,1,0}, {2,1,0}, {-1,-1,-1}
120:   }, {
121:     {0,0,0}, {0,1,0}, {1,1,0}, {1,2,0}, {2,2,0}, {-1,-1,-1}
122:   }, {
123:     {0,0,0}, {1,0,0}, {0,1,0}, {0,1,1}, {-1,-1,-1}
124:   }, {
125:     {0,0,0}, {1,0,0}, {1,1,0}, {2,1,0}, {1,2,0}, {-1,-1,-1}
126:   }, {
127:     {1,0,0}, {0,1,0}, {1,1,0}, {2,1,0}, {1,2,0}, {-1,-1,-1}
128:   }, {
129:     {0,0,0}, {1,0,0}, {2,0,0}, {3,0,0}, {0,1,0}, {2,1,0}, {-1,-1,-1}
130:   }
131: };
132: 
133: typedef unsigned long BitVec;
134: typedef unsigned long long RotPiece;
135: typedef struct Choice {
136:     BitVec c[NUM_CHOICE_WORDS];
137: } Choice;
138: 
139: int      rotnr[NUM_CHOICES][MAX_ROTATIONS];
140: int      xrotnr[MAX_X_ROTATIONS];
141: RotPiece rotations[NUM_ALL_ROTATIONS];
142: Choice   choices[NUM_ALL_ROTATIONS];
143: int      nr[NUM_ALL_ROTATIONS];
144: BitVec   conflicts[NUM_ALL_ROTATIONS][NUM_CHOICES][MAX_ROTATIONS / 32];
145: 
146: #define SET_BIT(c,k,l) c[k][(l)>>5] |= 1 << ((l) & 31)
147: #define CLR_BIT(c,k,l) c[k][(l)>>5] &= ~(1 << ((l) & 31))
148: 
149: 
150: int   numrots[NUM_CHOICES] = {0,};
151: int  xnumrots = 0;
152: int   totalrots = 0;
153: 
154: 
155: #define HASH_DEPTH    7
156: #define HASH_SIZE 0x1000000
157: 
158: /* The hashcode is simple, because it must be fast, and it also makes sure
159:  * that same positions with different used values get a different hashcode.
160:  */
161: #define hashcode(pos,used) \
162:    (((pos) ^ (pos >> 13) ^ (pos >> 23) ^ (pos >> 40) ^ (used)) & (HASH_SIZE-1))
163: /*
164: #define hashcode(pos,used) \
165:    ((((pos) ^ (pos >> 13) ^ (pos >> 23) ^ (pos >> 40)) & (0x7fff)) \
166:     ^ (used << 11))
167: */
168: 
169: 
170: #define COUNT_SAVED
171: #define shrink_subs(x)  ((x) >> 12)
172: 
173: typedef struct hashed_pos {
174:   long long pos;
175: #ifdef COUNT_SAVED
176:   int solutions;
177:   int substates;
178: #else
179:   unsigned short solutions;
180:   unsigned short substates;
181: #endif
182: } hashed_pos;
183: hashed_pos hashtable[HASH_SIZE];
184: 
185: 
186: static __inline__ int find_bit (BitVec word)
187: {
188:     int tmp;
189:     __asm__ ("bsfl %1,%0"
190:              :           "=r" (tmp)
191:              :           "r" (word));
192:     return tmp;
193: }
194: 
195: 
196: void dumpPiece(RotPiece piece) {
197:   int z, y, x;
198:   for (z = 2; z >= 0; z--) {
199:     for (y = 3; y >= 0; y--) {
200:       for (x = 0; x < 5; x++) {
201:         printf("%c ", (piece & 1LL << coord2bit(x,y,z)) ? 'X' : '.');
202:       }
203:       printf("\n");
204:     }
205:     printf("\n");
206:   }
207: }
208: 
209: void dumpBoard(RotPiece board, RotPiece piece) {
210:   char bchar[4] = {'.', 'p', 'X', '*'};
211:   int z, y, x;
212:   for (z = 2; z >= 0; z--) {
213:     for (y = 3; y >= 0; y--) {
214:       for (x = 0; x < 5; x++) {
215:         int i = coord2bit(x,y,z);
216:         int b = (board >> i) & 1;
217:         int p = (piece >> i) & 1;
218:         printf("%c ", bchar[b*2+p]);
219:       }
220:       printf("   ");
221:       for (x = 0; x < 5; x++) {
222:         printf("%3d", coord2bit(x,y,z));
223:       }
224:       printf("\n");
225:     }
226:     printf("\n");
227:   }
228: }
229: 
230: void rotate(coord c, int rot, coord dest) {
231:   switch (rot / 4) {
232:   case 0:
233:     dest[0] = c[0];
234:     dest[1] = c[1];
235:     dest[2] = c[2];
236:     break;
237:   case 1:
238:     dest[0] = c[0];
239:     dest[1] = c[2];
240:     dest[2] = -c[1];
241:     break;
242:   case 2:
243:     dest[0] = c[1];
244:     dest[1] = c[0];
245:     dest[2] = -c[2];
246:     break;
247:   case 3:
248:     dest[0] = c[1];
249:     dest[1] = c[2];
250:     dest[2] = c[0];
251:     break;
252:   case 4:
253:     dest[0] = c[2];
254:     dest[1] = c[1];
255:     dest[2] = -c[0];
256:     break;
257:   case 5:
258:     dest[0] = c[2];
259:     dest[1] = c[0];
260:     dest[2] = c[1];
261:     break;
262:   }
263:   if (rot & 1) {
264:     dest[0] = -dest[0];
265:     dest[2] = -dest[2];
266:   }
267:   if (rot & 2) {
268:     dest[1] = -dest[1];
269:     dest[2] = -dest[2];
270:   }
271: }
272: 
273: RotPiece rotate_and_shift(piece p, int rot, int shift)
274: {
275:   int i;
276:   RotPiece bitvec = 0LL;
277: 
278:   for (i = 0; i < MAX_PIECE_SIZE; i++) {
279:     coord dest;
280:     if (p[i][0] == -1)
281:       break;
282:     rotate(p[i], rot, dest);
283:     dest[0] += shift % 5;
284:     dest[1] += (shift / 5) % 4;
285:     dest[2] += (shift / 20);
286:     if (dest[0] < 0 || dest[0] >= 5
287:         || dest[1] < 0 || dest[1] >= 4
288:         || dest[2] < 0 || dest[2] >= 3) {
289:       /* piece doesn't fit.. */
290:       return 0LL;
291:     }
292:     bitvec |= 1LL << coord2bit(dest[0], dest[1], dest[2]);
293:   }
294:   return bitvec;
295: }
296: 
297: RotPiece mirror(RotPiece rotation) {
298:     /* mirror a piece against x and z axis */
299:     int x,y,z;
300:     RotPiece mirror = 0LL;
301:     for (x=0; x < 5; x++) {
302:         for (y = 0; y < 4; y++) {
303:             for (z = 0; z < 3; z++) {
304:                 if (rotation & (1LL << coord2bit(x,y,z))) {
305:                     mirror |= 1LL << coord2bit(4-x,y,2-z);
306:                 }
307:             }
308:         }
309:     }
310:     return mirror;
311: }
312: 
313: int best_full_rotation(RotPiece rotation) {
314:   int x,y,z;
315:   RotPiece rot0, rot1, rot2, rot3;
316: 
317:   /* calculate the four rotations of the piece, but with
318:    * reversed bit order.
319:    */
320:   rot0 = rot1 = rot2 = rot3 = 0LL;
321:   for (x=0; x < 5; x++) {
322:     for (y = 0; y < 4; y++) {
323:       for (z = 0; z < 3; z++) {
324:         if (rotation & (1LL << coord2bit(x,y,z))) {
325:           rot0 |= 1LL << (coord2bit(  x,  y,  z));
326:           rot1 |= 1LL << (coord2bit(4-x,3-y,  z));
327:           rot2 |= 1LL << (coord2bit(  x,3-y,2-z));
328:           rot3 |= 1LL << (coord2bit(4-x,  y,2-z));
329:         }
330:       }
331:     }
332:   }
333:   /*
334:   dumpPiece(rotation);
335:   printf("0: %16Lx\n", rot0);
336:   printf("1: %16Lx\n", rot1);
337:   printf("2: %16Lx\n", rot2);
338:   printf("3: %16Lx\n", rot3);
339:   */
340: 
341:   /* We want the lowest bit of current rotation be higher than for any
342:    * other of the four rotation.  Since we reversed the bits, we want
343:    * the highest bit of rot0 be smaller than for any other rot.
344:    * The normal < operation does exactly what we want.
345:    */
346:   return rot0 <= rot1
347:     &&   rot0 <= rot2
348:     &&   rot0 <= rot3;
349: }
350: 
351: void add_choice(int rnr, int ch) {
352:     if (ch >= 0) {
353:         choices[rnr].c[ch >> 5] &= ~(1 << (ch&0x1f));
354:         rotnr[ch][numrots[ch]++] = rnr;
355:     }
356: }
357: 
358: void compile() {
359:     int rot, cube, i, j, ch;
360:     int pnr;
361:     RotPiece rotpiece;
362:     int num;
363:     
364:     for (pnr = 0; pnr < NUM_PIECES; pnr++) {
365:         num = 0;
366:         for (rot = 0; rot < NUM_ROTATIONS; rot++) {
367:             for (cube = 0; cube < NUM_CHOICES; cube++) {
368:                 rotpiece = rotate_and_shift(ctpieces[pnr], rot, cube);
369:                 if (!rotpiece)
370:                     continue;
371:                 
372: #ifdef ASYMMETRIC_PIECE
373:                 if (pnr == ASYMMETRIC_PIECE) {
374:                     /* Only take this piece if it is better than the 
375:                      * other 3 rotations with respect to the whole cuboid.
376:                      *
377:                      * Better means 
378:                      *   1. the lowest bit nr is higher.
379:                      *   2. the value is bigger.
380:                      */
381:                     if (!best_full_rotation(rotpiece))
382:                         continue;
383:                 }
384: #endif
385:           
386:                 for (j = 0; j < totalrots; j++) {
387:                     if (rotations[j] == rotpiece)
388:                         break;
389:                 }
390:                 
391:                 if (j == totalrots) {
392:                     /* Found new rotation */
393:                     rotations[totalrots] = rotpiece;
394: 
395:                     for (i = 0; i < NUM_CHOICES / 32; i++) {
396:                         choices[totalrots].c[i] = -1;
397:                     }
398:                     if (NUM_CHOICES & 0x1f) {
399:                         choices[totalrots].c[i] = 
400:                             (1UL << (NUM_CHOICES & 0x1f)) - 1;
401:                     }
402: 
403:                     nr[totalrots] = pnr;
404:                     
405:                     if (pnr == X_PIECE) {
406:                         for (i = 0; i < NUM_CUBES; i++) {
407:                             if ((rotpiece & 1LL << i)) {
408:                                 ch = cube2choice(i);
409:                                 if (ch >= 0)
410:                                     choices[totalrots].c[ch >> 5]
411:                                         &= ~(1 << (ch & 0x1f));
412:                             }
413:                         }
414:                         xrotnr[xnumrots++] = totalrots;
415:                     } else {
416:                         /* put piece at right position in array */
417:                         for (i = 0; i < NUM_CUBES; i++) {
418:                             if ((rotpiece & 1LL << i)) {
419:                                 add_choice(totalrots, cube2choice(i));
420:                             }
421:                         }
422:                         add_choice(totalrots, piece2choice(pnr));
423:                     }
424:                     
425:                     totalrots++;
426:                     num++;
427:                 }
428:             }
429:         }
430:         
431:         printf("Piece %d, %d rotations\n", pnr, num);
432:     }
433:     printf("Total %d rotations\n", totalrots);
434: }
435: 
436: void calc_conflicts() {
437:     int i, j, k;
438:     int maxtotpieces = 0;
439:     int bnr;
440:     BitVec bvec;
441:     BitVec *cptr;
442: 
443:     for (i = 0; i < NUM_CHOICES; i++) {
444:         int totpieces = numrots[i];
445:         printf("Choice %d: %d pieces\n", i, totpieces);
446:         if (totpieces > maxtotpieces)
447:             maxtotpieces = totpieces;
448:     }
449:     printf("Maximum: %d pieces\n", maxtotpieces);
450: 
451:     for (i = 0; i < totalrots; i++) {
452:         int keepsymmetric_piece2 = 1;
453: 
454: #if ASYMMETRIC_PIECE == X_PIECE
455:         if (nr[i] == X_PIECE)
456:             keepsymmetric_piece2 = (mirror(rotations[i]) != rotations[i]);
457: #endif
458: 
459:         for (j = 0; j < NUM_CHOICES; j++) {
460:             cptr = conflicts[i][j];
461:             bnr = 0; 
462:             bvec = 0;
463:             for (k = 0; k < numrots[j]; k++) {
464:                 int rnr = rotnr[j][k];
465:                 RotPiece rot = rotations[rnr];
466:                 if (nr[i] != nr[rnr]
467:                     && !(rotations[i] & rot)) {
468:                     if ((keepsymmetric_piece2
469:                          || nr[rnr] != ASYMMETRIC_PIECE2 
470:                          || mirror(rot) <= rot))
471:                         bvec |= 1 << bnr;
472:                 }
473:                 
474:                 if (++bnr == 32) {
475:                     *cptr++ = bvec;
476:                     bnr = 0;
477:                     bvec = 0;
478:                 }
479:             }
480:             *cptr = bvec;
481:         }
482:     }
483:     printf("Conflict table built.\n");
484: }
485: 
486: BitVec posspiece[NUM_PIECES+1][NUM_CHOICES][MAX_ROTATIONS/32];
487: Choice openchoices[NUM_PIECES+1];
488: unsigned long solutions = 0;
489: unsigned long placed = 0;
490: unsigned long placedP[NUM_PIECES];
491: RotPiece board[NUM_PIECES+1];
492: BitVec used[NUM_PIECES+1];
493: int xsymm;
494: 
495: unsigned long saved, hits;
496: unsigned long savedP[NUM_PIECES+1];
497: unsigned long hitsP[NUM_PIECES+1];
498: 
499: unsigned char bitcount[65536];
500: void init_bitcount() {
501:     int i;
502:     for (i = 0; i < 65536; i++) {
503:         int c = (i & 0x5555) + ((i>>1) & 0x5555);
504:         c = (c & 0x3333) + ((c >> 2) & 0x3333);
505:         c = ((c >> 4) + c) & 0x0f0f;
506:         c = ((c >> 8) + c) & 0x00ff;
507:         bitcount[i] = c;
508:     }
509: }
510: 
511: extern int merge(int depth, int rotnr, int *bestv);
512: 
513: /*#define merge portable_merge*/
514: 
515: 
516: int portable_merge(int depth, int rotnr, int *pbestv)
517: {
518:     BitVec *s1, *s2, *pp;
519:     int i, j;
520:     int best, bestv;
521: 
522:     best = -1;
523:     bestv = MAX_ROTATIONS;
524:     s1 = posspiece[depth-1][0];
525:     s2 = conflicts[rotnr][0];
526:     pp = posspiece[depth][0];
527:     for (i = 0; i < NUM_CHOICE_WORDS; i++) {
528:         openchoices[depth].c[i] = 
529:             openchoices[depth-1].c[i] & choices[rotnr].c[i];
530:     }
531: 
532:     for (i = 0; i < NUM_CHOICES; i++) {
533:         int cnt;
534:         if (!(openchoices[depth].c[i>>5] & (1L << (i&0x1f)))) {
535:             s1 += MAX_ROTATIONS/32;
536:             s2 += MAX_ROTATIONS/32;
537:             pp += MAX_ROTATIONS/32;
538:             continue;
539:         }
540: 
541:         cnt = 0;
542:         for (j = 0; j < MAX_ROTATIONS/32; j++) {
543:             BitVec w = *s1++ & *s2++;
544:             *pp++ = w;
545:             cnt += bitcount[w & 0xffff] + bitcount[w >> 16];
546:         }
547:         if (cnt < bestv) {
548: #if 0
549:             if (i >= CUBE_CHOICES) {
550:                 dumpBoard(board, 0LL);
551:                 printf("Choosing piece %d: %d <= %d\n", 
552:                        i - CUBE_CHOICES, cnt, bestv);
553:             }
554: #endif
555:             *pbestv = bestv = cnt; 
556:             best = i;
557:             if (!cnt)
558:               return best;
559:         }
560:     }
561:     return best;
562: }
563: 
564: 
565: 
566: void play_piece_fast(int depth, int rnr)
567: {
568:     int best, bestv;
569:     int (*rn)[32];
570:     BitVec *pp;
571: 
572:     best = merge(depth, rnr, &bestv);
573:     if (!bestv)
574:         return;
575: 
576:     if (depth == NUM_PIECES - 1) {
577:         solutions += bestv;
578:         return;
579:     }
580: 
581:     pp = posspiece[depth][best];
582:     rn = (int (*) [32]) rotnr[best];
583:     for ( ;; ) {
584:         BitVec x = *pp;
585: 
586:         while (x) {
587:             if (depth == NUM_PIECES - 1) {
588:                 solutions++;
589:             } else {
590:                 placed++;
591: #if 0
592:                 placedP[depth]++;
593: #endif
594:                 play_piece_fast(depth+1, (*rn)[find_bit(x)]);
595:             }
596:             /* clear least significant bit */
597:             x &= (x-1);
598:             if (--bestv == 0)
599:                 return;
600:         }
601:         pp++;
602:         rn++;
603:     }
604: }
605: 
606: 
607: void play_piece(int depth, int rnr)
608: {
609:     int best, bestv;
610:     int (*rn)[32];
611:     BitVec *pp;
612: 
613:     int oldplaced, oldsolutions, hc;
614:     board[depth] = board[depth-1] | rotations[rnr];
615:     used[depth] = used[depth-1] | (1 << nr[rnr]);
616: 
617:     __asm__("hashstart:\n");
618:     
619:     hc = hashcode(board[depth], used[depth] ^ xsymm);
620:     if (hashtable[hc].pos == board[depth]) {
621:         __asm__("hashfound:\n");
622: #ifdef COUNT_SAVED
623:         int subs;
624: #endif
625:         solutions += hashtable[hc].solutions;
626:         
627: #ifdef COUNT_SAVED
628:         subs = hashtable[hc].substates;
629:         placed += subs;
630:         saved += subs;
631:         savedP[depth] += subs;
632: #endif
633:         hitsP[depth]++;
634:         hits++;
635:         __asm__("hashreturn:\n");
636:         return;
637:     }
638:     oldplaced = placed;
639:     oldsolutions = solutions;
640:     
641: 
642:     __asm__("hashend:\n");
643:     best = merge(depth, rnr, &bestv);
644: #if 0
645:     {
646:         int best1, bestv1;
647:         best1 = portable_merge(depth, rnr, &bestv1);
648: 
649:         if (best != best1 || bestv != bestv1) {
650:             dumpBoard(board[depth], 0LL);
651:             printf("%llx: %d != %d || %d != %d\n", board[depth], best, best1, bestv, bestv1);
652:             abort();
653:         }
654: 
655:     }
656: #endif
657: 
658:     if (!bestv) {
659: #if 0
660:         dumpBoard(board[depth], 0LL);
661:         printf("%*s%d:  early return %d\n", depth, "", depth, best);
662: #endif
663:         return;
664:     }
665: 
666: #if 0
667:     static int maxbestv=10;
668:     if (bestv > maxbestv) {
669:       printf("%*s%d:  bestv: %d\n", depth, "", depth, bestv);
670:       maxbestv= bestv;
671:     }
672: #endif
673: 
674: #ifdef DEBUG
675:     if (depth < 3) {
676:         int i;
677:         printf("%*s%d:  best %d (%d rots) %lu solutions with %lu placements\n",
678:                depth, "", depth, best, bestv, solutions, placed);
679:         for (i = 0; i < NUM_PIECES; i++) {
680:             printf("%lu+", placedP[i]);
681:         }
682:         printf("\n");
683:     }
684: #endif
685: 
686: #if HASH_DEPTH >= NUM_PIECES - 1
687:     if (depth == NUM_PIECES - 1) {
688:         solutions += bestv;
689:         return;
690:     }
691: #endif
692: 
693:     pp = posspiece[depth][best];
694:     rn = (int (*) [32]) rotnr[best];
695: 
696:     if (depth < HASH_DEPTH) {
697:         for ( ;; ) {
698:             BitVec x = *pp;
699:             
700:             while (x) {
701:                 
702:                 int newrnr = (*rn)[find_bit(x)];
703:                 placed++;
704:                 placedP[depth]++;
705: 
706: #if 0
707:                 if (!rotations[newrnr]) {
708:                     abort();
709:                 }
710:                 if ((board[depth] & rotations[newrnr])) {
711:                     dumpBoard(board[depth], rotations[newrnr]);
712:                     abort();
713:                 }
714: #endif
715:                 play_piece(depth+1, newrnr);
716: 
717:                 /* clear least significant bit */
718:                 x &= (x-1);
719:                 
720:                 if (--bestv == 0)
721:                     goto exit;
722:             }
723:             pp++;
724:             rn++;
725:         }
726: 
727:     } else {
728: 
729:         for ( ;; ) {
730:             BitVec x;
731:             while (!(x = *pp++))
732:                 rn++;
733:             
734:             while (x) {
735:                 
736:                 int newrnr = (*rn)[find_bit(x)];
737:                 placed++;
738:                 placedP[depth]++;
739:                 play_piece_fast(depth+1, newrnr);
740: 
741:                 /* clear least significant bit */
742:                 x &= (x-1);
743:                 
744:                 --bestv;
745:             }
746:             if (!bestv)
747:                 goto exit;
748:             rn++;
749:         }
750:     }
751: 
752:  exit:
753:     
754:     if (depth > 1 && depth < HASH_DEPTH
755: #ifdef COUNT_SAVED
756:         && hashtable[hc].substates <= placed - oldplaced
757: #else
758:         && hashtable[hc].substates <= shrink_subs(placed - oldplaced)
759: #endif
760:         ) {
761:         
762:         hashtable[hc].pos = board[depth];
763:         hashtable[hc].solutions = solutions - oldsolutions;
764: #ifdef COUNT_SAVED
765:         hashtable[hc].substates = placed - oldplaced;
766: #else
767:         hashtable[hc].substates = shrink_subs(placed - oldplaced);
768: #endif
769:     }
770:     return;
771: }
772: 
773: void init_mmx(void);
774: 
775: int main() {
776:     int i, j;
777: 
778:     init_mmx();
779:     init_bitcount();
780:     compile();
781:     calc_conflicts();
782:     
783:     board[0] = 0LL;
784:     memset(&posspiece[0], -1, sizeof(posspiece[0]));
785:     memset(&openchoices[0], -1, sizeof(openchoices[0]));
786: 
787:     for (i = 0; i < xnumrots; i++) {
788:         placed++;
789:         placedP[0]++;
790:         /* Remember whether the x piece is symmetric.  We must
791:          * not use the same hash entries when in one the x is
792:          * symmetric and in the other it is not. 
793:          * This is because we allow different rotations of 
794:          * ASYMMETRIC_PIECE2 in these cases.
795:          */
796:         used[0] = (mirror(rotations[xrotnr[i]])
797:                    == rotations[xrotnr[i]]) << NUM_PIECES;
798:         play_piece(1, xrotnr[i]);
799: 
800:         dumpPiece(rotations[xrotnr[i]]);
801: 
802:         printf("Found %lu solutions so far.\nplaced: %lu = ", 
803:                solutions, placed);
804:         for (j = 0; j < NUM_PIECES; j++) {
805:             printf("%lu+", placedP[j]);
806:         }
807:         printf("(%lu saved)\nsaved: %lu = ", saved, saved);
808:         for (j = 2; j < HASH_DEPTH; j++) {
809:             printf("%lu+", savedP[j]);
810:         }
811:         printf("\nhits: %lu = ", hits);
812:         for (j = 2; j < HASH_DEPTH; j++) {
813:             printf("%lu+", hitsP[j]);
814:         }
815:         printf("\n");
816:     }
817: 
818:     printf("Found %lu solutions.\n", solutions);
819:     return 0;
820: }
821: