david98031

Solve Eternity 2 style puzzles with dancing links

Jan 12th, 2021 (edited)
797
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <stdio.h>
  2. #include <string.h>
  3. #include <stdlib.h>
  4. #include "dlx.h"
  5.  
  6. typedef struct {
  7.   const char *name;
  8.   int width;
  9.   int height;
  10.   int (*pieces)[4];
  11. } puzinfo;
  12.  
  13. #include "pieces.h"
  14.  
  15. int main(int argc, char *argv[]) {
  16.   puzinfo *p;
  17.   int i, j, rownum=0, size, pos, pos2=0, piecenum, row, col, width, height, rot, edgebits=0, edges[4], edge, edge2;
  18.  
  19.   // Initialize a new exact cover instance.
  20.   dlx_t dlx = dlx_new();
  21.  
  22.   char *puz_name = argv[1];
  23.  
  24.   for(i=0;;i++) {
  25.     if(!strcmp(pi[i].name, puz_name)) {
  26.       p = &pi[i];
  27.       break;
  28.     }
  29.   }
  30.   width = p->width;
  31.   height = p->height;
  32.   printf("width = %d\n", p->width);
  33.   printf("height = %d\n", p->height);
  34.   size = p->width * p->height;
  35.  
  36.   // count the edgebits
  37.   j = 0;
  38.   for (piecenum=0; piecenum<size; piecenum++) {
  39.     for (i=0; i<4; i++) {
  40.       if (p->pieces[piecenum][i] > j) {
  41.         j = p->pieces[piecenum][i];
  42.       }
  43.     }
  44.   }
  45.   printf("max edge = %d\n", j);
  46.   while (j > 0) {
  47.     edgebits++;
  48.     j /= 2;
  49.   }
  50.   printf("edge bits = %d\n", edgebits);
  51.  
  52.   char **rownames = calloc(size*size*4, sizeof(char *));
  53.  
  54.   for (pos = 0; pos < size; pos++) {
  55.     row = pos / width;
  56.     col = pos % width;
  57.     for (piecenum = 0; piecenum < size; piecenum++) {
  58.       for (i=0; i<4; i++) {
  59.         edges[i] = p->pieces[piecenum][i];
  60.       }
  61.       for (rot=0; rot<4; rot++) {
  62.         if (((pos == 0) == (piecenum == 0)) &&
  63.             (((edges[0] == 0) == (row == 0)) &&
  64.              ((edges[1] == 0) == (col+1 == width)) &&
  65.              ((edges[2] == 0) == (row+1 == height)) &&
  66.              ((edges[3] == 0) == (col == 0)))) {
  67.           // legal piece placement, proceed
  68.           // mark the position occupied
  69.           dlx_set(dlx, rownum, pos);
  70.           printf("dlx_set(dlx, %d, %d);\n", rownum, pos);
  71.           // mark the piece used
  72.           dlx_set(dlx, rownum, size+piecenum);
  73.           printf("dlx_set(dlx, %d, %d);\n", rownum, size+piecenum);
  74.           // mark the edge placement
  75.           for (edge=0; edge<4; edge++) {
  76.             for (j=0; j<edgebits; j++) {
  77.               if ((edges[edge] & (1<<j)) ||
  78.                   (edge == 0 && row == 0) ||
  79.                   (edge == 1 && col+1 == width) ||
  80.                   (edge == 2 && row+1 == height) ||
  81.                   (edge == 3 && col == 0)) {
  82.                 // mark this edge
  83.                 pos2 = pos;
  84.                 edge2 = edge;
  85.               } else {
  86.                 pos2 = pos + (int []){-width, 1, width, -1}[edge];
  87.                 edge2 = (edge + 2) % 4;
  88.               }
  89.               dlx_set(dlx, rownum, size*2 + (pos2*4 + edge2)*edgebits + j);
  90.               printf("dlx_set(dlx, %d, %d);\n", rownum, size*2 + (pos2*4 + edge2)*edgebits + j);
  91.             }
  92.           }
  93.  
  94.           rownames[rownum] = malloc(32);
  95.           sprintf(rownames[rownum], "%d,%d,%d/%d", row, col, piecenum, rot);
  96.  
  97.           //printf("pos %d, piece %d/%d\n", pos, piecenum, rot);
  98.           fflush(stdout);
  99.           rownum++;
  100.         } else {
  101.           //printf("skipping pos %d, piece %d/%d\n", pos, piecenum, rot);
  102.         }
  103.         // rotate the piece
  104.         j = edges[3];
  105.         for (i=3; i>0; i--) {
  106.           edges[i] = edges[i-1];
  107.         }
  108.         edges[0] = j;
  109.       }
  110.     }
  111.   }
  112.   printf("row count = %d\n", rownum);
  113.  
  114.   // Mark the last column as optional.
  115.   //dlx_mark_optional(dlx, 2);
  116.  
  117.   void f(int row[], int n) {
  118.     printf("Solution: rows:");
  119.     for(int i = 0; i < n; i++) {
  120.       printf(" %s", rownames[row[i]]);
  121.     }
  122.     printf("\n");
  123.   }
  124.   dlx_forall_cover(dlx, f);
  125.  
  126.   dlx_clear(dlx);
  127.   return 0;
  128. }
RAW Paste Data

Adblocker detected! Please consider disabling it...

We've detected AdBlock Plus or some other adblocking software preventing Pastebin.com from fully loading.

We don't have any obnoxious sound, or popup ads, we actively block these annoying types of ads!

Please add Pastebin.com to your ad blocker whitelist or disable your adblocking software.

×