nono.c

   1 // Nonogram solver.
   2 #include <stdint.h>
   3 #include <stdlib.h>
   4 #include <stdio.h>
   5 #include <string.h>
   6 #include "zdd.h"
   7 #include <stdarg.h>
   8 #include "io.h"
   9
  10 static int max;
  11
  12 // Build ZDD for given row clues, and the root of the ZDD for all later rows.
  13 // Call this from the bottom row to the top row to produce the ZDD of all
  14 // sets satisfying the row clues.
  15 uint32_t add_row_clue(int row, int *a, int size, int root) {
  16   uint32_t v = row * max + 1;
  17   uint32_t table[max][max + 1];
  18   uint32_t partial_row(uint32_t i, int *a, int count, int sum) {
  19     // Return old result if already computed.
  20     if (table[i][count] != 0) return table[i][count];
  21     // Handle the case when the first coloured segment appears immediately.
  22     uint32_t first, last;
  23     first = last = table[i][count] = zdd_add_node(v + i, 0, 1);
  24     for(int j = 1; j < *a; j++) {
  25       last = zdd_add_node(v + i + j, 0, 1);
  26     }
  27     if (1 == count) {
  28       // The last number in the clue for this row.
  29       zdd_set_hi(last, root);
  30     } else {
  31       // Hop over the next node; it must be false, as it represents a gap
  32       // between two coloured segments.
  33       zdd_set_hi(last, partial_row(i + *a + 1, a + 1, count - 1, sum - *a));
  34     }
  35     // Recurse for all other cases, if applicable.
  36     if (max - count - sum + 1 - i > 0) {
  37       zdd_set_lo(first, partial_row(i + 1, a, count, sum));
  38     }
  39     return table[i][count];
  40   }
  41
  42   memset(table, 0, sizeof(uint32_t) * max * (max + 1));
  43   int sum = 0;
  44   for (int i = 0; i < size; i++) {
  45     sum += a[i];
  46   }
  47   return partial_row(0, a, size, sum);
  48 }
  49
  50 uint32_t compute_col_clue(int col, int *a, int size) {
  51   uint32_t table[max + 1][max + 1];
  52   memset(table, 0, sizeof(uint32_t) * (max + 1) * (max + 1));
  53   // Variables outside this column can be in our out, so until we reach
  54   // the last node we send both edges to the next node.
  55   uint32_t tail(uint32_t v, uint32_t i) {
  56     if (table[i][0] != 0) return table[i][0];
  57     table[i][0] = zdd_next_node();
  58     if (max == i) {
  59       while(v < max * max) zdd_add_node(v++, 1, 1);
  60       zdd_add_node(v, -1, -1);
  61     } else {
  62       // Keep adding nodes until we reach this column again. Hop over the
  63       // next node because it is part of the blank space after the last
  64       // coloured segment in this column.
  65       while(v < max * i + col + 1) zdd_add_node(v++, 1, 1);
  66       v++;
  67       uint32_t last = zdd_last_node();
  68       zdd_set_hilo(last, tail(v, i + 1));
  69     }
  70     return table[i][0];
  71   }
  72   uint32_t partial_col(uint32_t v, uint32_t i, int *a, int count, int sum) {
  73     if (table[i][count] != 0) return table[i][count];
  74     uint32_t first, last;
  75     table[i][count] = zdd_next_node();
  76     // Variables outside this column can be in our out.
  77     while(v < col + 1 + i * max) zdd_add_node(v++, 1, 1);
  78     first = last = zdd_add_node(v++, 0, 1);
  79     uint32_t oldv = v;
  80     for(int j = 1; j < *a; j++) {
  81       while(v < col + 1 + (i + j) * max) zdd_add_node(v++, 1, 1);
  82       last = zdd_add_node(v++, 0, 1);
  83     }
  84     if (1 == count) {
  85       zdd_set_hi(last, tail(v, i + *a));
  86     } else {
  87       while(v < col + 1 + (i + *a) * max) zdd_add_node(v++, 1, 1);
  88       v++;
  89       last = zdd_last_node();
  90       zdd_set_hilo(last,
  91           partial_col(v, i + *a + 1, a + 1, count - 1, sum - *a));
  92     }
  93     if (max - count - sum + 1 - i > 0) {
  94       zdd_set_lo(first, partial_col(oldv, i + 1, a, count, sum));
  95     }
  96     return table[i][count];
  97   }
  98
  99   int sum = 0;
 100   for (int i = 0; i <= max; i++) for (int j = 0; j <= max; j++) table[i][j] = 0;
 101   for (int i = 0; i < size; i++) sum += a[i];
 102   if (!size) return tail(1, 0);
 103   return partial_col(1, 0, a, size, sum);
 104 }
 105
 106 int main() {
 107   zdd_init();
 108   if (!scanf("%d\n", &max)) die("input error");
 109   // Read max row clues, then max column clues.
 110   int clue[max * 2][max + 1];
 111   for(int i = 0; i < max * 2; i++) {
 112     char s[80];
 113     if (!fgets(s, 80, stdin)) {
 114       die("input error");
 115     }
 116     char *w = s;
 117     for(int j = 0; j < max; j++) {
 118       if (!sscanf(w, "%d", &clue[i][j + 1]) || !clue[i][j + 1]) {
 119         clue[i][0] = j;
 120         break;
 121       }
 122       w = strchr(w + 1, ' ');
 123       if (!w) {
 124         clue[i][0] = j + 1;
 125         break;
 126       }
 127     }
 128   }
 129
 130   // Construct ZDD for all row clues.
 131   zdd_push();
 132   uint32_t root = 1;
 133   for(int i = max - 1; i >= 0; i--) {
 134     if (clue[i][0]) {
 135       root = add_row_clue(i, &clue[i][1], clue[i][0], root);
 136     }
 137   }
 138   zdd_set_root(root);
 139
 140   //printf("all rows: %d\n", zdd_next_node());
 141   // Intersect each column clue into the ZDD
 142   for(int i = 0; i < max; i++) {
 143     zdd_push();
 144     compute_col_clue(i, &clue[i + max][1], clue[i + max][0]);
 145     //printf("column %d: %d\n", i, zdd_next_node());
 146     zdd_intersection();
 147     //printf("intersected: %d\n", zdd_next_node());
 148   }
 149
 150   zdd_check();
 151
 152   // Print lexicographically largest solution, assuming it exists.
 153   int board[max][max];
 154   memset(board, 0, sizeof(int) * max * max);
 155   uint32_t v = zdd_root();
 156   while(v != 1) {
 157     int r = zdd_v(v) - 1;
 158     int c = r % max;
 159     r /= max;
 160     board[r][c] = 1;
 161     v = zdd_hi(v);
 162   }
 163   for (int i = 0; i < max; i++) {
 164     for (int j = 0; j < max; j++) {
 165       putchar(board[i][j] ? 'X' : '.');
 166     }
 167     putchar('\n');
 168   }
 169
 170   return 0;
 171 }