4700b849 |
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 | |