11d273f7 |
1 | /* |
2 | * Library code to divide up a rectangle into a number of equally |
3 | * sized ominoes, in a random fashion. |
4 | * |
5 | * Could use this for generating solved grids of |
6 | * http://www.nikoli.co.jp/ja/puzzles/block_puzzle/ |
7 | * or for generating the playfield for Jigsaw Sudoku. |
8 | */ |
9 | |
9d36cbd7 |
10 | /* |
82ed4789 |
11 | * This code is restricted to simply connected solutions: that is, |
12 | * no single polyomino may completely surround another (not even |
13 | * with a corner visible to the outside world, in the sense that a |
14 | * 7-omino can `surround' a single square). |
15 | * |
16 | * It's tempting to think that this is a natural consequence of |
17 | * all the ominoes being the same size - after all, a division of |
18 | * anything into 7-ominoes must necessarily have all of them |
19 | * simply connected, because if one was not then the 1-square |
20 | * space in the middle could not be part of any 7-omino - but in |
21 | * fact, for sufficiently large k, it is perfectly possible for a |
22 | * k-omino to completely surround another k-omino. A simple |
23 | * example is this one with two 25-ominoes: |
24 | * |
25 | * +--+--+--+--+--+--+--+ |
26 | * | | |
27 | * + +--+--+--+--+--+ + |
28 | * | | | | |
29 | * + + + + |
30 | * | | | | |
31 | * + + + +--+ |
32 | * | | | | |
33 | * + + + +--+ |
34 | * | | | | |
35 | * + + + + |
36 | * | | | | |
37 | * + +--+--+--+--+--+ + |
38 | * | | |
39 | * +--+--+--+--+--+--+--+ |
40 | * |
2b3825a0 |
41 | * I claim the smallest k which can manage this is 23. More |
42 | * formally: |
43 | * |
44 | * If a k-omino P is completely surrounded by another k-omino Q, |
45 | * such that every edge of P borders on Q, then k >= 23. |
46 | * |
47 | * Proof: |
48 | * |
49 | * It's relatively simple to find the largest _rectangle_ a |
50 | * k-omino can enclose. So I'll construct my proof in two parts: |
51 | * firstly, show that no 22-omino or smaller can enclose a |
52 | * rectangle as large as itself, and secondly, show that no |
53 | * polyomino can enclose a larger non-rectangle than a rectangle. |
54 | * |
55 | * The first of those claims: |
56 | * |
57 | * To surround an m x n rectangle, a polyomino must have 2m |
58 | * squares along the two m-sides of the rectangle, 2n squares |
59 | * along the two n-sides, and must fill in at least three of the |
60 | * corners in order to be connected. Thus, 2(m+n)+3 <= k. We wish |
61 | * to find the largest value of mn subject to that constraint, and |
62 | * it's clear that this is achieved when m and n are as close to |
63 | * equal as possible. (If they aren't, WLOG suppose m < n; then |
64 | * (m+1)(n-1) = mn + n - m - 1 >= mn, with equality only when |
65 | * m=n-1.) |
66 | * |
67 | * So the area of the largest rectangle which can be enclosed by a |
68 | * k-omino is given by floor(k'/2) * ceil(k'/2), where k' = |
69 | * (k-3)/2. This is a monotonic function in k, so there will be a |
70 | * unique point at which it goes from being smaller than k to |
71 | * being larger than k. That point is between 22 (maximum area 20) |
72 | * and 23 (maximum area 25). |
73 | * |
74 | * The second claim: |
75 | * |
76 | * Suppose we have an inner polyomino P surrounded by an outer |
77 | * polyomino Q. I seek to show that if P is non-rectangular, then |
78 | * P is also non-maximal, in the sense that we can transform P and |
79 | * Q into a new pair of polyominoes in which P is larger and Q is |
80 | * at most the same size. |
81 | * |
82 | * Consider walking along the boundary of P in a clockwise |
83 | * direction. (We may assume, of course, that there is only _one_ |
84 | * boundary of P, i.e. P has no hole in the middle. If it does |
85 | * have a hole in the middle, it's _trivially_ non-maximal because |
86 | * we can just fill the hole in!) Our walk will take us along many |
87 | * edges between squares; sometimes we might turn left, and |
88 | * certainly sometimes we will turn right. Always there will be a |
89 | * square of P on our right, and a square of Q on our left. |
90 | * |
91 | * The net angle through which we turn during the entire walk must |
92 | * add up to 360 degrees rightwards. So if there are no left |
93 | * turns, then we must turn right exactly four times, meaning we |
94 | * have described a rectangle. Hence, if P is _not_ rectangular, |
95 | * then there must have been a left turn at some point. A left |
96 | * turn must mean we walk along two edges of the same square of Q. |
97 | * |
98 | * Thus, there is some square X in Q which is adjacent to two |
99 | * diagonally separated squares in P. Let us call those two |
100 | * squares N and E; let us refer to the other two neighbours of X |
101 | * as S and W; let us refer to the other mutual neighbour of S and |
102 | * W as D; and let us refer to the other mutual neighbour of S and |
103 | * E as Y. In other words, we have named seven squares, arranged |
104 | * thus: |
105 | * |
106 | * N |
107 | * W X E |
108 | * D S Y |
109 | * |
110 | * where N and E are in P, and X is in Q. |
111 | * |
112 | * Clearly at least one of W and S must be in Q (because otherwise |
113 | * X would not be connected to any other square in Q, and would |
114 | * hence have to be the whole of Q; and evidently if Q were a |
115 | * 1-omino it could not enclose _anything_). So we divide into |
116 | * cases: |
117 | * |
118 | * If both W and S are in Q, then we take X out of Q and put it in |
119 | * P, which does not expose any edge of P. If this disconnects Q, |
120 | * then we can reconnect it by adding D to Q. |
121 | * |
122 | * If only one of W and S is in Q, then wlog let it be W. If S is |
123 | * in _P_, then we have a particularly easy case: we can simply |
124 | * take X out of Q and add it to P, and this cannot disconnect X |
125 | * since X was a leaf square of Q. |
126 | * |
127 | * Our remaining case is that W is in Q and S is in neither P nor |
128 | * Q. Again we take X out of Q and put it in P; we also add S to |
129 | * Q. This ensures we do not expose an edge of P, but we must now |
130 | * prove that S is adjacent to some other existing square of Q so |
131 | * that we haven't disconnected Q by adding it. |
132 | * |
133 | * To do this, we recall that we walked along the edge XE, and |
134 | * then turned left to walk along XN. So just before doing all |
135 | * that, we must have reached the corner XSE, and we must have |
136 | * done it by walking along one of the three edges meeting at that |
137 | * corner which are _not_ XE. It can't have been SY, since S would |
138 | * then have been on our left and it isn't in Q; and it can't have |
139 | * been XS, since S would then have been on our right and it isn't |
140 | * in P. So it must have been YE, in which case Y was on our left, |
141 | * and hence is in Q. |
142 | * |
143 | * So in all cases we have shown that we can take X out of Q and |
144 | * add it to P, and add at most one square to Q to restore the |
145 | * containment and connectedness properties. Hence, we can keep |
146 | * doing this until we run out of left turns and P becomes |
147 | * rectangular. [] |
148 | * |
149 | * ------------ |
150 | * |
151 | * Anyway, that entire proof was a bit of a sidetrack. The point |
152 | * is, although constructions of this type are possible for |
153 | * sufficiently large k, divvy_rectangle() will never generate |
154 | * them. This could be considered a weakness for some purposes, in |
155 | * the sense that we can't generate all possible divisions. |
156 | * However, there are many divisions which we are highly unlikely |
157 | * to generate anyway, so in practice it probably isn't _too_ bad. |
82ed4789 |
158 | * |
159 | * If I wanted to fix this issue, I would have to make the rules |
160 | * more complicated for determining when a square can safely be |
161 | * _removed_ from a polyomino. Adding one becomes easier (a square |
162 | * may be added to a polyomino iff it is 4-adjacent to any square |
163 | * currently part of the polyomino, and the current test for loop |
164 | * formation may be dispensed with), but to determine which |
165 | * squares may be removed we must now resort to analysis of the |
166 | * overall structure of the polyomino rather than the simple local |
167 | * properties we can currently get away with measuring. |
168 | */ |
169 | |
170 | /* |
9d36cbd7 |
171 | * Possible improvements which might cut the fail rate: |
172 | * |
173 | * - instead of picking one omino to extend in an iteration, try |
174 | * them all in succession (in a randomised order) |
175 | * |
176 | * - (for real rigour) instead of bfsing over ominoes, bfs over |
177 | * the space of possible _removed squares_. That way we aren't |
178 | * limited to randomly choosing a single square to remove from |
179 | * an omino and failing if that particular square doesn't |
180 | * happen to work. |
181 | * |
4d31c526 |
182 | * However, I don't currently think it's necessary to do either of |
183 | * these, because the failure rate is already low enough to be |
184 | * easily tolerable, under all circumstances I've been able to |
185 | * think of. |
9d36cbd7 |
186 | */ |
187 | |
11d273f7 |
188 | #include <assert.h> |
189 | #include <stdio.h> |
190 | #include <stdlib.h> |
191 | #include <stddef.h> |
192 | |
193 | #include "puzzles.h" |
194 | |
195 | /* |
196 | * Subroutine which implements a function used in computing both |
197 | * whether a square can safely be added to an omino, and whether |
198 | * it can safely be removed. |
199 | * |
200 | * We enumerate the eight squares 8-adjacent to this one, in |
201 | * cyclic order. We go round that loop and count the number of |
202 | * times we find a square owned by the target omino next to one |
203 | * not owned by it. We then return success iff that count is 2. |
204 | * |
205 | * When adding a square to an omino, this is precisely the |
206 | * criterion which tells us that adding the square won't leave a |
a9ea89c5 |
207 | * hole in the middle of the omino. (If it did, then things get |
208 | * more complicated; see above.) |
11d273f7 |
209 | * |
210 | * When removing a square from an omino, the _same_ criterion |
211 | * tells us that removing the square won't disconnect the omino. |
a9ea89c5 |
212 | * (This only works _because_ we've ensured the omino is simply |
213 | * connected.) |
11d273f7 |
214 | */ |
215 | static int addremcommon(int w, int h, int x, int y, int *own, int val) |
216 | { |
217 | int neighbours[8]; |
218 | int dir, count; |
219 | |
220 | for (dir = 0; dir < 8; dir++) { |
221 | int dx = ((dir & 3) == 2 ? 0 : dir > 2 && dir < 6 ? +1 : -1); |
222 | int dy = ((dir & 3) == 0 ? 0 : dir < 4 ? -1 : +1); |
223 | int sx = x+dx, sy = y+dy; |
224 | |
225 | if (sx < 0 || sx >= w || sy < 0 || sy >= h) |
226 | neighbours[dir] = -1; /* outside the grid */ |
227 | else |
228 | neighbours[dir] = own[sy*w+sx]; |
229 | } |
230 | |
231 | /* |
232 | * To begin with, check 4-adjacency. |
233 | */ |
234 | if (neighbours[0] != val && neighbours[2] != val && |
235 | neighbours[4] != val && neighbours[6] != val) |
236 | return FALSE; |
237 | |
238 | count = 0; |
239 | |
240 | for (dir = 0; dir < 8; dir++) { |
241 | int next = (dir + 1) & 7; |
242 | int gotthis = (neighbours[dir] == val); |
243 | int gotnext = (neighbours[next] == val); |
244 | |
245 | if (gotthis != gotnext) |
246 | count++; |
247 | } |
248 | |
249 | return (count == 2); |
250 | } |
251 | |
252 | /* |
253 | * w and h are the dimensions of the rectangle. |
254 | * |
255 | * k is the size of the required ominoes. (So k must divide w*h, |
256 | * of course.) |
257 | * |
258 | * The returned result is a w*h-sized dsf. |
259 | * |
260 | * In both of the above suggested use cases, the user would |
261 | * probably want w==h==k, but that isn't a requirement. |
262 | */ |
9d36cbd7 |
263 | static int *divvy_internal(int w, int h, int k, random_state *rs) |
11d273f7 |
264 | { |
265 | int *order, *queue, *tmp, *own, *sizes, *addable, *removable, *retdsf; |
266 | int wh = w*h; |
267 | int i, j, n, x, y, qhead, qtail; |
268 | |
269 | n = wh / k; |
270 | assert(wh == k*n); |
271 | |
272 | order = snewn(wh, int); |
273 | tmp = snewn(wh, int); |
274 | own = snewn(wh, int); |
275 | sizes = snewn(n, int); |
276 | queue = snewn(n, int); |
277 | addable = snewn(wh*4, int); |
278 | removable = snewn(wh, int); |
279 | |
280 | /* |
281 | * Permute the grid squares into a random order, which will be |
282 | * used for iterating over the grid whenever we need to search |
283 | * for something. This prevents directional bias and arranges |
284 | * for the answer to be non-deterministic. |
285 | */ |
286 | for (i = 0; i < wh; i++) |
287 | order[i] = i; |
288 | shuffle(order, wh, sizeof(*order), rs); |
289 | |
290 | /* |
291 | * Begin by choosing a starting square at random for each |
292 | * omino. |
293 | */ |
294 | for (i = 0; i < wh; i++) { |
295 | own[i] = -1; |
296 | } |
297 | for (i = 0; i < n; i++) { |
298 | own[order[i]] = i; |
299 | sizes[i] = 1; |
300 | } |
301 | |
302 | /* |
303 | * Now repeatedly pick a random omino which isn't already at |
304 | * the target size, and find a way to expand it by one. This |
305 | * may involve stealing a square from another omino, in which |
306 | * case we then re-expand that omino, forming a chain of |
307 | * square-stealing which terminates in an as yet unclaimed |
308 | * square. Hence every successful iteration around this loop |
309 | * causes the number of unclaimed squares to drop by one, and |
310 | * so the process is bounded in duration. |
311 | */ |
312 | while (1) { |
313 | |
314 | #ifdef DIVVY_DIAGNOSTICS |
315 | { |
316 | int x, y; |
317 | printf("Top of loop. Current grid:\n"); |
318 | for (y = 0; y < h; y++) { |
319 | for (x = 0; x < w; x++) |
320 | printf("%3d", own[y*w+x]); |
321 | printf("\n"); |
322 | } |
323 | } |
324 | #endif |
325 | |
326 | /* |
327 | * Go over the grid and figure out which squares can |
328 | * safely be added to, or removed from, each omino. We |
329 | * don't take account of other ominoes in this process, so |
330 | * we will often end up knowing that a square can be |
331 | * poached from one omino by another. |
332 | * |
333 | * For each square, there may be up to four ominoes to |
334 | * which it can be added (those to which it is |
335 | * 4-adjacent). |
336 | */ |
337 | for (y = 0; y < h; y++) { |
338 | for (x = 0; x < w; x++) { |
339 | int yx = y*w+x; |
340 | int curr = own[yx]; |
341 | int dir; |
342 | |
343 | if (curr < 0) { |
9d36cbd7 |
344 | removable[yx] = FALSE; /* can't remove if not owned! */ |
345 | } else if (sizes[curr] == 1) { |
346 | removable[yx] = TRUE; /* can always remove a singleton */ |
11d273f7 |
347 | } else { |
348 | /* |
349 | * See if this square can be removed from its |
350 | * omino without disconnecting it. |
351 | */ |
352 | removable[yx] = addremcommon(w, h, x, y, own, curr); |
353 | } |
354 | |
355 | for (dir = 0; dir < 4; dir++) { |
356 | int dx = (dir == 0 ? -1 : dir == 1 ? +1 : 0); |
357 | int dy = (dir == 2 ? -1 : dir == 3 ? +1 : 0); |
358 | int sx = x + dx, sy = y + dy; |
359 | int syx = sy*w+sx; |
360 | |
361 | addable[yx*4+dir] = -1; |
362 | |
363 | if (sx < 0 || sx >= w || sy < 0 || sy >= h) |
364 | continue; /* no omino here! */ |
365 | if (own[syx] < 0) |
366 | continue; /* also no omino here */ |
367 | if (own[syx] == own[yx]) |
368 | continue; /* we already got one */ |
369 | if (!addremcommon(w, h, x, y, own, own[syx])) |
370 | continue; /* would non-simply connect the omino */ |
371 | |
372 | addable[yx*4+dir] = own[syx]; |
373 | } |
374 | } |
375 | } |
376 | |
377 | for (i = j = 0; i < n; i++) |
378 | if (sizes[i] < k) |
379 | tmp[j++] = i; |
380 | if (j == 0) |
381 | break; /* all ominoes are complete! */ |
382 | j = tmp[random_upto(rs, j)]; |
f40d37bd |
383 | #ifdef DIVVY_DIAGNOSTICS |
384 | printf("Trying to extend %d\n", j); |
385 | #endif |
11d273f7 |
386 | |
387 | /* |
388 | * So we're trying to expand omino j. We breadth-first |
389 | * search out from j across the space of ominoes. |
390 | * |
391 | * For bfs purposes, we use two elements of tmp per omino: |
392 | * tmp[2*i+0] tells us which omino we got to i from, and |
393 | * tmp[2*i+1] numbers the grid square that omino stole |
394 | * from us. |
395 | * |
396 | * This requires that wh (the size of tmp) is at least 2n, |
397 | * i.e. k is at least 2. There would have been nothing to |
398 | * stop a user calling this function with k=1, but if they |
399 | * did then we wouldn't have got to _here_ in the code - |
400 | * we would have noticed above that all ominoes were |
401 | * already at their target sizes, and terminated :-) |
402 | */ |
403 | assert(wh >= 2*n); |
404 | for (i = 0; i < n; i++) |
405 | tmp[2*i] = tmp[2*i+1] = -1; |
406 | qhead = qtail = 0; |
407 | queue[qtail++] = j; |
408 | tmp[2*j] = tmp[2*j+1] = -2; /* special value: `starting point' */ |
409 | |
410 | while (qhead < qtail) { |
411 | int tmpsq; |
412 | |
413 | j = queue[qhead]; |
414 | |
415 | /* |
416 | * We wish to expand omino j. However, we might have |
417 | * got here by omino j having a square stolen from it, |
418 | * so first of all we must temporarily mark that |
419 | * square as not belonging to j, so that our adjacency |
420 | * calculations don't assume j _does_ belong to us. |
421 | */ |
422 | tmpsq = tmp[2*j+1]; |
423 | if (tmpsq >= 0) { |
424 | assert(own[tmpsq] == j); |
9d36cbd7 |
425 | own[tmpsq] = -3; |
11d273f7 |
426 | } |
427 | |
428 | /* |
429 | * OK. Now begin by seeing if we can find any |
430 | * unclaimed square into which we can expand omino j. |
431 | * If we find one, the entire bfs terminates. |
432 | */ |
433 | for (i = 0; i < wh; i++) { |
434 | int dir; |
435 | |
9d36cbd7 |
436 | if (own[order[i]] != -1) |
11d273f7 |
437 | continue; /* this square is claimed */ |
9d36cbd7 |
438 | |
439 | /* |
440 | * Special case: if our current omino was size 1 |
441 | * and then had a square stolen from it, it's now |
442 | * size zero, which means it's valid to `expand' |
443 | * it into _any_ unclaimed square. |
444 | */ |
445 | if (sizes[j] == 1 && tmpsq >= 0) |
446 | break; /* got one */ |
447 | |
448 | /* |
449 | * Failing that, we must do the full test for |
450 | * addability. |
451 | */ |
11d273f7 |
452 | for (dir = 0; dir < 4; dir++) |
453 | if (addable[order[i]*4+dir] == j) { |
454 | /* |
455 | * We know this square is addable to this |
456 | * omino with the grid in the state it had |
457 | * at the top of the loop. However, we |
458 | * must now check that it's _still_ |
459 | * addable to this omino when the omino is |
460 | * missing a square. To do this it's only |
461 | * necessary to re-check addremcommon. |
f40d37bd |
462 | */ |
11d273f7 |
463 | if (!addremcommon(w, h, order[i]%w, order[i]/w, |
464 | own, j)) |
465 | continue; |
466 | break; |
467 | } |
468 | if (dir == 4) |
469 | continue; /* we can't add this square to j */ |
9d36cbd7 |
470 | |
11d273f7 |
471 | break; /* got one! */ |
472 | } |
473 | if (i < wh) { |
474 | i = order[i]; |
475 | |
476 | /* |
9d36cbd7 |
477 | * Restore the temporarily removed square _before_ |
478 | * we start shifting ownerships about. |
479 | */ |
480 | if (tmpsq >= 0) |
481 | own[tmpsq] = j; |
482 | |
483 | /* |
11d273f7 |
484 | * We are done. We can add square i to omino j, |
485 | * and then backtrack along the trail in tmp |
486 | * moving squares between ominoes, ending up |
487 | * expanding our starting omino by one. |
488 | */ |
f40d37bd |
489 | #ifdef DIVVY_DIAGNOSTICS |
490 | printf("(%d,%d)", i%w, i/w); |
491 | #endif |
11d273f7 |
492 | while (1) { |
493 | own[i] = j; |
f40d37bd |
494 | #ifdef DIVVY_DIAGNOSTICS |
495 | printf(" -> %d", j); |
496 | #endif |
11d273f7 |
497 | if (tmp[2*j] == -2) |
498 | break; |
499 | i = tmp[2*j+1]; |
500 | j = tmp[2*j]; |
f40d37bd |
501 | #ifdef DIVVY_DIAGNOSTICS |
502 | printf("; (%d,%d)", i%w, i/w); |
503 | #endif |
11d273f7 |
504 | } |
f40d37bd |
505 | #ifdef DIVVY_DIAGNOSTICS |
506 | printf("\n"); |
507 | #endif |
11d273f7 |
508 | |
509 | /* |
510 | * Increment the size of the starting omino. |
511 | */ |
512 | sizes[j]++; |
513 | |
514 | /* |
515 | * Terminate the bfs loop. |
516 | */ |
517 | break; |
518 | } |
519 | |
520 | /* |
521 | * If we get here, we haven't been able to expand |
522 | * omino j into an unclaimed square. So now we begin |
523 | * to investigate expanding it into squares which are |
524 | * claimed by ominoes the bfs has not yet visited. |
525 | */ |
526 | for (i = 0; i < wh; i++) { |
527 | int dir, nj; |
528 | |
529 | nj = own[order[i]]; |
530 | if (nj < 0 || tmp[2*nj] != -1) |
531 | continue; /* unclaimed, or owned by wrong omino */ |
532 | if (!removable[order[i]]) |
533 | continue; /* its omino won't let it go */ |
534 | |
535 | for (dir = 0; dir < 4; dir++) |
536 | if (addable[order[i]*4+dir] == j) { |
537 | /* |
538 | * As above, re-check addremcommon. |
539 | */ |
540 | if (!addremcommon(w, h, order[i]%w, order[i]/w, |
541 | own, j)) |
542 | continue; |
543 | |
544 | /* |
545 | * We have found a square we can use to |
546 | * expand omino j, at the expense of the |
547 | * as-yet unvisited omino nj. So add this |
548 | * to the bfs queue. |
549 | */ |
550 | assert(qtail < n); |
551 | queue[qtail++] = nj; |
552 | tmp[2*nj] = j; |
553 | tmp[2*nj+1] = order[i]; |
554 | |
555 | /* |
556 | * Now terminate the loop over dir, to |
557 | * ensure we don't accidentally add the |
558 | * same omino twice to the queue. |
559 | */ |
560 | break; |
561 | } |
562 | } |
563 | |
564 | /* |
565 | * Restore the temporarily removed square. |
566 | */ |
567 | if (tmpsq >= 0) |
568 | own[tmpsq] = j; |
569 | |
570 | /* |
571 | * Advance the queue head. |
572 | */ |
573 | qhead++; |
574 | } |
575 | |
576 | if (qhead == qtail) { |
577 | /* |
578 | * We have finished the bfs and not found any way to |
579 | * expand omino j. Panic, and return failure. |
580 | * |
581 | * FIXME: or should we loop over all ominoes before we |
582 | * give up? |
583 | */ |
f40d37bd |
584 | #ifdef DIVVY_DIAGNOSTICS |
585 | printf("FAIL!\n"); |
586 | #endif |
11d273f7 |
587 | retdsf = NULL; |
588 | goto cleanup; |
589 | } |
590 | } |
591 | |
f40d37bd |
592 | #ifdef DIVVY_DIAGNOSTICS |
593 | { |
594 | int x, y; |
595 | printf("SUCCESS! Final grid:\n"); |
596 | for (y = 0; y < h; y++) { |
597 | for (x = 0; x < w; x++) |
598 | printf("%3d", own[y*w+x]); |
599 | printf("\n"); |
600 | } |
601 | } |
602 | #endif |
603 | |
11d273f7 |
604 | /* |
605 | * Construct the output dsf. |
606 | */ |
607 | for (i = 0; i < wh; i++) { |
608 | assert(own[i] >= 0 && own[i] < n); |
609 | tmp[own[i]] = i; |
610 | } |
611 | retdsf = snew_dsf(wh); |
612 | for (i = 0; i < wh; i++) { |
613 | dsf_merge(retdsf, i, tmp[own[i]]); |
614 | } |
615 | |
616 | /* |
617 | * Construct the output dsf a different way, to verify that |
618 | * the ominoes really are k-ominoes and we haven't |
619 | * accidentally split one into two disconnected pieces. |
620 | */ |
621 | dsf_init(tmp, wh); |
622 | for (y = 0; y < h; y++) |
623 | for (x = 0; x+1 < w; x++) |
624 | if (own[y*w+x] == own[y*w+(x+1)]) |
625 | dsf_merge(tmp, y*w+x, y*w+(x+1)); |
626 | for (x = 0; x < w; x++) |
627 | for (y = 0; y+1 < h; y++) |
628 | if (own[y*w+x] == own[(y+1)*w+x]) |
629 | dsf_merge(tmp, y*w+x, (y+1)*w+x); |
630 | for (i = 0; i < wh; i++) { |
631 | j = dsf_canonify(retdsf, i); |
632 | assert(dsf_canonify(tmp, j) == dsf_canonify(tmp, i)); |
633 | } |
634 | |
635 | cleanup: |
636 | |
637 | /* |
638 | * Free our temporary working space. |
639 | */ |
640 | sfree(order); |
641 | sfree(tmp); |
642 | sfree(own); |
643 | sfree(sizes); |
644 | sfree(queue); |
645 | sfree(addable); |
646 | sfree(removable); |
647 | |
648 | /* |
649 | * And we're done. |
650 | */ |
651 | return retdsf; |
652 | } |
653 | |
654 | #ifdef TESTMODE |
9d36cbd7 |
655 | static int fail_counter = 0; |
656 | #endif |
657 | |
658 | int *divvy_rectangle(int w, int h, int k, random_state *rs) |
659 | { |
660 | int *ret; |
661 | |
662 | do { |
663 | ret = divvy_internal(w, h, k, rs); |
664 | |
665 | #ifdef TESTMODE |
666 | if (!ret) |
667 | fail_counter++; |
668 | #endif |
669 | |
670 | } while (!ret); |
671 | |
672 | return ret; |
673 | } |
674 | |
675 | #ifdef TESTMODE |
11d273f7 |
676 | |
677 | /* |
678 | * gcc -g -O0 -DTESTMODE -I.. -o divvy divvy.c ../random.c ../malloc.c ../dsf.c ../misc.c ../nullfe.c |
679 | * |
680 | * or to debug |
681 | * |
682 | * gcc -g -O0 -DDIVVY_DIAGNOSTICS -DTESTMODE -I.. -o divvy divvy.c ../random.c ../malloc.c ../dsf.c ../misc.c ../nullfe.c |
683 | */ |
684 | |
685 | int main(int argc, char **argv) |
686 | { |
687 | int *dsf; |
9d36cbd7 |
688 | int i; |
11d273f7 |
689 | int w = 9, h = 4, k = 6, tries = 100; |
690 | random_state *rs; |
691 | |
692 | rs = random_new("123456", 6); |
693 | |
694 | if (argc > 1) |
695 | w = atoi(argv[1]); |
696 | if (argc > 2) |
697 | h = atoi(argv[2]); |
698 | if (argc > 3) |
699 | k = atoi(argv[3]); |
700 | if (argc > 4) |
701 | tries = atoi(argv[4]); |
702 | |
11d273f7 |
703 | for (i = 0; i < tries; i++) { |
9d36cbd7 |
704 | int x, y; |
11d273f7 |
705 | |
9d36cbd7 |
706 | dsf = divvy_rectangle(w, h, k, rs); |
707 | assert(dsf); |
708 | |
709 | for (y = 0; y <= 2*h; y++) { |
710 | for (x = 0; x <= 2*w; x++) { |
711 | int miny = y/2 - 1, maxy = y/2; |
712 | int minx = x/2 - 1, maxx = x/2; |
713 | int classes[4], tx, ty; |
714 | for (ty = 0; ty < 2; ty++) |
715 | for (tx = 0; tx < 2; tx++) { |
716 | int cx = minx+tx, cy = miny+ty; |
717 | if (cx < 0 || cx >= w || cy < 0 || cy >= h) |
718 | classes[ty*2+tx] = -1; |
11d273f7 |
719 | else |
9d36cbd7 |
720 | classes[ty*2+tx] = dsf_canonify(dsf, cy*w+cx); |
11d273f7 |
721 | } |
9d36cbd7 |
722 | switch (y%2 * 2 + x%2) { |
723 | case 0: /* corner */ |
724 | /* |
725 | * Cases for the corner: |
726 | * |
727 | * - if all four surrounding squares belong |
728 | * to the same omino, we print a space. |
729 | * |
730 | * - if the top two are the same and the |
731 | * bottom two are the same, we print a |
732 | * horizontal line. |
733 | * |
734 | * - if the left two are the same and the |
735 | * right two are the same, we print a |
736 | * vertical line. |
737 | * |
738 | * - otherwise, we print a cross. |
739 | */ |
740 | if (classes[0] == classes[1] && |
741 | classes[1] == classes[2] && |
742 | classes[2] == classes[3]) |
743 | printf(" "); |
744 | else if (classes[0] == classes[1] && |
745 | classes[2] == classes[3]) |
746 | printf("-"); |
747 | else if (classes[0] == classes[2] && |
748 | classes[1] == classes[3]) |
749 | printf("|"); |
750 | else |
751 | printf("+"); |
752 | break; |
753 | case 1: /* horiz edge */ |
754 | if (classes[1] == classes[3]) |
755 | printf(" "); |
756 | else |
757 | printf("--"); |
758 | break; |
759 | case 2: /* vert edge */ |
760 | if (classes[2] == classes[3]) |
761 | printf(" "); |
762 | else |
763 | printf("|"); |
764 | break; |
765 | case 3: /* square centre */ |
766 | printf(" "); |
767 | break; |
11d273f7 |
768 | } |
11d273f7 |
769 | } |
770 | printf("\n"); |
11d273f7 |
771 | } |
9d36cbd7 |
772 | printf("\n"); |
773 | sfree(dsf); |
11d273f7 |
774 | } |
775 | |
9d36cbd7 |
776 | printf("%d retries needed for %d successes\n", fail_counter, tries); |
11d273f7 |
777 | |
778 | return 0; |
779 | } |
780 | |
781 | #endif |