nuri.c

   1 // Solve a Nurikabe puzzle.
   2 #include <stdint.h>
   3 #include <stdlib.h>
   4 #include <stdio.h>
   5 #include <string.h>
   6 #include <gmp.h>
   7 #include "darray.h"
   8 #include "io.h"
   9 #include "zdd.h"
  10
  11 int main() {
  12   zdd_init();
  13   int rcount, ccount;
  14
  15   if (!scanf("%d %d\n", &rcount, &ccount)) die("input error");
  16   int board[rcount][ccount];
  17
  18   for (int i = 0; i < rcount; i++) {
  19     int c;
  20     for (int j = 0; j < ccount; j++) {
  21       c = getchar();
  22       if (c == EOF || c == '\n') die("input error");
  23       int encode(char c) {
  24         switch(c) {
  25           case '.':
  26             return 0;
  27             break;
  28           case '1' ... '9':
  29             return c - '0';
  30             break;
  31           case 'a' ... 'z':
  32             return c - 'a' + 10;
  33             break;
  34           case 'A' ... 'Z':
  35             return c - 'A' + 10;
  36             break;
  37         }
  38         die("input error");
  39       }
  40       board[i][j] = encode(c);
  41     }
  42     c = getchar();
  43     if (c != '\n') die("input error");
  44   }
  45   zdd_set_vmax(rcount * ccount);
  46
  47   // Label squares according to this scheme:
  48   //   1 2 4 ...
  49   //   3 5 ...
  50   //   6 ...
  51   int vtab[rcount][ccount];
  52   int rtab[zdd_vmax() + 1], ctab[zdd_vmax() + 1];
  53   int v = 1;
  54   int i = 0, j = 0;
  55   for(;;) {
  56     rtab[v] = i;
  57     ctab[v] = j;
  58     vtab[i][j] = v++;
  59     if (v > zdd_vmax()) break;
  60     // If we're on the left or bottom edge:
  61     if (i == rcount - 1 || !j) {
  62       // Try advancing to the top of the column.
  63       j = i + j + 1;
  64       i = 0;
  65       if (j >= ccount) {
  66         // If it's out of bounds, move diagonally bottom-left.
  67         i = j - (ccount - 1);
  68         j = ccount - 1;
  69       }
  70     } else {
  71       i++, j--;
  72     }
  73   }
  74
  75   // The state represents which squares are connected.
  76   // state[i] = -2: i is not selected.
  77   // state[i] = -1: i is unconnected to anything else in the state.
  78   // state[i] = i - j: i is connected to j and j is the largest square less
  79   // than i with this property.
  80   void recurse(int v, char* state, int start, int size) {
  81     int r = rtab[v];
  82     int c = ctab[v];
  83
  84     int newsize = size;
  85     if (r - 1 < 0 || c - 1 < 0) newsize++;
  86     char newstate[newsize];
  87     for (int i = 0; i < size; i++) newstate[i] = state[i];
  88     // Omit v:
  89     newstate[v] = -1;
  90     // Include v:
  91     //newstate[v] =
  92   }
  93   recurse(1, NULL, 0, 0);
  94
  95   return 0;
  96 }