Advertisement
david98031

Solve Eternity 2 style puzzles with dancing links

Jan 12th, 2021 (edited)
1,367
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C 3.58 KB | None | 0 0
  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. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement