tiling_test.c

   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"
   8
   9 inta_t board[8][8];
  10
  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++);
  19     }
  20   }
  21
  22   zdd_set_vmax(v - 1);
  23   printf("variables: %d\n", zdd_vmax());
  24   EXPECT(64 == zdd_vmax());
  25
  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();
  30     }
  31   }
  32
  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);
  39
  40   zdd_count(z);
  41   gmp_printf("1-onimo tilings: %Zd\n", z);
  42   EXPECT(!mpz_cmp(z, answer));
  43
  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]);
  50   }
  51 }
  52
  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++);
  64       }
  65       if (i != 8 - 1) {
  66         inta_append(board[i][j], v);
  67         inta_append(board[i + 1][j], v++);
  68       }
  69     }
  70   }
  71
  72   zdd_set_vmax(v - 1);
  73   printf("variables: %d\n", zdd_vmax());
  74   EXPECT(112 == zdd_vmax());
  75
  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();
  80     }
  81   }
  82
  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);
  89
  90   zdd_count(z);
  91   gmp_printf("2-omino tilings: %Zd\n", z);
  92   EXPECT(!mpz_cmp(z, answer));
  93
  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]);
 100   }
 101 }
 102
 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++);
 115       }
 116       if (i != 8 - 1) {
 117         inta_append(board[i][j], v);
 118         inta_append(board[i + 1][j], v++);
 119       }
 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++);
 126       }
 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++);
 131       }
 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++);
 137
 138         inta_append(board[i][j], v);
 139         inta_append(board[i + 1][j], v);
 140         inta_append(board[i + 1][j + 1], v++);
 141
 142         inta_append(board[i][j], v);
 143         inta_append(board[i][j + 1], v);
 144         inta_append(board[i + 1][j + 1], v++);
 145
 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++);
 149       }
 150     }
 151   }
 152
 153   zdd_set_vmax(v - 1);
 154   printf("variables: %d\n", zdd_vmax());
 155   EXPECT(468 == zdd_vmax());
 156
 157   /*
 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);
 162       }
 163       inta_forall(board[i][j], print_it);
 164       printf("\t\t");
 165     }
 166     printf("\n");
 167   }
 168   */
 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();
 173     }
 174     int n = i + 1;
 175     while (!(n & 1)) {
 176       n >>= 1;
 177       zdd_intersection();
 178     }
 179   }
 180
 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);
 187
 188   zdd_count(z);
 189   gmp_printf("1-, 2-, 3-omino tilings: %Zd\n", z);
 190   EXPECT(!mpz_cmp(z, answer));
 191
 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]);
 198   }
 199 }
 200
 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]);
 206   }
 207
 208   test_monomino_tilings();
 209   test_domino_tilings();
 210   test_123_tilings();
 211
 212   // Clear board.
 213   for (int i = 0; i < 8; i++) for (int j = 0; j < 8; j++) {
 214     inta_clear(board[i][j]);
 215   }
 216   return 0;
 217 }