0001: // ctpuzzle.cpp : Definiert den Einsprungpunkt für die Konsolenanwendung.

0002: //

0003: 
0004: #include "stdafx.h"
0005: 
0006: // #define ZAEHLEN

0007: 
0008: typedef unsigned __int64 int64;
0009: typedef unsigned long int32;
0010: typedef unsigned short int16;
0011: typedef unsigned char byte;
0012: 
0013: // Oft gebrauchte Verschiebe-Operationen als Shifts ausgedrückt

0014: #define SHIFT_PLUSX(x)   (((x)&(int64)033333333333333333333)<<1)
0015: #define SHIFT_PLUS2X(x)  (((x)&(int64)011111111111111111111)<<2)
0016: #define SHIFT_MINUSX(x)  (((x)&(int64)066666666666666666666)>>1)
0017: #define SHIFT_MINUS2X(x) (((x)&(int64)044444444444444444444)>>2)
0018: #define SHIFT_PLUSY(x)   (((x)&(int64)007770777077707770777)<<3)
0019: #define SHIFT_PLUS2Y(x)  (((x)&(int64)000770077007700770077)<<6)
0020: #define SHIFT_MINUSY(x)  (((x)&(int64)077707770777077707770)>>3)
0021: #define SHIFT_MINUS2Y(x) (((x)&(int64)077007700770077007700)>>6)
0022: #define SHIFT_PLUSZ(x)   (((x)&(int64)000007777777777777777)<<12)
0023: #define SHIFT_PLUS2Z(x)  (((x)&(int64)000000000777777777777)<<24)
0024: #define SHIFT_MINUSZ(x)  (((x)&(int64)077777777777777770000)>>12)
0025: #define SHIFT_MINUS2Z(x) (((x)&(int64)077777777777700000000)>>24)
0026: 
0027: // Ab diesen Grenzwerten beginnt vorab ausgerechnetes "Endspiel":

0028: // Alle Kombinationen von Steinen, die komplett oberhalb von 

0029: // Bit ENDSPIEL_START liegen.

0030: #define HAUPTSPIEL_MASKE   ((int64) 0x00000007fffffff)
0031: #define ENDSPIEL_START 31
0032: #define ENDSPIEL_RESTMASKE ((int64) 0x000000f80000000)
0033: #define EXTENDER_SIZE 1500000
0034: 
0035: 
0036: //

0037: // -------------------------

0038: //      Datenstrukturen

0039: // -------------------------

0040: //

0041: 
0042: #define N_VARIANTEN 128
0043: #define SUCH_EBENEN 5
0044: 
0045: 
0046: // Ein Puzzle-Teil in allen Varianten

0047: typedef struct {
0048:     int64 basisform;
0049:     int64 relVarianten[5][12][N_VARIANTEN];
0050:     short schluessel[5][12][20];
0051:     int64 alleVarianten[577];
0052:     int64 variantenEndspiel[400];
0053: } Stein;
0054: 
0055: 
0056: // Eine Lösung im Endspiel 

0057: typedef struct {
0058:     // Belegung Bits 36-59 bilden den Index für das Array 'endspiele'.

0059:     // Sie brauchen deshalb hier nicht abgelegt zu werden.

0060:     int16 muster;        // High 6 Bit: Belegung (30-35), Low 10 Bit: Verbrauch

0061:     int16 nloesungen;        // Anzahl verschiedener Lösungen zu dieser Belegung

0062: } EndspielLoesung;
0063: 
0064: 
0065: // Verketteter Datenblock für Endspiel-Speicherung

0066: typedef struct extender {
0067:     EndspielLoesung loesungen[7];
0068:     struct extender *next;
0069: } EndspielExtender;
0070: 
0071: 
0072: // XYZ-Koordinate für das Rotieren/Verschieben in der Initialisierungsphase

0073: typedef struct {
0074:     int x;
0075:     int y;
0076:     int z;
0077:     bool valid;
0078: } XYZ;
0079: 
0080: 
0081: //

0082: // -------------------------

0083: //        Variablen

0084: // -------------------------

0085: //

0086: 
0087: // Programmstart

0088: time_t start;
0089: 
0090: 
0091: // Folge von 1-Bit-Masken (war mal zentrale Steuerung 

0092: // für die Suchreihenfolge, ist jetzt fast überflüssig)

0093: int64 reihenfolge[60];
0094: 
0095: 
0096: // Steine in Grundform

0097: Stein basisSteine[12];
0098: 
0099: // Kopie von 'basisSteine', 

0100: // aber hier werden jeweils die mit den vorab gesetzten Steinen 

0101: // kollidierenden Varianten herausgelöscht.

0102: Stein steine[12];
0103: 
0104: 
0105: // Steuer-Struktur, die für eine 12-Bit-Ebenenbelegung sagt,

0106: // welche Position als nächste besetzt werden soll ('Hotspot').

0107: // Außerdem Info auf Basis der Hotspot-Nachbarn, welche 

0108: // Varianten-Teilmenge passen kann.

0109: // Indizes [0] = Hotspot, [1] = Start-Schlüssel, [2] = End-Schlüssel

0110: 
0111: // Hotspot für Ebenen 0 und 1

0112: short hotspotSchluessel[0x1000][4];
0113: 
0114: // Hotspot für Ebene 2, vermeidet Positionen, 

0115: // die schon im Endspiel abgelegt sind.

0116: short hotspotSchluesselE2[0x1000][4];
0117: 
0118: 
0119: // (Hash-)Array als Einstieg in den Endspiel-Speicher.

0120: // Hashcode = Bits 36-59

0121: EndspielExtender *endspiele[0x1000000];
0122: 
0123: // Vorrat an Blöcken für verkettete Endspiel-Daten

0124: EndspielExtender extender[EXTENDER_SIZE];
0125: 
0126: // Belegungs-Zähler für 'extender'

0127: int32 nExtender = 0;
0128: 
0129: 
0130: // Eine recht brauchbare statische Suchreihenfolge

0131: int BIT_REIHE_INV_RINGE[] = {
0132:     0 , 1, 2, 5, 8,11,10, 9, 6, 3, 4, 7,
0133:     12,13,14,17,20,23,22,21,18,15,16,19,
0134:     24,25,26,29,32,35,34,33,30,27,28,31,
0135:     36,37,38,41,44,47,46,45,42,39,40,43,
0136:     48,49,50,53,56,59,58,57,54,51,52,55
0137: };
0138: 
0139: 
0140: /** Bitmuster der Nachbarn in einer Ebene. */
0141: int NACHBARN[] = {
0142:     00012, 00025, 00042,
0143:     00121, 00252, 00424,
0144:     01210, 02520, 04240,
0145:     02100, 05200, 02400
0146: };
0147: 
0148: // Einige Statistik-Zähler, wenn #define ZAEHLEN

0149: 
0150: // Anzahl ins Puzzle gesetzter Steine

0151: int32 nSuchvorgaenge = 0;
0152: 
0153: // Anzahl an Versuchen, einen Stein zu setzen

0154: int64 nVersuche = 0;
0155: 
0156: // Anzahl an Versuchen, eine Konfiguration 

0157: // als Endspiel zu bestätigen oder zu verwerfen

0158: int32 nEndspiele = 0;
0159: 
0160: // !!! DIE WICHTIGSTE VARIABLE !!!

0161: int32 nLoesungen;
0162: 
0163: //

0164: // -------------------------

0165: //        Funktionen

0166: // -------------------------

0167: //

0168: 
0169: 
0170:     /**

0171:      * Liefert True, wenn die Koordinaten im vorgegebenen 3*4*5-Quader liegen.

0172:      * @param koords Array der Koordinaten, jeweils als {x, y, z}

0173:      * @return True, wenn alle im 3*4*5-Quader liegen

0174:      */
0175:     bool isGueltig(XYZ koords[]) {
0176:         XYZ *p;
0177:         for (p=koords; p->valid; p++) {
0178:             if (!((p->x >= 0) && (p->x < 3) &&
0179:                   (p->y >= 0) && (p->y < 4) &&
0180:                   (p->z >= 0) && (p->z < 5))) {
0181:                 return false;
0182:             }
0183:         }
0184:         return true;
0185:     }
0186: 
0187: 
0188:     inline XYZ newXYZ(int x, int y, int z) {
0189:         XYZ pt;
0190:         pt.x = x;
0191:         pt.y = y;
0192:         pt.z = z;
0193:         pt.valid = true;
0194:         return pt;
0195:     }
0196: 
0197: 
0198:     /**

0199:      * Verschiebt die Punkte in den positiven Oktanten, auf jeder Achse

0200:      * beginnend mit 0 als kleinstem Wert.

0201:      */
0202:     void verschiebeNachNull(XYZ koords[]) {
0203:         int xMin = 1000;
0204:         int yMin = 1000;
0205:         int zMin = 1000;
0206:         XYZ *kp;
0207: 
0208:         for (kp=koords; kp->valid; kp++) {
0209:             if (kp->x < xMin) xMin = kp->x;
0210:             if (kp->y < yMin) yMin = kp->y;
0211:             if (kp->z < zMin) zMin = kp->z;
0212:         }
0213:         for (kp=koords; kp->valid; kp++) {
0214:             kp->x -= xMin;
0215:             kp->y -= yMin;
0216:             kp->z -= zMin;
0217:         }
0218:     }
0219: 
0220:     /**

0221:      * Verschiebt den Stein um DX, DY, DZ.

0222:      */
0223:     void verschiebe(XYZ koords[], XYZ ziel[], int dx, int dy, int dz) {
0224:         XYZ *kp, *zp;
0225:         for (kp=koords, zp=ziel; kp->valid; kp++, zp++) {
0226:             ziel->x = kp->x + dx;
0227:             ziel->y = kp->y + dy;
0228:             ziel->z = kp->z + dz;
0229:         }
0230:         zp->valid = false;
0231:     }
0232: 
0233:     /**

0234:      * Verschiebt den Stein um DX, DY, DZ.

0235:      */
0236:     int64 verschiebeBits(int64 bits, int dx, int dy, int dz) {
0237:         int shift = dx + 3 * dy + 12 * dz;
0238:         return bits << shift;
0239:     }
0240: 
0241:     /**

0242:      * Bestimmt die Ausdehnung des Steins in Richtung der X-Achse.

0243:      * Es wird vorausgesetzt, dass der Stein an Null-Position liegt.

0244:      * @param koords Stein als Koordinaten-Array

0245:      * @return Ausdehnung in der angegebenen Achse

0246:      */
0247:     int xAusdehnung(XYZ koords[]) {
0248:         int maxwert = 0;
0249:         XYZ *kp;
0250:         for (kp=koords; kp->valid; kp++) {
0251:             if (kp->x > maxwert) maxwert = kp->x;
0252:         }
0253:         return maxwert + 1;
0254:     }
0255: 
0256:     /**

0257:      * Bestimmt die Ausdehnung des Steins in Richtung der Y-Achse.

0258:      * Es wird vorausgesetzt, dass der Stein an Null-Position liegt.

0259:      * @param koords Stein als Koordinaten-Array

0260:      * @return Ausdehnung in der angegebenen Achse

0261:      */
0262:     int yAusdehnung(XYZ koords[]) {
0263:         int maxwert = 0;
0264:         XYZ *kp;
0265:         for (kp=koords; kp->valid; kp++) {
0266:             if (kp->y > maxwert) maxwert = kp->y;
0267:         }
0268:         return maxwert + 1;
0269:     }
0270: 
0271:     /**

0272:      * Bestimmt die Ausdehnung des Steins in Richtung der Z-Achse.

0273:      * Es wird vorausgesetzt, dass der Stein an Null-Position liegt.

0274:      * @param koords Stein als Koordinaten-Array

0275:      * @return Ausdehnung in der angegebenen Achse

0276:      */
0277:     int zAusdehnung(XYZ koords[]) {
0278:         int maxwert = 0;
0279:         XYZ *kp;
0280:         for (kp=koords; kp->valid; kp++) {
0281:             if (kp->z > maxwert) maxwert = kp->z;
0282:         }
0283:         return maxwert + 1;
0284:     }
0285: 
0286:     /**

0287:      * Wandelt von Koordinaten-Array in Bitvektor um.

0288:      */
0289:     int64 getBits(XYZ koords[]) {
0290:         int64 result = 0;
0291:         XYZ *kp;
0292:         for (kp=koords; kp->valid; kp++) {
0293:             result += ((int64) 1) <<
0294:                 (kp->x + 3*kp->y + 12*kp->z);
0295:         }
0296:         return result;
0297:     }
0298: 
0299:     /**

0300:      * Wandelt von Bitvektor in Koordinaten-Array um.

0301:      */
0302:     void getKoords(int64 bits, XYZ ziel[]) {
0303:         XYZ *zp = ziel;
0304:         int64 maske = 1;
0305:         int x, y, z;
0306:         for (z=0; z<5; z++) {
0307:             for (y=0; y<4; y++) {
0308:                 for (x=0; x<3; x++) {
0309:                     if ((bits & maske) != 0) {
0310:                         *zp++ = newXYZ(x, y, z);
0311:                     }
0312:                     maske = maske << 1;
0313:                 }
0314:             }
0315:         }
0316:         zp->valid = false;
0317:     }
0318: 
0319:     /**

0320:      * Rotiert einen Punkt um den Quader-Mittelpunkt.

0321:      * @param punkt originaler Punkt

0322:      * @param orientierung Version von 0 bis 23

0323:      * @return rotierter Punkt.

0324:      */
0325:     XYZ rotiereXYZ(XYZ punkt, int orientierung) {
0326:         int x = punkt.x;
0327:         int y = punkt.y;
0328:         int z = punkt.z;
0329: 
0330:         switch (orientierung) {
0331:             case  0: return newXYZ(x,   y,   z);
0332:             case  1: return newXYZ(2-x, 3-y, z);
0333:             case  2: return newXYZ(2-x, y,   4-z);
0334:             case  3: return newXYZ(x,   3-y, 4-z);
0335:             case  4: return newXYZ(y,   z,   x);
0336:             case  5: return newXYZ(2-y, 3-z, x);
0337:             case  6: return newXYZ(2-y, z,   4-x);
0338:             case  7: return newXYZ(y,   3-z, 4-x);
0339:             case  8: return newXYZ(z,   x,   y);
0340:             case  9: return newXYZ(2-z, 3-x, y);
0341:             case 10: return newXYZ(2-z, x,   4-y);
0342:             case 11: return newXYZ(z,   3-x, 4-y);
0343:             case 12: return newXYZ(2-x, 3-z, 4-y);
0344:             case 13: return newXYZ(x,   z,   4-y);
0345:             case 14: return newXYZ(x,   3-z, y);
0346:             case 15: return newXYZ(2-x, z,   y);
0347:             case 16: return newXYZ(2-z, 3-y, 4-x);
0348:             case 17: return newXYZ(z,   y,   4-x);
0349:             case 18: return newXYZ(z,   3-y, x);
0350:             case 19: return newXYZ(2-z, y,   x);
0351:             case 20: return newXYZ(2-y, 3-x, 4-z);
0352:             case 21: return newXYZ(y,   x,   4-z);
0353:             case 22: return newXYZ(y,   3-x, z);
0354:             case 23: return newXYZ(2-y, x,   z);
0355:             default: return punkt;
0356:         }
0357:     }
0358: 
0359: 
0360:     /**

0361:      * Stein in Form eines XYZ-Arrays drehen.

0362:      */
0363:     void rotiere(XYZ koords[], XYZ ziel[], int orientierung) {
0364:         XYZ *kp, *zp;
0365:         for (kp=koords, zp=ziel; kp->valid; kp++, zp++) {
0366:             *zp = rotiereXYZ(*kp, orientierung);
0367:         }
0368:         zp->valid = false;
0369:     }
0370: 
0371:     /**

0372:      * Stein in Form eines Bitmusters drehen.

0373:      */
0374:     int64 rotiereBits(int64 bits, int orientierung) {
0375:         XYZ koords[7], rotiert[7];
0376:         getKoords(bits, koords);
0377:         rotiere(koords, rotiert, orientierung);
0378:         return getBits(rotiert);
0379:     }
0380: 
0381: 
0382:     /**

0383:      * Liefert zu einer Stein-Lage den Start-Schritt gemäß eingestellter

0384:      * Schritt-Reihenfolge.

0385:      */
0386:     int getStartPos(int64 bits) {
0387:         int i;
0388:         for (i=0; i<60; i++) {
0389:             if ((bits & reihenfolge[i]) != 0) {
0390:                 return i;
0391:             }
0392:         }
0393:         return 63;
0394:     }
0395: 
0396: 
0397:     /**

0398:      * Gibt es irgendwo ein isoliertes Einer-Loch?

0399:      */
0400:     inline bool isGesund(int64 belegung) {
0401:         int64 freie = (~belegung) & (int64) 077777777777777777777;
0402:         int64 muster = 
0403:             belegung |
0404:             ((freie & (int64) 033333333333333333333) <<  1) |
0405:             ((freie & (int64) 066666666666666666666) >>  1) |
0406:             ((freie & (int64) 007770777077707770777) <<  3) |
0407:             ((freie & (int64) 077707770777077707770) >>  3) |
0408:             ((freie & (int64) 000007777777777777777) << 12) |
0409:             ((freie & (int64) 077777777777777770000) >> 12);
0410:         return (muster  == (int64) 077777777777777777777);
0411:     }
0412: 
0413: 
0414:     /**

0415:      * Gibt es irgendwo ein isoliertes Einer- oder Zweier-Loch?

0416:      */
0417:     inline bool isGesund2(int64 bel) {
0418:         int64 frei = (~bel) & (int64) 077777777777777777777;
0419:         int64 kreuz;
0420: 
0421:         kreuz = 
0422:             bel |
0423:             SHIFT_PLUSY(frei) | 
0424:             SHIFT_MINUSY(frei) |
0425:             SHIFT_PLUSZ(frei) |
0426:             SHIFT_MINUSZ(frei);
0427:         if ((SHIFT_PLUSX(frei) | kreuz | SHIFT_MINUSX(frei))
0428:             != 077777777777777777777) {
0429:             return false;
0430:         }
0431:         if ((SHIFT_PLUSX(frei) | kreuz | SHIFT_MINUSX(kreuz) | SHIFT_MINUS2X(frei))
0432:             != 077777777777777777777) {
0433:             return false;
0434:         }
0435: 
0436:         kreuz =
0437:             bel | 
0438:             SHIFT_PLUSX(frei) |
0439:             SHIFT_MINUSX(frei) |
0440:             SHIFT_PLUSZ(frei) |
0441:             SHIFT_MINUSZ(frei);
0442:         if ((SHIFT_PLUSY(frei) | kreuz | SHIFT_MINUSY(kreuz) | SHIFT_MINUS2Y(frei))
0443:             != 077777777777777777777) {
0444:             return false;
0445:         }
0446: 
0447:         kreuz = 
0448:             bel | 
0449:             SHIFT_PLUSX(frei) |
0450:             SHIFT_MINUSX(frei) |
0451:             SHIFT_PLUSY(frei) |
0452:             SHIFT_MINUSY(frei);
0453:         if ((SHIFT_PLUSZ(frei) | kreuz | SHIFT_MINUSZ(kreuz) | SHIFT_MINUS2Z(frei))
0454:             != 077777777777777777777) {
0455:             return false;
0456:         }
0457: 
0458:         return true;
0459:     }
0460: 
0461:     /**

0462:      * Füllt 'alleVarianten'.

0463:      */
0464:     void berechneAlleVarianten(Stein *stein) {
0465:         XYZ koords[7];
0466:         getKoords(stein->basisform, koords);
0467: 
0468:         // Alle rotierten Versionen erzeugen

0469:         int64 alleRotiertenVersionen[24];
0470:         int nRotierteVersionen = 0;
0471:         for (int orientierung=0; orientierung<24; orientierung++) {
0472:             XYZ koordsNeu[7];
0473:             rotiere(koords, koordsNeu, orientierung);
0474:             verschiebeNachNull(koordsNeu);
0475:             int64 rotiert = getBits(koordsNeu);
0476:             if (isGueltig(koordsNeu)) {
0477:                 bool istNeu = true;
0478:                 for (int i=0; i<nRotierteVersionen; i++) {
0479:                     if (alleRotiertenVersionen[i] == rotiert) {
0480:                         istNeu = false;
0481:                         break;
0482:                     }
0483:                 }
0484:                 if (istNeu) {
0485:                     alleRotiertenVersionen[nRotierteVersionen++] = rotiert;
0486:                 }
0487:             }
0488:         }
0489: 
0490:         int nAlle = 0;
0491: 
0492:         for (int i=0; i<nRotierteVersionen; i++) {
0493:             int64 basisVersion = alleRotiertenVersionen[i];
0494:             XYZ koordsVersion[7];
0495:             getKoords(basisVersion, koordsVersion);
0496:             int xSchritte = 4 - xAusdehnung(koordsVersion);
0497:             int ySchritte = 5 - yAusdehnung(koordsVersion);
0498:             int zSchritte = 6 - zAusdehnung(koordsVersion);
0499:             for (int z=0; z<zSchritte; z++) {
0500:                 for (int y=0; y<ySchritte; y++) {
0501:                     for (int x=0; x<xSchritte; x++) {
0502:                         int64 verschoben = 
0503:                             verschiebeBits(basisVersion, x, y, z);
0504:                         stein->alleVarianten[nAlle++] = verschoben;
0505:                     }
0506:                 }
0507:             }
0508:         }
0509:     }
0510: 
0511: 
0512:     bool gesundheitTesten(int verbrauchsMaske, int64 belegung) {
0513:         int64 belegbar = 0;
0514:         for (int i=0, sMaske=1; i<10; i++, sMaske=sMaske<<1) {
0515:             if ((verbrauchsMaske & sMaske) == 0) {
0516:                 int64 variante;
0517:                 int64 *varp;
0518:                 for (varp=steine[i].alleVarianten; (variante=*varp)!=0; varp++) {
0519:                     if ((belegung & variante) == 0) {
0520:                         belegbar |= variante;
0521:                     }
0522:                 }
0523:             }
0524:         }
0525:         return ((belegbar | belegung) == (int64) 077777777777777777777);
0526:     }
0527: 
0528:     /**

0529:      * Füllt 'alleVarianten', behält dabei von den 

0530:      * je 4 symmetrischen Varianten die, die am weitesten 

0531:      * "vorne" liegt.

0532:      */
0533:     void berechneSymmetrieVarianten(Stein *stein) {
0534:         XYZ koords[7];
0535:         getKoords(stein->basisform, koords);
0536: 
0537:         // Alle rotierten Versionen erzeugen

0538:         int64 alleRotiertenVersionen[24];
0539:         int nRotierteVersionen = 0;
0540:         for (int orientierung=0; orientierung<24; orientierung+=4) {
0541:             XYZ koordsNeu[7];
0542:             rotiere(koords, koordsNeu, orientierung);
0543:             verschiebeNachNull(koordsNeu);
0544:             int64 rotiert = getBits(koordsNeu);
0545:             if (isGueltig(koordsNeu)) {
0546:                 bool istNeu = true;
0547:                 for (int i=0; i<nRotierteVersionen; i++) {
0548:                     if (alleRotiertenVersionen[i] == rotiert) {
0549:                         istNeu = false;
0550:                         break;
0551:                     }
0552:                 }
0553:                 if (istNeu) {
0554:                     alleRotiertenVersionen[nRotierteVersionen++] = rotiert;
0555:                 }
0556:             }
0557:         }
0558: 
0559:         int nAlle = 0;
0560:         for (int i=0; i<nRotierteVersionen; i++) {
0561:             int64 basisVersion = alleRotiertenVersionen[i];
0562:             XYZ koordsVersion[7];
0563:             getKoords(basisVersion, koordsVersion);
0564:             int xSchritte = 4 - xAusdehnung(koordsVersion);
0565:             int ySchritte = 5 - yAusdehnung(koordsVersion);
0566:             int zSchritte = 6 - zAusdehnung(koordsVersion);
0567:             for (int z=0; z<zSchritte; z++) {
0568:                 for (int y=0; y<ySchritte; y++) {
0569:                     for (int x=0; x<xSchritte; x++) {
0570:                         int64 verschoben1 = 
0571:                             verschiebeBits(basisVersion, x, y, z);
0572:                         int startbit1 = getStartPos(verschoben1);
0573:                         int64 verschoben2 = rotiereBits(verschoben1, 1);
0574:                         int startbit2 = getStartPos(verschoben2);
0575:                         int64 verschoben3 = rotiereBits(verschoben1, 2);
0576:                         int startbit3 = getStartPos(verschoben3);
0577:                         int64 verschoben4 = rotiereBits(verschoben1, 3);
0578:                         int startbit4 = getStartPos(verschoben4);
0579: 
0580: 
0581:                         int64 kandidat = verschoben1;
0582:                         int kleinstePos = startbit1;
0583:                         if (startbit2 < kleinstePos) {
0584:                             kandidat = verschoben2;
0585:                             kleinstePos = startbit2;
0586:                         }
0587:                         if (startbit3 < kleinstePos) {
0588:                             kandidat = verschoben3;
0589:                             kleinstePos = startbit3;
0590:                         }
0591:                         if (startbit4 < kleinstePos) {
0592:                             kandidat = verschoben4;
0593:                             kleinstePos = startbit4;
0594:                         }
0595: 
0596:                         stein->alleVarianten[nAlle++] = kandidat;
0597:                     }
0598:                 }
0599:             }
0600:         }
0601:     }
0602: 
0603:     int64 listeA[145];
0604:     int64 listeB[145];
0605:     int64 listeC[145];
0606:     int64 listeD[145];
0607:     int64 listeE[145];
0608:     int64 listeF[145];
0609:     int64 listeG[145];
0610:     int64 listeI[145];
0611:     int64 listeJ[145];
0612:     int64 listeK[145];
0613:     int64 listeM[145];
0614: 
0615: 
0616:     /**

0617:      * Baut aus 'alleVarianten' die verschiedenen sortierten Arrays.

0618:      *

0619:      * 'variantenEndspiel' enthält alle, die für das Endspiel passen.

0620:      *

0621:      * 'relVarianten[ebene][pos_in_ebene] enthält die, die bei der Suche

0622:      * an der Stelle [ebene][pos_in_ebene] in Frage kommen. 

0623:      * Die Reihenfolge im Array ist so organisiert, dass für alle möglichen

0624:      * Belegungen der 4 Nachbarplätze ein zusammenhängender Ausschnitt

0625:      * des Arrays die passenden Varianten ergibt.

0626:      */
0627:     void sortiereVarianten(Stein *stein) {
0628:         int nEndspiel = 0;
0629:         for (int64 *p=stein->alleVarianten; *p!=0; p++) {
0630:             int64 variante = *p;
0631:             if ((variante & HAUPTSPIEL_MASKE) == 0) {
0632:                 stein->variantenEndspiel[nEndspiel++] = variante;
0633:             }
0634:         }
0635:         stein->variantenEndspiel[nEndspiel] = 0;
0636: 
0637:         int maxIndex = 0;
0638: 
0639:         for (int ebene=0; ebene<SUCH_EBENEN; ebene++) {
0640:             int64 nullMaske = 0xffffffffffff >> (12 * (4 - ebene));
0641:             for (int relpos=0; relpos<12; relpos++) {
0642:                 int64 nonNullMaske = ((int64) 1) << (12 * ebene + relpos);
0643:                 int nA=0, nB=0, nC=0, nD=0, nE=0, nF=0, nG=0, nI=0, nJ=0, nK=0, nM=0;
0644: 
0645:                 for (int64 *p2=stein->alleVarianten; *p2!=0; p2++) {
0646:                     int64 variante = *p2;
0647:                     if (((variante & nonNullMaske) != 0) &&
0648:                         ((variante & nullMaske) == 0)) {
0649:                         int64 relVariante = variante >> (12 * ebene);
0650:                         int32 schnitt = relVariante & 0xfff;
0651:                         int32 pattern = (schnitt & NACHBARN[relpos]) << (11 - relpos);
0652:                         switch (pattern) {
0653:                         case 0x0000:
0654:                             listeA[nA++] = relVariante;
0655:                             break;
0656:                         case 0x0100:
0657:                             listeB[nB++] = relVariante;
0658:                             break;
0659:                         case 0x0400:
0660:                             listeC[nC++] = relVariante;
0661:                             break;
0662:                         case 0x0500:
0663:                             listeD[nD++] = relVariante;
0664:                             break;
0665:                         case 0x1000:
0666:                             listeE[nE++] = relVariante;
0667:                             break;
0668:                         case 0x1100:
0669:                             listeF[nF++] = relVariante;
0670:                             break;
0671:                         case 0x1400:
0672:                             listeG[nG++] = relVariante;
0673:                             break;
0674:                         case 0x4000:
0675:                             listeI[nI++] = relVariante;
0676:                             break;
0677:                         case 0x4100:
0678:                             listeJ[nJ++] = relVariante;
0679:                             break;
0680:                         case 0x4400:
0681:                             listeK[nK++] = relVariante;
0682:                             break;
0683:                         case 0x5000:
0684:                             listeM[nM++] = relVariante;
0685:                             break;
0686:                         case 0x1500:
0687:                         case 0x4500:
0688:                         case 0x5100:
0689:                         case 0x5400:
0690:                         case 0x5500:
0691:                             // Diese Patterns brauchen nicht indiziert zu werden!

0692:                             // Wegen Hotspot-Reihenfolge werden sie nie an dieser 

0693:                             // Startposition auftreten.

0694:                             break;
0695:                         default:
0696:                             printf("Logikfehler bei Stein %07x%08x, Ebene %d, Pos %d:\n",
0697:                                    (int32) (stein->basisform >> 32),
0698:                                    (int32) stein->basisform,
0699:                                    ebene, relpos);
0700:                             printf("   Variante %07x%08x ergibt %04x\n",
0701:                                    (int32) (relVariante >> 32),
0702:                                    (int32) relVariante,
0703:                                    pattern);
0704:                             exit(1);
0705:                         }
0706:                     }
0707:                 }
0708:                 int64 *pl = stein->relVarianten[ebene][relpos];
0709:                 int index = 0;
0710:                 short *ps = stein->schluessel[ebene][relpos];
0711:                 *ps++ = index;
0712: 
0713:                 memcpy(&pl[index], listeD, nD * sizeof(int64));
0714:                 index += nD;
0715:                 *ps++ = index;
0716: 
0717:                 memcpy(&pl[index], listeB, nB * sizeof(int64));
0718:                 index += nB;
0719:                 *ps++ = index;
0720: 
0721:                 memcpy(&pl[index], listeA, nA * sizeof(int64));
0722:                 index += nA;
0723:                 *ps++ = index;
0724: 
0725:                 memcpy(&pl[index], listeC, nC * sizeof(int64));
0726:                 index += nC;
0727:                 *ps++ = index;
0728: 
0729:                 memcpy(&pl[index], listeG, nG * sizeof(int64));
0730:                 index += nG;
0731:                 *ps++ = index;
0732: 
0733:                 memcpy(&pl[index], listeE, nE * sizeof(int64));
0734:                 index += nE;
0735:                 *ps++ = index;
0736:                 
0737:                 memcpy(&pl[index], listeA, nA * sizeof(int64));
0738:                 index += nA;
0739:                 *ps++ = index;
0740: 
0741:                 memcpy(&pl[index], listeF, nF * sizeof(int64));
0742:                 index += nF;
0743:                 *ps++ = index;
0744: 
0745:                 memcpy(&pl[index], listeB, nB * sizeof(int64));
0746:                 index += nB;
0747:                 *ps++ = index;
0748: 
0749:                 memcpy(&pl[index], listeJ, nJ * sizeof(int64));
0750:                 index += nJ;
0751:                 *ps++ = index;
0752: 
0753:                 memcpy(&pl[index], listeI, nI * sizeof(int64));
0754:                 index += nI;
0755:                 *ps++ = index;
0756: 
0757:                 memcpy(&pl[index], listeA, nA * sizeof(int64));
0758:                 index += nA;
0759:                 *ps++ = index;
0760: 
0761:                 memcpy(&pl[index], listeC, nC * sizeof(int64));
0762:                 index += nC;
0763:                 *ps++ = index;
0764: 
0765:                 memcpy(&pl[index], listeK, nK * sizeof(int64));
0766:                 index += nK;
0767:                 *ps++ = index;
0768: 
0769:                 memcpy(&pl[index], listeA, nA * sizeof(int64));
0770:                 index += nA;
0771:                 *ps++ = index;
0772: 
0773:                 memcpy(&pl[index], listeE, nE * sizeof(int64));
0774:                 index += nE;
0775:                 *ps++ = index;
0776: 
0777:                 memcpy(&pl[index], listeI, nI * sizeof(int64));
0778:                 index += nI;
0779:                 *ps++ = index;
0780: 
0781:                 memcpy(&pl[index], listeM, nM * sizeof(int64));
0782:                 index += nM;
0783:                 *ps++ = index;
0784: 
0785:                 if (index > maxIndex) maxIndex = index;
0786:             }
0787:         }
0788:     }
0789: 
0790: 
0791:     /**

0792:      * Bits im Wort zählen ohne die eigentlich naheliegende Schleife.

0793:      */
0794:     int zaehleShortBits(int zahl) {
0795:         zahl = zahl - ((zahl >> 1) & 0x5555);
0796:         zahl = (zahl & 0x3333) + ((zahl >> 2) & 0x3333);
0797:         zahl = (zahl & 0x0f0f) + ((zahl >> 4) & 0x0f0f);
0798:         return (zahl & 0x00ff) + ((zahl >> 8) & 0x00ff);
0799:     }
0800: 
0801: 
0802:     /**

0803:      * Stein initialisieren.

0804:      */
0805:     void initStein(Stein *stein, int64 basisform, bool symmetrieFilter) {
0806:         memset(stein, 0, sizeof(stein));
0807:         stein->basisform = basisform;
0808:         if (symmetrieFilter) {
0809:             berechneSymmetrieVarianten(stein);
0810:         }
0811:         else {
0812:             berechneAlleVarianten(stein);
0813:         }
0814:         sortiereVarianten(stein);
0815:     }
0816: 
0817: 
0818:     /**

0819:      * Kopiert den Stein von QUELLE nach ZIEL, löscht dabei aber 

0820:      * alle Varianten, die mit BELEGT kollidieren.

0821:      * Das im Betrieb irrelevante Feld 'variantenEndspiel' bleibt leer.

0822:      */
0823:     void steinFiltern(Stein *ziel, Stein *quelle, int64 belegt)
0824:     {
0825:         ziel->basisform = quelle->basisform;
0826:         ziel->variantenEndspiel[0] = 0;
0827: 
0828:         int nAlle = 0;
0829:         for (int64 *pa=quelle->alleVarianten; *pa!=0; pa++) {
0830:             int64 variante = *pa;
0831:             if ((variante & belegt) == 0) {
0832:                 ziel->alleVarianten[nAlle++] = variante;
0833:             }
0834:         }
0835:         ziel->alleVarianten[nAlle] = 0;
0836: 
0837:         for (int e=0; e<SUCH_EBENEN; e++) {
0838:             int64 relBelegt = belegt >> (12 * e);
0839:             for (int pos=0; pos<12; pos++) {
0840:                 int iq=0;
0841:                 int iz=0;
0842:                 for (int is=0; is<=18; is++) {
0843:                     int schl=quelle->schluessel[e][pos][is];
0844:                     while (iq < schl) {
0845:                         int64 variante = quelle->relVarianten[e][pos][iq++];
0846:                         if ((variante & relBelegt) == 0) {
0847:                             ziel->relVarianten[e][pos][iz++] = variante;
0848:                         }
0849:                     }
0850:                     ziel->schluessel[e][pos][is] = iz;
0851:                 }
0852:             }
0853:         }
0854:     }
0855: 
0856:     /**

0857:      * Die 12 Steine des Puzzles in individueller Reihenfolge

0858:      */
0859:     void initSteine(void) {
0860:         initStein(&basisSteine[0],  020013, false);
0861:         initStein(&basisSteine[1],  010033, false);
0862:         initStein(&basisSteine[2],    0472, false);
0863:         initStein(&basisSteine[3],    0323, false);
0864:         initStein(&basisSteine[4],    0326, false);
0865:         initStein(&basisSteine[5],   01113, false);
0866:         initStein(&basisSteine[6],   02322, false);
0867:         initStein(&basisSteine[7],    0722, false);
0868:         initStein(&basisSteine[8],    0133, false);
0869:         initStein(&basisSteine[9],    0136, false);
0870:         initStein(&basisSteine[10],  02323, true);
0871:         initStein(&basisSteine[11],   0272, false);
0872:     }
0873: 
0874: 
0875:     /**

0876:      * Initialisierung von 'reihenfolge'.

0877:      */
0878:     void initReihenfolge(void) {
0879:         for (int i=0; i<60; i++) {
0880:             reihenfolge[i] = ((int64) 1) << BIT_REIHE_INV_RINGE[i];
0881:         }
0882:     }
0883: 
0884: 
0885:     /**

0886:      * Hotspot-Datenstruktur initialisieren...

0887:      */
0888:     void initHotspot(short hotspotSchluessel[4096][4], int nBits) {
0889: 
0890:         // Für alle 4096 Belegungen einer 3*4-Ebene...

0891:         for (int pat=0; pat<0x1000; pat++) {
0892:             int frei = 0xfff - pat;
0893:             int hotspot = -1;
0894:             int nHotspot = 999999;
0895: 
0896:             // Welche Lücke hat die wenigsten Nachbarn?

0897:             // Das ist der Hotspot dieser Belegung

0898:             for (int p=0, maske=1; p<nBits; p++, maske<<=1) {
0899:                 if ((frei & maske) != 0) {
0900:                     int n = zaehleShortBits(frei & NACHBARN[p]);
0901:                     if (n < nHotspot) {
0902:                         nHotspot = n;
0903:                         hotspot = p;
0904:                     }
0905:                 }
0906:             }
0907:             hotspotSchluessel[pat][0] = hotspot;
0908: 
0909:             //

0910:             // Schlüssel ablegen, damit die Suche die "richtige" Teilmenge

0911:             // der 'relVarianten' findet.

0912:             // Das implementierte Verfahren liefert der Suche eine vorgefilterte

0913:             // Teilmenge, die mit den 4 Nachbarn garantiert kollisionsfrei ist.

0914:             //

0915: 
0916:             // Konfiguration der maximal 4 Nachbarn um den Hotspot:

0917:             // Es gibt davon 16 Stück, benannt A (0000) bis P (1111).

0918:             // Einige entfallen, weil ein Hotspot nie im Leeren steht.

0919:             // (Der Hotspot steht durch Shiften an Bitposition 0x800)

0920:             int32 konfig = ((~pat) & NACHBARN[hotspot]) << (11 - hotspot);
0921: 
0922:             // Welche Steine-Varianten passen?

0923:             // Variantengruppen heißen je nach Belegung der Nachbarn

0924:             // auch A bis P.

0925:             // Varianten A passen immer,

0926:             // Varianten B bei Konfiguration B, D, F, J

0927:             // usw.

0928:             // Stein trägt in 'relVarianten' eine Variantenliste 

0929:             // laut String DBACGEAFBJIACKAEIM.

0930:             // Welcher Ausschnitt (Start- und End-Index) aus DBACGEAFBJIACKAEIM ?

0931:             switch (konfig) {
0932:             case 0x0000:    // Konfig A braucht A

0933:                 hotspotSchluessel[pat][1] = 2;
0934:                 hotspotSchluessel[pat][2] = 3;
0935:                 break;
0936:             case 0x0100:    // B braucht AB

0937:                 hotspotSchluessel[pat][1] = 1;
0938:                 hotspotSchluessel[pat][2] = 3;
0939:                 break;
0940:             case 0x0400:    // C braucht AC

0941:                 hotspotSchluessel[pat][1] = 2;
0942:                 hotspotSchluessel[pat][2] = 4;
0943:                 break;
0944:             case 0x0500:    // D braucht ABCD

0945:                 hotspotSchluessel[pat][1] = 0;
0946:                 hotspotSchluessel[pat][2] = 4;
0947:                 break;
0948:             case 0x1000:    // E braucht AE

0949:                 hotspotSchluessel[pat][1] = 5;
0950:                 hotspotSchluessel[pat][2] = 7;
0951:                 break;
0952:             case 0x1100:    // F braucht ABEF

0953:                 hotspotSchluessel[pat][1] = 5;
0954:                 hotspotSchluessel[pat][2] = 9;
0955:                 break;
0956:             case 0x1400:    // G braucht ACEG

0957:                 hotspotSchluessel[pat][1] = 2;
0958:                 hotspotSchluessel[pat][2] = 5;
0959:                 break;
0960:             case 0x4000:    // I braucht AI

0961:                 hotspotSchluessel[pat][1] = 10;
0962:                 hotspotSchluessel[pat][2] = 12;
0963:                 break;
0964:             case 0x4100:    // J braucht ABIJ

0965:                 hotspotSchluessel[pat][1] = 8;
0966:                 hotspotSchluessel[pat][2] = 12;
0967:                 break;
0968:             case 0x4400:    // K braucht ACIK

0969:                 hotspotSchluessel[pat][1] = 10;
0970:                 hotspotSchluessel[pat][2] = 14;
0971:                 break;
0972:             case 0x5000:    // M braucht AEIM

0973:                 hotspotSchluessel[pat][1] = 14;
0974:                 hotspotSchluessel[pat][2] = 18;
0975:                 break;
0976: 
0977:             default:
0978:                 printf("Logikfehler: Bild %03x, Pos %d ergibt %04x\n",
0979:                        pat, hotspot, konfig);
0980:                 exit(1);
0981:             }
0982:         }
0983:     }
0984: 
0985:     /**

0986:      * Nullen der Endspiel-Daten.

0987:      */
0988:     void initEndspiele(void) {
0989:         memset(endspiele, 0, sizeof(endspiele));
0990:         memset(extender, 0, sizeof(extender));
0991:     }
0992: 
0993: 
0994:     /**

0995:      * Notiert das Komplement einer vorwärts gefundenen 

0996:      * Steine-Konfiguration als Endspiel-Lösung.

0997:      * @param verbrauch Verbrauch aus Vorwärts-Suche

0998:      * @param belegung Belegung aus Vorwärts-Suche

0999:      */
1000:     void merkeEndspiel(int16 verbrauch, int64 belegung) {
1001:         int32 index = ((~belegung) >> 36) & 0xffffff;
1002:         int16 muster = 
1003:             ((~verbrauch) & 0x3ff) + 
1004:             (((~belegung) & ENDSPIEL_RESTMASKE) >> 20);
1005:         int i;
1006:         EndspielExtender **quelle = &endspiele[index];
1007:         EndspielExtender *ex = *quelle;
1008:         // Bis zum letzten Extender in der Kette springen

1009:         for ( ; ex!=NULL; ex=ex->next) {
1010:             for (int i=0; i<7; i++) {
1011:                 if (ex->loesungen[i].muster == muster) {
1012:                     ex->loesungen[i].nloesungen++;
1013:                     return;
1014:                 }
1015:                 if (ex->loesungen[i].nloesungen == 0) {
1016:                     ex->loesungen[i].muster = muster;
1017:                     ex->loesungen[i].nloesungen = 1;
1018:                     return;
1019:                 }
1020:             }
1021:             quelle = &ex->next;
1022:         }
1023: 
1024:         // Neuen Extender anhängen

1025:         ex = &extender[nExtender++];
1026:         *quelle = ex;
1027:         ex->loesungen[0].muster = muster;
1028:         ex->loesungen[0].nloesungen = 1;
1029: 
1030:         if (nExtender >= EXTENDER_SIZE) {
1031:             printf("Groesse des EndspielExtenders reicht nicht.\n");
1032:         }
1033:     }
1034: 
1035: 
1036:     /**

1037:      * Rekursives Füllen des Endspiel-Speichers. Geht über die Steine

1038:      * und nicht über die Positionen. Auf jeder Aufruf-Ebene wird ein

1039:      * Stein in jeder erlaubten Lage gesetzt oder auch gar nicht gesetzt.

1040:      * 

1041:      * @param steinNum Nummer des Steins

1042:      * @param verbrauchsMaske Bitmaske der bislang verbrauchten Steine

1043:      * @param belegung Bitmaske der bisher belegten Positionen

1044:      */
1045:     void suchenEndspielInvers(int steinNum,
1046:                               int16 verbrauchsMaske,
1047:                               int64 belegung) {
1048:         if (steinNum >= 10) {
1049:             merkeEndspiel(verbrauchsMaske, belegung);
1050:             return;
1051:         }
1052: 
1053:         int nextNum = steinNum + 1;
1054:         int nextVm = verbrauchsMaske | (1<<steinNum);
1055:         int64 *varp = basisSteine[steinNum].variantenEndspiel;
1056:         int64 steinForm;
1057:         while ((steinForm = *varp++) != 0) {
1058:             if ((steinForm & belegung) == 0) {
1059:                 int64 belNeu = belegung | steinForm;
1060:                 if (isGesund2(belNeu)) {
1061:                     suchenEndspielInvers(nextNum, nextVm, belNeu);
1062:                 }
1063:             }
1064:         }
1065:         suchenEndspielInvers(nextNum, verbrauchsMaske, belegung);
1066:     }
1067: 
1068: 
1069:     /**

1070:      * Vor-Initialisieren der Endspielvarianten .

1071:      */
1072:     void initMoeglichkeitenMitInverserSuche(void) {
1073:         initEndspiele();
1074:         suchenEndspielInvers(0, 0, 0);
1075: 
1076:         printf("Circa %d Endspiele vorberechnet.\n", nExtender);
1077:     }
1078: 
1079: 
1080:     /**

1081:      * Sucht eine gegebene Konfiguration im Endspiel-Speicher.

1082:      * @param verbrauchsMaske Verbrauch bisher

1083:      * @param belegung Belegung, 24 Bit geshiftet, wie für Ebene2.

1084:      */
1085:     inline void suchenE(int verbrauchsMaske, int64 belegung) {
1086: 
1087: #ifdef ZAEHLEN
1088:         nEndspiele++;
1089: #endif

1090: 
1091:         int32 index = (int32)(belegung >> 12) & 0xffffff;
1092:         int16 muster = 
1093:             ((belegung << 4) & (ENDSPIEL_RESTMASKE >> 20)) | 
1094:             (verbrauchsMaske & 0x3ff);
1095: 
1096:         EndspielExtender *exp = endspiele[index];
1097:         for ( ; exp!=NULL; exp=exp->next) {
1098:             for (int i=0; i<7; i++) {
1099:                 if (exp->loesungen[i].muster == muster) {
1100:                     nLoesungen += exp->loesungen[i].nloesungen;
1101:                     return;
1102:                 }
1103:                 if (exp->loesungen[i].nloesungen == 0) {
1104:                     return;
1105:                 }
1106:             }
1107:         }
1108:     }        
1109: 
1110:     /**

1111:      * Rekursives Suchen auf Ebene 2.

1112:      * @param verbrauchsMaske Bitmaske der bislang verbrauchten Steine

1113:      * @param belegung Bitmaske der bisher belegten Positionen,

1114:      *                 um 24 Bit abwärts geshiftet

1115:      */
1116:     void suchen2(int verbrauchsMaske, int64 belegung) {
1117:         if (!isGesund(belegung)) {
1118:             return;
1119:         }
1120:         int schnitt = ((int32) belegung) & 0xfff;
1121:         int relpos = hotspotSchluesselE2[schnitt][0];
1122:         if (relpos < 0) {
1123:             suchenE(verbrauchsMaske, belegung);
1124:             return;
1125:         }
1126: 
1127:         int sStart = hotspotSchluesselE2[schnitt][1];
1128:         int sEnde = hotspotSchluesselE2[schnitt][2];
1129:         int i;
1130:         int sMaske;
1131: 
1132:         // ACHTUNG: Stein 0 muss immer vorab gesetzt sein!

1133:         for (i=0, sMaske=1; i<10; i++, sMaske=sMaske<<1) {
1134:             if ((verbrauchsMaske & sMaske) == 0) {
1135:                 int vmNeu = verbrauchsMaske | sMaske;
1136: 
1137:                 int64 *varp = steine[i].relVarianten[2][relpos];
1138:                 int start = steine[i].schluessel[2][relpos][sStart];
1139:                 int ende = steine[i].schluessel[2][relpos][sEnde];
1140: 
1141: #ifdef ZAEHLEN
1142:                 nVersuche += (ende - start);
1143: #endif

1144: 
1145:                 for (int j=start; j<ende; j++) 
1146:                 {
1147:                     int64 variante = varp[j];
1148:                     if ((belegung & variante) == 0) {
1149: #ifdef ZAEHLEN
1150:                         nSuchvorgaenge++;
1151: #endif

1152:                         int64 belNeu = belegung | variante;
1153: 
1154:                         suchen2(vmNeu, belNeu);
1155:                     }
1156:                 }
1157:             }
1158:         }
1159:     }
1160: 
1161:     /**

1162:      * Rekursives Suchen auf Ebene 1.

1163:      * 

1164:      * @param verbrauchsMaske Bitmaske der bislang verbrauchten Steine

1165:      * @param belegung Bitmaske der bisher belegten Positionen,

1166:      *                 um 12 Bit abwärts geshiftet.

1167:      */
1168:     void suchen1(int verbrauchsMaske, int64 belegung) {
1169:         if (!isGesund(belegung)) {
1170:             return;
1171:         }
1172:         int schnitt = ((int32) belegung) & 0xfff;
1173:         int relpos = hotspotSchluessel[schnitt][0];
1174:         if (relpos < 0) {
1175:             suchen2(verbrauchsMaske, (belegung >> 12) | (int64) 0xfff000000000000);
1176:             return;
1177:         }
1178: 
1179:         int sStart = hotspotSchluessel[schnitt][1];
1180:         int sEnde = hotspotSchluessel[schnitt][2];
1181:         int i;
1182:         int sMaske;
1183: 
1184:         // ACHTUNG: Stein 0 muss immer vorab gesetzt sein!

1185:         for (i=0, sMaske=1; i<10; i++, sMaske=sMaske<<1) {
1186:             if ((verbrauchsMaske & sMaske) == 0) {
1187:                 int vmNeu = verbrauchsMaske | sMaske;
1188: 
1189:                 int64 *varp = steine[i].relVarianten[1][relpos];
1190:                 int start = steine[i].schluessel[1][relpos][sStart];
1191:                 int ende = steine[i].schluessel[1][relpos][sEnde];
1192: 
1193: #ifdef ZAEHLEN
1194:                 nVersuche += (ende - start);
1195: #endif

1196: 
1197:                 for (int j=start; j<ende; j++) 
1198:                 {
1199:                     int64 variante = varp[j];
1200:                     if ((belegung & variante) == 0) {
1201: #ifdef ZAEHLEN
1202:                         nSuchvorgaenge++;
1203: #endif

1204:                         int64 belNeu = belegung | variante;
1205: 
1206:                         suchen1(vmNeu, belNeu);
1207:                     }
1208:                 }
1209:             }
1210:         }
1211:     }
1212: 
1213:     /**

1214:      * Rekursives Suchen auf Ebene 0.

1215:      * 

1216:      * @param verbrauchsMaske Bitmaske der bislang verbrauchten Steine

1217:      * @param belegung Bitmaske der bisher belegten Positionen

1218:      */
1219:     void suchen0(int verbrauchsMaske, int64 belegung) {
1220:         if (!isGesund(belegung)) {
1221:             return;
1222:         }
1223:         int schnitt = ((int32) belegung) & 0xfff;
1224:         int relpos = hotspotSchluessel[schnitt][0];
1225:         if (relpos < 0) {
1226:             suchen1(verbrauchsMaske, (belegung >> 12) | (int64) 0xfff000000000000);
1227:             return;
1228:         }
1229: 
1230:         int sStart = hotspotSchluessel[schnitt][1];
1231:         int sEnde = hotspotSchluessel[schnitt][2];
1232:         int i;
1233:         int sMaske;
1234: 
1235: 
1236:         // ACHTUNG: Stein 0 muss immer vorab gesetzt sein!

1237:         for (i=0, sMaske=1; i<10; i++, sMaske=sMaske<<1) {
1238:             if ((verbrauchsMaske & sMaske) == 0) {
1239:                 int vmNeu = verbrauchsMaske | sMaske;
1240: 
1241:                 int64 *varp = steine[i].relVarianten[0][relpos];
1242:                 int start = steine[i].schluessel[0][relpos][sStart];
1243:                 int ende = steine[i].schluessel[0][relpos][sEnde];
1244: 
1245: #ifdef ZAEHLEN
1246:                 nVersuche += (ende - start);
1247: #endif

1248: 
1249:                 for (int j=start; j<ende; j++) {
1250:                     int64 variante = varp[j];
1251:                     if ((belegung & variante) == 0) {
1252: 
1253: #ifdef ZAEHLEN
1254:                         nSuchvorgaenge++;
1255: #endif

1256:                         int64 belNeu = belegung | variante;
1257: 
1258:                         suchen0(vmNeu, belNeu);
1259:                     }
1260:                 }
1261:             }
1262:         }
1263:     }
1264: 
1265: 
1266:     /**

1267:      * Ablauf der Suche. Steine 10 und 11 werden vorab in allen Varianten 

1268:      * gesetzt. Für alle anderen Steine gilt das ebenenweise Füllen 

1269:      * mit dynamischer Bitreihenfolge (Hotspot).

1270:      */
1271:     void suchablauf() {
1272:         start = time(NULL);
1273:         initReihenfolge();
1274:         initHotspot(hotspotSchluessel, 12);
1275:         initHotspot(hotspotSchluesselE2, ENDSPIEL_START - 24);
1276:         initSteine();
1277:         for (int j=0; j<12; j++) {
1278:             steine[j] = basisSteine[j];
1279:         }
1280:         initMoeglichkeitenMitInverserSuche();
1281: 
1282:         // Variante: Stein 0 vorab platzieren

1283:         int64 *ps0;
1284:         int64 stein0;
1285:         int i0;
1286: 
1287:         for (ps0 = basisSteine[10].alleVarianten, i0 = 1; 
1288:              (stein0=*ps0) != 0; 
1289:              ps0++, i0++) 
1290:         {
1291:             int64 *ps1;
1292:             int64 stein1;
1293:             int i1;
1294: 
1295:             for (ps1 = basisSteine[11].alleVarianten, i1 = 1; 
1296:                  (stein1=*ps1) != 0; 
1297:                  ps1++, i1++) 
1298:             {
1299:                 if ((stein1 & stein0) == 0) {
1300:                     int64 belegung = stein0 | stein1;
1301: 
1302:                     // Varianten ausfiltern, die mit den schon gesetzten

1303:                     // Steinen 10 und 11 kollidieren.

1304:                     for (int j=0; j<10; j++) {
1305:                         steinFiltern(&steine[j], &basisSteine[j], belegung);
1306:                     }
1307: 
1308:                     suchen0(0xc00, belegung);
1309:                 }
1310:             }
1311: 
1312:             time_t schritt = time(NULL);
1313: #ifdef ZAEHLEN
1314:             printf ("%2d von 56: %4d sec bei %6d Lsg. nach %5d/%5d/%5d Mio. Schritten...\n",
1315:                     i0, schritt - start, nLoesungen, 
1316:                     nSuchvorgaenge / 1000000,
1317:                     (int) (nVersuche / 1000000),
1318:                     nEndspiele / 1000000);
1319: #else

1320:             printf ("%2d von 56: %4d sec bei %6d Lsg.\n",
1321:                     i0, schritt - start, nLoesungen);
1322: #endif

1323: 
1324:         }
1325: 
1326:         time_t ende = time(NULL);
1327:         printf("%d Loesungen nach %d Sekunden.\n",
1328:                 nLoesungen, ende - start);
1329:     }
1330: 
1331: 
1332: int main(int argc, char* argv[])
1333: {
1334:     suchablauf();
1335:     return 0;
1336: }
1337: