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.
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);
28 // The last number in the clue for this row.
29 zdd_set_hi(last
, root
);
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
));
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
));
39 return table
[i
][count
];
42 memset(table
, 0, sizeof(uint32_t) * max
* (max
+ 1));
44 for (int i
= 0; i
< size
; i
++) {
47 return partial_row(0, a
, size
, sum
);
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();
59 while(v
< max
* max
) zdd_add_node(v
++, 1, 1);
60 zdd_add_node(v
, -1, -1);
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);
67 uint32_t last
= zdd_last_node();
68 zdd_set_hilo(last
, tail(v
, i
+ 1));
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
];
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);
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);
85 zdd_set_hi(last
, tail(v
, i
+ *a
));
87 while(v
< col
+ 1 + (i
+ *a
) * max
) zdd_add_node(v
++, 1, 1);
89 last
= zdd_last_node();
91 partial_col(v
, i
+ *a
+ 1, a
+ 1, count
- 1, sum
- *a
));
93 if (max
- count
- sum
+ 1 - i
> 0) {
94 zdd_set_lo(first
, partial_col(oldv
, i
+ 1, a
, count
, sum
));
96 return table
[i
][count
];
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
);
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
++) {
113 if (!fgets(s
, 80, stdin
)) {
117 for(int j
= 0; j
< max
; j
++) {
118 if (!sscanf(w
, "%d", &clue
[i
][j
+ 1]) || !clue
[i
][j
+ 1]) {
122 w
= strchr(w
+ 1, ' ');
130 // Construct ZDD for all row clues.
133 for(int i
= max
- 1; i
>= 0; i
--) {
135 root
= add_row_clue(i
, &clue
[i
][1], clue
[i
][0], root
);
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
++) {
144 compute_col_clue(i
, &clue
[i
+ max
][1], clue
[i
+ max
][0]);
145 //printf("column %d: %d\n", i, zdd_next_node());
147 //printf("intersected: %d\n", zdd_next_node());
152 // Print lexicographically largest solution, assuming it exists.
154 memset(board
, 0, sizeof(int) * max
* max
);
155 uint32_t v
= zdd_root();
157 int r
= zdd_v(v
) - 1;
163 for (int i
= 0; i
< max
; i
++) {
164 for (int j
= 0; j
< max
; j
++) {
165 putchar(board
[i
][j
] ? 'X' : '.');