0001: 
0002: //

0003: // ----------------------------

0004: // --    c't-Puzzle lösen    --

0005: // ----------------------------

0006: //

0007: // Autor: Tobias Glasmachers

0008: //

0009: // Dies ist mein Beitrag zum c't-Puzzle Programmierwettbewerb,

0010: // Das Programm habe ich mit dem Intel-Compiler (icc) und den

0011: // Compiler-Optionen O3, Qip, QxW/QaxW übersetzt.

0012: //

0013: //

0014: // Ich habe nichts dagegen, wenn der Sourcecode von Anderen weiterverwendet wird.

0015: // Vielleicht kann ja irgendjemand etwas wirklich sinnvolles damit anfangen.

0016: // Wenn allerdings eine veränderte Version des Codes weitergegeben oder

0017: // veröffentlicht wird, so muss die Datei entsprechend gekennzeichnet sein.

0018: //

0019: 
0020: 
0021: #include <io.h>
0022: #include <stdio.h>
0023: #include <time.h>
0024: 
0025: 
0026: #define UINT64                        unsigned _int64
0027: #define UINT                        unsigned int
0028: #define WORD                        unsigned short
0029: #define BYTE                        unsigned char
0030: 
0031: 
0032: #define DREI_D_TEST                        0x0600
0033: #define INVALID_NF                        0xff
0034: 
0035: 
0036: // #define AUFRUFE

0037: 
0038: 
0039: // Datenstrukturen

0040: /////////////////////////////////////////////////////////////////////

0041: 
0042: 
0043: // Interpretation:

0044: // Es werden 4 12er-Ebenen repräsentiert. Die 5. Ebene wird sowieso nicht benutzt.

0045: union tBelegung
0046: {
0047:         UINT64 int64;
0048:         struct
0049:         {
0050:                 UINT bits0;
0051:                 UINT bits1;
0052:         };
0053:         WORD word_bits[4];
0054: };
0055: 
0056: struct tBauform
0057: {
0058:         int m_Drehungen;                // aktuelle Anzahl Drehungen

0059:         int m_DrehungenSymmY;        // Drehungen ohne y-Symmetrie

0060:         int m_DrehungenGesamtY;        // Anzahl echt verschiedener Drehungen

0061: 
0062:         struct tGedreht
0063:         {
0064:                 int m_MaxX;                        // maximale Verschiebung in dieser Drehung

0065:                 int m_MaxY;
0066:                 int m_MaxZ;
0067:                 tBelegung m_Bits;        // Bit-Repräsentation

0068:         };
0069: 
0070:         tGedreht m_Gedreht[24];
0071: };
0072: 
0073: struct tPassendeForm
0074: {
0075:         WORD form;
0076:         tBelegung belegung;
0077: };
0078: 
0079: struct tPassendeForm4
0080: {
0081:         WORD form;
0082:         UINT belegung;
0083: };
0084: 
0085: struct tZustand
0086: {
0087:         BYTE m_FreiesFeld_Nachbarn;                        // 0..191, siehe Abbildung NachbarFeld

0088:         WORD m_VerbauteFormen;                                // 11 Bit

0089:         tBelegung m_Belegung;
0090: };
0091: 
0092: 
0093: // globale Daten

0094: /////////////////////////////////////////////////////////////////////

0095: 
0096: 
0097: int rot[24][3][3] = {                                                // Alle orientierungserhaltenden rechtwinkligen 3x3-Drehmatrizen

0098:         {{1, 0, 0}, {0, 1, 0}, {0, 0, 1}},
0099:         {{0, 1, 0}, {-1, 0, 0}, {0, 0, 1}},
0100:         {{-1, 0, 0}, {0, -1, 0}, {0, 0, 1}},
0101:         {{0, -1, 0}, {1, 0, 0}, {0, 0, 1}},
0102: 
0103:         {{1, 0, 0}, {0, 0, -1}, {0, 1, 0}},
0104:         {{0, 0, 1}, {1, 0, 0}, {0, 1, 0}},
0105:         {{-1, 0, 0}, {0, 0, 1}, {0, 1, 0}},
0106:         {{0, 0, -1}, {-1, 0, 0}, {0, 1, 0}},
0107: 
0108:         {{0, 1, 0}, {0, 0, 1}, {1, 0, 0}},
0109:         {{0, 0, 1}, {0, -1, 0}, {1, 0, 0}},
0110:         {{0, -1, 0}, {0, 0, -1}, {1, 0, 0}},
0111:         {{0, 0, -1}, {0, 1, 0}, {1, 0, 0}},
0112: 
0113: 
0114:         {{-1, 0, 0}, {0, 1, 0}, {0, 0, -1}},
0115:         {{0, -1, 0}, {-1, 0, 0}, {0, 0, -1}},
0116:         {{1, 0, 0}, {0, -1, 0}, {0, 0, -1}},
0117:         {{0, 1, 0}, {1, 0, 0}, {0, 0, -1}},
0118: 
0119:         {{-1, 0, 0}, {0, 0, -1}, {0, -1, 0}},
0120:         {{0, 0, -1}, {1, 0, 0}, {0, -1, 0}},
0121:         {{1, 0, 0}, {0, 0, 1}, {0, -1, 0}},
0122:         {{0, 0, 1}, {-1, 0, 0}, {0, -1, 0}},
0123: 
0124:         {{0, -1, 0}, {0, 0, 1}, {-1, 0, 0}},
0125:         {{0, 0, -1}, {0, -1, 0}, {-1, 0, 0}},
0126:         {{0, 1, 0}, {0, 0, -1}, {-1, 0, 0}},
0127:         {{0, 0, 1}, {0, 1, 0}, {-1, 0, 0}},
0128: };
0129: 
0130: 
0131: // 30 hoffentlich sinnvoll ausgewählte Bitkombinationen mit wenigen gesetzten Bit

0132: // Es ist leider überhaupt nicht klar, wie Optimal oder auch nicht diese Auswahl und Reihenfolge ist.

0133: WORD Komprimierung_Invers[30] = {
0134:                 0x003, 0x006, 0x600, 0xc00,
0135:                 0x009, 0x240, 0x024, 0x900,
0136:                 0x018, 0x030, 0x0c0, 0x180,
0137:                 0x048, 0x090, 0x120,
0138: 
0139:                 0x001, 0x002, 0x004,
0140:                 0x008, 0x010, 0x020,
0141:                 0x040, 0x080, 0x100,
0142:                 0x200, 0x400, 0x800,
0143: 
0144:                 0x000,
0145: };
0146: 
0147: 
0148: WORD bit16[16];
0149: UINT bit32[32];
0150: UINT64 bit64[64];
0151: 
0152: 
0153: tBauform Bauform[11];
0154: BYTE NachbarFeld[384];
0155: 
0156: 
0157: UINT Loesungen;
0158: UINT Aufrufe;
0159: 
0160: 
0161: tPassendeForm* PassendIndex1[192];
0162: UINT PassendCount1[192];
0163: tPassendeForm* PassendIndex3[192];
0164: UINT PassendCount3[192];
0165: tPassendeForm4* PassendIndex4[192];
0166: UINT PassendCount4[192];
0167: tPassendeForm4* PassendIndex5[192];
0168: UINT PassendCount5[192];
0169: 
0170: int Komprimierung[4096];                                // Bit-Komprimierung von 12 auf 6 Bit

0171: BYTE BestesFeld[0x1e000];
0172: 
0173: tPassendeForm PassendeFormen1[12772];
0174: tPassendeForm PassendeFormen3[10644];
0175: tPassendeForm4 PassendeFormen4[7504];
0176: tPassendeForm4 PassendeFormen5[3204];
0177: 
0178: 
0179: 
0180: // Programm

0181: /////////////////////////////////////////////////////////////////////

0182: 
0183: 
0184: #define CALC_INDEX_B \
0185: { \
0186:         int top6 = Komprimierung[(4095-zustand.m_Belegung.word_bits[0]) & (zustand.m_Belegung.word_bits[1])]; \
0187:         b = BestesFeld[zustand.m_Belegung.word_bits[0] | top6]; \
0188: }
0189: 
0190: #define CALC_INDEX_B5 \
0191:         b = BestesFeld[zustand.m_Belegung.word_bits[1] + 29*4096];
0192: 
0193: 
0194: 
0195: 
0196: // Parameter:

0197: // index 0..10

0198: // pos1 .. pos6 sind Koordinaten der Form 111..345

0199: void InitBauform(int index, int pos1, int pos2, int pos3, int pos4, int pos5, int pos6)
0200: {
0201:         tBauform* pB = &Bauform[index];
0202: 
0203:         int i, j, k;
0204:         int x, y, z;
0205:         int xmax, ymax, zmax, xp, yp, zp;
0206:         int count;
0207:         int pos[6], posX[6], posY[6], posZ[6];
0208:         tBauform::tGedreht* pG;
0209: 
0210:         count = 4;
0211:         pos[0] = pos1;
0212:         pos[1] = pos2;
0213:         pos[2] = pos3;
0214:         pos[3] = pos4;
0215:         if (pos5 != 0)
0216:         {
0217:                 pos[4] = pos5;
0218:                 count++;
0219:         }
0220:         if (pos6 != 0)
0221:         {
0222:                 pos[5] = pos6;
0223:                 count++;
0224:         }
0225:         for (i=0; i<count; i++)
0226:         {
0227:                 posX[i] = pos[i] / 100 % 10 - 1;
0228:                 posY[i] = pos[i] / 10 % 10 - 1;
0229:                 posZ[i] = pos[i] % 10 - 1;
0230:         }
0231: 
0232:         // Alle Drehungen durchgehen

0233:         pB->m_DrehungenGesamtY = 0;
0234:         pB->m_DrehungenSymmY = 0;
0235:         for (j=0; j<24; j++)
0236:         {
0237:                 pG = &pB->m_Gedreht[pB->m_DrehungenGesamtY];
0238: 
0239:                 xmax = 0; ymax = 0; zmax = 0;
0240:                 xp = 0; yp = 0; zp = 0;
0241: 
0242:                 // Lage im Raum berechnen

0243:                 pG->m_Bits.int64 = 0;
0244: 
0245:                 // minimale Translation berechnen

0246:                 for (i=0; i<count; i++)
0247:                 {
0248:                         // lineare Transformation

0249:                         x = rot[j][0][0]*posX[i] + rot[j][0][1]*posY[i] + rot[j][0][2]*posZ[i];
0250:                         y = rot[j][1][0]*posX[i] + rot[j][1][1]*posY[i] + rot[j][1][2]*posZ[i];
0251:                         z = rot[j][2][0]*posX[i] + rot[j][2][1]*posY[i] + rot[j][2][2]*posZ[i];
0252:                         if (-x > xp) xp = -x;
0253:                         if (-y > yp) yp = -y;
0254:                         if (-z > zp) zp = -z;
0255:                 }
0256: 
0257:                 for (i=0; i<count; i++)
0258:                 {
0259:                         // Affine Transformation

0260:                         x = rot[j][0][0]*posX[i] + rot[j][0][1]*posY[i] + rot[j][0][2]*posZ[i] + xp;
0261:                         y = rot[j][1][0]*posX[i] + rot[j][1][1]*posY[i] + rot[j][1][2]*posZ[i] + yp;
0262:                         z = rot[j][2][0]*posX[i] + rot[j][2][1]*posY[i] + rot[j][2][2]*posZ[i] + zp;
0263: 
0264:                         if (x > xmax) xmax = x;
0265:                         if (y > ymax) ymax = y;
0266:                         if (z > zmax) zmax = z;
0267: 
0268:                         pG->m_Bits.word_bits[z] |= bit16[x + 3*y];
0269:                 }
0270: 
0271:                 // maximale Translation merken

0272:                 pG->m_MaxX = 2 - xmax;
0273:                 pG->m_MaxY = 3 - ymax;
0274:                 pG->m_MaxZ = 4 - zmax;
0275: 
0276:                 if (pG->m_MaxX < 0)
0277:                 {
0278:                         // Die gedrehte Bauform passt nicht in den Quader

0279:                         continue;
0280:                 }
0281: 
0282:                 // Bitmuster suchen (Symmterien nutzen)

0283:                 for (k=0; k<pB->m_DrehungenGesamtY; k++)
0284:                 {
0285:                         if (pB->m_Gedreht[k].m_Bits.int64 == pG->m_Bits.int64)
0286:                         {
0287:                                 k = -1;
0288:                                 break;
0289:                         }
0290:                 }
0291:                 if (k == -1) continue;
0292: 
0293:                 // echt neue Lage gefunden

0294:                 pB->m_DrehungenGesamtY++;
0295:                 if (j < 12) pB->m_DrehungenSymmY++;
0296:         }
0297:         pB->m_Drehungen = pB->m_DrehungenGesamtY;
0298: }
0299: 
0300: void InitPassendeFormen()
0301: {
0302:         // PassendIndex*

0303:         // PassendCount*

0304:         // PassendeFormen*

0305: 
0306:         tPassendeForm* pF1;
0307:         tPassendeForm* pF3;
0308:         tPassendeForm4* pF4;
0309:         tPassendeForm4* pF5;
0310:         int r, b, f, d;
0311:         int dcount, xcount, ycount;
0312:         int x, y, xs, ys;
0313:         int index;
0314:         BYTE byte;
0315:         tBelegung belegung;
0316:         tBauform* pB;
0317:         tBauform::tGedreht* pG;
0318:         UINT belegt32;
0319: 
0320:         int f2, d2, dcount2;
0321:         tBauform* pB2;
0322:         tBauform::tGedreht* pG2;
0323:         UINT64 belegtefelder;
0324:         UINT64 feldbit;
0325:         WORD belegt16, belegt16_2;
0326: 
0327:         pF1 = &PassendeFormen1[0];
0328:         pF3 = &PassendeFormen3[0];
0329:         pF4 = &PassendeFormen4[0];
0330:         pF5 = &PassendeFormen5[0];
0331:         for (r=0; r<12; r++)
0332:         {
0333:                 feldbit = bit64[r];
0334:                 x = r % 3;
0335:                 y = r / 3;
0336: 
0337:                 for (b=0; b<32; b++)
0338:                 {
0339:                         byte = NachbarFeld[(r << 5) + b];
0340:                         if (byte == INVALID_NF) continue;
0341: 
0342:                         PassendIndex1[byte] = pF1;
0343:                         PassendIndex3[byte] = pF3;
0344:                         PassendIndex4[byte] = pF4;
0345:                         PassendIndex5[byte] = pF5;
0346:                         PassendCount1[byte] = 0;
0347:                         PassendCount3[byte] = 0;
0348:                         PassendCount4[byte] = 0;
0349:                         PassendCount5[byte] = 0;
0350: 
0351:                         if (b == 31) continue;
0352: 
0353:                         belegt32 = 0;
0354: 
0355:                         if (b & 1 && x != 0) belegt32 |= bit32[r-1];
0356:                         if (b & 2 && x != 2) belegt32 |= bit32[r+1];
0357:                         if (b & 4 && y != 0) belegt32 |= bit32[r-3];
0358:                         if (b & 8 && y != 3) belegt32 |= bit32[r+3];
0359:                         if (b & 16) belegt32 |= bit32[r+16];
0360: 
0361:                         for (f=0; f<11; f++)
0362:                         {
0363:                                 pB = &Bauform[f];
0364:                                 dcount = pB->m_Drehungen;
0365:                                 for (d=0; d<dcount; d++)
0366:                                 {
0367:                                         pG = &pB->m_Gedreht[d];
0368:                                         xcount = pG->m_MaxX;
0369:                                         ycount = pG->m_MaxY;
0370:                                         for (ys=0; ys<=ycount; ys++)
0371:                                         {
0372:                                                 for (xs=0; xs<=xcount; xs++)
0373:                                                 {
0374:                                                         index = xs + 3*ys;
0375:                                                         belegung.int64 = pG->m_Bits.int64 << index;
0376:                                                         if (belegung.int64 & feldbit)
0377:                                                         {
0378:                                                                 if ((belegung.bits0 & belegt32) == 0)
0379:                                                                 {
0380:                                                                         // Stein passt - hinzufügen

0381:                                                                         pF1->belegung.int64 = belegung.int64;
0382:                                                                         pF1->form = bit16[f];
0383:                                                                         PassendCount1[byte]++;
0384:                                                                         pF1++;
0385: 
0386:                                                                         if (belegung.bits1 < 65536)
0387:                                                                         {
0388:                                                                                 // Passt für Rec3

0389:                                                                                 pF3->belegung.int64 = belegung.int64;
0390:                                                                                 pF3->form = bit16[f];
0391:                                                                                 PassendCount3[byte]++;
0392:                                                                                 pF3++;
0393: 
0394:                                                                                 if (belegung.bits1 == 0)
0395:                                                                                 {
0396:                                                                                         // Passt für Rec4

0397:                                                                                         pF4->belegung = belegung.bits0;
0398:                                                                                         pF4->form = bit16[f];
0399:                                                                                         PassendCount4[byte]++;
0400:                                                                                         pF4++;
0401: 
0402:                                                                                         if (belegung.bits0 < 65536)
0403:                                                                                         {
0404:                                                                                                 // Passt für Rec5

0405:                                                                                                 pF5->belegung = belegung.bits0 << 16;
0406:                                                                                                 pF5->form = bit16[f];
0407:                                                                                                 PassendCount5[byte]++;
0408:                                                                                                 pF5++;
0409:                                                                                         }
0410:                                                                                 }
0411:                                                                         }
0412:                                                                 }
0413:                                                         }
0414:                                                 }
0415:                                         }
0416:                                 }
0417:                         }
0418:                 }
0419:         }
0420: }
0421: 
0422: void InitData()
0423: {
0424:         UINT i;
0425:         int r, r2, f, d, b;
0426:         int count, dcount, xcount, ycount, zcount;
0427:         int x, y;
0428:         int xs, ys, zs;
0429:         int index;
0430:         int val, best;
0431:         int feld;
0432:         UINT64 i64;
0433:         tBauform* pB;
0434:         tBauform::tGedreht* pG;
0435:         UINT nb;
0436:         UINT belegt32;
0437:         UINT64 belegt64;
0438: 
0439:         // bit

0440:         i = 1;
0441:         for (r=0; r<16; r++)
0442:         {
0443:                 bit16[r] = i;
0444:                 i *= 2;
0445:         }
0446: 
0447:         i = 1;
0448:         for (r=0; r<32; r++)
0449:         {
0450:                 bit32[r] = i;
0451:                 i *= 2;
0452:         }
0453: 
0454:         i64 = 1;
0455:         for (r=0; r<64; r++)
0456:         {
0457:                 bit64[r] = i64;
0458:                 i64 *= 2;
0459:         }
0460: 
0461:         printf("\n- Bauformen...");
0462: 
0463:         // Bauform

0464:         InitBauform(0, 111, 211, 112, 113, 213, 0);                        // c

0465:         InitBauform(1, 311, 112, 212, 312, 313, 0);                        // T

0466:         InitBauform(2, 111, 211, 221, 231, 331, 0);                        // s

0467:         InitBauform(3, 311, 312, 212, 213, 113, 0);                        // w

0468:         InitBauform(4, 211, 112, 212, 213, 313, 0);                        // y

0469:         InitBauform(5, 111, 112, 212, 113, 213, 0);                        // b

0470:         InitBauform(6, 111, 211, 112, 113, 213, 114);                // 4er t

0471:         InitBauform(7, 111, 112, 113, 114, 213, 0);                        // 4er Y

0472:         InitBauform(8, 111, 112, 113, 114, 214, 0);                        // 4er L

0473:         InitBauform(9, 111, 112, 212, 122, 222, 0);                        // 3D-5er

0474:         InitBauform(10, 211, 212, 222, 122, 0, 0);                        // 3D-4er

0475: 
0476:         printf(" ok\n- passende Formen...");
0477: 
0478:         // Abbildung Nachbarn/Feld -> 0..191

0479:         index = 0;
0480:         count = 0;
0481:         for (r=0; r<12; r++)
0482:         {
0483:                 x = r % 3;
0484:                 y = r / 3;
0485:                 for (b=0; b<32; b++)
0486:                 {
0487:                         if (((b & 1) == 0 && (x == 0))
0488:                                         || ((b & 2) == 0 && (x == 2))
0489:                                         || ((b & 4) == 0 && (y == 0))
0490:                                         || ((b & 8) == 0 && (y == 3)))
0491:                         {
0492:                                 NachbarFeld[index] = 255;                // ungültig

0493:                         }
0494:                         else
0495:                         {
0496:                                 NachbarFeld[index] = count;
0497:                                 count++;
0498:                         }
0499:                         index++;
0500:                 }
0501:         }
0502: 
0503:         // Passende Bauformen für gegebene Feld/Nachbar-Kombination

0504:         InitPassendeFormen();
0505: 
0506:         printf(" ok\n- bestes Feld...");
0507: 
0508:         // Komprimierung

0509:         // Diese Schleife initialisiert Komprimierung aufgrund von Komprimierung_Invers.

0510:         int t;
0511:         for (r=0; r<4096; r++)
0512:         {
0513:                 for (t=0; t<30; t++)
0514:                 {
0515:                         if ((r & Komprimierung_Invers[t]) == Komprimierung_Invers[t])
0516:                         {
0517:                                 Komprimierung[r] = (t << 12);
0518:                                 break;
0519:                         }
0520:                 }
0521:         }
0522: 
0523:         UINT feldbit32;
0524:         tPassendeForm* pF;
0525: 
0526:         // BestesFeld

0527:         for (r=0; r<4096; r++)
0528:         {
0529:                 for (t=0; t<30; t++)
0530:                 {
0531:                         r2 = Komprimierung_Invers[t];
0532:                         best = 0;
0533:                         for (index=0; index<12; index++)
0534:                         {
0535:                                 feldbit32 = bit32[index];
0536:                                 if (feldbit32 & r) continue;
0537: 
0538:                                 val = 1000;
0539: 
0540:                                 nb = 0;
0541:                                 x = index % 3;
0542:                                 y = index / 3;
0543:                                 if (x == 0 || r & bit32[index-1]) nb |= 1;
0544:                                 if (x == 2 || r & bit32[index+1]) nb |= 2;
0545:                                 if (y == 0 || r & bit32[index-3]) nb |= 4;
0546:                                 if (y == 3 || r & bit32[index+3]) nb |= 8;
0547:                                 if (r2 & bit32[index]) nb |= 16;
0548:                                 b = NachbarFeld[(index << 5) | nb];
0549:                                 pF = PassendIndex1[b];
0550:                                 count = PassendCount1[b];
0551:                                 for (f=0; f<count; f++)
0552:                                 {
0553:                                         if (pF->belegung.bits0 & feldbit32)
0554:                                         {
0555:                                                 if ((pF->belegung.bits0 & ((r2 << 16) | r)) == 0)
0556:                                                 {
0557:                                                         val--;
0558:                                                 }
0559:                                         }
0560:                                         pF++;
0561:                                 }
0562: 
0563:                                 if (val > best)
0564:                                 {
0565:                                         best = val;
0566:                                         feld = b;
0567:                                 }
0568:                         }
0569:                         if (best == 1000)
0570:                         {
0571:                                 BestesFeld[(t << 12) | r] = INVALID_NF;
0572:                         }
0573:                         else
0574:                         {
0575:                                 BestesFeld[(t << 12) | r] = feld;
0576:                         }
0577:                 }
0578:         }
0579: 
0580:         printf(" ok\n\n");
0581: }
0582: 
0583: 
0584: // Diese Routine füllt die fünfte 12er-Ebene.

0585: void Rec5(tZustand* pZ)
0586: {
0587: #ifdef AUFRUFE
0588:         Aufrufe++;
0589: #endif

0590: 
0591:         int t, count;
0592:         tZustand zustand;
0593:         tPassendeForm4* pF;
0594:         BYTE b;
0595: 
0596:         pF = PassendIndex5[pZ->m_FreiesFeld_Nachbarn];
0597:         count = PassendCount5[pZ->m_FreiesFeld_Nachbarn];
0598: 
0599:         for (t=0; t<count; t++)
0600:         {
0601:                 if ((pF->form & pZ->m_VerbauteFormen) == 0)
0602:                 {
0603:                         // Bauform passt! Einsetzen

0604:                         zustand.m_VerbauteFormen = pZ->m_VerbauteFormen + pF->form;
0605:                         zustand.m_Belegung.bits0 = pZ->m_Belegung.bits0 | pF->belegung;
0606: 
0607:                         // bestes nächstes Feld suchen

0608:                         if (zustand.m_Belegung.word_bits[1] == 0x0fff)
0609:                         {
0610:                                 // Diese Ebene ist voll - Dies ist eine Lösung!

0611:                                 Loesungen++;
0612:                         }
0613:                         else
0614:                         {
0615:                                 CALC_INDEX_B5
0616:                                 if (b != INVALID_NF)
0617:                                 {
0618:                                         zustand.m_FreiesFeld_Nachbarn = b;
0619: 
0620:                                         // Rekursion

0621:                                         Rec5(&zustand);
0622:                                 }
0623:                         }
0624:                 }
0625: 
0626:                 pF++;
0627:         }
0628: }
0629: 
0630: 
0631: // Diese Routine füllt die vierte 12er-Ebene.

0632: // Sie kommt mit 32 Bit zur Darstellung der Felder aus.

0633: void Rec4(tZustand* pZ)
0634: {
0635: #ifdef AUFRUFE
0636:         Aufrufe++;
0637: #endif

0638: 
0639:         int t, count;
0640:         tZustand zustand;
0641:         tPassendeForm4* pF;
0642:         BYTE b;
0643: 
0644:         pF = PassendIndex4[pZ->m_FreiesFeld_Nachbarn];
0645:         count = PassendCount4[pZ->m_FreiesFeld_Nachbarn];
0646: 
0647:         for (t=0; t<count; t++)
0648:         {
0649:                 if ((pF->form & pZ->m_VerbauteFormen) == 0)
0650:                 {
0651:                         if ((pZ->m_Belegung.bits0 & pF->belegung) == 0)
0652:                         {
0653:                                 // Bauform passt! Einsetzen

0654:                                 zustand.m_VerbauteFormen = pZ->m_VerbauteFormen + pF->form;
0655:                                 zustand.m_Belegung.bits0 = (pZ->m_Belegung.bits0 | pF->belegung);
0656: 
0657:                                 // bestes nächstes Feld suchen

0658:                                 if (zustand.m_Belegung.word_bits[0] == 0x0fff)
0659:                                 {
0660:                                         // Diese Ebene ist voll

0661:                                         if (zustand.m_Belegung.word_bits[1] == 0x0fff)
0662:                                         {
0663:                                                 // Diese Ebene ist auch voll

0664:                                                 // Dies ist eine Lösung

0665:                                                 Loesungen++;
0666:                                         }
0667:                                         else
0668:                                         {
0669:                                                 // Ebene 5 beginnen

0670:                                                 if (zustand.m_VerbauteFormen >= DREI_D_TEST)
0671:                                                 {
0672:                                                         CALC_INDEX_B5
0673:                                                         if (b != INVALID_NF)
0674:                                                         {
0675:                                                                 zustand.m_FreiesFeld_Nachbarn = b;
0676:                                                                 Rec5(&zustand);
0677:                                                         }
0678:                                                 }
0679:                                         }
0680:                                 }
0681:                                 else
0682:                                 {
0683:                                         CALC_INDEX_B
0684:                                         if (b != INVALID_NF)
0685:                                         {
0686:                                                 zustand.m_FreiesFeld_Nachbarn = b;
0687: 
0688:                                                 // Rekursion

0689:                                                 Rec4(&zustand);
0690:                                         }
0691:                                 }
0692:                         }
0693:                 }
0694: 
0695:                 pF++;
0696:         }
0697: }
0698: 
0699: 
0700: // Diese Routine füllt die dritte 12er-Ebene.

0701: void Rec3(tZustand* pZ)
0702: {
0703: #ifdef AUFRUFE
0704:         Aufrufe++;
0705: #endif

0706: 
0707:         int t, count;
0708:         tZustand zustand;
0709:         tPassendeForm* pF;
0710:         BYTE b;
0711: 
0712:         pF = PassendIndex3[pZ->m_FreiesFeld_Nachbarn];
0713:         count = PassendCount3[pZ->m_FreiesFeld_Nachbarn];
0714: 
0715:         for (t=0; t<count; t++)
0716:         {
0717:                 if ((pF->form & pZ->m_VerbauteFormen) == 0)
0718:                 {
0719:                         if ((pZ->m_Belegung.int64 & pF->belegung.int64) == 0)
0720:                         {
0721:                                 // Bauform passt! Einsetzen

0722:                                 zustand.m_VerbauteFormen = pZ->m_VerbauteFormen + pF->form;
0723:                                 zustand.m_Belegung.int64 = (pZ->m_Belegung.int64 | pF->belegung.int64);
0724: 
0725:                                 // bestes nächstes Feld suchen

0726:                                 if (zustand.m_Belegung.word_bits[0] == 0x0fff)
0727:                                 {
0728:                                         // Diese Ebene ist voll

0729:                                         if (zustand.m_Belegung.word_bits[1] == 0x0fff)
0730:                                         {
0731:                                                 // Diese Ebene ist auch voll

0732:                                                 if (zustand.m_Belegung.word_bits[2] == 0x0fff)
0733:                                                 {
0734:                                                         // Dies ist eine Lösung

0735:                                                         Loesungen++;
0736:                                                 }
0737:                                                 else
0738:                                                 {
0739:                                                         // Ebene 5 beginnen

0740:                                                         if (zustand.m_VerbauteFormen >= DREI_D_TEST)
0741:                                                         {
0742:                                                                 zustand.m_Belegung.bits0 = (zustand.m_Belegung.bits1 << 16) | 0x0fff;
0743:                                                                 CALC_INDEX_B5
0744:                                                                 if (b != INVALID_NF)
0745:                                                                 {
0746:                                                                         zustand.m_FreiesFeld_Nachbarn = b;
0747: 
0748:                                                                         Rec5(&zustand);
0749:                                                                 }
0750:                                                         }
0751:                                                 }
0752:                                         }
0753:                                         else
0754:                                         {
0755:                                                 // Ebene 4 beginnen

0756:                                                 zustand.m_Belegung.bits0 = (UINT)(zustand.m_Belegung.int64 >> 16);
0757:                                                 CALC_INDEX_B
0758:                                                 if (b != INVALID_NF)
0759:                                                 {
0760:                                                         zustand.m_FreiesFeld_Nachbarn = b;
0761: 
0762:                                                         Rec4(&zustand);
0763:                                                 }
0764:                                         }
0765:                                 }
0766:                                 else
0767:                                 {
0768:                                         CALC_INDEX_B
0769:                                         if (b != INVALID_NF)
0770:                                         {
0771:                                                 zustand.m_FreiesFeld_Nachbarn = b;
0772: 
0773:                                                 // Rekursion

0774:                                                 Rec3(&zustand);
0775:                                         }
0776:                                 }
0777:                         }
0778:                 }
0779: 
0780:                 pF++;
0781:         }
0782: }
0783: 
0784: 
0785: // Diese Routine füllt die zweite 12er-Ebene.

0786: void Rec2(tZustand* pZ)
0787: {
0788: #ifdef AUFRUFE
0789:         Aufrufe++;
0790: #endif

0791: 
0792:         int t, count;
0793:         tZustand zustand;
0794:         tPassendeForm* pF;
0795:         BYTE b;
0796: 
0797:         pF = PassendIndex1[pZ->m_FreiesFeld_Nachbarn];
0798:         count = PassendCount1[pZ->m_FreiesFeld_Nachbarn];
0799: 
0800:         for (t=0; t<count; t++)
0801:         {
0802:                 if ((pF->form & pZ->m_VerbauteFormen) == 0)
0803:                 {
0804:                         if ((pZ->m_Belegung.int64 & pF->belegung.int64) == 0)
0805:                         {
0806:                                 // Bauform passt! Einsetzen

0807:                                 zustand.m_VerbauteFormen = pZ->m_VerbauteFormen + pF->form;
0808:                                 zustand.m_Belegung.int64 = (pZ->m_Belegung.int64 | pF->belegung.int64);
0809: 
0810:                                 // bestes nächstes Feld suchen

0811:                                 if (zustand.m_Belegung.word_bits[0] == 0x0fff)
0812:                                 {
0813:                                         // Ebene 2 ist voll

0814:                                         if (zustand.m_Belegung.word_bits[1] == 0x0fff)
0815:                                         {
0816:                                                 // Diese Ebene ist auch voll

0817:                                                 if (zustand.m_Belegung.word_bits[2] == 0x0fff)
0818:                                                 {
0819:                                                         if (zustand.m_Belegung.word_bits[3] == 0x0fff)
0820:                                                         {
0821:                                                                 // Dies ist eine Lösung

0822:                                                                 Loesungen++;
0823:                                                         }
0824:                                                         else
0825:                                                         {
0826:                                                                 // Ebene 5 beginnen

0827:                                                                 if (zustand.m_VerbauteFormen >= DREI_D_TEST)
0828:                                                                 {
0829:                                                                         zustand.m_Belegung.bits0 = zustand.m_Belegung.bits1;
0830:                                                                         CALC_INDEX_B5
0831:                                                                         if (b != INVALID_NF)
0832:                                                                         {
0833:                                                                                 zustand.m_FreiesFeld_Nachbarn = b;
0834: 
0835:                                                                                 Rec5(&zustand);
0836:                                                                         }
0837:                                                                 }
0838:                                                         }
0839:                                                 }
0840:                                                 else
0841:                                                 {
0842:                                                         // Ebene 4 beginnen

0843:                                                         zustand.m_Belegung.bits0 = zustand.m_Belegung.bits1;
0844: 
0845:                                                         CALC_INDEX_B
0846:                                                         if (b != INVALID_NF)
0847:                                                         {
0848:                                                                 zustand.m_FreiesFeld_Nachbarn = b;
0849: 
0850:                                                                 Rec4(&zustand);
0851:                                                         }
0852:                                                 }
0853:                                         }
0854:                                         else
0855:                                         {
0856:                                                 // Ebene 3 beginnen

0857:                                                 zustand.m_Belegung.int64 >>= 16;
0858:                                                 CALC_INDEX_B
0859:                                                 if (b != INVALID_NF)
0860:                                                 {
0861:                                                         zustand.m_FreiesFeld_Nachbarn = b;
0862: 
0863:                                                         Rec3(&zustand);
0864:                                                 }
0865:                                         }
0866:                                 }
0867:                                 else
0868:                                 {
0869:                                         CALC_INDEX_B
0870:                                         if (b != INVALID_NF)
0871:                                         {
0872:                                                 zustand.m_FreiesFeld_Nachbarn = b;
0873: 
0874:                                                 // Rekursion

0875:                                                 Rec2(&zustand);
0876:                                         }
0877:                                 }
0878:                         }
0879:                 }
0880: 
0881:                 pF++;
0882:         }
0883: }
0884: 
0885: 
0886: // Diese Routine füllt die erste 12er-Ebene.

0887: void Rec1(tZustand* pZ)
0888: {
0889: #ifdef AUFRUFE
0890:         Aufrufe++;
0891: #endif

0892: 
0893:         int t, count;
0894:         tZustand zustand;
0895:         tPassendeForm* pF;
0896:         BYTE b;
0897: 
0898:         pF = PassendIndex1[pZ->m_FreiesFeld_Nachbarn];
0899:         count = PassendCount1[pZ->m_FreiesFeld_Nachbarn];
0900: 
0901:         for (t=0; t<count; t++)
0902:         {
0903:                 if ((pF->form & pZ->m_VerbauteFormen) == 0)
0904:                 {
0905:                         if ((pZ->m_Belegung.int64 & pF->belegung.int64) == 0)
0906:                         {
0907:                                 // Bauform passt! Einsetzen

0908:                                 zustand.m_VerbauteFormen = pZ->m_VerbauteFormen + pF->form;
0909:                                 zustand.m_Belegung.int64 = (pZ->m_Belegung.int64 | pF->belegung.int64);
0910: 
0911:                                 // bestes nächstes Feld suchen

0912:                                 if (zustand.m_Belegung.word_bits[0] == 0x0fff)
0913:                                 {
0914:                                         // Ebene 1 ist voll

0915: 
0916:                                         if (zustand.m_Belegung.word_bits[1] == 0x0fff)
0917:                                         {
0918:                                                 // Ebene 2 ist auch voll

0919:                                                 if (zustand.m_Belegung.word_bits[2] == 0x0fff)
0920:                                                 {
0921:                                                         if (zustand.m_Belegung.word_bits[3] == 0x0fff)
0922:                                                         {
0923:                                                                 // Ebene 5 beginnen

0924:                                                                 if (zustand.m_VerbauteFormen >= DREI_D_TEST)
0925:                                                                 {
0926:                                                                         zustand.m_Belegung.bits0 = 0x00000fff;
0927:                                                                         zustand.m_FreiesFeld_Nachbarn = NachbarFeld[21];
0928:                                                                         // toter Code, aber egal

0929: 
0930:                                                                         Rec5(&zustand);
0931:                                                                 }
0932:                                                         }
0933:                                                         else
0934:                                                         {
0935:                                                                 // Ebene 4 beginnen

0936:                                                                 zustand.m_Belegung.bits0 = zustand.m_Belegung.word_bits[3];
0937:                                                                 CALC_INDEX_B
0938:                                                                 if (b != INVALID_NF)
0939:                                                                 {
0940:                                                                         zustand.m_FreiesFeld_Nachbarn = b;
0941: 
0942:                                                                         Rec4(&zustand);
0943:                                                                 }
0944:                                                         }
0945:                                                 }
0946:                                                 else
0947:                                                 {
0948:                                                         // Ebene 3 beginnen

0949:                                                         zustand.m_Belegung.int64 >>= 32;
0950:                                                         CALC_INDEX_B
0951:                                                         if (b != INVALID_NF)
0952:                                                         {
0953:                                                                 zustand.m_FreiesFeld_Nachbarn = b;
0954: 
0955:                                                                 Rec3(&zustand);
0956:                                                         }
0957:                                                 }
0958:                                         }
0959:                                         else
0960:                                         {
0961:                                                 // Ebene 2 beginnen

0962:                                                 zustand.m_Belegung.int64 >>= 16;
0963:                                                 CALC_INDEX_B
0964:                                                 if (b != INVALID_NF)
0965:                                                 {
0966:                                                         zustand.m_FreiesFeld_Nachbarn = b;
0967: 
0968:                                                         Rec2(&zustand);
0969:                                                 }
0970:                                         }
0971:                                 }
0972:                                 else
0973:                                 {
0974:                                         CALC_INDEX_B
0975:                                         if (b != INVALID_NF)
0976:                                         {
0977:                                                 zustand.m_FreiesFeld_Nachbarn = b;
0978: 
0979:                                                 // Rekursion

0980:                                                 Rec1(&zustand);
0981:                                         }
0982:                                 }
0983:                         }
0984:                 }
0985: 
0986:                 pF++;
0987:         }
0988: }
0989: 
0990: 
0991: // Diese Routine platziert den X-Bauklotz in seine 12 Positionen.

0992: void solve()
0993: {
0994:         tZustand zustand;
0995:         zustand.m_VerbauteFormen = 0;
0996: 
0997:         printf("x");
0998:         zustand.m_Belegung.word_bits[0] = 0x00ba;
0999:         zustand.m_Belegung.word_bits[1] = 0;
1000:         zustand.m_Belegung.word_bits[2] = 0;
1001:         zustand.m_Belegung.word_bits[3] = 0;
1002:         zustand.m_FreiesFeld_Nachbarn = NachbarFeld[0*32 + 15];
1003:         Rec1(&zustand);
1004: 
1005:         printf("x");
1006:         zustand.m_Belegung.word_bits[0] = 0;
1007:         zustand.m_Belegung.word_bits[1] = 0x00ba;
1008:         zustand.m_Belegung.word_bits[2] = 0;
1009:         zustand.m_Belegung.word_bits[3] = 0;
1010:         zustand.m_FreiesFeld_Nachbarn = NachbarFeld[4*32 + 16];
1011:         Rec1(&zustand);
1012: 
1013:         printf("x");
1014:         zustand.m_Belegung.word_bits[0] = 0x0002;
1015:         zustand.m_Belegung.word_bits[1] = 0x0007;
1016:         zustand.m_Belegung.word_bits[2] = 0x0002;
1017:         zustand.m_Belegung.word_bits[3] = 0;
1018:         zustand.m_FreiesFeld_Nachbarn = NachbarFeld[0*32 + 23];
1019:         Rec1(&zustand);
1020: 
1021:         printf("x");
1022:         zustand.m_Belegung.word_bits[0] = 0x0010;
1023:         zustand.m_Belegung.word_bits[1] = 0x0038;
1024:         zustand.m_Belegung.word_bits[2] = 0x0010;
1025:         zustand.m_Belegung.word_bits[3] = 0;
1026:         zustand.m_FreiesFeld_Nachbarn = NachbarFeld[3*32 + 19];
1027:         Rec1(&zustand);
1028: 
1029:         printf("x");
1030:         zustand.m_Belegung.word_bits[0] = 0x0008;
1031:         zustand.m_Belegung.word_bits[1] = 0x0049;
1032:         zustand.m_Belegung.word_bits[2] = 0x0008;
1033:         zustand.m_Belegung.word_bits[3] = 0;
1034:         zustand.m_FreiesFeld_Nachbarn = NachbarFeld[0*32 + 29];
1035:         Rec1(&zustand);
1036: 
1037:         printf("x");
1038:         zustand.m_Belegung.word_bits[0] = 0x0040;
1039:         zustand.m_Belegung.word_bits[1] = 0x0248;
1040:         zustand.m_Belegung.word_bits[2] = 0x0040;
1041:         zustand.m_Belegung.word_bits[3] = 0;
1042:         zustand.m_FreiesFeld_Nachbarn = NachbarFeld[9*32 + 29];
1043:         Rec1(&zustand);
1044: 
1045:         printf("x");
1046:         zustand.m_Belegung.word_bits[0] = 0;
1047:         zustand.m_Belegung.word_bits[1] = 0x0008;
1048:         zustand.m_Belegung.word_bits[2] = 0x0049;
1049:         zustand.m_Belegung.word_bits[3] = 0x0008;
1050:         zustand.m_FreiesFeld_Nachbarn = NachbarFeld[0*32 + 5];
1051:         Rec1(&zustand);
1052: 
1053:         printf("x");
1054:         zustand.m_Belegung.word_bits[0] = 0x0010;
1055:         zustand.m_Belegung.word_bits[1] = 0x0092;
1056:         zustand.m_Belegung.word_bits[2] = 0x0010;
1057:         zustand.m_Belegung.word_bits[3] = 0;
1058:         zustand.m_FreiesFeld_Nachbarn = NachbarFeld[1*32 + 28];
1059:         Rec1(&zustand);
1060: 
1061: 
1062:         // bezüglich Y-Drehung symmetrische Positionen:

1063:         // zusätzliche Symmetrie berücksichtigen!

1064:         printf("\nNeuinitialisierung einiger Tabellen...");
1065:         Bauform[9].m_Drehungen = Bauform[9].m_DrehungenSymmY;
1066:         InitPassendeFormen();
1067:         printf(" ok\n");
1068: 
1069:         printf("x");
1070:         zustand.m_Belegung.word_bits[0] = 0;
1071:         zustand.m_Belegung.word_bits[1] = 0;
1072:         zustand.m_Belegung.word_bits[2] = 0x00ba;
1073:         zustand.m_Belegung.word_bits[3] = 0;
1074:         zustand.m_FreiesFeld_Nachbarn = NachbarFeld[0*32 + 5];
1075:         Rec1(&zustand);
1076: 
1077:         printf("x");
1078:         zustand.m_Belegung.word_bits[0] = 0;
1079:         zustand.m_Belegung.word_bits[1] = 0x0002;
1080:         zustand.m_Belegung.word_bits[2] = 0x0007;
1081:         zustand.m_Belegung.word_bits[3] = 0x0002;
1082:         zustand.m_FreiesFeld_Nachbarn = NachbarFeld[0*32 + 5];
1083:         Rec1(&zustand);
1084: 
1085:         printf("x");
1086:         zustand.m_Belegung.word_bits[0] = 0;
1087:         zustand.m_Belegung.word_bits[1] = 0x0010;
1088:         zustand.m_Belegung.word_bits[2] = 0x0038;
1089:         zustand.m_Belegung.word_bits[3] = 0x0010;
1090:         zustand.m_FreiesFeld_Nachbarn = NachbarFeld[3*32 + 1];
1091:         Rec1(&zustand);
1092: 
1093:         printf("x");
1094:         zustand.m_Belegung.word_bits[0] = 0;
1095:         zustand.m_Belegung.word_bits[1] = 0x0010;
1096:         zustand.m_Belegung.word_bits[2] = 0x0092;
1097:         zustand.m_Belegung.word_bits[3] = 0x0010;
1098:         zustand.m_FreiesFeld_Nachbarn = NachbarFeld[4*32 + 16];
1099:         Rec1(&zustand);
1100: }
1101: 
1102: 
1103: int main(int argc, char* argv[])
1104: {
1105:         printf("c't-Puzzle loesen\n\n");
1106: 
1107:         time_t zeit_anfang;
1108:         time_t zeit_ende;
1109:         time(&zeit_anfang);
1110: 
1111:         printf("Initialisierung");
1112:         InitData();
1113: 
1114:         Aufrufe = 0;
1115:         Loesungen = 0;
1116: 
1117:         printf("Berechnung\n");
1118:         solve();
1119:         time(&zeit_ende);
1120: 
1121:         int time_used = (int)difftime(zeit_ende, zeit_anfang);
1122:         int sekunden = time_used % 60;
1123:         int minuten = time_used / 60;
1124: 
1125:         printf("\n\nZeit:      %02d:%02d\nLoesungen: %d\n", minuten, sekunden, Loesungen);
1126: #ifdef AUFRUFE
1127:         printf("Aufrufe:   %d\n", Aufrufe);
1128: #endif

1129: 
1130:         return 0;
1131: }