001: #include <stdio.h>
002: #include <stdlib.h>
003: #include <string.h>
004: #include <time.h>
005: 
006: #define TEILE 12
007: #define BX 3
008: #define BY 4
009: #define BZ 5
010: #define BLOECKE BX*BY*BZ
011: #define pwr2(x) ((uint64)1 << (x))
012: #define TEILKOMB ((int) pwr2(TEILE))
013: #define FELDMASK (pwr2(BLOECKE) - 1)
014: #define FELDMASKSM ((bitvsm) pwr2(BLOECKE-32) - 1)
015: 
016: typedef unsigned __int64 uint64;
017: typedef uint64 bitv;
018: 
019: typedef unsigned long bitvsm;
020: typedef int *vector;
021: 
022: char teile[] =
023:   "##.. ...." ".##. ...." "#... ...." "###. ...."
024:   "#... ...." "##.. ...." "##.. ...." ".#.. ...."
025:   "##.. ...." ".#.. ...." "#... ...." ".#.. ...."
026:   ".... ...." ".... ...." "##.. ...." ".... ...."
027: 
028:   ".##. ...." "##.. ...." "##.. #..." ".#.. ...."
029:   ".#.. ...." "##.. ...." "##.. ...." "###. ...."
030:   "##.. ...." "#... ...." ".... ...." ".#.. ...."
031:   ".... ...." ".... ...." ".... ...." ".... ...."
032:   
033:   "##.. #..." "##.. ...." ".##. ...." "#... ...."
034:   ".... #..." "#... ...." "##.. ...." "##.. ...."
035:   ".... ...." "#... ...." "#... ...." "#... ...."
036:   ".... ...." "#... ...." ".... ...." "#... ....";
037: 
038: 
039: clock_t start;
040: unsigned int loesungen = 0;
041: unsigned int tries = 0;
042: 
043: bitv teilposits[TEILE][BLOECKE * 24];
044: int teilpositsnum[TEILE];
045: 
046: bitv *posits[BLOECKE][TEILKOMB];
047: bitvsm *positssm[BLOECKE][TEILKOMB];
048: 
049: int bitpos[BX][BY][BZ];
050: bitv vorbelegung = 0;
051: 
052: int M[4][4];
053: 
054: uint64 oneshl[64];
055: 
056: int teilmitmaxposits = TEILE, teilmitmaxpositsnum = 0;
057: int teilmitminposits = TEILE, teilmitminpositsnum = 10000;
058: 
059: int
060: bittest (bitv p, int bit)
061: {
062:   return (p & oneshl[bit]) != 0;
063: }
064: 
065: 
066: // liefert bitnr. für koordinaten x,y,z oder -1 wenn koord nicht im würfel
067: 
068: int
069: bitpos_checked (int x, int y, int z)
070: {
071:   if (x >= BX || y >= BY || z >= BZ || x < 0 || y < 0 || z < 0)
072:         return -1;
073: 
074:   return bitpos[x][y][z];
075: }
076: 
077: 
078: // vector nach bitv
079: bitv
080: bitvec (vector v)
081: {
082:   int b;
083: 
084:   b = bitpos_checked (v[0], v[1], v[2]);
085:   return b == -1 ? 0 : oneshl[b];
086: }
087: 
088: void
089: setvector (vector v, int x, int y, int z, int u)
090: {
091:   v[0] = x;  v[1] = y;  v[2] = z;  v[3] = u;
092: }
093: 
094: void
095: copyvector (vector v, vector w)
096: {
097:   v[0] = w[0];  v[1] = w[1];  v[2] = w[2];  v[3] = w[3];
098: }
099: 
100: // spiegelt einen bitv entlang den koor-achsen
101: bitv
102: flip_bitv (bitv p, int sx, int sy, int sz)
103: {
104:   int x, y, z;
105:   int v[4];
106:   bitv u;
107: 
108:   u = 0;
109: 
110:   for (x = 0; x < BX; x++)
111:         for (y = 0; y < BY; y++)
112:           for (z = 0; z < BZ; z++)
113:         {
114:           setvector (v, x, y, z, 1);
115:           if (p & bitvec (v))
116:                 {
117:                   setvector (v, sx ? BX - x - 1 : x, sy ? BY - y - 1 : y,
118:                          sz ? BZ - z - 1 : z, 1);
119:                   u |= bitvec (v);
120:                 }
121:         }
122: 
123:   return u;
124: }
125: 
126: // matrix-multiplikation mit M
127: void
128: mmul (vector w, vector v)
129: {
130:   int i, j;
131: 
132:   for (i = 0; i < 4; i++)
133:         {
134:           w[i] = 0;
135:           for (j = 0; j < 4; j++)
136:         w[i] += v[j] * M[j][i];
137:         }
138: }
139: 
140: 
141: // projeziert mit M das teil in eine position und fügt es in teilposits,
142: // wenn es passt
143: void
144: doprojteil (int teil)
145: {
146:   char c;
147:   int x, y, z;
148:   bitv p, pos = 0;
149:   bitv *pp;
150:   int v[4], w[4];
151: 
152:   for (x = 0; x < 4; x++)
153:         for (y = 0; y < 4; y++)
154:           for (z = 0; z < 2; z++)
155:                 {
156:                   c = teile[x + z * 5 + (teil % 4) * 9 + (y + (teil / 4) * 4) * 9 * 4];
157:                   if (c != '#')        continue;
158: 
159:                   setvector (v, x, y, z, 1);
160:                   mmul (w, v);
161:                   p = bitvec (w);
162:                   if (!p) return;
163:                   pos |= p;
164:                 }
165: 
166:   if (p & vorbelegung) return;
167: 
168:   pp = teilposits[teil];
169: 
170:   while (p = *pp++)
171:         {
172:           if (p == pos) break;
173: 
174:           if (teil == teilmitminposits && (
175:                           p == flip_bitv (pos, 1, 1, 0) ||
176:                         p == flip_bitv (pos, 1, 0, 1) ||
177:                         p == flip_bitv (pos, 0, 1, 1) ) )
178:                 {
179:                   if ((pos & -pos) < (p & -p)) *(pp - 1) = pos;
180:                   break;
181:                 }
182: 
183:           if (teil == teilmitmaxposits && (
184:                   (p == flip_bitv (pos, 1, 1, 0) && vorbelegung == flip_bitv (vorbelegung, 1, 1, 0)) ||
185:                   (p == flip_bitv (pos, 1, 0, 1) && vorbelegung == flip_bitv (vorbelegung, 1, 0, 1)) ||
186:                   (p == flip_bitv (pos, 0, 1, 1) && vorbelegung == flip_bitv (vorbelegung, 0, 1, 1)) ) )
187:                 {
188:                   if ((pos & -pos) > (p & -p)) *(pp - 1) = pos;
189:                   break;
190:                 }
191:         }
192: 
193:   if (!p)
194:         {
195:           *(pp - 1) = pos;
196:           *pp = 0;
197:         }
198: }
199: 
200: 
201: void
202: dotransteil (int teil)
203: {
204:   int tx, ty, tz;
205:           
206:   for (tz = 0; tz < BZ; tz++)
207:         for (ty = 0; ty < BY; ty++)
208:           for (tx = 0; tx < BX; tx++)
209:                 {
210:                   setvector (M[3], tx, ty, tz, 1);
211:                   doprojteil (teil);
212:                 }
213: }
214: 
215: 
216: void
217: dorotteil (int teil)
218: {
219:   int basevec[6][4] = {
220:         {1, 0, 0, 0}, {0, 1, 0, 0}, {0, 0, 1, 0},
221:         {-1, 0, 0, 0}, {0, -1, 0, 0}, {0, 0, -1, 0}
222:   };
223: 
224:   int mx, my;
225: 
226:   for (mx = 0; mx < 6; mx++)
227:         {
228:           copyvector (M[0], basevec[mx]);
229:           for (my = 0; my < 6; my++)
230:                 {
231:                   copyvector (M[1], basevec[my]);
232: 
233:                   // px und py müssen l.u. sein
234:                   if (M[0][0] * M[1][0] + M[0][1] * M[1][1] + M[0][2] * M[1][2] != 0)
235:                         continue;
236: 
237:                   // pz = px kreuz py
238:                   M[2][0] = M[0][1] * M[1][2] - M[0][2] * M[1][1];
239:                   M[2][1] = M[0][2] * M[1][0] - M[0][0] * M[1][2];
240:                   M[2][2] = M[0][0] * M[1][1] - M[0][1] * M[1][0];
241:                   M[2][3] = 0;
242:                           
243:                   dotransteil (teil);
244:                 }
245:         }
246: }
247: 
248: 
249: void
250: gen_teilposits (void)
251: {
252:   int teil, anz, anzsumme = 0;
253: 
254:   for (teil = 0; teil < TEILE; teil++)
255:         {
256:           // if (teil == teilmitminposits) continue;
257:           dorotteil (teil);
258:           anz = 0;
259:           while (teilposits[teil][anz])        anz++;
260:           anzsumme += anz;
261:           teilpositsnum[teil] = anz;
262:           printf ("%d moegliche Positionen fuer Teil %d\n", anz, teil);
263:         }
264:   printf ("insgesamt moegliche Positionen: %d\n", anzsumme);
265: }
266: 
267: 
268: bitv *
269: gen_posits (int bit, int tb)
270: {
271:   int i, teil;
272:   bitv p;
273:   bitv *tpos, *t, *pp;
274: 
275:   tpos = (bitv *) malloc ((BLOECKE * 24) * sizeof (bitv));
276:   t = tpos;
277: 
278:   for (teil = 0; teil < TEILE; teil++)
279:         {
280:           // teil schon benutzt?
281:           if ((1 << teil) & tb)        continue;
282: 
283:           pp = teilposits[teil];
284:           while (p = *pp++)
285:                 {
286:                   // posit muss bit 'bit' gesetzt haben
287:                   if (!bittest (p, bit)) continue;
288: 
289:                   // alle niedrigeren bits muessen 0 sein
290:                   if ((oneshl[bit] - 1) & p) continue;
291: 
292:                   *t++ = p | ((bitv) teil << BLOECKE);
293:                 }
294:         }
295: 
296:   *t++ = 0;
297: 
298:   posits[bit][tb] = (bitv *) realloc (tpos, (t - tpos) * sizeof (bitv));
299: 
300:   // printf("posits   : bit %d  tb %3x  n %d\n", bit, tb, t-tpos);
301: 
302:   return posits[bit][tb];
303: }
304: 
305: 
306: bitvsm *
307: gen_positssm (int bit, int tb)
308: {
309:   int i, teil;
310:   bitv p, *pp;
311:   bitvsm *tpos, *t;
312: 
313:   tpos = (bitvsm *) malloc ((BLOECKE * 24) * sizeof (bitvsm));
314:   t = tpos;
315: 
316:   for (teil = 0; teil < TEILE; teil++)
317:         {
318:           // teil schon benutzt?
319:           if ((1 << teil) & tb)        continue;
320: 
321:           pp = teilposits[teil];
322:           while (p = *pp++)
323:                 {
324:                   // posit muss bit 'bit' gesetzt haben
325:                   if (!bittest (p, bit)) continue;
326: 
327:                   // alle niedrigeren bits muessen 0 sein
328:                   if ((oneshl[bit] - 1) & p) continue;
329:                         
330:                   *t++ = (p | ((bitv) teil << BLOECKE)) >> 32;
331:                 }
332:         }
333: 
334:   *t++ = 0;
335: 
336:   positssm[bit][tb] = (bitvsm *) realloc (tpos, (t - tpos) * sizeof (bitvsm));
337: 
338:   // printf("positsm  : bit %d  tb %3x  n %d\n", bit, tb, t-tpos);
339: 
340:   return positssm[bit][tb];
341: }
342: 
343: 
344: void
345: recsolveinner (bitvsm feld, int tb)
346: {
347:   bitvsm p, mi;
348:   bitvsm *pp, *p1, *p2;
349:   int i, teil, bit;
350: 
351:   if (tb == (1 << TEILE) - 1)
352:   {
353:         loesungen++;
354:         #ifdef DEBUG
355:         printf("tb %08X  feld %08lX  LOESUNG!!!\n", tb, feld);
356:         #endif
357:         if ((loesungen % 737) == 0)
358:         {
359:           double d;
360: 
361:           d = (double) (clock () - start) / CLOCKS_PER_SEC;
362:           printf ("%u Loesungen in %.2fs, %.2f/s, %u Aufrufe...\n",
363:                   loesungen, d, loesungen / d, tries);
364:         }
365:         return;
366:   }
367: 
368:   __asm
369:   {
370:         mov eax, feld
371:         not eax
372:         bsf eax, eax
373:         add eax, 32
374:         mov bit, eax
375:   }
376: 
377:   #ifdef DEBUG
378:   printf("bit %2d  tb %08X  feld %08lX\n", bit, tb, feld);
379:   #endif
380: 
381:   if (!(pp = positssm[bit][tb]))
382:         pp = gen_positssm (bit, tb);
383: 
384:   tries++;
385: 
386:   while (1)
387:         {
388:           while ((p = *pp++) & feld);
389: 
390:           if (!p) break;
391: 
392:           teil = p >> (BLOECKE - 32);
393: 
394:           recsolveinner (feld | p & FELDMASKSM, tb | (1 << teil));
395:         }
396: }
397: 
398: 
399: void
400: recsolve (bitv feld, int tb)
401: {
402:   bitv p, mi;
403:   bitv *pp, *p1, *p2;
404:   int i, teil, bit;
405: 
406:   __asm
407:   {
408:         mov eax, dword ptr feld
409:         not eax
410:         bsf eax, eax
411:         mov edx, -1
412:         cmovz eax, edx
413:         mov bit, eax
414:   }
415: 
416:   #ifdef DEBUG
417:   printf("bit %2d  tb %08X  feld %016I64X\n", bit, tb, feld);
418:   #endif
419: 
420:   if (bit == -1)
421:         {
422:           // alle untern 32 bit sind gesetzt, weiter in der inneren schleife
423:           recsolveinner ((int)(feld >> 32), tb);
424:           return;
425:         }
426: 
427:   if (!(pp = posits[bit][tb]))
428:         pp = gen_posits (bit, tb);
429: 
430:   tries++;
431: 
432:   while (1)
433:         {
434:           while ((p = *pp++) & feld);
435: 
436:           if (!p) break;
437: 
438:           teil = p >> BLOECKE;
439: 
440:           recsolve (feld | p & FELDMASK, tb | (1 << teil));
441: 
442: #ifdef TEST
443:         if (bit == 0)
444:         return;
445: #endif
446:         }
447: }
448: 
449: 
450: void
451: gen_bitpos(void)
452: {
453:   int x,y,z;
454:   int ind[BX][BY] = { { 2, 3, 4, 5 },
455:                            { 1,10,11, 6 },
456:                       { 0, 9, 8, 7 }  };
457: 
458:   for (x=0; x<BX; x++)
459:     for (y=0; y<BY; y++)
460:       for (z=0; z<BZ; z++)
461:       {
462:               bitpos[x][y][z] = ind[x][y] + z*BX*BY;
463:       }
464: }
465: 
466: 
467: void
468: solve (void)
469: {
470:   int anz, i, tb, minteil;
471: 
472:   gen_bitpos();
473: 
474:   gen_teilposits();
475: 
476:   for (i=0; i<TEILE; i++)
477:   {
478:           anz = teilpositsnum[i];
479: 
480:         if (anz > teilmitmaxpositsnum)
481:         {
482:                 teilmitmaxpositsnum = anz;
483:                 teilmitmaxposits = i;
484:         }
485:         if (anz < teilmitminpositsnum)
486:         {
487:                 teilmitminpositsnum = anz;
488:                 teilmitminposits = i;
489:         }
490:   }
491: 
492:   for (i=0; i<TEILE; i++)
493:   {
494:           teilposits[i][0] = 0;
495:   }
496:   gen_teilposits();
497: 
498:   printf("max %d teil %d min %d teil %d\n",
499:     teilmitmaxpositsnum, teilmitmaxposits, teilmitminpositsnum, teilmitminposits);
500: 
501:   for (minteil = 0; minteil < teilpositsnum[teilmitminposits]; minteil++)
502:   {
503:           #ifdef PARA_ODD
504:           if (minteil & 1) continue;
505:           #endif
506: 
507:           #ifdef PARA_EVEN
508:           if (!(minteil & 1)) continue;
509:           #endif
510: 
511:           for (i=0; i<BLOECKE; i++)
512:             for (tb=0; tb<TEILKOMB; tb++)
513:             {
514:                     if (posits[i][tb])
515:                     {
516:                             free(posits[i][tb]);
517:                             posits[i][tb] = NULL;
518:                     }
519: 
520:                     if (positssm[i][tb])
521:                     {
522:                             free(positssm[i][tb]);
523:                             positssm[i][tb] = NULL;
524:                     }
525:             }
526: 
527:             for (i=0; i<TEILE; i++)
528:             {
529:                     if (i == teilmitminposits) continue;
530:                     teilposits[i][0] = 0;
531:             }
532: 
533:             printf ("Lauf %d von %d\n", minteil+1, teilpositsnum[teilmitminposits]);
534:             vorbelegung = teilposits[teilmitminposits][minteil];
535:             gen_teilposits();
536:       tb = 1 << teilmitminposits;
537:             recsolve (vorbelegung, tb);
538:   }
539: }
540: 
541: 
542: int main(int argc, char **argv)
543: {
544:   int i;
545:   double d;
546: 
547:   for (i = 0; i < 64; i++)
548:         oneshl[i] = pwr2(i);
549: 
550:   start = clock ();
551: 
552:   solve ();
553: 
554:   d = (double) (clock () - start) / CLOCKS_PER_SEC;
555:   printf ("\n\n**** ENDE ******\n");
556:   printf ("%u Loesungen gefunden, %.2f Loesungen/s.\n",
557:           loesungen, loesungen / d);
558:   printf ("Laufzeit: %.2fs, %u Aufrufe", d, tries);
559: 
560:   return 0;
561: }