| 1 | /* |
| 2 | * laydomino.c: code for performing a domino (2x1 tile) layout of |
| 3 | * a given area of code. |
| 4 | */ |
| 5 | |
| 6 | #include <stdio.h> |
| 7 | #include <stdlib.h> |
| 8 | #include <assert.h> |
| 9 | |
| 10 | #include "puzzles.h" |
| 11 | |
| 12 | /* |
| 13 | * This function returns an array size w x h representing a grid: |
| 14 | * each grid[i] = j, where j is the other end of a 2x1 domino. |
| 15 | * If w*h is odd, one square will remain referring to itself. |
| 16 | */ |
| 17 | |
| 18 | int *domino_layout(int w, int h, random_state *rs) |
| 19 | { |
| 20 | int *grid, *grid2, *list; |
| 21 | int wh = w*h; |
| 22 | |
| 23 | /* |
| 24 | * Allocate space in which to lay the grid out. |
| 25 | */ |
| 26 | grid = snewn(wh, int); |
| 27 | grid2 = snewn(wh, int); |
| 28 | list = snewn(2*wh, int); |
| 29 | |
| 30 | domino_layout_prealloc(w, h, rs, grid, grid2, list); |
| 31 | |
| 32 | sfree(grid2); |
| 33 | sfree(list); |
| 34 | |
| 35 | return grid; |
| 36 | } |
| 37 | |
| 38 | /* |
| 39 | * As for domino_layout, but with preallocated buffers. |
| 40 | * grid and grid2 should be size w*h, and list size 2*w*h. |
| 41 | */ |
| 42 | void domino_layout_prealloc(int w, int h, random_state *rs, |
| 43 | int *grid, int *grid2, int *list) |
| 44 | { |
| 45 | int i, j, k, m, wh = w*h, todo, done; |
| 46 | |
| 47 | /* |
| 48 | * To begin with, set grid[i] = i for all i to indicate |
| 49 | * that all squares are currently singletons. Later we'll |
| 50 | * set grid[i] to be the index of the other end of the |
| 51 | * domino on i. |
| 52 | */ |
| 53 | for (i = 0; i < wh; i++) |
| 54 | grid[i] = i; |
| 55 | |
| 56 | /* |
| 57 | * Now prepare a list of the possible domino locations. There |
| 58 | * are w*(h-1) possible vertical locations, and (w-1)*h |
| 59 | * horizontal ones, for a total of 2*wh - h - w. |
| 60 | * |
| 61 | * I'm going to denote the vertical domino placement with |
| 62 | * its top in square i as 2*i, and the horizontal one with |
| 63 | * its left half in square i as 2*i+1. |
| 64 | */ |
| 65 | k = 0; |
| 66 | for (j = 0; j < h-1; j++) |
| 67 | for (i = 0; i < w; i++) |
| 68 | list[k++] = 2 * (j*w+i); /* vertical positions */ |
| 69 | for (j = 0; j < h; j++) |
| 70 | for (i = 0; i < w-1; i++) |
| 71 | list[k++] = 2 * (j*w+i) + 1; /* horizontal positions */ |
| 72 | assert(k == 2*wh - h - w); |
| 73 | |
| 74 | /* |
| 75 | * Shuffle the list. |
| 76 | */ |
| 77 | shuffle(list, k, sizeof(*list), rs); |
| 78 | |
| 79 | /* |
| 80 | * Work down the shuffled list, placing a domino everywhere |
| 81 | * we can. |
| 82 | */ |
| 83 | for (i = 0; i < k; i++) { |
| 84 | int horiz, xy, xy2; |
| 85 | |
| 86 | horiz = list[i] % 2; |
| 87 | xy = list[i] / 2; |
| 88 | xy2 = xy + (horiz ? 1 : w); |
| 89 | |
| 90 | if (grid[xy] == xy && grid[xy2] == xy2) { |
| 91 | /* |
| 92 | * We can place this domino. Do so. |
| 93 | */ |
| 94 | grid[xy] = xy2; |
| 95 | grid[xy2] = xy; |
| 96 | } |
| 97 | } |
| 98 | |
| 99 | #ifdef GENERATION_DIAGNOSTICS |
| 100 | printf("generated initial layout\n"); |
| 101 | #endif |
| 102 | |
| 103 | /* |
| 104 | * Now we've placed as many dominoes as we can immediately |
| 105 | * manage. There will be squares remaining, but they'll be |
| 106 | * singletons. So loop round and deal with the singletons |
| 107 | * two by two. |
| 108 | */ |
| 109 | while (1) { |
| 110 | #ifdef GENERATION_DIAGNOSTICS |
| 111 | for (j = 0; j < h; j++) { |
| 112 | for (i = 0; i < w; i++) { |
| 113 | int xy = j*w+i; |
| 114 | int v = grid[xy]; |
| 115 | int c = (v == xy+1 ? '[' : v == xy-1 ? ']' : |
| 116 | v == xy+w ? 'n' : v == xy-w ? 'U' : '.'); |
| 117 | putchar(c); |
| 118 | } |
| 119 | putchar('\n'); |
| 120 | } |
| 121 | putchar('\n'); |
| 122 | #endif |
| 123 | |
| 124 | /* |
| 125 | * Our strategy is: |
| 126 | * |
| 127 | * First find a singleton square. |
| 128 | * |
| 129 | * Then breadth-first search out from the starting |
| 130 | * square. From that square (and any others we reach on |
| 131 | * the way), examine all four neighbours of the square. |
| 132 | * If one is an end of a domino, we move to the _other_ |
| 133 | * end of that domino before looking at neighbours |
| 134 | * again. When we encounter another singleton on this |
| 135 | * search, stop. |
| 136 | * |
| 137 | * This will give us a path of adjacent squares such |
| 138 | * that all but the two ends are covered in dominoes. |
| 139 | * So we can now shuffle every domino on the path up by |
| 140 | * one. |
| 141 | * |
| 142 | * (Chessboard colours are mathematically important |
| 143 | * here: we always end up pairing each singleton with a |
| 144 | * singleton of the other colour. However, we never |
| 145 | * have to track this manually, since it's |
| 146 | * automatically taken care of by the fact that we |
| 147 | * always make an even number of orthogonal moves.) |
| 148 | */ |
| 149 | k = 0; |
| 150 | for (j = 0; j < wh; j++) { |
| 151 | if (grid[j] == j) { |
| 152 | k++; |
| 153 | i = j; /* start BFS here. */ |
| 154 | } |
| 155 | } |
| 156 | if (k == (wh % 2)) |
| 157 | break; /* if area is even, we have no more singletons; |
| 158 | if area is odd, we have one singleton. |
| 159 | either way, we're done. */ |
| 160 | |
| 161 | #ifdef GENERATION_DIAGNOSTICS |
| 162 | printf("starting b.f.s. at singleton %d\n", i); |
| 163 | #endif |
| 164 | /* |
| 165 | * Set grid2 to -1 everywhere. It will hold our |
| 166 | * distance-from-start values, and also our |
| 167 | * backtracking data, during the b.f.s. |
| 168 | */ |
| 169 | for (j = 0; j < wh; j++) |
| 170 | grid2[j] = -1; |
| 171 | grid2[i] = 0; /* starting square has distance zero */ |
| 172 | |
| 173 | /* |
| 174 | * Start our to-do list of squares. It'll live in |
| 175 | * `list'; since the b.f.s can cover every square at |
| 176 | * most once there is no need for it to be circular. |
| 177 | * We'll just have two counters tracking the end of the |
| 178 | * list and the squares we've already dealt with. |
| 179 | */ |
| 180 | done = 0; |
| 181 | todo = 1; |
| 182 | list[0] = i; |
| 183 | |
| 184 | /* |
| 185 | * Now begin the b.f.s. loop. |
| 186 | */ |
| 187 | while (done < todo) { |
| 188 | int d[4], nd, x, y; |
| 189 | |
| 190 | i = list[done++]; |
| 191 | |
| 192 | #ifdef GENERATION_DIAGNOSTICS |
| 193 | printf("b.f.s. iteration from %d\n", i); |
| 194 | #endif |
| 195 | x = i % w; |
| 196 | y = i / w; |
| 197 | nd = 0; |
| 198 | if (x > 0) |
| 199 | d[nd++] = i - 1; |
| 200 | if (x+1 < w) |
| 201 | d[nd++] = i + 1; |
| 202 | if (y > 0) |
| 203 | d[nd++] = i - w; |
| 204 | if (y+1 < h) |
| 205 | d[nd++] = i + w; |
| 206 | /* |
| 207 | * To avoid directional bias, process the |
| 208 | * neighbours of this square in a random order. |
| 209 | */ |
| 210 | shuffle(d, nd, sizeof(*d), rs); |
| 211 | |
| 212 | for (j = 0; j < nd; j++) { |
| 213 | k = d[j]; |
| 214 | if (grid[k] == k) { |
| 215 | #ifdef GENERATION_DIAGNOSTICS |
| 216 | printf("found neighbouring singleton %d\n", k); |
| 217 | #endif |
| 218 | grid2[k] = i; |
| 219 | break; /* found a target singleton! */ |
| 220 | } |
| 221 | |
| 222 | /* |
| 223 | * We're moving through a domino here, so we |
| 224 | * have two entries in grid2 to fill with |
| 225 | * useful data. In grid[k] - the square |
| 226 | * adjacent to where we came from - I'm going |
| 227 | * to put the address _of_ the square we came |
| 228 | * from. In the other end of the domino - the |
| 229 | * square from which we will continue the |
| 230 | * search - I'm going to put the distance. |
| 231 | */ |
| 232 | m = grid[k]; |
| 233 | |
| 234 | if (grid2[m] < 0 || grid2[m] > grid2[i]+1) { |
| 235 | #ifdef GENERATION_DIAGNOSTICS |
| 236 | printf("found neighbouring domino %d/%d\n", k, m); |
| 237 | #endif |
| 238 | grid2[m] = grid2[i]+1; |
| 239 | grid2[k] = i; |
| 240 | /* |
| 241 | * And since we've now visited a new |
| 242 | * domino, add m to the to-do list. |
| 243 | */ |
| 244 | assert(todo < wh); |
| 245 | list[todo++] = m; |
| 246 | } |
| 247 | } |
| 248 | |
| 249 | if (j < nd) { |
| 250 | i = k; |
| 251 | #ifdef GENERATION_DIAGNOSTICS |
| 252 | printf("terminating b.f.s. loop, i = %d\n", i); |
| 253 | #endif |
| 254 | break; |
| 255 | } |
| 256 | |
| 257 | i = -1; /* just in case the loop terminates */ |
| 258 | } |
| 259 | |
| 260 | /* |
| 261 | * We expect this b.f.s. to have found us a target |
| 262 | * square. |
| 263 | */ |
| 264 | assert(i >= 0); |
| 265 | |
| 266 | /* |
| 267 | * Now we can follow the trail back to our starting |
| 268 | * singleton, re-laying dominoes as we go. |
| 269 | */ |
| 270 | while (1) { |
| 271 | j = grid2[i]; |
| 272 | assert(j >= 0 && j < wh); |
| 273 | k = grid[j]; |
| 274 | |
| 275 | grid[i] = j; |
| 276 | grid[j] = i; |
| 277 | #ifdef GENERATION_DIAGNOSTICS |
| 278 | printf("filling in domino %d/%d (next %d)\n", i, j, k); |
| 279 | #endif |
| 280 | if (j == k) |
| 281 | break; /* we've reached the other singleton */ |
| 282 | i = k; |
| 283 | } |
| 284 | #ifdef GENERATION_DIAGNOSTICS |
| 285 | printf("fixup path completed\n"); |
| 286 | #endif |
| 287 | } |
| 288 | } |
| 289 | |
| 290 | /* vim: set shiftwidth=4 :set textwidth=80: */ |
| 291 | |