001: /* Copyright 2003, Jochen Hoenicke
002:  * 
003:  * Der Algorithmus ist wie folgt:
004: 
005: Zuerst werden alle Rotationen der Teile die in der Quader passen
006: berechnet und in der Datenstruktur "compiled" abgelegt.  Die Teile
007: sind dabei in einer verketteten Liste.  Von dem x-förmigen Teil werden
008: alle symmetrischen Stellungen entfernt, so dass am Ende nur 12
009: Rotationen übrig bleiben, von denen allerdings 4 noch eine Symmetrie
010: haben.  Für diese symmetrischen Stellungen wird dann die Symmetrie
011: über ein asymmetrisches Teil entfernt (das zunächst in asym kompiliert
012: wird).  In dieser Datenstruktur werden zu jedem Bit die Rotationen
013: gespeichert, die dieses bit als niederwertigstes haben.
014: 
015: Als erstes wird dann das x-förmige Teil in placeFirst gelegt (der
016: berühmt-berüchtigte X-Trick), je nachdem ob es symmetrisch ist oder
017: nicht wird dann asym oder das nicht reduzierte Teil in die verkettete
018: Liste gehängt.  Der X-Trick folgt der These den Such-Baum schmal zu
019: halten, denn es gibt nur 12 Möglichkeiten, während es für Bit 0 über
020: 80 Möglichkeiten gibt es zu füllen.
021: 
022: Weil die Reihenfolge der bits bestimmt in welcher Reihenfolge der
023: Quader gefüllt wird, werden anschließend die bits so geshufflet dass
024: es in jedem Schritt möglichst wenige Rotationen gibt.  Dazu berechnet
025: reorder die mittlere Anzahl der Rotationen für jedes bit über
026: Wahrscheinlichkeiten.  Anschliessend werden alle Teile entsprechend
027: der neuen Bit-Reihenfolge transponiert.
028: 
029: Nun läuft endlich die rekursive solve-Methode (zu der es ein etwas
030: schnelleres Assembler-Pendant gibt).  Diese benutzt eine Hashtabelle
031: um ähnliche Stellungen (d.h. gleiche Teile und gleiche Felder belegt)
032: zu erkennen und dort abzukürzen.  Ab einer gewissen Rekursionsstufe
033: läuft dann nur noch die schnelle Assembler-Version, die keine
034: Hashtabelle benutzt.
035: 
036: Als weiterer Trick werden ab Bit Nr. 32 nur noch das hi-word der
037: Rotationen gespeicher, denn das lo-word ist sowieso leer.  Die
038: Assembler-Version hat entsprechen zwei Teile, einen falls das lo-word
039: schon gefüllt ist, und eine bei der das nicht ist.
040: 
041: */
042: 
043: 
044: #include <stdio.h>
045: #include <stdlib.h>
046: #include <string.h>
047: #include "ctpuz.h"
048: 
049: #define NUM_ROTATIONS  24
050: #define FIELD_SIZE     60
051: #define MAX_PIECE_SIZE 10
052: 
053: #define X_PIECE 10
054: #define ASYMMETRIC_PIECE 6
055: #define NUM_PIECES 12
056: 
057: #define coord2bit(x,y,z)  ((x)*12+(y)*3+(z)+4)
058: #define shrink_subs(x)  ((x) >> 10)
059: 
060: typedef int coord[3];
061: typedef coord piece[MAX_PIECE_SIZE];
062: 
063: unsigned char bitordering[64];
064: 
065: /* The compiled pieces are held in a linked list.
066:  * For each firstbit value rotations hold the rotated pieces.
067:  */
068: typedef struct compiled_piece {
069:   struct compiled_piece *next;
070:   long long             *rots[32];
071:   long                  *rots_hi[32];
072:   int                    nr;
073: } compiled_piece;
074: 
075: typedef struct hashed_pos {
076:   long long pos;
077:   int solutions;
078:   int substates;
079: } hashed_pos;
080: 
081: static __inline__ unsigned long
082: log2 (unsigned long word)
083: {
084:   __asm__ ("bsfl %1,%0"
085: :           "=r" (word)
086: :           "r" (word));
087:   return word;
088: }
089: 
090: hashed_pos *hashtable;
091: #define hashcode(pos,used) \
092:     (((pos>>4) ^ (pos >> 13) ^ (pos >> 23) ^ (pos >> 40) ^ used) & (HASH_SIZE-1))
093: 
094: piece ctpieces[NUM_PIECES] = {
095:   {
096:     {0,0,0}, {1,0,0}, {0,1,0}, {0,2,0}, {1,2,0}, {-1,-1,-1}
097:   }, {
098:     {1,0,0}, {2,0,0}, {1,1,0}, {0,2,0}, {1,2,0}, {-1,-1,-1}
099:   }, {
100:     {0,0,0}, {0,1,0}, {0,2,0}, {0,3,0}, {1,3,0}, {-1,-1,-1}
101:   }, {
102:     {0,0,0}, {0,1,0}, {1,1,0}, {0,2,0}, {0,3,0}, {-1,-1,-1}
103:   }, {
104:     {0,0,0}, {1,0,0}, {0,1,0}, {1,1,0}, {1,1,1}, {-1,-1,-1}
105:   }, {
106:     {0,0,0}, {1,0,0}, {2,0,0}, {1,1,0}, {1,2,0}, {-1,-1,-1}
107:   }, {
108:     {0,0,0}, {1,0,0}, {0,1,0}, {1,1,0}, {2,1,0}, {-1,-1,-1}
109:   }, {
110:     {0,0,0}, {0,1,0}, {1,1,0}, {1,2,0}, {2,2,0}, {-1,-1,-1}
111:   }, {
112:     {0,0,0}, {1,0,0}, {0,1,0}, {0,1,1}, {-1,-1,-1}
113:   }, {
114:     {0,0,0}, {1,0,0}, {1,1,0}, {2,1,0}, {1,2,0}, {-1,-1,-1}
115:   }, {
116:     {1,0,0}, {0,1,0}, {1,1,0}, {2,1,0}, {1,2,0}, {-1,-1,-1}
117:   }, {
118:     {0,0,0}, {1,0,0}, {2,0,0}, {3,0,0}, {0,1,0}, {2,1,0}, {-1,-1,-1}
119:   }
120: };
121: 
122: compiled_piece compiled[NUM_PIECES];
123: compiled_piece asym;
124: 
125: compiled_piece reordered[NUM_PIECES];
126: compiled_piece *first_piece;
127: 
128: #ifdef STATISTICS
129: static void dumpBoard(long long board, long long piece) {
130:   char bchar[4] = {'.', 'p', 'X', '*'};
131:   int z, y, x;
132:   for (z = 2; z >= 0; z--) {
133:     for (y = 3; y >= 0; y--) {
134:       for (x = 0; x < 5; x++) {
135:         int i = bitordering[coord2bit(x,y,z)];
136:         int b = (board >> i) & 1;
137:         int p = (piece >> i) & 1;
138:         printf("%c ", bchar[b*2+p]);
139:       }
140:       printf("   ");
141:       for (x = 0; x < 5; x++) {
142:         int i = bitordering[coord2bit(x,y,z)];
143:         printf(" %2d", i);
144:       }
145:       printf("\n");
146:     }
147:     printf("\n");
148:   }
149: }
150: #endif
151: 
152: void rotate(coord c, int rot, coord dest) {
153:   switch (rot / 4) {
154:   case 0:
155:     dest[0] = c[0];
156:     dest[1] = c[1];
157:     dest[2] = c[2];
158:     break;
159:   case 1:
160:     dest[0] = c[0];
161:     dest[1] = c[2];
162:     dest[2] = -c[1];
163:     break;
164:   case 2:
165:     dest[0] = c[1];
166:     dest[1] = c[0];
167:     dest[2] = -c[2];
168:     break;
169:   case 3:
170:     dest[0] = c[1];
171:     dest[1] = c[2];
172:     dest[2] = c[0];
173:     break;
174:   case 4:
175:     dest[0] = c[2];
176:     dest[1] = c[1];
177:     dest[2] = -c[0];
178:     break;
179:   case 5:
180:     dest[0] = c[2];
181:     dest[1] = c[0];
182:     dest[2] = c[1];
183:     break;
184:   }
185:   if (rot & 1) {
186:     dest[0] = -dest[0];
187:     dest[2] = -dest[2];
188:   }
189:   if (rot & 2) {
190:     dest[1] = -dest[1];
191:     dest[2] = -dest[2];
192:   }
193: }
194: 
195: long long rotate_and_shift(piece p, int rot, int shift)
196: {
197:   int i;
198:   long long bitvec = 0LL;
199: 
200:   for (i = 0; i < MAX_PIECE_SIZE; i++) {
201:     coord dest;
202:     if (p[i][0] == -1)
203:       break;
204:     rotate(p[i], rot, dest);
205:     dest[0] += shift % 5;
206:     dest[1] += (shift / 5) % 4;
207:     dest[2] += (shift / 20);
208:     if (dest[0] < 0 || dest[0] >= 5
209:         || dest[1] < 0 || dest[1] >= 4
210:         || dest[2] < 0 || dest[2] >= 3) {
211:       /* piece doesn't fit.. */
212:       return 0LL;
213:     }
214:     bitvec |= 1LL << coord2bit(dest[0], dest[1], dest[2]);
215:   }
216:   return bitvec;
217: }
218: 
219: int better(long long rot1, long long rot2) {
220:   /* Better means 
221:    *   1. the lowest bit nr is higher.
222:    *   2. the value is bigger.
223:    */
224:   return (rot1 & -rot1) > (rot2 & -rot2)
225:     || ((rot1 & -rot1) == (rot2 & -rot2)
226:         && rot1 >= rot2);
227: }
228: 
229: long long mirror(long long rotation) {
230:   long long rot = 0LL;
231:   int x,y,z;
232: 
233:   for (x=0; x < 5; x++) {
234:     for (y = 0; y < 4; y++) {
235:       for (z = 0; z < 3; z++) {
236:         if (rotation & (1LL << coord2bit(x,y,z))) {
237:           rot |= 1LL << coord2bit(4-x,  y,2-z);
238:         }
239:       }
240:     }
241:   }
242:   return rot;
243: }
244: 
245: int best_full_rotation(long long rotation, int axes) {
246:   int x,y,z;
247:   long long rot0, rot1, rot2, rot3;
248: 
249:   if (axes == 2) {
250:     /* calculate the four rotations of the piece, but with
251:      * reversed bit order.
252:      */
253:     rot0 = rot1 = rot2 = rot3 = 0LL;
254:     for (x=0; x < 5; x++) {
255:       for (y = 0; y < 4; y++) {
256:         for (z = 0; z < 3; z++) {
257:           if (rotation & (1LL << coord2bit(x,y,z))) {
258:             rot0 |= 1LL << (63-coord2bit(  x,  y,  z));
259:             rot1 |= 1LL << (63-coord2bit(4-x,3-y,  z));
260:             rot2 |= 1LL << (63-coord2bit(  x,3-y,2-z));
261:             rot3 |= 1LL << (63-coord2bit(4-x,  y,2-z));
262:           }
263:         }
264:       }
265:     }
266:     return rot0 >= rot1
267:       &&   rot0 >= rot2
268:       &&   rot0 >= rot3;
269:     
270:   } else {
271:     /* calculate the four rotations of the piece, but with
272:      * reversed bit order.
273:      */
274:     rot0 = rot1 = rot2 = rot3 = 0LL;
275:     for (x=0; x < 5; x++) {
276:       for (y = 0; y < 4; y++) {
277:         for (z = 0; z < 3; z++) {
278:           if (rotation & (1LL << coord2bit(x,y,z))) {
279:             rot0 |= 1LL << (63 - coord2bit(  x,  y,  z));
280:             rot3 |= 1LL << (63 - coord2bit(4-x,  y,2-z));
281:           }
282:         }
283:       }
284:     }
285:     /* We want the lowest bit of current rotation be higher than for any
286:      * other of the four rotation.  Since we reversed the bits, we want
287:      * the highest bit of rot0 be smaller than for any other rot.
288:      * We can use normal < operation.
289:      */
290:     return rot0 <= rot3;
291:   }
292: }
293: 
294: 
295: void compile(int pnr, int reduce_symm, compiled_piece *dest) {
296:   int rot, shift, i, j;
297:   long long rotpiece;
298:   int numrot[64];
299:   int totalrot = 0;
300:   int hirot = 0;
301:   long long rots[64][24*6];
302:   long long *comprots;
303:   long *comprots_hi;
304: 
305:   dest->nr = pnr;
306:   
307:   for (shift = 0; shift < 64; shift++)
308:     numrot[shift] = 0;
309: 
310:   for (rot = 0; rot < NUM_ROTATIONS; rot++) {
311:     for (shift = 0; shift < FIELD_SIZE; shift++) {
312:       rotpiece = rotate_and_shift(ctpieces[pnr], rot, shift);
313:       if (!rotpiece)
314:         continue;
315: 
316:       if (reduce_symm) {
317:         /* Only take this piece if it is better than the 
318:          * other 3 rotations with respect to the whole cuboid.
319:          *
320:          * Better means 
321:          *   1. the lowest bit nr is higher.
322:          *   2. the value is bigger.
323:          */
324:         if (!best_full_rotation(rotpiece, reduce_symm))
325:           continue;
326:       }
327: 
328:       /* put piece at right position in array */
329:       for (i = 0; i < FIELD_SIZE; i++) {
330:         if ((rotpiece & 1LL << i))
331:           break;
332:       }
333: 
334:       for (j = 0; j < numrot[i]; j++) {
335:         if (rots[i][j] == rotpiece)
336:           /* Rotation was already seen */
337:           goto next_rotation;
338:       }
339: 
340:       rots[i][numrot[i]] = rotpiece;
341:       numrot[i]++;
342:       totalrot++;
343:       if (i > 31)
344:         hirot++;
345:       if (numrot[i] > 24 * 6) {
346:         printf("Too many rotations for %d,%d!",pnr,i);
347:         exit(0);
348:       }
349: 
350:       /*printf("%2d,%2d,%2d: %16Lx\n", pnr, i, rot, rotpiece);*/
351:       /*  dumpBoard(0, rotpiece);*/
352:     }
353:   next_rotation:
354:   }
355: 
356:   printf("Piece %d, %d rotations\n", pnr, totalrot);
357: 
358:   comprots = malloc(sizeof(long long) * (totalrot - hirot + 28)
359:                     + sizeof(long) * (hirot + 32));
360:   for (i = 4; i < 32; i++) {
361:     dest->rots[i] = comprots;
362:     for (j = 0; j < numrot[i]; j++)
363:       *comprots++ = rots[i][j];
364:     *comprots++ = 1LL;
365:   }
366: 
367:   comprots_hi = (long *) comprots;
368:   for (i = 32; i < 64; i++) {
369:     dest->rots_hi[i-32] = comprots_hi;
370:     for (j = 0; j < numrot[i]; j++)
371:       *comprots_hi++ = rots[i][j] >> 32;
372:     *comprots_hi++ = 0LL;
373:   }
374: }
375: 
376: int solutions;
377: 
378: 
379: int used;
380: long long rotpieces[NUM_PIECES];
381: #ifdef COUNT_PLACED
382: unsigned int placedP[NUM_PIECES];
383: #endif
384: #ifdef COUNT_SAVED
385: int hits = 0;
386: unsigned int hitsP[NUM_PIECES] = {0};
387: unsigned int savedP[NUM_PIECES] = {0};
388: long long int saved = 0;
389: #endif
390: int placed = 0;
391: 
392: #ifdef COUNT_STEPS
393: int ctr[20] = {0,};
394: #endif
395: 
396: #if 0
397: static void dumpSolution(int pieces) {
398:   char bchar[] = "0123456789AB....";
399:   int z, y, x, i;
400:   for (z = 2; z >= 0; z--) {
401:     for (y = 3; y >= 0; y--) {
402:       for (x = 0; x < 5; x++) {
403:         long long mask = 1LL << bitordering[coord2bit(x,y,z)];
404:         for (i = 0; i < pieces; i++) {
405:           if ((rotpieces[i] & mask))
406:             break;
407:         }
408:         printf("%c ", i == pieces? '.' : bchar[i]);
409:       }
410:       printf("\n");
411:     }
412:     printf("\n");
413:   }
414: }
415: #endif
416: 
417: #ifdef STATISTICS
418: void statistics() {
419: #if defined(COUNT_PLACED) || defined(COUNT_SAVED) || defined(COUNT_STEPS)
420:     int i;
421: #endif
422:     printf("placed: %u ", placed);
423: #ifdef COUNT_PLACED
424:     for (i = 0; i < NUM_PIECES; i++) {
425:         printf("%u+", placedP[i]);
426:     }
427: #endif
428:     printf("\n");
429: #ifdef COUNT_SAVED
430:     printf("Hits: %d  splitted:", hits);
431:     for (i = 0; i < NUM_PIECES; i++) {
432:         printf("%u+", hitsP[i]);
433:     }
434:     printf("\n");
435:     printf("Saved: %lld  splitted:", saved);
436:     for (i = 0; i < NUM_PIECES; i++) {
437:         printf("%u, ", savedP[i]);
438:     }
439:     printf("\n");
440: #endif
441:     
442: #ifdef COUNT_STEPS
443:     printf("Counters: ");
444:     for (i = 0; i < 20; i++) {
445:         printf("%u, ", ctr[i]);
446:     }
447:     printf("\n");
448: #endif
449: }
450: #endif
451: 
452: extern void solve_asm(long long board, int firstbit, int depth);
453: 
454: /* This is the C version of the recursive solve method.  There is also
455:  * an assembler version that is used for the last rotations, where speed
456:  * is important.  The C version differs in that it keeps a hashtable and
457:  * that it can't handle rot_hi.
458:  */
459: void solve(long long board, int firstbit, int depth) {
460:   int i;
461:   int solved = 1;
462:   int hc, oldplaced, oldsolutions;
463:   struct compiled_piece **ppiece;
464: 
465:   for (i = firstbit; i < FIELD_SIZE; i++) {
466:     if (!(board & (1LL << i))) {
467:       firstbit = i;
468:       break;
469:     }
470:   }
471:   if (firstbit > 31) {
472:     solve_asm(board, firstbit, depth);
473:     return;
474:   }
475: 
476:   ppiece = &first_piece;
477:   while (*ppiece) {
478:     struct compiled_piece *piece;
479:     long long *rots;
480: 
481:     piece = *ppiece;
482:     *ppiece = piece->next;
483:     used ^= 1 << piece->nr;
484:     rots = piece->rots[firstbit];
485: 
486:     solved = 0;
487:     while (!(*(long*)rots & 1)) {
488:       long long piecemask = *rots++;
489: 
490:       if ((board & piecemask) == 0LL) {
491: 
492:         long long nboard;
493: #ifdef COUNT_PLACED
494:         placedP[depth]++;
495: #endif
496:         placed++;
497:         rotpieces[depth] = piecemask;
498: 
499:         oldsolutions = solutions;
500:         oldplaced = placed;
501: 
502:         nboard = board | piecemask;
503:         hc = hashcode(nboard, used);
504:         if (hashtable[hc].pos == nboard) {
505:           int subs;
506:           solutions += hashtable[hc].solutions;
507: 
508:           subs = hashtable[hc].substates;
509:           placed += subs;
510: #ifdef COUNT_SAVED
511:           saved += subs;
512:           savedP[depth] += subs;
513:           hitsP[depth]++;
514:           hits++;
515: #endif
516:         } else {          
517:           if (depth < HASH_DEPTH) {
518:             solve(nboard, firstbit+1, depth + 1);
519:           } else {
520: #if NUM_PIECES == HASH_DEPTH + 1
521:             dumpSolution(depth + 1);
522:             solutions++;
523: #else
524:             solve_asm(nboard, firstbit+1, depth + 1);
525: #endif
526:           }
527: 
528:           if (hashtable[hc].substates < placed - oldplaced)
529:           {
530:             hashtable[hc].pos = nboard;
531:             hashtable[hc].solutions = solutions - oldsolutions;
532:             hashtable[hc].substates = placed - oldplaced;
533:           }
534:         }
535: #if 0
536:         if (solutions == oldsolutions && (placed - oldplaced) > 100000) {
537:           dumpSolution(depth + 1);
538:           printf("has no solutions but %d pieces placed\n", placed - oldplaced);
539:         }
540: #endif
541: #ifdef STATISTICS
542: #if STATISTICS >= 2
543:         if (depth < STATISTICS /* && solutions > oldsolutions*/) {
544:           printf("%d: %2d %4d solutions ; %7d solutions total\n", 
545:                  depth, piece->nr, solutions - oldsolutions, solutions);
546:           dumpBoard(board, piecemask);
547:           statistics();
548:         }
549: #endif
550: #endif
551:       }
552:     }
553:     used ^= 1 << piece->nr;
554:     *ppiece = piece;
555:     ppiece = &piece->next;
556:   }
557: }
558: 
559: long long transpose(long long piece) {
560:     long long result = 0LL;
561:     int i;
562:     for (i = 0; i < 64; i++) {
563:         if (piece & (1ULL << i)) {
564:             result |= 1ULL << bitordering[i];
565:         }
566:     }
567:     return result;
568: }
569: 
570: void transpose_piece(struct compiled_piece *piece, 
571:                      struct compiled_piece *dest) {
572:     int totalrot = 0;
573:     int hirot = 0;
574:     long long rots[64][24*6];
575:     long long *prots;
576:     long *prots_hi;
577:     int numrot[64];
578:     int i, j;
579:     for (i = 4; i < 64; i++)
580:         numrot[i] = 0;
581: 
582:     for (i = 4; i < 32; i++) {
583:         prots = piece->rots[i];
584:         while (*prots != 1ULL) {
585:             long long rot = transpose(*prots);
586:             for (j = 4; j < 64; j++)
587:                 if (rot & (1ULL << j))
588:                     break;
589:             rots[j][numrot[j]++] = rot;
590:             totalrot++;
591:             if (j >= 32)
592:                 hirot++;
593:             prots++;
594:         }
595:     }
596:     for (i = 32; i < 64; i++) {
597:         prots_hi = piece->rots_hi[i-32];
598:         while (*prots_hi != 0LL) {
599:             long long rot = transpose((long long) *prots_hi << 32);
600:             for (j = 4; j < 64; j++)
601:                 if (rot & (1ULL << j))
602:                     break;
603:             rots[j][numrot[j]++] = rot;
604:             totalrot++;
605:             if (j >= 32)
606:                 hirot++;
607:             prots_hi++;
608:         }
609:     }
610:     
611:     dest->nr = piece->nr;
612:     prots = malloc(sizeof(long long) * (totalrot - hirot + 28)
613:                    + sizeof(long) * (hirot + 32));
614:     for (i = 4; i < 32; i++) {
615:         dest->rots[i] = prots;
616:         for (j = 0; j < numrot[i]; j++)
617:             *prots++ = rots[i][j];
618:         *prots++ = 1LL;
619:     }
620:     
621:     prots_hi = (long *) prots;
622:     for (i = 32; i < 64; i++) {
623:         dest->rots_hi[i-32] = prots_hi;
624:         for (j = 0; j < numrot[i]; j++)
625:             *prots_hi++ = rots[i][j] >> 32;
626:         *prots_hi++ = 0L;
627:     }
628: }
629: 
630: long long reorder(long long board, struct compiled_piece *piece_list) {
631:     double cube_freeness[64];
632:     double rotations[64];
633:     double rotations_used[64];
634:     unsigned char usedbit[64];
635:     int i, j;
636:     struct compiled_piece *p;
637:     struct compiled_piece **last;
638:     int bit = 0;
639: 
640:     for (i = 0; i < 64; i++) {
641:         if (!(board & (1ULL << i))) {
642:             cube_freeness[i] = 1.0;
643:             usedbit[i] = 0;
644:         } else {
645:             bitordering[i] = bit++;
646:             cube_freeness[i] = 0.0;
647:             usedbit[i] = 1;
648:         }
649:     }
650: 
651: /*#define DEBUG_BITORDERING	*/
652: #ifdef DEBUG_BITORDERING        
653:     printf ("Bitordering:");
654: #endif
655:     for (; bit < 64; bit++) { 
656:         int best;
657:         double bestrot;
658:         for (j = 4; j < 64; j++) {
659:             rotations[j] = 0.0;
660:             rotations_used[j] = 0.0;
661:         }
662:         for (p = piece_list; p; p = p->next) {
663:             for (i = 4; i < 32; i++) {
664:                 long long *rots = p->rots[i];
665:                 while (*rots != 1LL) {
666:                     double weight = 1.0;
667:                     for (j = i; j < 64; j++) {
668:                         if (*rots & (1ULL << j)) {
669:                             weight *= cube_freeness[j];
670:                         }
671:                     }
672:                     /* weight is the probability, that this rotation
673:                      * is still usable
674:                      */
675:                     for (j = i; j < 64; j++) {
676:                         if (*rots & (1ULL << j)) {
677:                             rotations[j] += weight;
678:                         }
679:                     }
680:                     rots++;
681:                 }
682:             }
683:             for (i = 32; i < 64; i++) {
684:                 long *rots_hi = p->rots_hi[i-32];
685:                 while (*rots_hi != 0) {
686:                     double weight = 1.0;
687:                     for (j = i; j < 64; j++) {
688:                         if (*rots_hi & (1UL << (j-32))) {
689:                             weight *= cube_freeness[j];
690:                         }
691:                     }
692:                     for (j = i; j < 64; j++) {
693:                         if (*rots_hi & (1UL << (j-32))) {
694:                             rotations[j] += weight;
695:                         }
696:                     }
697:                     rots_hi++;
698:                 }
699:             }
700:         }
701:         best = 0;
702:         bestrot = 1000.0;
703:         for (i = 4; i < 64; i++) {
704:             if (!usedbit[i]
705:                 && (rotations[i] * cube_freeness[best]
706:                     < bestrot * cube_freeness[i]
707:                     || cube_freeness[i] == 0.0))
708:             {
709:                 best = i;
710:                 bestrot = rotations[i];
711:             }
712:         }
713:         usedbit[best] = 1;
714:         bitordering[best] = bit;
715: 
716: #ifdef DEBUG_BITORDERING        
717:         printf("\n");
718:         int z, y, x;
719:         for (z = 2; z >= 0; z--) {
720:             for (y = 3; y >= 0; y--) {
721:                 for (x = 0; x < 5; x++) {
722:                     int i = coord2bit(x,y,z);
723:                     printf("%3.3lf ", cube_freeness[i]);
724:                 }
725:                 printf("    ");
726:                 for (x = 0; x < 5; x++) {
727:                     int i = coord2bit(x,y,z);
728:                     printf("%6.2lf%c ", rotations[i] / cube_freeness[i],
729:                            i == best ? '*': ' ');
730:                 }
731:                 printf("\n");
732:             }
733:             printf("\n");
734:         }
735:         printf(" %d", best);
736: #endif
737: 
738: 
739:         if (bestrot == 0.0)
740:             continue;
741:         
742:         for (p = piece_list; p; p = p->next) {
743:             for (i = 4; i < 32 && i <= best; i++) {
744:                 long long *rots = p->rots[i];
745:                 while (*rots != 1LL) {
746:                     if (*rots & (1ULL << best)) {
747:                         double weight = 1.0;
748:                         for (j = i; j < 64; j++) {
749:                             if (*rots & (1ULL << j)) {
750:                                 weight *= cube_freeness[j];
751:                             }
752:                         }
753:                         for (j = i; j < 64; j++) {
754:                             if (*rots & (1ULL << j)) {
755:                                 rotations_used[j] += weight;
756:                             }
757:                         }
758:                     }
759:                     rots++;
760:                 }
761:             }
762:             for (i = 32; i <= best; i++) {
763:                 long *rots_hi = p->rots_hi[i-32];
764:                 while (*rots_hi != 0) {
765:                     if (*rots_hi & (1UL << (best-32))) {
766:                         double weight = 1.0;
767:                         for (j = i; j < 64; j++) {
768:                             if (*rots_hi & (1UL << (j-32))) {
769:                                 weight *= cube_freeness[j];
770:                             }
771:                         }
772:                         for (j = i; j < 64; j++) {
773:                             if (*rots_hi & (1UL << (j-32))) {
774:                                 rotations_used[j] += weight;
775:                             }
776:                         }
777:                     }
778:                     rots_hi++;
779:                 }
780:             }
781:         }
782: 
783:         double factor = cube_freeness[best] / bestrot;
784:         for (j = 4; j < 64; j++) {
785:             cube_freeness[j] *= 1 - factor * rotations_used[j];
786:         }
787:         cube_freeness[best] = 0;
788:     }
789: #ifdef DEBUG_BITORDERING        
790:     printf ("\n");
791: #endif
792: 
793:     if (first_piece) {
794:         for (p = first_piece; p; p = p->next) {
795:             free(p->rots[4]);
796:         }
797:     }
798: 
799:     i = 0;
800:     last = &first_piece;
801:     for (p = piece_list; p; p = p->next) {
802:         transpose_piece(p, &reordered[i]);
803:         *last = &reordered[i];
804:         last = &reordered[i].next;
805:         i++;
806:     }
807:     last = NULL;
808:     board = transpose(board);
809: #ifdef DEBUG_BITORDERING        
810:     printf("reordering done\n");
811: #endif
812:     return board;
813: }
814: 
815: void placeFirst(long long rot) {
816:     int oldsolutions = solutions;
817:     long long board;
818:     placed++;
819: #ifdef COUNT_PLACED
820:     placedP[0]++;
821: #endif
822:     /* The first piece is the x piece.  We must distinguish whether that
823:      * piece is in a symmetric position or not.  If it is symmetric we
824:      * need to use the asymmetric_piece to remove symmetric solutions.
825:      *
826:      * We also hack the used vector so that the hashtable isn't shared
827:      * between symmetric and asymmetric cases.
828:      */
829:     if (mirror(rot) == rot) {
830:         used = 1 << X_PIECE;
831:         compiled[ASYMMETRIC_PIECE-1].next = &asym;
832:     } else {
833:         used = 0;
834:         compiled[ASYMMETRIC_PIECE-1].next = &compiled[ASYMMETRIC_PIECE];
835:     }
836: 
837:     board = reorder(15ULL | rot, &compiled[0]);
838:     rotpieces[0] = board;
839: 
840:     /* hashtable mustn't be reused! */
841:     memset(hashtable, 0, HASH_SIZE * sizeof(*hashtable));
842: 
843:     solve(board, coord2bit(0,0,0), 1);
844: #ifdef STATISTICS
845:     printf("0: %2d %4d solutions ; %7d solutions total\n", 
846:            X_PIECE, solutions - oldsolutions, solutions);
847:     dumpBoard(15ULL, board);
848:     statistics();
849: #endif
850: }
851: 
852: int main() {
853:     int i;
854:     /* compile all pieces.  Remove all symmetries for the X_PIECE */
855:     for (i = 0 ; i< NUM_PIECES; i++) {
856:         compile(i, i == X_PIECE ? 2 : 0, &compiled[i]);
857:     }
858:     /* compile ASYMMETRIC_PIECE again with removed symmetries.  It
859:      * is used when the X_PIECE is symmetric.
860:      */
861:     compile(ASYMMETRIC_PIECE, 1, &asym);
862:     
863:     /* link the compiled pieces together */
864:     for (i = 0 ; i< NUM_PIECES-1; i++)
865:         compiled[i].next = &compiled[i+1];
866:     compiled[NUM_PIECES-1].next = NULL;
867: 
868:     /* remove X_PIECE from the list, as it is placed first. */
869:     compiled[X_PIECE-1].next = &compiled[X_PIECE+1];
870:     /* Set asym.next to right value. */
871:     asym.next = &compiled[ASYMMETRIC_PIECE + 1];
872:     
873:     printf("Rotation table built\n");
874:     
875:     first_piece = NULL;
876:     solutions = 0;
877:     placed = 0;
878: #ifdef COUNT_PLACED
879:     for (i = 0; i < NUM_PIECES; i++) {
880:         placedP[i] = 0;
881:     }
882: #endif
883:     
884:     hashtable = malloc(HASH_SIZE * sizeof(*hashtable));
885:     printf("Hashtable allocated\n");
886:     
887:     /* place x piece */
888:     for (i = 4; i < 32; i++) {
889:         long long *rots = compiled[X_PIECE].rots[i];
890:         while (*rots != 1LL) {
891:             placeFirst(*rots);
892:             rots++;
893:         }
894:     }
895:     for (i = 32; i < 64; i++) {
896:         long *rots_hi = compiled[X_PIECE].rots_hi[i-32];
897:         while (*rots_hi != 0L) {
898:             placeFirst(((long long) *rots_hi) << 32);
899:             rots_hi++;
900:         }
901:     }
902:     printf("solutions: %d\n", solutions);
903:     return 0;
904: }