Minor documentation edits.
[zddfun.git] / light.c
blobed2bb8a505edb2dc1a05652a724aacafa454df17
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"
11 int main() {
12 zdd_init();
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);
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;
42 die("input error");
44 board[i][j] = encode(c);
46 c = getchar();
47 if (c != '\n') die("input error");
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));
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));
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));
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));
77 for(int k = i + 1; k < rcount && board[k][j] == -1; k++) {
78 inta_append(a, getv(k, j));
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));
88 zdd_contains_at_most_1(inta_raw(a), inta_count(a));
89 zdd_intersection();
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));
97 zdd_contains_at_most_1(inta_raw(a), inta_count(a));
98 // Defer the intersection.
99 colcount++;
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));
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();
119 zdd_intersection();
122 while(colcount) {
123 zdd_intersection();
124 colcount--;
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] = '*';
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]);
150 putchar('\n');
152 putchar('\n');
155 zdd_forall(printsol);
156 return 0;