fill.c

   1 // Solve a Fillomino puzzle.
   2 #include <stdint.h>
   3 #include <stdlib.h>
   4 #include <stdio.h>
   5 #include <string.h>
   6 #include "darray.h"
   7 #include "inta.h"
   8 #include "zdd.h"
   9 #include <stdarg.h>
  10 #include "io.h"
  11
  12 int main() {
  13   zdd_init();
  14
  15   uint32_t rcount, ccount;
  16   if (!scanf("%d %d\n", &rcount, &ccount)) die("input error");
  17   int board[rcount][ccount];
  18   inta_t white[rcount][ccount];
  19   inta_t black[rcount][ccount];
  20   inta_t must[rcount * ccount];
  21
  22   for (int i = 0; i < rcount; i++) {
  23     int c;
  24     for (int j = 0; j < ccount; j++) {
  25       inta_init(white[i][j]);
  26       inta_init(black[i][j]);
  27       inta_init(must[i * ccount + j]);
  28       c = getchar();
  29       if (c == EOF || c == '\n') die("input error");
  30       int encode(char c) {
  31         switch(c) {
  32           case '.':
  33             return 0;
  34             break;
  35           case '1' ... '9':
  36             return c - '0';
  37             break;
  38           case 'a' ... 'z':
  39             return c - 'a' + 10;
  40             break;
  41           case 'A' ... 'Z':
  42             return c - 'A' + 10;
  43             break;
  44         }
  45         die("input error");
  46       }
  47       board[i][j] = encode(c);
  48     }
  49     c = getchar();
  50     if (c != '\n') die("input error");
  51   }
  52   int v = 1;
  53   inta_t r, c, blackr, blackc, growth, dupe, psize;
  54   darray_t adj;
  55   inta_init(r);
  56   inta_init(c);
  57   inta_init(blackr);
  58   inta_init(blackc);
  59   inta_init(growth);
  60   inta_init(dupe);
  61   inta_init(psize);
  62   darray_init(adj);
  63   // Sacrifice a void * so we can index psize from 1.
  64   inta_append(psize, 0);
  65
  66   int onboard(int x, int y) {
  67     return x >= 0 && x < rcount && y >= 0 && y < ccount;
  68   }
  69
  70   for (int i = 0; i < rcount; i++) {
  71     for (int j = 0; j < ccount; j++) {
  72       int n = board[i][j];
  73       if (n) {
  74         // We store more information than we need in scratch for debugging.
  75         // The entry [i][j] is:
  76         //  -1 when being considered as part of the current polyomino
  77         //  -2 when already searched from the same home square
  78         //  -3 when already searched from a different home square
  79         //   0 when not involved yet
  80         //  >0 when a potential site to grow the current polyomino
  81         int scratch[rcount][ccount];
  82         memset(scratch, 0, rcount * ccount * sizeof(int));
  83         scratch[i][j] = -1;
  84
  85         void recurse(int x, int y, int m, int lower) {
  86           // Even when m = n we look for sites to grow the polyomino, because
  87           // in this case, we blacklist these squares; no other n-omino
  88           // may intersect these squares.
  89           void check(int x, int y) {
  90             // See if square is suitable for growing polyomino.
  91             if (onboard(x,y) && !scratch[x][y] &&
  92                 (board[x][y] == n || board[x][y] == 0)) {
  93               inta_append(r, x);
  94               inta_append(c, y);
  95               scratch[x][y] = inta_count(r);
  96               // Have we seen this polyomino before?
  97               if (board[x][y] == n) {
  98                 if ((x < i || (x == i && y < j))) {
  99                   // We already handled it last time we encountered it.
 100                   // Mark it as already searched.
 101                   scratch[x][y] = -3;
 102                 } else {
 103                   inta_append(dupe, x * ccount + y);
 104                 }
 105               }
 106             }
 107           }
 108           int old = inta_count(r);
 109           int olddupecount = inta_count(dupe);
 110           check(x - 1, y);
 111           check(x, y + 1);
 112           check(x + 1, y);
 113           check(x, y - 1);
 114
 115           if (m == n) {
 116             // It has grown to the right size.
 117             // Check squares adjacent to polyomino. We need only check
 118             // the unsearched growth sites and squares already searched because
 119             // these are the only potential trouble spots.
 120             for(int k = 0; k < inta_count(r); k++) {
 121               int x = inta_at(r, k);
 122               int y = inta_at(c, k);
 123               if (scratch[x][y] != -1) {
 124                 if (board[x][y] == n) {
 125                   // An n-polyomino cannot border a square clued with n.
 126                   inta_remove_all(blackr);
 127                   inta_remove_all(blackc);
 128                   goto abort;
 129                 } else {
 130                   inta_append(blackr, x);
 131                   inta_append(blackc, y);
 132                 }
 133               }
 134             }
 135     /*
 136     printf("v %d\n", v);
 137     for(int a = 0; a < rcount; a++) {
 138       for (int b = 0; b < ccount; b++) {
 139         putchar(scratch[a][b] + '0');
 140       }
 141       putchar('\n');
 142     }
 143     putchar('\n');
 144     */
 145
 146             inta_append(psize, n);
 147             void checkconflict(int w) {
 148               // If the other polyomino covers our home square then don't
 149               // bother reporting the conflict, because we handle this case
 150               // elsewhere.
 151               if (inta_index_of(must[i * ccount + j], w) >= 0) return;
 152               if (inta_at(psize, w) == n) {
 153                 inta_ptr a = (inta_ptr) malloc(sizeof(inta_t));
 154                 inta_init(a);
 155                 darray_append(adj, (void *) a);
 156                 inta_append(a, w);
 157                 inta_append(a, v);
 158                 //printf("conflict %d %d\n", w, v);
 159               }
 160             }
 161             for(int k = 0; k < inta_count(blackr); k++) {
 162               int x = inta_at(blackr, k);
 163               int y = inta_at(blackc, k);
 164               inta_append(black[x][y], v);
 165               inta_forall(white[x][y], checkconflict);
 166             }
 167             inta_remove_all(blackr);
 168             inta_remove_all(blackc);
 169             inta_append(white[i][j], v);
 170             void addv(int k) {
 171               int x = inta_at(r, k);
 172               int y = inta_at(c, k);
 173               inta_append(white[x][y], v);
 174             }
 175             inta_forall(growth, addv);
 176             inta_append(must[i * ccount + j], v);
 177             void addmust(int k) { inta_append(must[k], v); }
 178             inta_forall(dupe, addmust);
 179             v++;
 180           } else {
 181             // Recurse through each growing site.
 182             for(int k = lower; k < inta_count(r); k++) {
 183               int x = inta_at(r, k);
 184               int y = inta_at(c, k);
 185               if (scratch[x][y] != -3) {
 186                 inta_append(growth, k);
 187                 scratch[x][y] = -1;
 188                 recurse(x, y, m + 1, k + 1);
 189                 scratch[x][y] = -2;
 190                 inta_remove_last(growth);
 191               }
 192             }
 193           }
 194 abort:
 195           for(int k = old; k < inta_count(r); k++) {
 196             scratch[inta_at(r, k)][inta_at(c, k)] = 0;
 197           }
 198           inta_set_count(r, old);
 199           inta_set_count(c, old);
 200           inta_set_count(dupe, olddupecount);
 201         }
 202         recurse(i, j, 1, 0);
 203         inta_remove_all(r);
 204         inta_remove_all(c);
 205       }
 206     }
 207   }
 208   zdd_set_vmax(v - 1);
 209   // Each clue n must be covered by exactly one n-polyomino.
 210   for (int i = 0; i < rcount * ccount; i++) {
 211     if (inta_count(must[i]) > 0) {
 212       zdd_contains_exactly_1(inta_raw(must[i]), inta_count(must[i]));
 213       zdd_intersection();
 214     }
 215   }
 216
 217   // Othewise, each square can be covered by at most one of the polyominoes we
 218   // enumerated.
 219   for (int i = 0; i < rcount; i++) {
 220     int first = 1;
 221     for (int j = 0; j < ccount; j++) {
 222       if (board[i][j] != 0) continue;
 223       if (inta_count(white[i][j]) > 1) {
 224         zdd_contains_at_most_1(inta_raw(white[i][j]), inta_count(white[i][j]));
 225         if (first) first = 0; else zdd_intersection();
 226       }
 227     }
 228     zdd_intersection();
 229   }
 230
 231   // Adjacent polyominoes must differ in size.
 232   void handleadj(void *data) {
 233     inta_ptr list = (inta_ptr) data;
 234     zdd_contains_at_most_1(inta_raw(list), inta_count(list));
 235     zdd_intersection();
 236   }
 237   darray_forall(adj, handleadj);
 238
 239   int solcount = 0;
 240   void printsol(int *v, int count) {
 241     char pic[rcount][ccount];
 242     memset(pic, '.', rcount * ccount);
 243     for(int k = 0; k < count; k++) {
 244       for (int i = 0; i < rcount; i++) {
 245         for (int j = 0; j < ccount; j++) {
 246           if (inta_index_of(white[i][j], v[k]) >= 0) {
 247             int n = inta_at(psize, v[k]);
 248             pic[i][j] = n < 10 ? '0' + n : 'A' + n - 10;
 249           }
 250         }
 251       }
 252     }
 253     // Now we have a new problem: tile the remaining squares with polyominoes
 254     // of arbitrary size to satisfy the puzzle conditions.
 255     // TODO: Brute force search to finish the puzzle. For now, we only check
 256     // the simplest cases.
 257     for (int i = 0; i < rcount; i++) {
 258       for (int j = 0; j < ccount; j++) {
 259         int scratch[rcount][ccount];
 260         memset(scratch, 0, rcount * ccount * sizeof(int));
 261
 262         void neighbour_run(void (*fn)(int, int), int i, int j) {
 263           fn(i - 1, j);
 264           fn(i + 1, j);
 265           fn(i, j - 1);
 266           fn(i, j + 1);
 267         }
 268         if ('.' == pic[i][j]) {
 269           int count = 0;
 270           void paint(int i, int j) {
 271             scratch[i][j] = -1;
 272             inta_append(r, i);
 273             inta_append(c, j);
 274             count++;
 275             void bleed(int i, int j) {
 276               if (onboard(i, j) &&
 277                   pic[i][j] == '.' && !scratch[i][j]) paint(i, j);
 278             }
 279             neighbour_run(bleed, i, j);
 280           }
 281           paint(i, j);
 282           if (count == 1) {
 283             int n1 = 0;
 284             void count1(int i, int j) {
 285               if (onboard(i, j) && pic[i][j] == '1') n1++;
 286             }
 287             neighbour_run(count1, i, j);
 288             if (n1) {
 289               inta_remove_all(r);
 290               inta_remove_all(c);
 291               return;
 292             }
 293             pic[i][j] = '1';
 294           } else if (count == 2) {
 295             int n1 = 0;
 296             void count1(int i, int j) {
 297               if (onboard(i, j) && pic[i][j] == '2') {
 298                 n1++;
 299               }
 300             }
 301             int x = inta_at(r, 0);
 302             int y = inta_at(c, 0);
 303             neighbour_run(count1, x, y);
 304             x = inta_at(r, 1);
 305             y = inta_at(c, 1);
 306             neighbour_run(count1, x, y);
 307             if (n1) {
 308               inta_remove_all(r);
 309               inta_remove_all(c);
 310               return;
 311             }
 312             x = inta_at(r, 0);
 313             y = inta_at(c, 0);
 314             pic[x][y] = '2';
 315             x = inta_at(r, 1);
 316             y = inta_at(c, 1);
 317             pic[x][y] = '2';
 318           }
 319           inta_remove_all(r);
 320           inta_remove_all(c);
 321         }
 322       }
 323     }
 324
 325     printf("Solution #%d:\n", ++solcount);
 326     for (int i = 0; i < rcount; i++) {
 327       for (int j = 0; j < ccount; j++) {
 328         putchar(pic[i][j]);
 329       }
 330       putchar('\n');
 331     }
 332     putchar('\n');
 333   }
 334   zdd_forall(printsol);
 335   return 0;
 336 }