Minor documentation edits.
[zddfun.git] / tiling_test.c
blob592d6661326621604b33d4797acd38d5213fca32
1 // Test basic ZDD routines by comparing against results in Knuth's book.
2 #include <stdint.h>
3 #include <stdlib.h>
4 #include <stdio.h>
5 #include "inta.h"
6 #include "zdd.h"
7 #include "io.h"
9 inta_t board[8][8];
11 // How many ways can you tile a chessboard with monominoes?
12 // This trivial case serves as a sanity check.
13 void test_monomino_tilings() {
14 int v = 1;
15 for (int i = 0; i < 8; i++) {
16 for (int j = 0; j < 8; j++) {
17 // Monominoes.
18 inta_append(board[i][j], v++);
22 zdd_set_vmax(v - 1);
23 printf("variables: %d\n", zdd_vmax());
24 EXPECT(64 == zdd_vmax());
26 for (int i = 0; i < 8; i++) {
27 for (int j = 0; j < 8; j++) {
28 zdd_contains_exactly_1(inta_raw(board[i][j]), inta_count(board[i][j]));
29 zdd_intersection();
33 printf("nodes: %d\n", zdd_size());
34 EXPECT(zdd_size() == 8 * 8 + 2);
35 mpz_t z, answer;
36 mpz_init(z);
37 mpz_init(answer);
38 mpz_set_str(answer, "1", 0);
40 zdd_count(z);
41 gmp_printf("1-onimo tilings: %Zd\n", z);
42 EXPECT(!mpz_cmp(z, answer));
44 mpz_clear(z);
45 mpz_clear(answer);
46 zdd_pop();
47 // Empty board.
48 for (int i = 0; i < 8; i++) for (int j = 0; j < 8; j++) {
49 inta_remove_all(board[i][j]);
53 // How many ways can you tile a chessboard with dominoes?
54 // Using the obvious approach with ZDDs, we should end up with a 112-variable
55 // 2300-node ZDD describing 12988816 solutions.
56 void test_domino_tilings() {
57 int v = 1;
58 for (int i = 0; i < 8; i++) {
59 for (int j = 0; j < 8; j++) {
60 // Dominoes.
61 if (j != 8 - 1) {
62 inta_append(board[i][j], v);
63 inta_append(board[i][j + 1], v++);
65 if (i != 8 - 1) {
66 inta_append(board[i][j], v);
67 inta_append(board[i + 1][j], v++);
72 zdd_set_vmax(v - 1);
73 printf("variables: %d\n", zdd_vmax());
74 EXPECT(112 == zdd_vmax());
76 for (int i = 0; i < 8; i++) {
77 for (int j = 0; j < 8; j++) {
78 zdd_contains_exactly_1(inta_raw(board[i][j]), inta_count(board[i][j]));
79 zdd_intersection();
83 printf("nodes: %d\n", zdd_size());
84 EXPECT(zdd_size() == 2300);
85 mpz_t z, answer;
86 mpz_init(z);
87 mpz_init(answer);
88 mpz_set_str(answer, "12988816", 0);
90 zdd_count(z);
91 gmp_printf("2-omino tilings: %Zd\n", z);
92 EXPECT(!mpz_cmp(z, answer));
94 mpz_clear(z);
95 mpz_clear(answer);
96 zdd_pop();
97 // Empty board.
98 for (int i = 0; i < 8; i++) for (int j = 0; j < 8; j++) {
99 inta_remove_all(board[i][j]);
103 // How many ways can you tile a chessboard with 1-, 2- and 3-polyonominoes?
104 // We expect 468 variables, 512227 nodes and 92109458286284989468604 solutions.
105 void test_123_tilings() {
106 int v = 1;
107 for (int i = 0; i < 8; i++) {
108 for (int j = 0; j < 8; j++) {
109 // Monominoes.
110 inta_append(board[i][j], v++);
111 // Dominoes.
112 if (j != 8 - 1) {
113 inta_append(board[i][j], v);
114 inta_append(board[i][j + 1], v++);
116 if (i != 8 - 1) {
117 inta_append(board[i][j], v);
118 inta_append(board[i + 1][j], v++);
120 // Trionimoes.
121 // 3x1 trionimoes.
122 if (i < 8 - 2) {
123 inta_append(board[i][j], v);
124 inta_append(board[i + 1][j], v);
125 inta_append(board[i + 2][j], v++);
127 if (j < 8 - 2) {
128 inta_append(board[i][j], v);
129 inta_append(board[i][j + 1], v);
130 inta_append(board[i][j + 2], v++);
132 // 2x2 - 1 tile trionimoes.
133 if (i != 8 - 1 && j != 8 - 1) {
134 inta_append(board[i][j], v);
135 inta_append(board[i + 1][j], v);
136 inta_append(board[i][j + 1], v++);
138 inta_append(board[i][j], v);
139 inta_append(board[i + 1][j], v);
140 inta_append(board[i + 1][j + 1], v++);
142 inta_append(board[i][j], v);
143 inta_append(board[i][j + 1], v);
144 inta_append(board[i + 1][j + 1], v++);
146 inta_append(board[i + 1][j], v);
147 inta_append(board[i][j + 1], v);
148 inta_append(board[i + 1][j + 1], v++);
153 zdd_set_vmax(v - 1);
154 printf("variables: %d\n", zdd_vmax());
155 EXPECT(468 == zdd_vmax());
158 for (int i = 0; i < 8; i++) {
159 for (int j = 0; j < 8; j++) {
160 void print_it(int i) {
161 printf(" %d", i);
163 inta_forall(board[i][j], print_it);
164 printf("\t\t");
166 printf("\n");
169 for (int i = 0; i < 8; i++) {
170 for (int j = 0; j < 8; j++) {
171 zdd_contains_exactly_1(inta_raw(board[i][j]), inta_count(board[i][j]));
172 if (j) zdd_intersection();
174 int n = i + 1;
175 while (!(n & 1)) {
176 n >>= 1;
177 zdd_intersection();
181 printf("nodes: %d\n", zdd_size());
182 EXPECT(zdd_size() == 512227);
183 mpz_t z, answer;
184 mpz_init(z);
185 mpz_init(answer);
186 mpz_set_str(answer, "92109458286284989468604", 0);
188 zdd_count(z);
189 gmp_printf("1-, 2-, 3-omino tilings: %Zd\n", z);
190 EXPECT(!mpz_cmp(z, answer));
192 mpz_clear(z);
193 mpz_clear(answer);
194 zdd_pop();
195 // Empty board.
196 for (int i = 0; i < 8; i++) for (int j = 0; j < 8; j++) {
197 inta_remove_all(board[i][j]);
201 int main() {
202 zdd_init();
203 // Initialize board.
204 for (int i = 0; i < 8; i++) for (int j = 0; j < 8; j++) {
205 inta_init(board[i][j]);
208 test_monomino_tilings();
209 test_domino_tilings();
210 test_123_tilings();
212 // Clear board.
213 for (int i = 0; i < 8; i++) for (int j = 0; j < 8; j++) {
214 inta_clear(board[i][j]);
216 return 0;