0001: /*>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>*/
0002: /* This Header is built automatically. Do not change.               */
0003: /* $Id: main.c,v 1.28 2003/04/30 20:32:50 raap Exp $ */
0004: /*<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<*/
0005: 
0006: /* This program is (c) 2003 Horst Raap and may be freely distributed under the GNU GPL */
0007: 
0008: /********************************************************************/
0009: /* 

0010: Dieses Programm löst das c't Puzzle.

0011: Folgende Ideen zur Zeitoptimierung wurden zusätzlich zu den im Artikel beschriebenen eingebaut:

0012: 

0013: - Es wird nicht immer versucht, das nächste Loch im Klotz aufzufüllen, sondern je nach Gegebenheit wird

0014:         entweder das Loch mit den wenigsten Füll-Möglichkeiten durchprobiert oder aber es wird versucht,

0015:         das Teil mit den wenigsten Möglichkeiten an irgendeine Stelle des Klotzes zu packen.

0016:         Quasi nebenbei werden so sehr schnell unfüllbare Löcher und/oder nicht mehr platzierbare Klötze entdeckt.

0017: 

0018: - Es wird eine relativ komplizierte Datenstruktur "FillList" aufgebaut, die zu jedem Loch im Klotz angibt, welche Teile in welchen

0019:         Lagen noch dort hineinpassen. Bis zu einer gewissen Tiefe wird diese Struktur ständig aktualisiert, damit man zügig die o. g.

0020:         Informationen ermitteln kann. 

0021:         

0022: -  Auch bei herausgerechneten Symmetrien ergeben sich bei obigem Vorgehen Situationen, die bereits durchprobiert wurden,

0023:         d. h. dieselbe Menge von Teilen belegt die gleichen Teilwürfel. Für solche Situationen, die keine Lösungen liefern 

0024:         (das sind die meisten), wird eine Hash-Tabelle angelegt, so dass bei einer Wiederholung nicht mehr erneut gesucht werden muss.

0025: 

0026: - Einige Situationen können recht frühzeitig als unlösbar erkannt werden, wenn man ein Paritäts-Argument benutzt:

0027:         Die Teilwürfel des Klotzes werden dabei abwechselnd schwarz und weiß gefärbt. Wenn der Klotz ganz gefüllt ist, sind genauso

0028:         viele schwarze wie weiße Teilwürfel belegt, d. h. die Parität muss bei jeder Lösung 0 sein.

0029:         Jetzt stelle man sich vor, es sind noch drei weiße und drei schwarze Teilwürfel frei und das einzufügende Teil ist

0030:         das "T". Das "T" hat aber in jeder Lage eine Parität von 2 oder -2, so dass es keine Lösung geben kann.

0031:         Dieser Algorithmus ist hier etwas verallgemeinert implementiert.

0032: */
0033: /********************************************************************/
0034: 
0035: #define DEBUG
0036: //#define EARLYABORT

0037: 
0038: /*=================================================================*/
0039: /*              Include files needed are following here !          */
0040: /*=================================================================*/
0041: 
0042: #include <stdio.h>
0043: #include <stdlib.h>
0044: #include <unistd.h>
0045: #define _GNU_SOURCE
0046: #include <getopt.h>
0047: 
0048: 
0049: /*=================================================================*/
0050: /*              End of includes !                                  */
0051: /*=================================================================*/
0052: 
0053: 
0054: /* /////////////////////////////////////////////////////////////// */
0055: /*              External Variables and Functions                   */
0056: /* /////////////////////////////////////////////////////////////// */
0057: 
0058: int getopt(int argc, char * const argv[],
0059:                   const char *optstring);
0060: 
0061: extern char *optarg;
0062: extern int optind, opterr, optopt;
0063: 
0064:       
0065: /* \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\ */
0066: /*              Global Variables                                   */
0067: /* \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\ */
0068: 
0069: 
0070: 
0071: /* Verbosity */
0072: int Verb = 0;
0073: 
0074: /* Is set to 1 iff we must print solutions */
0075: int PrtSol = 0;
0076: 
0077: #ifdef EARLYABORT
0078:         int mindepth = 0;
0079: #endif

0080: 
0081: #define HashDepth 7
0082: #define UPDATEFILLDEPTH 5
0083: 
0084: /* This part will be treated differently due to symmetry */
0085: #define SYMMPART 2
0086: 
0087: /* Is 1 iff the part currently is in use */
0088: int Used[12];
0089: /* Same as above but with bits */
0090: unsigned int UseMap;
0091: 
0092: /* Used to find the lowest 0-Bit in an integer fast */
0093: unsigned char LeastZero[(1<<16)];
0094: 
0095: 
0096: int solutions;
0097: 
0098: /* Preference ordering of the parts */
0099: int TryList[12]={11,10,7,5,3,2,1,0,9,8,6,4}; 
0100: 
0101: #ifdef DEBUG
0102: int Nodes[12];
0103: int MinHoleTries[12];
0104: int SpecialHoleTries[12];
0105: int PartTries[12];
0106: int ParityFails[12];
0107: int Repetitions[12];
0108: int ZeroHoles[12];
0109: #endif

0110: 
0111: /*\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\*/
0112: /*              End of Global Variables                            */
0113: /*\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\*/
0114: 
0115: /*------------------------ Local Variables ------------------------*/
0116: 
0117: /* Allow automatic identification by RCS */
0118: static char RcsId[]="$Id: main.c,v 1.28 2003/04/30 20:32:50 raap Exp $";
0119: 
0120: 
0121: /*------------------ Forward Function definitions -----------------*/
0122: 
0123: void CleanExit();    /* terminate program gracefully */
0124: static void Usage();        /* give a usage message */
0125: 
0126: /*-----------------------------------------------------------------*/
0127: 
0128: /* Just for convenience */
0129: #define bool int
0130: 
0131: 
0132: /* A 60 bit BitMap represents the cubes of the block

0133:         or a part at a spcific placement within the block

0134: */  
0135: typedef struct {
0136:         unsigned long w1;
0137:         unsigned long w2;
0138: } BitMap; 
0139: 
0140: /* -------------------------- General functions ------------------------------------- */
0141: void NewLine() {
0142:         printf("\n");
0143: };
0144: 
0145: static inline
0146: int abs(int a){
0147:         if (a < 0) return -a;
0148:         else return a;
0149: };
0150: 
0151: 
0152: /* Mapping from coordinates to an integer 0..59 */
0153: int Coord2Index(int x, int y, int z){
0154:  return(z + y * 3 + x * 12); 
0155: };
0156: 
0157: 
0158: /* --------------------------- Bitmap handling --------------------------------------- */
0159: 
0160: /* For each integer below 2**16 store the index of the lowest 0-bit 

0161:          Stores 16 if there are no 0-bits 

0162: */
0163: void InitLeastZero(){
0164:         int i,j;
0165:         
0166:         for (i=0; i<(1<<16); i++){
0167:                 for (j=0; j<16; j++)
0168:                         if (0 == (i & (1<<j)))
0169:                                 break;
0170:                 LeastZero[i]=j;
0171:         };
0172: };
0173: 
0174: /* For each unsigned integer below 2**32 returns the index of the lowest 0-bit */
0175: static inline
0176: int LeastZero32(unsigned long w){
0177:         if ((w & 0xffffL) != 0xffffL)
0178:                 return LeastZero[w & 0xffffL];
0179:         else
0180:                 return LeastZero[w >> 16] + 16;
0181: };
0182: 
0183: 
0184: /* Returns index of the first empty space in given bitmap */
0185: static inline
0186: int FindFirstHole(BitMap *m){
0187:         if (m->w1 != 0xffffffff)
0188:                 return (LeastZero32(m->w1));
0189:         else
0190:                 return (LeastZero32((m->w2)) + 32);
0191: };
0192: 
0193: 
0194: /* Returns 0 iff the given bitmaps are disjoint (have no common bits set) */
0195: static inline 
0196: bool disjoint (BitMap *m1, BitMap *m2){
0197:         return ( ((m1->w1 & m2->w1) == 0)  &&
0198:                          ((m1->w2 & m2->w2) == 0) 
0199:         );
0200: };
0201: 
0202: 
0203: /* Anding two bitmaps together storing result in second bitmap */
0204: static inline 
0205: void SetAnd (BitMap *m1, BitMap *m2){
0206:         m2->w1 &= m1->w1;
0207:         m2->w2 &= m1->w2;
0208: };
0209: 
0210: 
0211: /* Returns <> 0 iff bit i is set in the given bitmap */
0212: bool GetBit(int i, BitMap *m) {
0213:         if (i<32) 
0214:                 return (m->w1 & (1<<i));
0215:         else
0216:                 return (m->w2 & (1<<(i-32)));
0217: };
0218: 
0219: void PrtBitMap(BitMap *m) {
0220:         int x, y, z;
0221:         NewLine();
0222:         
0223:         for (z=2; z>=0; z--){
0224:                 for (y=3; y>=0; y--){
0225:                         for (x=0; x<5; x++)
0226:                                 printf("%2d ", GetBit(Coord2Index(x,y,z),m)?1:0);
0227:                         NewLine();
0228:                 };
0229:                 NewLine();
0230:         }
0231: };
0232: 
0233: 
0234: /* Sets a bitmap to just the given bit */
0235: void IndexToBit (int idx, BitMap *m){
0236:         if (idx < 32) {
0237:                 m->w1 = 1 << idx;
0238:                 m->w2 = 0;
0239:         } else {
0240:                 m->w1 = 0;
0241:                 m->w2 = 1 << (idx-32);
0242:         };
0243: };
0244: 
0245: 
0246: /* Returns number of bits set in the given bitmap */
0247: int CntBits (BitMap *m){
0248:         int i, cnt=0;
0249:         for (i=0; i<60; i++)
0250:                 if (GetBit(i,m)) cnt++;
0251:         return cnt;
0252: };
0253: 
0254: 
0255: /* Returns TRUE iff the given bitmap is 1 at index i */
0256: static inline 
0257: bool IsSet (BitMap *m, int i){
0258:         if (i<32) return ( m->w1 & (1<<i)) ;
0259:         else return ( m->w2 & (1 << (i-32))); 
0260: };
0261: 
0262: 
0263: /* ------------------------------------------- Hash table handling ---------------------------------- */
0264: 
0265: /* The information to be stored in a hash entry */
0266: typedef struct {
0267:         BitMap        m;
0268:         unsigned short use;
0269:         short depth;
0270: } State;
0271:  
0272: 
0273: State *HashTable = NULL; 
0274: /* Number of entries in hash table */
0275: int        HashTableLim;
0276: unsigned long HashMask;
0277: /* some random bits used for hashing */
0278: long int Rand[1<<16];
0279: 
0280: void InitHash(){
0281:         int i;
0282:         srandom(1);
0283:         for (i=0; i<(1<<16); i++)
0284:                 Rand[i] = random();
0285:         /* We dont know how much memory we can get for the hash table, try some powers of two */
0286:         for (i=24; i>0; i--){
0287:                 HashTableLim = 1<<i;
0288:                 HashTable = (State *) calloc(HashTableLim,sizeof(State));
0289:                 if (HashTable != 0) break;
0290:         };
0291:         if (HashTable == 0)
0292:                 CleanExit("Not enough memory for hash table\n",20);
0293:         HashMask = HashTableLim - 1;
0294: 
0295:         for (i=0; i<HashTableLim; i++){
0296:                 (HashTable+i)->depth = 99;
0297:                 (HashTable+i)->use = 0xffff;
0298:         };                
0299: };
0300: 
0301: 
0302: /* Check if this situation is already in HashTable 

0303:         and return TRUE

0304:         else return 0

0305: */
0306: bool Recall (BitMap *bm){
0307:         unsigned int i;
0308:         State *s;
0309:         unsigned long hv, hv1;
0310:         
0311:         /* Compute HashValue */
0312:         hv1 = bm->w1 ^ bm->w2;
0313:         hv = Rand[hv1 & 0xffff] ^ Rand[hv1 >> 16] ^ Rand[UseMap];
0314: 
0315:         i = hv & HashMask;
0316:         s = HashTable+i;
0317:         if ((s->use == UseMap) && (s->m.w1 == bm->w1) && (s->m.w2 == bm->w2) )
0318:                 return 1;
0319: 
0320:         i = (hv + 1) & HashMask;
0321:         s = HashTable+i;
0322:         return ((s->use == UseMap) && (s->m.w1 == bm->w1) && (s->m.w2 == bm->w2) );
0323: };
0324: 
0325: 
0326: /* Store this situation in HashTable 

0327:         but do not override situations at lower depth

0328: */
0329: bool StoreHash(BitMap *bm, int depth){
0330:         unsigned int i;
0331:         State *s;
0332:         unsigned long hv, hv1;
0333:         
0334:         /* Compute HashValue */
0335:         hv1 = bm->w1 ^ bm->w2;
0336:         hv = Rand[hv1 & 0xffff] ^ Rand[hv1 >> 16] ^ Rand[UseMap];        
0337: 
0338:         i = hv & HashMask;
0339:         s = HashTable+i;                
0340:         if (s->depth >= depth) {
0341:                 s->use = UseMap;
0342:                 s->m = *bm;
0343:                 s->depth = depth;
0344:                 return 0;
0345:         };        
0346:         i = (hv + 1) & HashMask;
0347:         s = HashTable+i;                
0348:         if (s->depth >= depth) {
0349:                 s->use = UseMap;
0350:                 s->m = *bm;
0351:                 s->depth = depth;
0352:                 return 0;
0353:         };
0354: return 0;
0355: };
0356: 
0357: 
0358: /* -------------------------- Cube handling ----------------------------------------- */
0359: 
0360: /* A cube is defined by its 3D position */
0361: typedef struct {
0362:         int x;
0363:         int y;
0364:         int z;
0365:         BitMap m;
0366: } Cube;
0367: 
0368: /* Returns an index from 0 to 59 for each cube */
0369: int CubeIndex (Cube *c){
0370:         return ( Coord2Index(c->x, c->y, c->z)); 
0371: };
0372: 
0373: /* Sets a bit in the bitmap according to given cube */
0374: void SetBit(Cube *c, BitMap *m) {
0375:         int i;
0376:         i = CubeIndex(c);
0377:         if (i<32) 
0378:                 m->w1 |= 1<<i;
0379:         else
0380:                 m->w2 |= 1<<(i-32);
0381: };
0382: 
0383: void PrtCube (Cube *c) {
0384:         printf("(%d,%d,%d)", c->x, c->y, c->z);
0385: };
0386: 
0387: 
0388: /* Shift Cube c by a specified amount */
0389: void ShiftCube(Cube *c, int dx, int dy, int dz){
0390:         c->x += dx;
0391:         c->y += dy;
0392:         c->z += dz;
0393: };
0394: 
0395: /* Turn a cube 90 degrees around z-axis */
0396: void TurnCubeZ(Cube *c){
0397:         int h;
0398:         h = c->y;
0399:         c->y = c->x;
0400:         c->x = -h;
0401: };
0402: 
0403: /* Turn a cube 90 degrees around y-axis */
0404: void TurnCubeY(Cube *c){
0405:         int h;
0406:         h = c->z;
0407:         c->z = c->x;
0408:         c->x = -h;
0409: };
0410: 
0411: /* Turn a cube 90 degrees around x-axis */
0412: void TurnCubeX(Cube *c){
0413:         int h;
0414:         h = c->z;
0415:         c->z = c->y;
0416:         c->y = -h;
0417: };
0418: 
0419: /* Rotate the block around the given axis

0420:         and set Cube to new position

0421: */
0422: void RotateCube(Cube *c, int rx, int ry, int rz){
0423:         if (rx) {
0424:                 c->z = 2 - c->z;
0425:                 c->y = 3 - c->y;
0426:         };
0427:         if (ry) {
0428:                 c->x = 4 - c->x;
0429:                 c->z = 2 - c->z;
0430:         };
0431:         if (rz) {
0432:                 c->x = 4 - c->x;
0433:                 c->y = 3 - c->y;
0434:         };
0435: };
0436: 
0437: 
0438: /* --------------------------------------- Parity Handling ---------------------------------- */
0439: /*

0440:         We assign a color (black = 0, white = 1) to every cube in the block

0441:         The colors are assigned alternately black and white along each axis of the block.

0442:         starting with black at (0,0,0).

0443:         Whenever we place a part in the block, it will cover a number of white and a number of black cubes.

0444:         We call the parity of a part the difference between these two numbers.

0445:         The absolute parity is independent of the placement of the part within the block.

0446:         If we have found a solution, the total parity of the parts must equal the parity of the filled block,

0447:         which is 0.

0448:         By checking the parity of the unused parts we can sometimes detect unsolvable situations early on.

0449: */
0450: 
0451: /* Maximum possible parity which can be achieved by the unused parts */
0452: int MaxParity;
0453: 
0454: /* For each part its absolute parity */
0455: int AbsParity[12];
0456: 
0457: /* Will be filled with a pattern so that two neighbours in any direction are always 0 and 1*/
0458: BitMap ParityMap;
0459: 
0460: /* Sets the global ParityMap */
0461: void InitParity(){
0462:         Cube c;
0463:         
0464:         for (c.x=0; c.x<5; c.x++)
0465:                 for (c.y=0; c.y<4; c.y++)
0466:                         for (c.z=0; c.z<3; c.z++){
0467:                                 if ((c.x+c.y+c.z) & 1) SetBit(&c, &ParityMap);        
0468:         };
0469: };
0470: 
0471: 
0472: /* Returns parity of the given bitmap m1 (i.e. the number of white cubes set - number of black cubes set) */
0473: int Parity (BitMap *m1){
0474:         BitMap sum;
0475:         BitMap *pm = &ParityMap;
0476:         int cnt;
0477:         
0478:         sum.w1 = (m1->w1 & pm->w1); 
0479:         sum.w2 = (m1->w2 & pm->w2);
0480:         
0481:         cnt = CntBits(&sum);
0482:          
0483:         sum.w1 = (m1->w1 & ~(pm->w1)); 
0484:         sum.w2 = (m1->w2 & ~(pm->w2));
0485:         cnt -= CntBits(&sum);
0486:         return cnt;
0487: };
0488: 
0489: /* ---------------------------------------- Part handling ------------------------------------- */
0490: 
0491: /* A part consists of at most 6 cubes, a bitmap description and its parity at this point */
0492: typedef struct {
0493:         BitMap m;
0494:         int Parity; 
0495:         int n; /* number of cubes */
0496:         Cube c[6];
0497:         int PartNo;  /* Original part number */
0498: } Part;
0499:   
0500: 
0501: /* The original parts */
0502: Part Teil[12];
0503: 
0504: /* Initialize the global array of basic parts */
0505: void InitTeile( Part *Teil){
0506:         Teil[0].n = 5;
0507:         Teil[0].c[0] = (Cube) {0,0,0};
0508:         Teil[0].c[1] = (Cube) {1,0,0};
0509:         Teil[0].c[2] = (Cube) {0,1,0};
0510:         Teil[0].c[3] = (Cube) {0,2,0};
0511:         Teil[0].c[4] = (Cube) {1,2,0};
0512:         Teil[0].PartNo = 0;
0513:         
0514:         Teil[1].n = 5;
0515:         Teil[1].c[0] = (Cube) {0,0,0};
0516:         Teil[1].c[1] = (Cube) {1,0,0};
0517:         Teil[1].c[2] = (Cube) {1,1,0};
0518:         Teil[1].c[3] = (Cube) {1,2,0};
0519:         Teil[1].c[4] = (Cube) {2,2,0};
0520:         Teil[1].PartNo = 1;
0521:                 
0522:         Teil[2].n = 5;
0523:         Teil[2].c[0] = (Cube) {0,0,0};
0524:         Teil[2].c[1] = (Cube) {1,0,0};
0525:         Teil[2].c[2] = (Cube) {1,1,0};
0526:         Teil[2].c[3] = (Cube) {1,2,0};
0527:         Teil[2].c[4] = (Cube) {1,3,0};
0528:         Teil[2].PartNo = 2;
0529:         Teil[3].n = 5;
0530:         Teil[3].c[0] = (Cube) {0,0,0};
0531:         Teil[3].c[1] = (Cube) {0,1,0};
0532:         Teil[3].c[2] = (Cube) {0,2,0};
0533:         Teil[3].c[3] = (Cube) {0,3,0};
0534:         Teil[3].c[4] = (Cube) {1,2,0};
0535:         Teil[3].PartNo = 3;
0536:         
0537:         Teil[4].n = 5;
0538:         Teil[4].c[0] = (Cube) {0,0,0};
0539:         Teil[4].c[1] = (Cube) {0,1,0};
0540:         Teil[4].c[2] = (Cube) {1,0,0};
0541:         Teil[4].c[3] = (Cube) {1,1,0};
0542:         Teil[4].c[4] = (Cube) {1,1,1};
0543:         Teil[4].PartNo = 4;
0544:         
0545:         Teil[5].n = 5;
0546:         Teil[5].c[0] = (Cube) {1,0,0};
0547:         Teil[5].c[1] = (Cube) {1,1,0};
0548:         Teil[5].c[2] = (Cube) {1,2,0};
0549:         Teil[5].c[3] = (Cube) {0,2,0};
0550:         Teil[5].c[4] = (Cube) {2,2,0};
0551:         Teil[5].PartNo = 5;
0552:                 
0553:         Teil[6].n = 5;
0554:         Teil[6].c[0] = (Cube) {0,0,0};
0555:         Teil[6].c[1] = (Cube) {0,1,0};
0556:         Teil[6].c[2] = (Cube) {1,0,0};
0557:         Teil[6].c[3] = (Cube) {1,1,0};
0558:         Teil[6].c[4] = (Cube) {1,2,0};
0559:         Teil[6].PartNo = 6;
0560:         
0561:         Teil[7].n = 5;
0562:         Teil[7].c[0] = (Cube) {0,0,0};
0563:         Teil[7].c[1] = (Cube) {1,0,0};
0564:         Teil[7].c[2] = (Cube) {1,1,0};
0565:         Teil[7].c[3] = (Cube) {2,1,0};
0566:         Teil[7].c[4] = (Cube) {2,2,0};
0567:         Teil[7].PartNo = 7;
0568:         
0569:         Teil[8].n = 4;
0570:         Teil[8].c[0] = (Cube) {0,0,0};
0571:         Teil[8].c[1] = (Cube) {1,0,0};
0572:         Teil[8].c[2] = (Cube) {1,1,0};
0573:         Teil[8].c[3] = (Cube) {0,0,1};
0574:         Teil[8].PartNo = 8;
0575:         
0576:         Teil[9].n = 5;
0577:         Teil[9].c[0] = (Cube) {0,1,0};
0578:         Teil[9].c[1] = (Cube) {0,2,0};
0579:         Teil[9].c[2] = (Cube) {1,0,0};
0580:         Teil[9].c[3] = (Cube) {1,1,0};
0581:         Teil[9].c[4] = (Cube) {2,1,0};
0582:         Teil[9].PartNo = 9;
0583:         
0584:         Teil[10].n = 5;
0585:         Teil[10].c[0] = (Cube) {0,1,0};
0586:         Teil[10].c[1] = (Cube) {1,0,0};
0587:         Teil[10].c[2] = (Cube) {1,1,0};
0588:         Teil[10].c[3] = (Cube) {1,2,0};
0589:         Teil[10].c[4] = (Cube) {2,1,0};
0590:         Teil[10].PartNo = 10;
0591:         
0592:         Teil[11].n = 6;
0593:         Teil[11].c[0] = (Cube) {0,0,0};
0594:         Teil[11].c[1] = (Cube) {1,0,0};
0595:         Teil[11].c[2] = (Cube) {0,1,0};
0596:         Teil[11].c[3] = (Cube) {0,2,0};
0597:         Teil[11].c[4] = (Cube) {1,2,0};
0598:         Teil[11].c[5] = (Cube) {0,3,0};
0599:         Teil[11].PartNo = 11;
0600: };
0601: 
0602: 
0603: /* Returns TRUE iff both parts are composed of identical cubes */
0604: bool EqPart (Part *p1, Part *p2) {
0605:         
0606:         return ((p1->m.w1 == p2->m.w1) && (p1->m.w2 == p2->m.w2));
0607: };
0608: 
0609: 
0610: /* Print representation of part */
0611: void PrtPart (Part *p) {
0612:         int        i;
0613:         printf("[");
0614:         for (i=0; i<p->n; i++){
0615:                 PrtCube(&(p->c[i]));
0616:                 if (i != p->n - 1) printf(",");
0617:         };
0618:         printf("]");
0619: };
0620: 
0621: /* smallest x-coordinate of all cubes in p */
0622: int MinX (Part *p){
0623:         int i,m=9999;
0624:         for (i=0; i<p->n; i++){
0625:                 if (p->c[i].x < m) m=p->c[i].x;
0626:         };
0627:         return m;
0628: };
0629: 
0630: 
0631: /* smallest y-coordinate of all cubes in p */
0632: int MinY (Part *p) {
0633:         int i,m=9999;
0634:         for (i=0; i<p->n; i++){
0635:                 if (p->c[i].y < m) m=p->c[i].y;
0636:         };
0637:         return m;
0638: };
0639: 
0640: 
0641: /* smallest z-coordinate of all cubes in p */
0642: int MinZ (Part *p){
0643:         int i,m=9999;
0644:         for (i=0; i<p->n; i++){
0645:                 if (p->c[i].z < m) m=p->c[i].z;
0646:         };
0647:         return m;
0648: };
0649: 
0650: 
0651: /* Shift complete part by the given amount */
0652: void ShiftPart(Part *p, int dx, int dy, int dz){
0653:         int i;
0654:         for (i=0; i<p->n; i++){
0655:                 ShiftCube(&(p->c[i]), dx, dy, dz);
0656:         };
0657: };
0658: 
0659: /* Set the bitmap and parity of the given part to the correct values */
0660: void SetPartMap(Part *p) {
0661:         int i;
0662:         p->m.w1 = 0;
0663:         p->m.w2 = 0;
0664:         for (i=0; i<p->n; i++)
0665:                 SetBit( &(p->c[i]), &(p->m));
0666:         p->Parity = Parity(&(p->m));
0667: };
0668: 
0669: /* Shift Part, so that the lowest coordinates are 0 */
0670: void NormPart (Part *p){
0671:         int dx, dy, dz;
0672:         
0673:         dx = -MinX(p);
0674:         dy = -MinY(p);
0675:         dz = -MinZ(p);
0676:         ShiftPart(p, dx, dy, dz);
0677: };
0678: 
0679: 
0680: 
0681: /* Turn complete part by given amounts (90 degree turns) in each axis */
0682: void TurnPart (Part *p, int tx, int ty, int tz){
0683:         int i, t;
0684:         for (t=0; t<tx; t++)
0685:                 for (i=0; i<p->n; i++) 
0686:                         TurnCubeX(&(p->c[i]));
0687: 
0688:         for (t=0; t<ty; t++)
0689:                 for (i=0; i<p->n; i++) 
0690:                         TurnCubeY(&(p->c[i]));;
0691: 
0692:         for (t=0; t<tz; t++)
0693:                 for (i=0; i<p->n; i++) 
0694:                         TurnCubeZ(&(p->c[i]));
0695:                         
0696: };
0697: 
0698: /* Rotate complete part (180 degrees) around given axis of block */
0699: void RotatePart (Part *p, int rx, int ry, int rz){
0700:         int i;
0701:         
0702:         for (i=0; i<p->n; i++) 
0703:                 RotateCube(&(p->c[i]), rx, ry, rz);
0704:         SetPartMap(p);
0705: }
0706: 
0707: 
0708: /* Copy Part p1 to p2 */
0709: void CopyPart (Part *p1, Part *p2){
0710:         int i;
0711:         
0712:         p2->n = p1->n;
0713:         p2->m = p1->m;
0714:         p2->Parity = p1->Parity;
0715:         p2->PartNo = p1->PartNo;
0716:         for (i=0; i<p1->n; i++){
0717:                 p2->c[i] = p1->c[i];
0718:         }
0719: };
0720: 
0721: 
0722: 
0723: /* Returns 1 iff the given part fits completely inside puzzle area */ 
0724: bool Fits(Part *p){
0725:         int i;
0726:         for (i=0; i<p->n; i++){
0727:                 if (p->c[i].x > 4) return 0;
0728:                 if (p->c[i].y > 3) return 0;
0729:                 if (p->c[i].z > 2) return 0;
0730:         };
0731:         return 1;
0732: };
0733: 
0734: 
0735: 
0736: /* ---------------------------------------------- Handling of part lists ------------------------------------- */
0737: 
0738: /* A PartList can hold at most MAXPARTLIST parts */
0739: #define MAXPARTLIST 1023
0740: typedef struct {
0741:         int n;
0742:         Part p[MAXPARTLIST];
0743: } PartList;
0744: 
0745: /* A pplist can hold at most MAXPPLIST pointers to parts */
0746: #define MAXPPLIST 121
0747: typedef struct {
0748:         int n;
0749:         Part *pp[MAXPPLIST];
0750: } ppList;
0751: 
0752: /* A ppList for each space in the block is called a FillHoleList */
0753: typedef ppList FillHoleList[64];
0754: 
0755: /* A FillHoleList for each part number is called a FillList */
0756: typedef FillHoleList FillList[12];
0757: 
0758: 
0759:  /* We define an array which holds for each part and for each cube index a list with pointers to those part placements,

0760:     which can fill the block at this hole.

0761: */
0762: 
0763: /* This array holds a FillList for each depth of Try() */
0764: FillList FillsArray[12];
0765: 
0766: /* Sets contents of given FillList to correct values */
0767: void InitFills (PartList *Lagen, FillList *fills){
0768:         int i, j, k, count;
0769:         Part *curPart;
0770:         BitMap m;
0771:         
0772:         for (i=0; i<12; i++) {
0773:                 for (j=0; j<60; j++){
0774:                         count = 0;
0775:                         for (k=0; k<Lagen[i].n; k++){
0776:                                 curPart = &(Lagen[i].p[k]);
0777:                                 IndexToBit(j, &m);
0778:                                 if (! disjoint(&(curPart->m), &m)) {
0779:                                         (*fills)[i][j].pp[count] = curPart;
0780:                                         count++;
0781:                                 };
0782:                         };
0783:                         (*fills)[i][j].n = count;
0784:                 };
0785:         };
0786: };
0787: 
0788: /* We have a current FillList *oldf

0789:         All placements which are still possible within current block

0790:         will be copied to the new FillList *newf

0791: 

0792:         Ignore unused parts and already filled hole

0793: */
0794: void UpdateFill (BitMap *m, FillList *oldf, FillList *newf){
0795:         int i,j,k,count, pplim;
0796:         Part *curPart;
0797:         ppList *curppList;
0798:         
0799:         for (i=0; i<12; i++) {
0800:                 if (Used[i]) continue;
0801:                 for (j=0; j<60; j++){
0802:                         if (IsSet(m,j)) continue;
0803:                         count = 0;
0804:                         curppList = &( (*oldf)[i][j] );
0805:                         pplim = curppList->n;
0806:                         for (k=0; k < pplim; k++){
0807:                                 curPart = curppList->pp[k];
0808:                                 if ( disjoint(&(curPart->m), m)) {
0809:                                         (*newf)[i][j].pp[count++] = curPart;
0810:                                 };
0811:                         };
0812:                         (*newf)[i][j].n = count;
0813:                 };
0814:         };
0815: }
0816: 
0817: /* Returns 1 if the given part is already a member of the partlist */
0818: bool Member (Part *p, PartList *pl){
0819:         int i;
0820:         for (i=0; i<pl->n; i++)
0821:                 if (EqPart(p, &(pl->p[i])))
0822:                         return 1;
0823:         return 0;
0824: };
0825: 
0826: 
0827: /* Returns TRUE, iff any reflection of the given part along the blocks axis

0828:         results in a part which is already in the partlist

0829: */
0830: bool CheckRotations (Part *p, PartList *pl){
0831:         int rx,ry,rz;
0832:         Part pnew;
0833:         
0834:         for (rx=0; rx<2; rx++)
0835:                 for (ry=0; ry<2; ry++)
0836:                         for (rz=0; rz<2; rz++){
0837:                                 CopyPart(p,&pnew);
0838:                                 RotatePart(&pnew,rx,ry,rz);
0839:                                 if (Member(&pnew,pl)) 
0840:                                         return 1;
0841:                         };
0842:         return 0;
0843: }
0844: 
0845: void InsertPart(Part *pnew, PartList *pl){
0846:         if (pl->n >= MAXPARTLIST) 
0847:                 CleanExit("Too many parts in partlist",20);
0848:         CopyPart(pnew,&(pl->p[pl->n]));
0849:         (pl->n)++;
0850: };
0851: 
0852: /* Generate all turns of a given part and insert them normalized into the given PartList if not already there */
0853: void GenTurns(int pn, Part *p, PartList *pl){
0854:         Part pnew;
0855:         int i, j, k;
0856:         
0857:         for (i=0; i<4; i++)
0858:                 for (j=0; j<4; j++)
0859:                         for (k=0; k<4; k++) {
0860:                                 CopyPart(p, &pnew);
0861:                                 TurnPart(&pnew, i, j, k);
0862:                                 NormPart(&pnew);
0863:                                 if (!Fits(&pnew))
0864:                                         continue;
0865:                                 SetPartMap(&pnew);
0866:                                 if (pn == SYMMPART)
0867:                                         if (CheckRotations(&pnew, pl)) 
0868:                                                 continue;
0869:                                 if ( ! Member(&pnew, pl) )
0870:                                         InsertPart(&pnew,pl);
0871:                         };
0872: };
0873: 
0874: 
0875: /* Print representation of a PartList */
0876: void PrtPartList(PartList *pl){
0877:         int i;
0878:         for (i=0; i<pl->n; i++) {
0879:                 PrtPart(&(pl->p[i]));
0880:                 NewLine();
0881:         };
0882:         NewLine();
0883: };
0884: 
0885: 
0886: /* Generate all shifts of the Parts in the PartList 

0887:    We assume they are all normalized 

0888:   */
0889: void GenShifts (int pn, PartList *pl) {
0890:         Part pnew;
0891:         int i, np, dx, dy, dz;
0892:         
0893:         np = pl->n;
0894:         
0895:         for (i=0; i<np; i++)         
0896:                 for (dx=0; dx < 5; dx++)
0897:                         for (dy=0; dy < 4; dy++)
0898:                                 for (dz=0; dz < 3; dz++) {
0899:                                         CopyPart(&(pl->p[i]), &pnew);
0900:                                         ShiftPart(&pnew, dx, dy, dz);
0901:                                         if (!Fits(&pnew))
0902:                                                 continue;
0903:                                         SetPartMap(&pnew);
0904:                                         if (pn == SYMMPART)
0905:                                                 if (CheckRotations(&pnew, pl)) 
0906:                                                         continue;
0907:                                         if ( ! Member(&pnew, pl) ) 
0908:                                                 InsertPart(&pnew,pl); 
0909:                                 };
0910: };
0911:   
0912: 
0913:  PartList Lagen[12];
0914:    
0915: /* Fill the array with all possible placements of all 12 basic parts */
0916: void InitLagen (PartList *Lagen, Part *Teil){
0917: 
0918:         int i;
0919:         for (i=0; i<12; i++) {
0920:                 Lagen[i].n = 1;
0921:                 Lagen[i].p[0] = Teil[TryList[i]];
0922:                 SetPartMap( &(Lagen[i].p[0]) );
0923: 
0924:                 GenTurns(i, &(Lagen[i].p[0]), &(Lagen[i]));
0925:                 GenShifts(i, &(Lagen[i]));
0926:         };
0927: };
0928: 
0929: 
0930: /* Initialize the absolute parity for each part number */
0931: void InitAbsParity() {
0932:         int pn;
0933:         
0934:         for (pn=0; pn<12; pn++)
0935:                 AbsParity[pn] = abs( Lagen[pn].p[0].Parity );
0936: };
0937: 
0938: 
0939: 
0940: /* -------------------------------------------- block handling functions */
0941: 
0942: /* Bitmap and list of parts which fill this block */
0943: typedef struct {
0944:         /* Every hole already filled has its bit set */
0945:         BitMap m;
0946:         /* The current parity */
0947:         int Parity;
0948:         /* The placements of the parts */
0949:         Part *p[12];
0950: } Block;
0951: 
0952: Block b;
0953: 
0954: /* The block is initially empty */
0955: void InitBlock (Block *b){
0956:         int i;
0957: 
0958:         b->m.w1 = 0;
0959:         b->m.w2 = 0;
0960:         b->Parity = 0;
0961:         for (i=0; i<12; i++)
0962:                 b->p[i] = 0;
0963: };
0964: 
0965: 
0966: /* Print the block in human readable form */
0967: void PrtBlock(Block *b){
0968:         int i, j, x, y, z;
0969:         int PartNums[5][4][3];
0970:         Part *p;
0971:         
0972:         /* Clear the PartNums array */ 
0973:         for (z=2; z>=0; z--)
0974:                 for (y=3; y>=0; y--)
0975:                         for (x=0; x<5; x++)
0976:                                 PartNums[x][y][z] = 0;
0977: 
0978:         /* Which Parts are where ? */
0979:         for (i=0; i<12; i++) {
0980:                 if (b->p[i]) {
0981:                         p = b->p[i];
0982:                         /* Mark each cube of this part in array */
0983:                         for (j=0; j < p->n; j++) 
0984:                                 PartNums[p->c[j].x][p->c[j].y][p->c[j].z] = p->PartNo + 1;
0985:                 };
0986:         };
0987:         NewLine();
0988:         for (z=2; z>=0; z--){
0989:                 for (y=3; y>=0; y--){
0990:                         for (x=0; x<5; x++)
0991:                                 printf("%2d ", PartNums[x][y][z]);
0992:                         NewLine();
0993:                 };
0994:                 NewLine();
0995:         }
0996: };
0997: 
0998: 
0999: /* Mark this part as used */
1000: static inline 
1001: void Use(int pn){
1002:         Used[pn] = 1;
1003:         UseMap ^= 1<<pn;
1004:         MaxParity -= AbsParity[pn];
1005: };
1006: 
1007: /* Mark this part as not used anymore */
1008: static inline
1009: void UnUse(int pn){
1010:         Used[pn] = 0;
1011:         UseMap ^= 1<<pn;
1012:         MaxParity += AbsParity[pn];
1013: };
1014: 
1015: 
1016: /* Store this part in the block */
1017: static inline
1018: void Store (Part *p, Block *b){
1019:         b->m.w1 ^= p->m.w1;
1020:         b->m.w2 ^= p->m.w2;
1021:         b->Parity += p->Parity;
1022:         b->p[p->PartNo] = p;
1023: };
1024: 
1025: /* Remove part from block */
1026: static inline
1027: void Remove (Part *p, Block *b){
1028:         b->Parity -= p->Parity;
1029:         b->m.w1 ^= p->m.w1;
1030:         b->m.w2 ^= p->m.w2;
1031:         b->p[p->PartNo] = 0;
1032: };
1033: 
1034: 
1035: /* Returns 1 iff the given block is empty at index i */
1036: static inline 
1037: bool empty (Block *b, int i){
1038:         if (i<32) return (( b->m.w1 & (1<<i)) == 0);
1039:         else return (( b->m.w2 & (1 << (i-32))) == 0); 
1040: };
1041: 
1042: 
1043: /* Returns TRUE iff the given part fits in empty space of block */
1044: static inline 
1045: bool FitInBlock (Part *p, Block *b){
1046:         return ( disjoint(&(b->m), &(p->m)) ); 
1047: };        
1048: 
1049: 
1050: 
1051: /* We have found a solution, 

1052:         count it and maybe print it

1053: */
1054: void FoundSolution (Block *b) {
1055:         solutions++;
1056:         if (PrtSol){
1057:                 PrtBlock(b);
1058:         };
1059: };
1060: 
1061: 
1062: /*  Stores part placement in *ResPart 

1063:         iff there is a hole which can be filled only one way 

1064:         Does detect holes which can never be filled

1065:         and sets *h==-1 in this case

1066:         Sets *partno to the one part filling in the special hole only if there is one

1067:         Returns 1 iff a special hole has been found, else 0

1068:         !!! Currently does not prefer unfillable holes !!!

1069: */
1070: bool SpecialHole (Block *b, FillList *fl, int *partno, Part **ResPart){
1071:         int pn, ln, ci, pnum, lnlim;
1072:         int numfills;
1073:         ppList *ppl;
1074:         Part *resp;        
1075:         
1076:         /* For every empty cube */
1077:         for (ci=0;ci<60; ci++) {
1078:                 if (!empty(b, ci)) continue;
1079:                 
1080:                 /* Can this hole be filled two or more ways? */
1081:                 numfills=0;        
1082:                 for (pn=0; pn < 12; pn++) {
1083:                         if (Used[pn]) continue;
1084:                         ppl = &((*fl)[pn][ci]);
1085:                         lnlim = ppl->n;
1086:                         for (ln=0; ln < lnlim; ln++) {
1087:                                 if (FitInBlock(ppl->pp[ln],b)){
1088:                                         if ((numfills++) > 0) 
1089:                                                 goto toomuch;
1090:                                         else {
1091:                                                 pnum = pn;
1092:                                                 resp = ppl->pp[ln];
1093:                                         };
1094:                                 };
1095:                         };
1096:                 };
1097:                 /* Coming here there were 0 or 1 possible placements for this hole */
1098:                 if (numfills){
1099:                         *partno = pnum;
1100:                         *ResPart = resp;
1101:                 } else {
1102:                         *partno = -1;
1103:                 };
1104:                 return 1;
1105:                                 
1106:         /* Coming here we have found more than 1 possible placement for this hole

1107:                 Try the next hole

1108:          */
1109:         toomuch:
1110:         };
1111:         return 0;
1112: };
1113: 
1114: 
1115: /*  Look for an unfillable hole

1116:         Returns TRUE iff one is found

1117: */
1118: bool ZeroHole (Block *b, FillList *fl){
1119:         int pn, ln, ci, pnum, lnlim;
1120:         int numfills;
1121:         ppList *ppl;
1122:         
1123:         /* For every empty cube */
1124:         for (ci=0;ci<60; ci++) {
1125:                 if (!empty(b, ci)) continue;
1126:                 
1127:                 /* Can this hole be filled? */
1128:                 for (pn=0; pn < 12; pn++) {
1129:                         if (Used[pn]) continue;
1130:                         ppl = &((*fl)[pn][ci]);
1131:                         lnlim = ppl->n;
1132:                         for (ln=0; ln < lnlim; ln++) {
1133:                                 if (FitInBlock(ppl->pp[ln],b))
1134:                                         goto toomuch;
1135:                         };
1136:                 };
1137:                 /* Coming here there was no possible placement for this hole */
1138:                 return 1;
1139:                                 
1140:         /* Coming here we have found more than 1 possible placement for this hole

1141:                 Try the next hole

1142:          */
1143:         toomuch:
1144:                 continue;
1145:         };
1146:         return 0;
1147: };
1148: 
1149: 
1150: /* Returns hole index with minimal number of ways to fill it 

1151:         2 holes with equal counts are sorted according to the number of parts

1152:         Does not try to find holes with more than CurMin possibilities

1153: */
1154: int MinHole (Block *b, FillList *fl, int *HoleIndex, int CurMin){
1155:         Part *p;
1156:         int pn, ln, ci, pinc, pcnt;
1157:         int min = CurMin, pmax=0, numfills;
1158:         ppList *ppl;
1159:                 
1160:         /* For every empty cube */
1161:         for (ci=0;ci<60; ci++) {
1162:                 if (!empty(b, ci)) continue;
1163:         
1164:                 numfills=0;
1165:                 pcnt=0;
1166:                 
1167:                 /* Find all parts which fill this hole */        
1168:                 /* and are not already used */
1169:                 for (pn=0; pn <12; pn++) {
1170:                         if (Used[pn]) continue;
1171: 
1172:                         ppl = &((*fl)[pn][ci]);
1173:                         pinc = 0;
1174:                         for (ln=0; ln < ppl->n; ln++) {
1175:                                 p = ppl->pp[ln];
1176:                                 if (FitInBlock(p,b)){
1177:                                         pinc = 1; 
1178:                                         if (++numfills > min) break; /* No need to search further at this hole */
1179:                                 }; 
1180:                         };
1181:                         pcnt += pinc;
1182:                         if (numfills > min) break;
1183:                 };
1184:                 if (numfills < min) {
1185:                         min = numfills;
1186:                         *HoleIndex = ci;
1187:                         pmax = pcnt;
1188:                         if (min == 0) return min;
1189:                 } else {
1190:                         if ((numfills == min) && (pcnt > pmax)) {
1191:                                 min = numfills;
1192:                                 *HoleIndex = ci;
1193:                                 pmax = pcnt;
1194:                         };
1195:                 };
1196:         };
1197:         return min;
1198: };
1199: 
1200: 
1201: 
1202: /* Returns part placement iff part fits into given hole 

1203:         Tries possible placements for this hole

1204:         Returns 0 if no fit

1205: */
1206: Part *FitsHole(Block *b, int pn, int hole, FillList *fl) 
1207: {
1208:         ppList *ppl = &((*fl)[pn][hole]);
1209:         int ln;
1210:         Part *p;
1211:         
1212:         for (ln=0; ln < ppl->n; ln++) {
1213:                 p = ppl->pp[ln];
1214:                 if (FitInBlock(p,b)) 
1215:                         return p;
1216:         };
1217:         return (Part *) 0;
1218: };
1219: 
1220: 
1221: 
1222: void PrtDepth(int depth){
1223:         int i;
1224:         printf("%02d:",depth);
1225:         for (i=0; i<depth; i++)
1226:                 printf("  ");
1227: };
1228: 
1229: 
1230: /* Returns the first unused part */
1231: static inline 
1232: int FindUnusedPart(){
1233:         return LeastZero[UseMap];
1234: };
1235: 
1236: 
1237: 
1238: /* Returns number of placements so that part fits into block 

1239:         Does not check more than max placements per part

1240: */
1241: int NumFits(Block *b, int pn, int max){
1242:         PartList *pl = &(Lagen[pn]);
1243:         int ln, cnt=0;
1244:         Part *p;        
1245:         
1246:         for (ln=0; ln < pl->n; ln++) {
1247:                 p = &(pl->p[ln]);
1248:                 if (FitInBlock(p,b)){
1249:                         if (++cnt >= max) break;
1250:                 };
1251:         };
1252:         return cnt;
1253: };
1254: 
1255: 
1256: /* Examine all unused parts

1257:    Returns part index which should be tried next 

1258:    Sets min to the number of possible placements this part has

1259:    min is set to 0 iff no part can be placed

1260:   */
1261: int ExamineParts(Block *b, int *min){
1262:         int i,pn, h;
1263:         
1264:         *min = 99999;
1265:         
1266:         /* For every unused part */
1267:         for (i=0; i<12;i++){
1268:                 if (Used[i]) continue;
1269:                 h = NumFits(b,i, *min);
1270:                 if (h < *min) {
1271:                         *min=h;
1272:                         pn=i;
1273:                 };
1274:         }
1275:         return pn;
1276: };
1277: 
1278: /* Returns 0 iff parity is impossible to reach */
1279: int CheckParity(Block *b, int depth){
1280:         int pn, p1, p2;
1281:         
1282:         if  (abs(b->Parity) > MaxParity) {
1283: #ifdef DEBUG                        
1284:                         ParityFails[depth]++;
1285: #endif        
1286:                 return 0;
1287:         };
1288:         
1289:         if ( (depth == 10) ){
1290:         /* Find the first part which is still unused */
1291:                 pn = FindUnusedPart();
1292:                 p1 = abs(Lagen[pn].p[0].Parity);
1293:                 
1294:         /* Find the second part which is still unused */
1295:                 for (pn++; pn <12; pn++) 
1296:                         if (!Used[pn]) break;                
1297:                 p2 = abs(Lagen[pn].p[0].Parity);
1298:         
1299:                 if ( (p1+p2 != abs(b->Parity)) && ( abs(p1 - p2) != abs(b->Parity)) ){
1300: #ifdef DEBUG                        
1301:                         ParityFails[depth]++;
1302: #endif                        
1303:                         return 0;
1304:                 };
1305:         };
1306:         return 1;
1307: };
1308: 
1309: 
1310: int TryLastPart(Block *b, FillList *fl){
1311:         int i, pn;
1312:         Part *p;
1313:         
1314:         if (abs(b->Parity) != MaxParity) {
1315: #ifdef DEBUG                        
1316:                         ParityFails[11]++;
1317: #endif                        
1318:                 return 0;
1319:         };
1320:         /* Find first empty cube */
1321:         i = FindFirstHole(&(b->m));
1322:         
1323:         /* Find the part which is still unused */
1324:         pn = FindUnusedPart(); 
1325: 
1326:         if ( (p = FitsHole(b, pn, i, fl)) ) {
1327:                 Store (p, b);
1328:                 FoundSolution(b);
1329:                 Remove (p,b);
1330:                 return 1;
1331:         };
1332:         return 0;
1333: };
1334: 
1335: #define hashstore {if ( (depth<=HashDepth) && (sol == 0)) StoreHash(&(b->m), depth);}
1336: 
1337: /* This array tells Try() which FillList it shall use at which depth */
1338: FillList  *TryFills[12];
1339: 
1340: /* Forward declaration */
1341: int Try (Block *b, int depth);
1342: 
1343: 
1344: /* Try all placements of the given part 

1345:         and return number of solutions

1346: */
1347: int TryPart(Block *b, int pn, int depth){
1348:         int ln,sol=0;
1349:         PartList *pl;
1350:         Part *p;
1351:         
1352: #ifdef DEBUG
1353:         PartTries[depth]++;
1354: #endif

1355:         
1356:         Use(pn);
1357:         pl = &(Lagen[pn]);
1358:         for (ln=0; ln < pl->n; ln++) {
1359:                 p = &(pl->p[ln]);
1360: 
1361:                 if (!FitInBlock(p,b)) continue;
1362:                         
1363:                 /* Store Part in block */
1364: 
1365:                 Store (p, b);
1366: 
1367:                 /* Recursively try the rest of the block */
1368:                 sol += Try(b, depth+1);
1369: 
1370: #ifdef EARLYABORT        
1371:                 if (depth == mindepth) CleanExit("",0);
1372: #endif

1373: 
1374:                 /* Remove part from block */
1375:                 Remove(p,b);
1376:         }        
1377: 
1378:         UnUse(pn);
1379:         hashstore;
1380:         return sol;
1381: };
1382: 
1383: /* This routine handles the last stages of the search

1384:         It tries to find a solution very fast by always filling the first empty hole

1385: */
1386: int TryFirstHole (Block *b, FillList *fl, int depth){
1387:         int sol=0, pn, ln, h;
1388:         Part *p;
1389:         ppList *ppl;
1390: 
1391: #ifdef DEBUG
1392:         Nodes[depth]++;
1393: #endif

1394:         if (depth == 11) 
1395:                 return TryLastPart(b, fl);
1396: 
1397:         /* Check if the parity is still valid */
1398:         if (CheckParity(b, depth) == 0) 
1399:                 return 0;
1400:         
1401:         h = FindFirstHole(&(b->m));
1402:         
1403:                 for (pn=0; pn <12; pn++) {
1404:                         if (Used[pn]) continue;
1405:                 
1406:                         Use(pn);
1407:                         ppl = &( (*fl)[pn][h]);
1408:                         for (ln=0; ln < ppl->n; ln++) {
1409:                                 p = ppl->pp[ln];
1410:                                 if (FitInBlock(p,b)) { 
1411:                                         /* Store Part in block */
1412:                                         Store (p, b);
1413:                                         
1414:                                         sol += TryFirstHole(b, fl, depth+1);
1415: 
1416:                                         /* Remove part from block */
1417:                                         Remove(p,b);
1418: 
1419:                                 }
1420:                         };
1421:                         UnUse(pn);
1422:                 };
1423:         return sol;
1424: };
1425: 
1426: 
1427: /* Given a hole h, tries all possibilities to fill it 

1428:         Returns number of solutions

1429: */
1430: 
1431: int TryHole(Block *b, int h, int depth){
1432:         int sol=0, pn, ln;
1433:         Part *p;
1434:         ppList *ppl;
1435:                 
1436: #ifdef DEBUG
1437:                 MinHoleTries[depth]++;
1438: #endif

1439: 
1440:         for (pn=0; pn <12; pn++) {
1441:                 if (Used[pn]) continue;
1442:         
1443:                 Use(pn);
1444:                 ppl = &( (*(TryFills[depth]))[pn][h]);
1445: 
1446:                 for (ln=0; ln < ppl->n; ln++) {
1447:                         p = ppl->pp[ln];
1448:                         if (FitInBlock(p,b)) { 
1449:                                 /* Store Part in block */
1450:                                 Store (p, b);
1451:                                 
1452:                                 sol += Try(b, depth+1);
1453: 
1454:                                 /* Remove part from block */
1455:                                 Remove(p,b);
1456:                         }
1457:                 };
1458:                 UnUse(pn);
1459:         };
1460:         hashstore;
1461:         return sol;
1462: }
1463: 
1464: 
1465: /* Recursively try to solve the puzzle

1466:         Returns number of solutions found 

1467: */
1468: int Try (Block *b, int depth){
1469:         int pn, ln;
1470:         int  min, h,  minh, sol;
1471: 
1472:         Part *p;
1473:         ppList *ppl;
1474: 
1475: #ifdef DEBUG
1476:         Nodes[depth]++;
1477: #endif

1478: 
1479:         /* Check if we have already searched this situation and found no solution */
1480:         if ( (depth <= HashDepth) && Recall(&(b->m)) )  {
1481: #ifdef DEBUG
1482:                 Repetitions[depth]++;
1483: #endif                
1484:                 return 0;
1485:         };
1486: 
1487:         sol = 0;
1488:         
1489:         /* Is this the last part to fit ? */
1490:         if (depth == 11) 
1491:                 return TryLastPart(b, TryFills[10]);
1492: 
1493:         /* Check if the parity is still valid */
1494:         if (CheckParity(b, depth) == 0) 
1495:                 return 0;
1496: 
1497:         /* Update the list of possible moves per hole at shallow depths */
1498:         if (depth <= UPDATEFILLDEPTH) {
1499:                 UpdateFill(&(b->m), &(FillsArray[depth]), &(FillsArray[depth+1]) );
1500:                 TryFills[depth] = &FillsArray[depth+1];
1501:         } else {
1502:                 TryFills[depth] = TryFills[depth-1];
1503:         };
1504: 
1505:         if ((depth > 9) && ZeroHole(b,TryFills[depth])){
1506: #ifdef DEBUG
1507:                 ZeroHoles[depth]++;
1508: #endif

1509:                 return 0;
1510:         };
1511:         
1512:         /* Look for a hole which is unfillable or can only be filled one way */
1513:         if (  SpecialHole(b, TryFills[depth], &pn, &p) ) {
1514: #ifdef DEBUG
1515:                 SpecialHoleTries[depth]++;
1516: #endif

1517:                 /* Is there an unfillable hole ? */
1518:                 if (pn == -1) return 0; 
1519:                 /* Now we have a hole which can be filled only one way */
1520:                 /* Store Part in block */
1521:                 Use(pn);
1522:                 Store (p, b);
1523: 
1524:                 sol = Try(b, depth+1);
1525:         
1526:                 /* Remove part from block */
1527:                 Remove(p,b);
1528:                 UnUse(pn);
1529:                 hashstore;
1530:                 return sol;
1531:         };        
1532:         
1533:         /* Select a part which will possibly be tried */
1534:         min = 99999;
1535:         /* At shallow depths find the part with minimum possible placements */
1536:         if (depth < 6) {
1537:                 pn=ExamineParts(b, &min);
1538:                 /* Do we have a part which can not be placed anywhere ? */
1539:                 if (min == 0) 
1540:                         return 0;
1541:         } else {
1542:                 /* At higher depths simply take the first unused part */
1543:                 pn=FindUnusedPart();
1544:         };
1545:         
1546:         /* Find the hole with the minumum number of placements possible

1547:                 Make sure we are below the minimum number possible for a part

1548:         */
1549:         if ( (depth < 7) && (min > 4)  && ((minh=MinHole(b, TryFills[depth], &h, min-3)) < (min - 3) ) ) {
1550:                 return TryHole(b, h, depth);
1551: 
1552:         };
1553:         if (depth > 6) return TryFirstHole(b, TryFills[depth], depth);
1554:         
1555:         return TryPart(b,pn,depth);
1556: };
1557: 
1558: 
1559: #ifdef DEBUG
1560: void InitStatistics() {
1561:         int i;
1562:         for (i=0; i<12; i++){
1563:                 Nodes[i] = 0;
1564:                 MinHoleTries[i] = 0;
1565:                 SpecialHoleTries[i] = 0;
1566:                 PartTries[i] = 0;
1567:                 ParityFails[i] = 0;
1568:                 Repetitions[i] = 0;        
1569:                 ZeroHoles[i] = 0;
1570:         };        
1571: };
1572: 
1573: /*<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<*/
1574: void Statistics(){
1575:         int i, sum=0;        
1576:         printf("Solutions: %d\n", solutions);
1577:         printf("\nDepth\t\tNodes\t\tSpecial\t\tMinHole\t\tPart\t\tRepetitions\tParity\tZeroHole");
1578:         for (i=0; i<12; i++){
1579:                 printf("\n%3d: \t",i);
1580:                 printf("%10d\t", Nodes[i]);
1581:                 printf("%10d\t", SpecialHoleTries[i]);
1582:                 printf("%10d\t", MinHoleTries[i]);
1583:                 printf("%10d\t", PartTries[i]);
1584:                 printf("%10d\t",Repetitions[i]);        
1585:                 printf("%10d\t",ParityFails[i]);
1586:                 printf("%10d\n",ZeroHoles[i]);
1587:                 sum += Nodes[i];
1588:         };
1589:         printf("\nTotal Nodes: %d\n",sum);
1590: };
1591: #endif

1592: 
1593: /* -------------------------------------------------- Main Program --------------------------------------- */
1594:         
1595: int main(int argc, char *argv[])
1596: {
1597:   /* Variable needed for option processing */
1598:   int option;
1599: 
1600:   int i;
1601:   
1602:     
1603: /*+++++++++++++++++++ Process Options ++++++++++++++++++++++++++++++++++*/
1604: 
1605: 
1606:   while ( (option = getopt(argc,argv,"v:s")) != EOF)
1607:   {
1608:     switch (option)
1609:     {
1610:       
1611:                 case 'v':
1612:                 Verb = atoi(optarg);
1613:                 break;
1614: 
1615:                 case 's':
1616:                         PrtSol = 1;
1617:                         break;
1618:                                 
1619:      case '?':
1620:         Usage(argv[0]);
1621:         CleanExit("", 5);
1622:     }
1623:   }
1624: 
1625: 
1626: 
1627: /*====================================================================*/
1628: /*              User Initialization Routines go here!                 */
1629: /*====================================================================*/
1630:         InitLeastZero();
1631:         InitHash();
1632:         InitParity();
1633:         MaxParity = 14;  /* Hand computed */
1634: 
1635:         InitTeile(Teil);
1636: 
1637:         InitLagen(Lagen, Teil);
1638: 
1639:         InitAbsParity();
1640:          
1641: #ifdef DEBUG 
1642:         for (i=0; i<12; i++){
1643:                 printf("%d, ",Lagen[i].n);
1644:                 printf("%d, ",AbsParity[i]);
1645:         };
1646:         NewLine();
1647: #endif

1648: 
1649:         InitFills (Lagen, &(FillsArray[0]));
1650: 
1651:         InitBlock (&b);
1652: 
1653:         for (i=0; i<12; i++)
1654:                 Used[i]=0;
1655:         UseMap = 0;
1656: 
1657:         solutions = 0;
1658: 
1659: #ifdef DEBUG
1660:         InitStatistics();
1661: #endif

1662: 
1663: /*====================================================================*/
1664: /*              User Initialization is done!                          */
1665: /*====================================================================*/
1666: 
1667: 
1668: /*||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||*/
1669: /*              M A I N    L O O P                                    */
1670: /*||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||*/
1671: 
1672:         Try(&b,0);
1673:         printf("\nSolutions: %d\n", solutions);
1674: 
1675: 
1676: /*====================================================================*/
1677: /*              User CleanUp Procedures are Here !                    */
1678: /*====================================================================*/
1679:   
1680:          CleanExit("",0);
1681:          return(0);  /* Never executed, just to make compiler happy */
1682: }
1683: 
1684: 
1685: /*>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>*/
1686: /* Deallocate all used resources                                     */
1687: /* Terminate the program returning RetCode                           */
1688: /*<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<*/
1689: 
1690: void 
1691: CleanExit(char *pCh, int RetCode)
1692: {
1693: #ifdef DEBUG
1694:         Statistics();
1695: #endif

1696:         if (HashTable) free(HashTable);
1697:         fprintf(stderr, "%s\n", pCh);
1698:         exit(RetCode);
1699: }
1700: 
1701: 
1702: static void 
1703: Usage(char *ProgName)
1704: {
1705:   fprintf(stderr,"Usage: %s\n",ProgName);
1706:   fprintf(stderr,"Options: -v<i> :Set verbosity to <i>\n");
1707:   fprintf(stderr,"         -s    :Show solutions\n"); 
1708: }
1709: 
1710: 
1711:   /* THE END */
1712: