001: /*

002:         Programm zur vollständigen Suche nach allen Möglichkeiten der

003:         Anordnung von 12 Puzzleteilen aus 4-6 Einheitswürfeln

004:         (9 Teile entsprechen dem klassischen Pentomino)

005:         zu einem Quader mit den Seitenlängen 5 x 4 x 3

006:         4/2003 von Heinz Repp

007:         mit Anregungen von diversen Beiträgen im c't-Forum

008: 

009:         Vorüberlegungen:

010:         Für den Quader werden festgelegt:

011:         .

012:         Der Quader besteht aus 60 Teilwürfeln und wird so angeordnet, daß x in

013:         Richtung der größten und z in Richtung der kleinsten Ausdehnung zeigt.

014:         Jedem Teilwürfel des Quaders wird ein Bit einer 60-Bit-Ganzzahl

015:         zugeordnet, wobei in für die Bitposition 3*(4*x+y)+z genommen wird.

016: 

017:         Um die Anzahl der zu prüfenden Möglichkeiten einzuschränken, werden

018:         folgende Ansätze verwendet:

019: 

020:         1.        Der Quader wird Würfel für Würfel gefüllt, nicht Teil für Teil.

021:                 Aus praktischen Gründen wird bei Bit 59 begonnen. Die Füllreihen-

022:                 folge ist grob von oben nach unten, von hinten nach vorne und von

023:                 rechts nach links (wenn x nach links, y nach hinten und z nach oben

024:                 zeigt):

025: 

026:         2.        Damit sollte immer der Würfel als nächstes gefüllt werden, der

027:                 die wenigsten Anlagemöglichkeiten bietet. Ein Kriterium dafür ist

028:                 die Begrenztheit des umgebenden Raumes: am wenigsten Platz ist

029:                 an den Ecken der 3-er-Kante der 3x4-Grenzfläche; das legt nahe,

030:                 zuerst in Richtung der 3-er-Seite, dann erst in Richtung der

031:                 4-er-Seite und erst zum Schluß entlang der 5-er-Seite zu gehen.

032:                 Das legt die o.g. Bitcodierung nahe. Eigentlich wäre anzunehmen,

033:                 daß das noch nicht die optimale Bitreihenfolge ist; die getesteten

034:                 Alternativen (s.u.) schneiden jedoch schlechter ab.

035: 

036:         3.        Färbt man alle Würfel des Quaders so mit einer von zwei Farben,

037:                 etwa schwarz und weiß, ein, daß benachbarten Würfel immer verschie-

038:                 denfarbig sind, entsteht ein Schachbrettmuster. Jedes Teil belegt

039:                 davon in jeder Lage immer eine bestimmte Zahl weißer und schwarzer

040:                 Teilwürfel, wobei je nach Lage die ein oder andere Farbe überwiegt,

041:                 die Differenz jedoch immer gleich bleibt und ein Charakteristikum

042:                 dieses Teils darstellt. Hier fällt auf:

043:                 - es gibt nur ein Teil mit der Differenz 0, das 4-würflige, hier 'v'

044:                 - die meisten Teile haben die Differenz 1

045:                 - es gibt nur ein Teil mit der Differenz 2, das 6-würflige, hier 'F'

046:                 - nur ein Teil hat die Differenz 3: das '+'-förmige, hier 'x'.

047:                 Da jede 3x4-Ebene gleichviel schwarze und weiße Würfel enthält, muß

048:                 das durch ein 'x' eingebrachte Ungleichgewicht bereits im Nahbereich

049:                 wieder ausgeglichen werden - damit ergeben sich deutliche

050:                 Einschränkungen für die umgebenden Teile.

051: 

052:         4.        Um symmetrische Lösungen zu eliminieren, werden von einem Teil statt

053:                 weniger Orientierungen, die sich auf jeder Stufe gleichmäßig aus-

054:                 wirken würden, von wendesymmetrischen Lagen nur jeweils eine genommen.

055:                 Wenn von Lagen vier wendesymmetrische Varianten vorliegen, lassen sich

056:                 für diese Lage bereits alle symmetrischen Lösungen eleminieren, wenn nur

057:                 eine dieser Lagen verwendet wird. Gibt es von einer Lage nur einen wende-

058:                 symmetrischen Partner, müssen Symmetrien in einer zweiten Ebene durch ein

059:                 anderes Teil ausgeschlossen werden. Da das 'x'-Teil sehr restriktiv sein

060:                 sollte, das aber nur zum Tragen kommt, wenn dieses Teil möglichst früh

061:                 gelegt wird, werden von allen 'x'-Lagen, die in vierfacher Symmetrie

062:                 vorliegen, nur die rechten hinteren verwendet. Das trifft für alle 'x'-

063:                 Lagen zu, bei denen der mittlere Würfel auf einer der beiden rechten

064:                 x-Ebenen liegt. Da die y-Dimension gerade ist, werden davon alle Lagen

065:                 mit dem x-Mittelpunkt in der hinteren Hälfte genommen. 'x'-Lagen mit

066:                 dem Mittelpunkt in der mittleren x-Ebene werden bei Wendung um die y-

067:                 oder z-Achse wieder in die gleiche Ebene projeziert. Hier ist nur die

068:                 Wendesymmetrie um die x-Achse ausschaltbar, indem nur die hinteren Lagen

069:                 verwendet werden. In jedem Fall werden die verbleibenenden 'x'-Lagen als

070:                 erstes Teil gelegt und die Rekursion damit gestartet.

071: 

072:         5.        Um die verbleibenenen Symmetrien der mittleren 'x'-Lagen zu eliminieren,

073:                 werden von einem anderen Teil nur Lagen in einer x-Hälfte verwendet.

074:                 Da der Quader eine ungerade x-Dimension hat, bieten sich dafür Teile

075:                 mit nur geraden Dimensionen an, da nur diese sich immer eindeutig einer

076:                 x-Hälfte zuordnen lassen. Um durch dieses Teil den Suchbaum effektiv zu

077:                 reduzieren, sollte das Teil mit den meisten Lagen gewählt und davon die

078:                 in der Suche früh berücksichtigten Lagen weggelassen werden. Hier bietet

079:                 sich das Teil mit den meisten Lagen überhaupt (hier als 'Q' bezeichnet)

080:                 an, das mit dem 2x2x2-Format auch nur gerade Dimensionen besitzt. Von

081:                 diesem werden für die 'x'-x-Mittellagen nur die linken Lagen berücksichtigt.

082: 

083:         6.        Da die Bits von oben her gefüllt werden, kommen für das nächste freie

084:                 Bit nur die Lagen in Betracht, die nicht mit dem zuerst gelegten 'x'

085:                 kollidieren und für die dieses Bit das höchstwertige 1-er Bit ist.

086:                 Tabellen mit für jedes Bit möglichen Lagen lassen sich bereits vor der

087:                 eigentlichen Rekursion aufstellen.

088: 

089:         7.        Jede Legereihenfolge der Teile stellt eine bestimmte Permutation der

090:                 Teile dar: wenn nur Permutionen getestet werden, werden nur Teile

091:                 betrachtet, die noch nicht verwendet wurden, damit entfällt eine

092:                 entsprechende Prüfung. Dagegen steht der Aufwand, die Permutation immer

093:                 konsistent zu halten. Da der Aufwand proportional zur Anzahl der noch

094:                 nicht gelegten Teile ist, die alternative Prüfung, ob ein Teil bereits

095:                 verwendet wurde, immer für alle Teile notwendig ist, ist ein Gewinn erst

096:                 in den tieferen Rekursionsebenen zu erwarten, er bringt trotzdem im End-

097:                 effekt eine 23% geringere Laufzeit.

098: */
099: 
100: #include <stdio.h>
101: #include <stdlib.h>
102: #include <string.h>
103: #include <ctype.h>
104: #ifdef DEBUG
105:         #include <assert.h>
106: #endif

107: 
108: #define QUADWORD __int64
109: #define QUADER_X 5
110: #define QUADER_Y 4
111: #define QUADER_Z 3
112: 
113: typedef struct {
114:         int x;
115:         int y;
116:         int z;
117: } Wuerfel_t;
118: 
119: typedef struct {
120:         int WuerfelZahl;
121:         int x;
122:         int y;
123:         int z;
124:         Wuerfel_t *Wuerfel;
125: } PuzzleTeil_t;
126: 
127: char *Beschreibung[] = {"UHRV", "LHO", "VRRH", "LLHR", "LLL2H",
128:         "VLLL", "VLLL3H", "VRV2R", "RHHR", "VRVR", "RR1HH", "RH1R1V"};
129: int Loesungen = 0, Permutation[11] = {0,1,2,3,4,5,6,7,8,9,10}/*, BitPos[60]*/;
130: PuzzleTeil_t PuzzleTeil[12];
131: QUADWORD *NaechsteLage, *PassendeLagen;
132: struct _Teil {
133:         int Anzahl;
134:         QUADWORD *Lage;
135:         struct _Verteilung {
136:                 QUADWORD *Erste;
137:                 int Anzahl;
138:         } Verteilung[63];
139: } Teil[12];
140: #ifdef DEBUG
141:         int gelegt, LastBit, LastBitMax = 0;
142:         QUADWORD Plazierungen = 0;
143: #endif

144: 
145: 
146: void errorexit (char* s)
147: {
148:         fprintf (stderr, "\n%s\n", s);
149:         exit (1);
150: }
151: 
152: 
153: /*

154:         Bitumordnung habe ich wieder herausgenommen, da ich keine bessere

155:         Reihenfolge als die 3*(4*x+y)+z gefunden habe. Setzt man deren

156:         Laufzeit auf 100% mit 1380724348 Plazierungen, so haben, wenn mit

157:         Bit 59 angefangen wird (also auch in der Ebene 11 -> 0):

158: 

159:         3  6  9 11        diagonal, nach y+z geordnet

160:         1  4  7 10

161:         0  2  5  9        102% Laufzeit und 1405040246 Plazierungen

162: 

163:         4  3  2 11        spiralförmig von außen nach innen

164:         5  0  1 10

165:         6  7  8  9        103% Laufzeit und 1399571048 Plazierungen

166: 

167:         8  2  5 11        erst Ecken, dann Mitte, von beiden Seiten

168:         6  0  3  9

169:         7  1  4 10        112% Laufzeit und 1494671690 Plazierungen

170: 

171:         Reihenfolgen aufgrund einer Ordnung nach x+y+z oder y^2+z^2 oder

172:         x^2+y^2+z^2 waren noch deutlich schlechter.

173: 

174: void OptimiereBitOrdnung (void)

175: {

176:         int x, y, z, bn, Reverse[60];

177:         int Reihenfolge[4][3] = {{0, 1, 3}, {2, 4, 6}, {5, 7, 9}, {8, 10, 11}};

178: 

179:         for (x = 0; x < 5; x++)

180:                 for (y = 0; y < 4; y++)

181:                         for (z = 0; z < 3; z++)

182:                         {

183:                                 bn = (x * 4 + y) * 3 + z;

184:                                 Reverse[bn] = x * 12 + Reihenfolge[y][z];

185:                         }

186: 

187:         for (bn = 0; bn < 60; bn++)

188:                 BitPos[Reverse[bn]] = bn;

189: #ifdef DEBUG

190:         for (bn = 60; bn--; )

191:                 printf ("%2d: %2d\t%2d\n", bn, Reverse[bn], BitPos[bn]);

192: #endif

193: }

194: */
195: 
196: 
197: int BitNr (int x, int y, int z)
198: {
199: /*        da keine Bitumordnung (s.o.),

200:         statt:

201:         return BitPos[3*(4*x+y)+z];

202:         nur:

203: */        return 3*(4*x+y)+z;
204: }
205: 
206: 
207: int VergleicheWuerfel (Wuerfel_t *w1, Wuerfel_t *w2)
208: {
209:         if (w1->z > w2->z)
210:                 return 1;
211:         else if (w1->z < w2->z)
212:                 return -1;
213:         else if (w1->y > w2->y)
214:                 return 1;
215:         else if (w1->y < w2->y)
216:                 return -1;
217:         else if (w1->x > w2->x)
218:                 return 1;
219:         else
220:                 return -1;
221: }
222: 
223: 
224: void WendeX (PuzzleTeil_t *pt)
225: {
226:         int i;
227: 
228:         for (i = 0; i < pt->WuerfelZahl; i++)
229:         {
230:                 pt->Wuerfel[i].y = pt->y - pt->Wuerfel[i].y;
231:                 pt->Wuerfel[i].z = pt->z - pt->Wuerfel[i].z;
232:         }
233: 
234:         qsort (pt->Wuerfel,
235:                pt->WuerfelZahl,
236:                sizeof (Wuerfel_t),
237:                (int (*)(const void *,const void *)) VergleicheWuerfel);
238: }
239: 
240: 
241: void WendeY (PuzzleTeil_t *pt)
242: {
243:         int i;
244: 
245:         for (i = 0; i < pt->WuerfelZahl; i++)
246:         {
247:                 pt->Wuerfel[i].x = pt->x - pt->Wuerfel[i].x;
248:                 pt->Wuerfel[i].z = pt->z - pt->Wuerfel[i].z;
249:         }
250: 
251:         qsort (pt->Wuerfel,
252:                pt->WuerfelZahl,
253:                sizeof (Wuerfel_t),
254:                (int (*)(const void *,const void *)) VergleicheWuerfel);
255: }
256: 
257: 
258: void RotiereX (PuzzleTeil_t *pt)
259: {
260:         int i, temp;
261: 
262:         for (i = 0; i < pt->WuerfelZahl; i++)
263:         {
264:                 temp = pt->Wuerfel[i].y;
265:                 pt->Wuerfel[i].y = pt->z - pt->Wuerfel[i].z;
266:                 pt->Wuerfel[i].z = temp;
267:         }
268: 
269:         temp = pt->y;
270:         pt->y = pt->z;
271:         pt->z = temp;
272: 
273:         qsort (pt->Wuerfel,
274:                pt->WuerfelZahl,
275:                sizeof (Wuerfel_t),
276:                (int (*)(const void *,const void *)) VergleicheWuerfel);
277: }
278: 
279: 
280: void RotiereY (PuzzleTeil_t *pt)
281: {
282:         int i, temp;
283: 
284:         for (i = 0; i < pt->WuerfelZahl; i++)
285:         {
286:                 temp = pt->Wuerfel[i].z;
287:                 pt->Wuerfel[i].z = pt->x - pt->Wuerfel[i].x;
288:                 pt->Wuerfel[i].x = temp;
289:         }
290: 
291:         temp = pt->z;
292:         pt->z = pt->x;
293:         pt->x = temp;
294: 
295:         qsort (pt->Wuerfel,
296:                pt->WuerfelZahl,
297:                sizeof (Wuerfel_t),
298:                (int (*)(const void *,const void *)) VergleicheWuerfel);
299: }
300: 
301: 
302: void RotiereZ (PuzzleTeil_t *pt)
303: {
304:         int i, temp;
305: 
306:         for (i = 0; i < pt->WuerfelZahl; i++)
307:         {
308:                 temp = pt->Wuerfel[i].x;
309:                 pt->Wuerfel[i].x = pt->y - pt->Wuerfel[i].y;
310:                 pt->Wuerfel[i].y = temp;
311:         }
312: 
313:         temp = pt->x;
314:         pt->x = pt->y;
315:         pt->y = temp;
316: 
317:         qsort (pt->Wuerfel,
318:                pt->WuerfelZahl,
319:                sizeof (Wuerfel_t),
320:                (int (*)(const void *,const void *)) VergleicheWuerfel);
321: }
322: 
323: 
324: /*

325:         Teile aus Teilebeschreibung: der erste Würfel ist implizit, jeder

326:         Folgewürfel hat einen Buchstaben für die Richtung, in der er am

327:         Bezugswürfel sitzt, der normalerweise der vorhergehende ist. Eine

328:         Ziffer (0-9) bestimmt einen neuen Bezugswürfel. Der implizite erste

329:         Würfel hat den Index 0, der erste beschriebene Würfel die 1. Das Teil

330:         wird so ausgerichtet, daß x >= y >= z gilt.

331: */
332: void PuzzleTeilAusString (PuzzleTeil_t *pt, char *str)
333: {
334:         char *temp;
335:         int i, x_min, x_max, y_min, y_max, z_min, z_max;
336: 
337:         i = 1;
338:         temp = str;
339:         while (temp = strpbrk(temp, "lLrRvVhHuUoO"))
340:         {
341:                 i++;
342:                 temp++;
343:         }
344:         pt->Wuerfel = malloc (i * sizeof (Wuerfel_t));
345: 
346:         pt->Wuerfel[0].x = 0;
347:         pt->Wuerfel[0].y = 0;
348:         pt->Wuerfel[0].z = 0;
349:         pt->WuerfelZahl = 1;
350:         x_min = x_max = y_min = y_max = z_min = z_max = 0;
351:         i = 0;
352: 
353:         while (*str)
354:         {
355:                 if (isdigit (*str))
356:                 {
357:                         if ((i = *str++ - '0') >= pt->WuerfelZahl)
358:                                 errorexit ("Fehler in der Teilbeschreibung");
359:                 }
360:                 else
361:                 {
362:                         pt->Wuerfel[pt->WuerfelZahl] = pt->Wuerfel[i];
363:                         i = pt->WuerfelZahl++;
364:                         switch (*str++)
365:                         {
366:                                 case 'l':
367:                                 case 'L':
368:                                         pt->Wuerfel[i].x--;
369:                                         if (x_min > pt->Wuerfel[i].x)
370:                                                 x_min = pt->Wuerfel[i].x;
371:                                         break;
372:                                 case 'r':
373:                                 case 'R':
374:                                         pt->Wuerfel[i].x++;
375:                                         if (x_max < pt->Wuerfel[i].x)
376:                                                 x_max = pt->Wuerfel[i].x;
377:                                         break;
378:                                 case 'v':
379:                                 case 'V':
380:                                         pt->Wuerfel[i].y--;
381:                                         if (y_min > pt->Wuerfel[i].y)
382:                                                 y_min = pt->Wuerfel[i].y;
383:                                         break;
384:                                 case 'h':
385:                                 case 'H':
386:                                         pt->Wuerfel[i].y++;
387:                                         if (y_max < pt->Wuerfel[i].y)
388:                                                 y_max = pt->Wuerfel[i].y;
389:                                         break;
390:                                 case 'u':
391:                                 case 'U':
392:                                         pt->Wuerfel[i].z--;
393:                                         if (z_min > pt->Wuerfel[i].z)
394:                                                 z_min = pt->Wuerfel[i].z;
395:                                         break;
396:                                 case 'o':
397:                                 case 'O':
398:                                         pt->Wuerfel[i].z++;
399:                                         if (z_max < pt->Wuerfel[i].z)
400:                                                 z_max = pt->Wuerfel[i].z;
401:                                         break;
402:                                 default:
403:                                         errorexit ("Fehler in der Teilbeschreibung");
404:                         }
405:                 }
406:         }
407:         pt->x = x_max - x_min;
408:         pt->y = y_max - y_min;
409:         pt->z = z_max - z_min;
410: 
411:         for (i = 0; i < pt->WuerfelZahl; i++)
412:         {
413:                 pt->Wuerfel[i].x -= x_min;
414:                 pt->Wuerfel[i].y -= y_min;
415:                 pt->Wuerfel[i].z -= z_min;
416:         }
417: 
418:         if (pt->x < pt->y)
419:                 if (pt->y < pt->z)
420:                         RotiereY (pt);
421:                 else
422:                         RotiereZ (pt);
423:         else if (pt->x < pt->z)
424:                 RotiereY (pt);
425: 
426:         if (pt->y < pt->z)
427:                 RotiereX (pt);
428: 
429:         qsort (pt->Wuerfel,
430:                pt->WuerfelZahl,
431:                sizeof (Wuerfel_t),
432:                (int (*)(const void *,const void *)) VergleicheWuerfel);
433: }
434: 
435: 
436: void KopiereTeil (PuzzleTeil_t *pt1, PuzzleTeil_t *pt2)
437: {
438:         *pt2 = *pt1;
439:         pt2->Wuerfel = malloc (pt1->WuerfelZahl * sizeof (Wuerfel_t));
440:         memcpy (pt2->Wuerfel, pt1->Wuerfel, pt1->WuerfelZahl * sizeof (Wuerfel_t));
441: }
442: 
443: 
444: int TeileSindGleich (PuzzleTeil_t *pt1, PuzzleTeil_t *pt2)
445: {
446:         int i;
447: 
448:         if (pt1->WuerfelZahl != pt2->WuerfelZahl ||
449:                 pt1->x != pt2->x || pt1->y != pt2->y || pt1->z != pt2->z)
450:                 return 0;
451: 
452:         for (i = 0; i < pt1->WuerfelZahl; i++)
453:                 if (pt1->Wuerfel[i].x != pt2->Wuerfel[i].x ||
454:                     pt1->Wuerfel[i].y != pt2->Wuerfel[i].y ||
455:                     pt1->Wuerfel[i].z != pt2->Wuerfel[i].z)
456:                         return 0;
457: 
458:         return 1;
459: }
460: 
461: 
462: void AlleLagenVonTeil (int nr)
463: {
464:         PuzzleTeil_t AusgangsLage[6][4];
465:         int i, w, Wendungen, r, Rotationen, x, y, z;
466: 
467:         Wendungen = Rotationen = 1;
468: 
469:         KopiereTeil (&PuzzleTeil[nr], &AusgangsLage[0][0]);
470: 
471:         /* alle 180-Grad-Wendungen - die Dimensionen bleiben gleich */
472:         KopiereTeil (&AusgangsLage[0][0], &AusgangsLage[0][1]);
473:         WendeX (&AusgangsLage[0][1]);
474: 
475:         if (TeileSindGleich (&AusgangsLage[0][0], &AusgangsLage[0][1]))
476:                 free (AusgangsLage[0][1].Wuerfel);
477:         else
478:                 Wendungen++;
479: 
480:         KopiereTeil (&AusgangsLage[0][0], &AusgangsLage[0][Wendungen]);
481:         WendeY (&AusgangsLage[0][Wendungen]);
482: 
483:         for (w = 0; w < Wendungen; w++)
484:                 if (TeileSindGleich (&AusgangsLage[0][w], &AusgangsLage[0][Wendungen]))
485:                         break;
486: 
487:         if (w < Wendungen)
488:                 free (AusgangsLage[0][Wendungen].Wuerfel);
489:         else if (Wendungen++)
490:         {
491:                 KopiereTeil (&AusgangsLage[0][1], &AusgangsLage[0][Wendungen]);
492:                 WendeY (&AusgangsLage[0][Wendungen++]);
493:         }
494: 
495:         /*        alle 90-Grad-Wendungen; die Überprüfung auf Symmetrie berücksichtigt,

496:                 daß alle PuzzleTeile so aufgebaut wurden, daß ihre Dimensionen in

497:                 der Reihenfolge x >= y >= z vorliegen. */
498:         KopiereTeil (&AusgangsLage[0][0], &AusgangsLage[Rotationen][0]);
499:         RotiereX (&AusgangsLage[Rotationen][0]);
500: 
501:         if (PuzzleTeil[nr].y == PuzzleTeil[nr].z)
502:         {
503:                 for (w = 0; w < Wendungen; w++)
504:                         if (TeileSindGleich (&AusgangsLage[Rotationen][0], &AusgangsLage[0][w]))
505:                                 break;
506:         }
507:         else
508:                 w = Wendungen;
509: 
510:         if (w < Wendungen)        // x-Rotation symmetrisch?

511:         {
512:                 free (AusgangsLage[Rotationen][0].Wuerfel);
513: 
514:                 KopiereTeil (&AusgangsLage[0][0], &AusgangsLage[Rotationen][0]);
515:                 RotiereZ (&AusgangsLage[Rotationen][0]);
516: 
517:                 if (PuzzleTeil[nr].x == PuzzleTeil[nr].y)
518:                 {
519:                         for (w = 0; w < Wendungen; w++)
520:                                 if (TeileSindGleich (&AusgangsLage[Rotationen][0], &AusgangsLage[0][w]))
521:                                         break;
522:                 }
523:                 else
524:                         w = Wendungen;
525: 
526:                 if (w < Wendungen)        // z-Rotation symmetrisch?

527:                         free (AusgangsLage[Rotationen][0].Wuerfel);
528:                 else
529:                 {
530:                         for (w = 1; w < Wendungen; w++)
531:                         {
532:                                 KopiereTeil (&AusgangsLage[0][w], &AusgangsLage[Rotationen][w]);
533:                                 RotiereZ (&AusgangsLage[Rotationen][w]);
534:                         }
535:                         Rotationen++;
536: 
537:                         for (w = 0; w < Wendungen; w++)
538:                         {
539:                                 KopiereTeil (&AusgangsLage[0][w], &AusgangsLage[Rotationen][w]);
540:                                 RotiereY (&AusgangsLage[Rotationen][w]);
541:                         }
542:                         Rotationen++;
543:                 }
544:         }
545:         else        // x-Rotation nicht symmetrisch

546:         {
547:                 for (w = 1; w < Wendungen; w++)
548:                 {
549:                         KopiereTeil (&AusgangsLage[0][w], &AusgangsLage[Rotationen][w]);
550:                         RotiereX (&AusgangsLage[Rotationen][w]);
551:                 }
552:                 Rotationen++;
553: 
554:                 KopiereTeil (&AusgangsLage[0][0], &AusgangsLage[Rotationen][0]);
555:                 RotiereZ (&AusgangsLage[Rotationen][0]);
556: 
557:                 if (PuzzleTeil[nr].x == PuzzleTeil[nr].y)
558:                 {
559:                         for (w = 0; w < Wendungen; w++)
560:                                 if (TeileSindGleich (&AusgangsLage[Rotationen][0], &AusgangsLage[0][w]))
561:                                         break;
562:                 }
563:                 else
564:                         w = Wendungen;
565: 
566:                 if (w < Wendungen)        // z-Rotation symmetrisch?

567:                 {
568:                         free (AusgangsLage[Rotationen][0].Wuerfel);
569: 
570:                         for (w = 0; w < Wendungen; w++)
571:                         {
572:                                 KopiereTeil (&AusgangsLage[0][w], &AusgangsLage[Rotationen][w]);
573:                                 RotiereY (&AusgangsLage[Rotationen][w]);
574:                         }
575:                         Rotationen++;
576:                 }
577:                 else        // z-Rotation nicht symmetrisch

578:                 {
579:                         if (PuzzleTeil[nr].x == PuzzleTeil[nr].z)
580:                         {
581:                                 for (w = 0; w < Wendungen; w++)
582:                                         if (TeileSindGleich (&AusgangsLage[Rotationen][0], &AusgangsLage[1][w]))
583:                                                 break;
584:                         }
585:                         else
586:                                 w = Wendungen;
587: 
588:                         if (w < Wendungen)        // zyklische Symmetrie?

589:                                 free (AusgangsLage[Rotationen][0].Wuerfel);
590:                         else
591:                         {
592:                                 for (w = 1; w < Wendungen; w++)
593:                                 {
594:                                         KopiereTeil (&AusgangsLage[0][w], &AusgangsLage[Rotationen][w]);
595:                                         RotiereZ (&AusgangsLage[Rotationen][w]);
596:                                 }
597:                                 Rotationen++;
598: 
599:                                 KopiereTeil (&AusgangsLage[0][0], &AusgangsLage[Rotationen][0]);
600:                                 RotiereY (&AusgangsLage[Rotationen][0]);
601: 
602:                                 if (PuzzleTeil[nr].x == PuzzleTeil[nr].z)
603:                                 {
604:                                         for (w = 0; w < Wendungen; w++)
605:                                                 if (TeileSindGleich (&AusgangsLage[Rotationen][0], &AusgangsLage[0][w]))
606:                                                         break;
607:                                 }
608:                                 else
609:                                         w = Wendungen;
610: 
611:                                 if (w < Wendungen)        // y-Rotation symmetrisch?

612:                                         free (AusgangsLage[Rotationen][0].Wuerfel);
613:                                 else
614:                                 {
615:                                         for (w = 1; w < Wendungen; w++)
616:                                         {
617:                                                 KopiereTeil (&AusgangsLage[0][w], &AusgangsLage[Rotationen][w]);
618:                                                 RotiereY (&AusgangsLage[Rotationen][w]);
619:                                         }
620:                                         Rotationen++;
621: 
622:                                         for (r = 0; r < 2; r++)
623:                                                 for (w = 0; w < Wendungen; w++)
624:                                                 {
625:                                                         KopiereTeil (&AusgangsLage[1+r][w], &AusgangsLage[Rotationen+r][w]);
626:                                                         RotiereY (&AusgangsLage[Rotationen+r][w]);
627:                                                 }
628:                                         Rotationen += 2;
629:                                 }
630:                         }
631:                 }
632:         }
633: 
634:         Teil[nr].Lage = NaechsteLage;
635:         for (r = Rotationen; r--; )
636:                 for (w = Wendungen; w--; )
637:                         for (x = QUADER_X - AusgangsLage[r][w].x; x-- > 0; )
638:                                 for (y = QUADER_Y - AusgangsLage[r][w].y; y-- > 0; )
639:                                         for (z = QUADER_Z - AusgangsLage[r][w].z; z-- > 0; )
640:                                         {
641:                                                 *NaechsteLage = 0i64;
642:                                                 for (i = AusgangsLage[r][w].WuerfelZahl; i--; )
643:                                                         *NaechsteLage |= 1i64 <<
644:                                                                 BitNr (AusgangsLage[r][w].Wuerfel[i].x + x,
645:                                                                        AusgangsLage[r][w].Wuerfel[i].y + y,
646:                                                                        AusgangsLage[r][w].Wuerfel[i].z + z);
647:                                                 NaechsteLage++;
648:                                                 Teil[nr].Anzahl++;
649:                                         }
650: #ifdef DEBUG
651: printf ("Teil %2d: %3d Lagen\n", nr, Teil[nr].Anzahl);
652: #endif

653: 
654:         for (r = 0; r < Rotationen; r++)
655:                 for (w = 0; w < Wendungen; w++)
656:                         free (AusgangsLage[r][w].Wuerfel);
657: }
658: 
659: 
660: int VergleicheQuads (QUADWORD *qw1, QUADWORD *qw2)
661: {
662:         return *qw1 > *qw2 ? 1 : -1;
663: }
664: 
665: 
666: void AlleLagenVonX (void)
667: {
668:         PuzzleTeil_t AusgangsLage[3];
669:         int i, r, x, y, z;
670: 
671:         KopiereTeil (&PuzzleTeil[11], &AusgangsLage[0]);
672: 
673:         KopiereTeil (&AusgangsLage[0], &AusgangsLage[1]);
674:         RotiereX (&AusgangsLage[1]);
675: 
676:         KopiereTeil (&AusgangsLage[0], &AusgangsLage[2]);
677:         RotiereY (&AusgangsLage[2]);
678: 
679:         /* Tabelle der Lagen mit in der gleichen x-Ebene liegenden

680:                 Mittelpunkten aufstellen; symmetrische Lösungen, die durch

681:                 Wendung des Quaders um die X-Achse entstehen, werden dadurch

682:                 eliminiert, daß von den möglichen Mittelpunktslagen mit y-

683:                 Werten zwischen 0 und 3 nur dir mit y >= 2 berücksichtigt werden.

684:                 Symmetrien durch Y-Wendung werden für die x-Mittelpunktslagen außer

685:                 2 durch Beschränkung auf x >= 3 erreicht, da die x-Ebenen 0 und 1

686:                 zu 3 und 4 symmetrisch sind; für Ebene 2 wird diese Symmetrie

687:                 dadurch eliminiert, daß nur Lösungen mit dem Teil[0] ('Q') im

688:                 Teilquader mit x >= 2 berücksichtigt werden - diese sind

689:                 symmetrisch zu 'Q'-Positionen Teilquader x <= 2.

690:                 Mittelpunktslagen 'x' in den x-Ebenen 3 und 4 kommen in

691:                 Verteilung[0], Ebene 2 in Verteilung [1] */
692:         Teil[11].Lage = Teil[11].Verteilung[0].Erste = NaechsteLage;
693:         for (r = 3; r--; )
694:                 for (x = QUADER_X - AusgangsLage[r].x; x-- > 3 - AusgangsLage[r].x / 2; )
695:                         for (y = QUADER_Y - AusgangsLage[r].y; y-- > 2 - AusgangsLage[r].y / 2; )
696:                                 for (z = QUADER_Z - AusgangsLage[r].z; z-- > 0; )
697:                                 {
698:                                         *NaechsteLage = 0i64;
699:                                         for (i = AusgangsLage[r].WuerfelZahl; i--; )
700:                                                 *NaechsteLage |= 1i64 <<
701:                                                         BitNr (AusgangsLage[r].Wuerfel[i].x + x,
702:                                                                AusgangsLage[r].Wuerfel[i].y + y,
703:                                                                AusgangsLage[r].Wuerfel[i].z + z);
704:                                         NaechsteLage++;
705:                                         Teil[11].Verteilung[0].Anzahl++;
706:                                 }
707:         Teil[11].Anzahl = Teil[11].Verteilung[0].Anzahl;
708: 
709:         Teil[11].Verteilung[1].Erste = NaechsteLage;
710:         for (r = 3; r--; )
711:         {
712:                 x = 2 - AusgangsLage[r].x / 2;
713:                 for (y = QUADER_Y - AusgangsLage[r].y; y-- > 2 - AusgangsLage[r].y / 2; )
714:                         for (z = QUADER_Z - AusgangsLage[r].z; z-- > 0; )
715:                         {
716:                                 *NaechsteLage = 0i64;
717:                                 for (i = AusgangsLage[r].WuerfelZahl; i--; )
718:                                         *NaechsteLage |= 1i64 <<
719:                                                 BitNr (AusgangsLage[r].Wuerfel[i].x + x,
720:                                                        AusgangsLage[r].Wuerfel[i].y + y,
721:                                                        AusgangsLage[r].Wuerfel[i].z + z);
722:                                 NaechsteLage++;
723:                                 Teil[11].Verteilung[1].Anzahl++;
724:                         }
725:         }
726:         Teil[11].Anzahl += Teil[11].Verteilung[1].Anzahl;
727: #ifdef DEBUG
728: printf ("Teil 11: %3d Lagen\n", Teil[11].Anzahl);
729: #endif

730: 
731:         for (r = 0; r < 3; r++)
732:                 free (AusgangsLage[r].Wuerfel);
733: 
734:         qsort (Teil[11].Verteilung[0].Erste,
735:                Teil[11].Verteilung[0].Anzahl,
736:                sizeof (QUADWORD),
737:                (int (*)(const void *,const void *)) VergleicheQuads);
738: 
739:         qsort (Teil[11].Verteilung[1].Erste,
740:                Teil[11].Verteilung[1].Anzahl,
741:                sizeof (QUADWORD),
742:                (int (*)(const void *,const void *)) VergleicheQuads);
743: 
744: }
745: 
746: 
747: void Initialisiere (void)
748: {
749:         int i;
750: /*

751:         OptimiereBitOrdnung ();

752: */
753:         for (i = 0; i < 12; i++)
754:                 PuzzleTeilAusString (&PuzzleTeil[i], Beschreibung[i]);
755: 
756:         NaechsteLage = malloc (6210 * sizeof (QUADWORD));
757: 
758:         for (i = 0; i < 11; i++)
759:         {
760:                 AlleLagenVonTeil (i);
761: 
762:                 /* Teilepositionen nach höchstwertigem Bit sortieren */
763:                 qsort (Teil[i].Lage,
764:                        Teil[i].Anzahl,
765:                        sizeof (QUADWORD),
766:                        (int (*)(const void *,const void *)) VergleicheQuads);
767:         }
768: 
769:         AlleLagenVonX ();
770: }
771: 
772: 
773: void SelektierePassendeLagen (QUADWORD Vorlage, int Anzahl,
774:         QUADWORD *AlleLagen, struct _Verteilung *Verteilung)
775: {
776:         int Bit;
777:         QUADWORD Schwelle, temp;
778: 
779:         /* Tabelle der mit gleichem Bit beginnenden Lageserien aufstellen */
780:         while (*AlleLagen & Vorlage)
781:         {
782:                 AlleLagen++;
783:                 Anzahl--;
784:         }
785:         Bit = 0;
786:         Schwelle = 2;
787:         while (Schwelle <= *AlleLagen)
788:         {
789:                 Verteilung[Bit].Erste = NULL;
790:                 Verteilung[Bit].Anzahl = 0;
791:                 Schwelle <<= 1;
792:                 Bit++;
793:         }
794:         Verteilung[Bit].Erste = PassendeLagen;
795:         *PassendeLagen++ = *AlleLagen++;
796:         Anzahl--;
797:         while (Anzahl--)
798:         {
799:                 temp = *AlleLagen++;
800:                 if (!(temp & Vorlage))
801:                 {
802:                         while (Schwelle <= temp)
803:                         {
804:                                 Verteilung[Bit].Anzahl = PassendeLagen - Verteilung[Bit].Erste;
805:                                 Verteilung[++Bit].Erste = PassendeLagen;
806:                                 Schwelle <<= 1;
807:                         }
808:                         *PassendeLagen++ = temp;
809:                 }
810:         }
811:         Verteilung[Bit].Anzahl = PassendeLagen - Verteilung[Bit].Erste;
812:         while (++Bit < 60)
813:         {
814:                 Verteilung[Bit].Erste = NULL;
815:                 Verteilung[Bit].Anzahl = 0;
816:         }
817: }
818: 
819: 
820: void LegeTeileAbBit (int Bit, QUADWORD Quader, int Teile)
821: #ifdef HIGHSPEED
822:         ;
823: #else

824: {
825:         register QUADWORD *AktLage, QuaderNeu;
826:         register int j, dran, i, BitNeu;
827: 
828:         if (Teile)
829:         {
830:                 i = --Teile;
831:                 do
832:                 {
833:                         dran = Permutation[i];
834:                         Permutation[i] = Permutation[Teile];
835: 
836:                         if (j = Teil[dran].Verteilung[Bit].Anzahl)
837:                         {
838:                                 AktLage = Teil[dran].Verteilung[Bit].Erste;
839:                                 do
840:                                 {
841:                                         if (!(*AktLage & Quader))
842:                                         {
843: #ifdef DEBUG
844:                                                 gelegt++;
845:                                                 LastBit = Bit;
846: #endif

847:                                                 QuaderNeu = Quader | *AktLage;
848:                                                 BitNeu = Bit;
849:                                                 while (QuaderNeu & (1i64 << --BitNeu));
850: 
851:                                                 LegeTeileAbBit (BitNeu, QuaderNeu, Teile);
852:                                         }
853:                                         AktLage++;
854:                                 } while (--j);
855:                         }
856:                         Permutation[i] = dran;
857:                 } while (i--);
858:                 /* Schleife mit erstem Permutationselement! */
859:         }
860:         else
861:         {
862:                 Loesungen++;
863: #ifdef DEBUG
864:                 assert (Quader == 0xFFFFFFFFFFFFFFFFi64);
865:                 printf("\r%8d", Loesungen);
866:                 if (LastBitMax < LastBit)
867:                         LastBitMax = LastBit;
868: #endif

869:         }
870: }
871: #endif

872: 
873: 
874: void LegeTeileOhneQAbBit (int Bit, QUADWORD Quader, int Teile)
875: #ifdef HIGHSPEED
876:         ;
877: #else

878: {
879:         register QUADWORD *AktLage, QuaderNeu;
880:         register int j, dran, i, BitNeu;
881: 
882:         /* Schleife ohne erstes Permutationselement! */
883:         i = Teile--;
884:         while (--i)
885:         {
886:                 dran = Permutation[i];
887:                 Permutation[i] = Permutation[Teile];
888: 
889:                 if (j = Teil[dran].Verteilung[Bit].Anzahl)
890:                 {
891:                         AktLage = Teil[dran].Verteilung[Bit].Erste;
892:                         do
893:                         {
894:                                 if (!(*AktLage & Quader))
895:                                 {
896: #ifdef DEBUG
897:                                         gelegt++;
898: #endif

899:                                         QuaderNeu = Quader | *AktLage;
900:                                         BitNeu = Bit;
901:                                         while (QuaderNeu & (1i64 << --BitNeu));
902: 
903:                                         if (BitNeu >= 36)
904:                                                 LegeTeileOhneQAbBit (BitNeu, QuaderNeu, Teile);
905:                                         else
906:                                                 LegeTeileAbBit (BitNeu, QuaderNeu, Teile);
907:                                 }
908:                                 AktLage++;
909:                         } while (--j);
910:                 }
911:                 Permutation[i] = dran;
912:         }
913: }
914: #endif

915: 
916: 
917: void StarteSucheMitLagen (struct _Verteilung *LagenSerie,
918:         void (*LegeFunktion)(int, QUADWORD, int))
919: {
920:         int i, j;
921:         QUADWORD *AktLage;
922: 
923:         AktLage = LagenSerie->Erste;
924:         j = LagenSerie->Anzahl;
925:         while (j--)
926:         {
927:                 PassendeLagen = NaechsteLage;
928:                 for (i = 0; i < 11; i++)
929:                         SelektierePassendeLagen (*AktLage,
930:                                 Teil[i].Anzahl, Teil[i].Lage, Teil[i].Verteilung);
931: 
932: #ifdef DEBUG
933:                 gelegt = 0;
934: #endif

935: 
936:                 (*LegeFunktion) (59, *AktLage++ | 0xF000000000000000i64, 11);
937: 
938: #ifdef DEBUG
939:                 Plazierungen += gelegt;
940:                 printf (", %d\n", gelegt);
941: #else

942:                 printf ("\r... schon %d L”sungen ...", Loesungen);
943: #endif

944:         }
945: }
946: 
947: 
948: int main(void)
949: {
950:         int i;
951: 
952:         Initialisiere ();
953: #ifndef DEBUG
954:         printf ("... los geht's, suche ...");
955: #endif

956: 
957:         /* 'x'-Mittelpunkt-Ebenen x = 4, 3 */
958:         StarteSucheMitLagen (&Teil[11].Verteilung[0], LegeTeileAbBit);
959: 
960:         /* won 'Q' die rechten beiden Lagen entfernen */
961:         Teil[0].Anzahl >>= 1;
962: 
963:         /* 'x'-Mittelpunkt-Ebene x = 2 */
964:         StarteSucheMitLagen (&Teil[11].Verteilung[1], LegeTeileOhneQAbBit);
965: 
966:         printf ("\rEs gibt %d echt unterschiedliche L”sungen"
967: #ifdef DEBUG
968:                 " (%.0f Plazierungen - LastBitMax = %d)"
969: #endif

970:                 "!\n", Loesungen
971: #ifdef DEBUG
972:                 , (double) Plazierungen, LastBitMax
973: #endif

974:                 );
975:         return 0;
976: }
977: