dom.c

   1 // Solve a Dominosa puzzle.
   2 #include <stdint.h>
   3 #include <stdlib.h>
   4 #include <stdio.h>
   5 #include <string.h>
   6 #include "inta.h"
   7 #include "zdd.h"
   8
   9 #include <stdarg.h>
  10 #include "io.h"
  11
  12 int main() {
  13   zdd_init();
  14
  15   int n;
  16   if (!scanf("%d\n", &n)) die("input error");
  17   uint32_t rcount = n + 1, ccount = n + 2;
  18   int board[rcount][ccount];
  19   inta_t list[rcount][ccount];
  20
  21   for(int i = 0; i < rcount; i++) {
  22     int c;
  23     for(int j = 0; j < ccount; j++) {
  24       inta_init(list[i][j]);
  25       c = getchar();
  26       if (c == EOF || c == '\n') die("input error");
  27       int encode(char c) {
  28         switch(c) {
  29           case '0' ... '9':
  30             return c - '0';
  31             break;
  32           case 'a' ... 'z':
  33             return c - 'a' + 10;
  34             break;
  35           case 'A' ... 'Z':
  36             return c - 'A' + 10;
  37             break;
  38         }
  39         die("input error");
  40       }
  41       board[i][j] = encode(c);
  42     }
  43     c = getchar();
  44     if (c != '\n') die("input error");
  45   }
  46
  47   // n is useless as the highest number on a domino. Reuse it as
  48   // the total number of dominoes.
  49   n = rcount * ccount / 2;
  50   inta_t tally[n];
  51   for(int i = 0; i < n; i++) inta_init(tally[i]);
  52
  53   int geti(int a, int b) {
  54     // Return canonical numbering for a given domino.
  55     // Assumes a >= b.
  56     return a * (a + 1) / 2 + b;
  57   }
  58
  59   int v = 1;
  60   for(int i = 0; i < rcount; i++) {
  61     for(int j = 0; j < ccount; j++) {
  62       int a, b, c;
  63       if (j < ccount - 1) {
  64         // Horizontal tiling constraint.
  65         inta_append(list[i][j], v);
  66         inta_append(list[i][j + 1], v);
  67         a = board[i][j];
  68         b = board[i][j + 1];
  69         if (a < b) c = a, a = b, b = c;
  70         // One domino per board constraint.
  71         inta_append(tally[geti(a, b)], v);
  72         v++;
  73       }
  74
  75       if (i < rcount - 1) {
  76         // Vertical tiling constraint.
  77         inta_append(list[i][j], v);
  78         inta_append(list[i + 1][j], v);
  79         a = board[i][j];
  80         b = board[i + 1][j];
  81         if (a < b) c = a, a = b, b = c;
  82         // One domino per board constraint.
  83         inta_append(tally[geti(a, b)], v);
  84         v++;
  85       }
  86     }
  87   }
  88   zdd_set_vmax(v - 1);
  89
  90   int todo = rcount - 1;
  91   for(int i = 0; i < rcount; i++) {
  92     for(int j = 0; j < ccount; j++) {
  93       zdd_contains_exactly_1(inta_raw(list[i][j]), inta_count(list[i][j]));
  94       if (j) zdd_intersection();
  95     }
  96
  97     int n = i + 1;
  98     while (!(n & 1)) {
  99       n >>= 1;
 100       zdd_intersection();
 101       todo--;
 102     }
 103   }
 104   while(todo--) zdd_intersection();
 105
 106   int compar(const void *a, const void *b) {
 107     return inta_count((const inta_ptr) a) > inta_count((const inta_ptr) b);
 108   }
 109   qsort(tally, n, sizeof(inta_t), compar);
 110   for(int i = 0; i < n; i++) {
 111     //printf("%d/%d\n", i + 1, n);
 112     zdd_contains_exactly_1(inta_raw(tally[i]), inta_count(tally[i]));
 113     zdd_intersection();
 114   }
 115
 116   // Print lexicographically largest solution, assuming it exists.
 117   char pic[2 * rcount + 1][2 * ccount + 1];
 118   for(int i = 0; i < rcount; i++) {
 119     for(int j = 0; j < ccount; j++) {
 120       pic[2 * i][2 * j] = board[i][j] + '0';
 121       pic[2 * i][2 * j + 1] = '|';
 122       pic[2 * i + 1][2 * j] = '-';
 123       pic[2 * i + 1][2 * j + 1] = '+';
 124     }
 125     pic[2 * i][2 * ccount] = pic[2 * i + 1][2 * ccount] = '\0';
 126   }
 127   v = zdd_root();
 128   while(v != 1) {
 129     int i = zdd_v(v) / (rcount + ccount);
 130     int j = zdd_v(v) % (rcount + ccount);
 131     if (!j) {
 132       pic[2 * i - 1][2 * (ccount - 1)] = ' ';
 133     } else if (rcount - 1 == i) {
 134       pic[2 * i][2 * j - 1] = ' ';
 135     } else {
 136       if (j & 1) {
 137         pic[2 * i][j] = ' ';
 138       } else {
 139         pic[2 * i + 1][j - 2] = ' ';
 140       }
 141     }
 142     v = zdd_hi(v);
 143   }
 144   for(int i = 0; i < 2 * rcount; i++) {
 145     puts(pic[i]);
 146   }
 147   return 0;
 148 }