light.c

   1 // Solve a Light Up 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 #include <stdarg.h>
   9 #include "io.h"
  10
  11 int main() {
  12   zdd_init();
  13
  14   uint32_t rcount, ccount;
  15   if (!scanf("%d %d\n", &rcount, &ccount)) die("input error");
  16   int board[rcount][ccount];
  17   uint32_t getv(uint32_t i, uint32_t j) { return ccount * i + j + 1; }
  18   zdd_set_vmax(getv(rcount - 1, ccount - 1));
  19   inta_t a;
  20   inta_init(a);
  21
  22   for (int i = 0; i < rcount; i++) {
  23     int c;
  24     for (int j = 0; j < ccount; j++) {
  25       c = getchar();
  26       if (c == EOF || c == '\n') die("input error");
  27       int encode(char c) {
  28         switch(c) {
  29           case '.':
  30             return -1;
  31             break;
  32           case 'X':
  33           case 'x':
  34             inta_append(a, getv(i, j));
  35             return -2;
  36             break;
  37           case '0' ... '4':
  38             inta_append(a, getv(i, j));
  39             return c - '0';
  40             break;
  41         }
  42         die("input error");
  43       }
  44       board[i][j] = encode(c);
  45     }
  46     c = getchar();
  47     if (c != '\n') die("input error");
  48   }
  49   // Instead of constructing a ZDD excluding particular elements, we could
  50   // reduce the number of variables, but then we need to record which variable
  51   // represents which square.
  52   zdd_contains_0(inta_raw(a), inta_count(a));
  53
  54   int colcount = 0;
  55   for (uint32_t i = 0; i < rcount; i++) {
  56     inta_remove_all(a);
  57     zdd_contains_at_most_1(inta_raw(a), inta_count(a));
  58     for (uint32_t j = 0; j < ccount; j++) {
  59       switch(board[i][j]) {
  60         case -1:
  61           // There must be at least one light bulb in this square or a
  62           // square reachable in one rook move.
  63           inta_remove_all(a);
  64           int r0, c0;
  65           for(r0 = i; r0 > 0 && board[r0 - 1][j] == -1; r0--);
  66           for(int k = r0; k != i; k++) {
  67             inta_append(a, getv(k, j));
  68           }
  69           for(c0 = j; c0 > 0 && board[i][c0 - 1] == -1; c0--);
  70           for(int k = c0; k != j; k++) {
  71             inta_append(a, getv(i, k));
  72           }
  73           inta_append(a, getv(i, j));
  74           for(int k = j + 1; k < ccount && board[i][k] == -1; k++) {
  75             inta_append(a, getv(i, k));
  76           }
  77           for(int k = i + 1; k < rcount && board[k][j] == -1; k++) {
  78             inta_append(a, getv(k, j));
  79           }
  80           zdd_contains_at_least_1(inta_raw(a), inta_count(a));
  81           // There is at most one light bulb in this row. We record this when
  82           // we first enter the row.
  83           if (r0 == i) {
  84             inta_remove_all(a);
  85             for(int k = i; k < rcount && board[k][j] == -1; k++) {
  86               inta_append(a, getv(k, j));
  87             }
  88             zdd_contains_at_most_1(inta_raw(a), inta_count(a));
  89             zdd_intersection();
  90           }
  91           // Similarly for columns.
  92           if (c0 == j) {
  93             inta_remove_all(a);
  94             for(int k = j; k < ccount && board[i][k] == -1; k++) {
  95               inta_append(a, getv(i, k));
  96             }
  97             zdd_contains_at_most_1(inta_raw(a), inta_count(a));
  98             // Defer the intersection.
  99             colcount++;
 100           }
 101           zdd_intersection();
 102           break;
 103         case 0 ... 4:
 104           inta_remove_all(a);
 105           void check(int r, int c) {
 106             if (r >= 0 && r < rcount && c >= 0 && c < ccount
 107                 && board[r][c] == -1) {
 108               inta_append(a, getv(r, c));
 109             }
 110           }
 111           check(i - 1, j);
 112           check(i, j - 1);
 113           check(i, j + 1);
 114           check(i + 1, j);
 115           zdd_contains_exactly_n(board[i][j], inta_raw(a), inta_count(a));
 116           zdd_intersection();
 117       }
 118     }
 119     zdd_intersection();
 120   }
 121
 122   while(colcount) {
 123     zdd_intersection();
 124     colcount--;
 125   }
 126
 127   void printsol(int *v, int vcount) {
 128     char pic[rcount][ccount];
 129     memset(pic, '.', rcount * ccount);
 130     for(int i = 0; i < vcount; i++) {
 131       int r = v[i] - 1;
 132       int c = r % ccount;
 133       r /= ccount;
 134       pic[r][c] = '*';
 135     }
 136
 137     for (int i = 0; i < rcount; i++) {
 138       for (int j = 0; j < ccount; j++) {
 139         switch(board[i][j]) {
 140           case -2:
 141             putchar('x');
 142             break;
 143           case 0 ... 4:
 144             putchar('0' + board[i][j]);
 145             break;
 146           default:
 147             putchar(pic[i][j]);
 148         }
 149       }
 150       putchar('\n');
 151     }
 152     putchar('\n');
 153   }
 154
 155   zdd_forall(printsol);
 156   return 0;
 157 }