b819cfe19d407985e92359acfa9938d9c60ec3a4
2 * Library code to divide up a rectangle into a number of equally
3 * sized ominoes, in a random fashion.
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.
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).
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:
25 * +--+--+--+--+--+--+--+
27 * + +--+--+--+--+--+ +
37 * + +--+--+--+--+--+ +
39 * +--+--+--+--+--+--+--+
41 * I believe the smallest k which can manage this is 23, which I
42 * derive by considering the largest _rectangle_ a k-omino can
43 * surround. Consider: to surround an m x n rectangle, a polyomino
44 * must have 2m squares along the two m-sides of the rectangle, 2n
45 * squares along the n-sides, and fill in three of the corners. So
46 * m+n must be at most (k-3)/2. Hence, to find the largest area of
47 * such a rectangle, we must find m so as to maximise the product
48 * m((k-3)/2-m). This is achieved when m is as close as possible
49 * to half of (k-3)/2; so the largest rectangle surroundable by a
50 * k-omino is equal to floor(k'/2)*ceil(k'/2), with k'=(k-3)/2.
51 * The smallest k for which this is at least k is 23: a 23-omino
52 * can surround a 5x5 rectangle, whereas the best a 22-omino can
55 * (I don't have a definite argument to show that a k-omino cannot
56 * surround a larger area in non-rectangular than rectangular
57 * form, but it seems intuitively obvious to me that it can't. I
58 * may update this with a more rigorous proof if I think of one.)
60 * Anyway: the point is, although constructions of this type are
61 * possible for sufficiently large k, divvy_rectangle() will never
62 * generate them. This could be considered a weakness for some
63 * purposes, in the sense that we can't generate all possible
64 * divisions. However, there are many divisions which we are
65 * highly unlikely to generate anyway, so in practice it probably
68 * If I wanted to fix this issue, I would have to make the rules
69 * more complicated for determining when a square can safely be
70 * _removed_ from a polyomino. Adding one becomes easier (a square
71 * may be added to a polyomino iff it is 4-adjacent to any square
72 * currently part of the polyomino, and the current test for loop
73 * formation may be dispensed with), but to determine which
74 * squares may be removed we must now resort to analysis of the
75 * overall structure of the polyomino rather than the simple local
76 * properties we can currently get away with measuring.
80 * Possible improvements which might cut the fail rate:
82 * - instead of picking one omino to extend in an iteration, try
83 * them all in succession (in a randomised order)
85 * - (for real rigour) instead of bfsing over ominoes, bfs over
86 * the space of possible _removed squares_. That way we aren't
87 * limited to randomly choosing a single square to remove from
88 * an omino and failing if that particular square doesn't
91 * However, I don't currently think it's necessary to do either of
92 * these, because the failure rate is already low enough to be
93 * easily tolerable, under all circumstances I've been able to
105 * Subroutine which implements a function used in computing both
106 * whether a square can safely be added to an omino, and whether
107 * it can safely be removed.
109 * We enumerate the eight squares 8-adjacent to this one, in
110 * cyclic order. We go round that loop and count the number of
111 * times we find a square owned by the target omino next to one
112 * not owned by it. We then return success iff that count is 2.
114 * When adding a square to an omino, this is precisely the
115 * criterion which tells us that adding the square won't leave a
116 * hole in the middle of the omino. (There's no explicit
117 * requirement in the statement of our problem that the ominoes be
118 * simply connected, but we do know they must be all of equal size
119 * and so it's clear that we must avoid leaving holes, since a
120 * hole would necessarily be smaller than the maximum omino size.)
122 * When removing a square from an omino, the _same_ criterion
123 * tells us that removing the square won't disconnect the omino.
125 static int addremcommon(int w
, int h
, int x
, int y
, int *own
, int val
)
130 for (dir
= 0; dir
< 8; dir
++) {
131 int dx
= ((dir
& 3) == 2 ?
0 : dir
> 2 && dir
< 6 ?
+1 : -1);
132 int dy
= ((dir
& 3) == 0 ?
0 : dir
< 4 ?
-1 : +1);
133 int sx
= x
+dx
, sy
= y
+dy
;
135 if (sx
< 0 || sx
>= w
|| sy
< 0 || sy
>= h
)
136 neighbours
[dir
] = -1; /* outside the grid */
138 neighbours
[dir
] = own
[sy
*w
+sx
];
142 * To begin with, check 4-adjacency.
144 if (neighbours
[0] != val
&& neighbours
[2] != val
&&
145 neighbours
[4] != val
&& neighbours
[6] != val
)
150 for (dir
= 0; dir
< 8; dir
++) {
151 int next
= (dir
+ 1) & 7;
152 int gotthis
= (neighbours
[dir
] == val
);
153 int gotnext
= (neighbours
[next
] == val
);
155 if (gotthis
!= gotnext
)
163 * w and h are the dimensions of the rectangle.
165 * k is the size of the required ominoes. (So k must divide w*h,
168 * The returned result is a w*h-sized dsf.
170 * In both of the above suggested use cases, the user would
171 * probably want w==h==k, but that isn't a requirement.
173 static int *divvy_internal(int w
, int h
, int k
, random_state
*rs
)
175 int *order
, *queue
, *tmp
, *own
, *sizes
, *addable
, *removable
, *retdsf
;
177 int i
, j
, n
, x
, y
, qhead
, qtail
;
182 order
= snewn(wh
, int);
183 tmp
= snewn(wh
, int);
184 own
= snewn(wh
, int);
185 sizes
= snewn(n
, int);
186 queue
= snewn(n
, int);
187 addable
= snewn(wh
*4, int);
188 removable
= snewn(wh
, int);
191 * Permute the grid squares into a random order, which will be
192 * used for iterating over the grid whenever we need to search
193 * for something. This prevents directional bias and arranges
194 * for the answer to be non-deterministic.
196 for (i
= 0; i
< wh
; i
++)
198 shuffle(order
, wh
, sizeof(*order
), rs
);
201 * Begin by choosing a starting square at random for each
204 for (i
= 0; i
< wh
; i
++) {
207 for (i
= 0; i
< n
; i
++) {
213 * Now repeatedly pick a random omino which isn't already at
214 * the target size, and find a way to expand it by one. This
215 * may involve stealing a square from another omino, in which
216 * case we then re-expand that omino, forming a chain of
217 * square-stealing which terminates in an as yet unclaimed
218 * square. Hence every successful iteration around this loop
219 * causes the number of unclaimed squares to drop by one, and
220 * so the process is bounded in duration.
224 #ifdef DIVVY_DIAGNOSTICS
227 printf("Top of loop. Current grid:\n");
228 for (y
= 0; y
< h
; y
++) {
229 for (x
= 0; x
< w
; x
++)
230 printf("%3d", own
[y
*w
+x
]);
237 * Go over the grid and figure out which squares can
238 * safely be added to, or removed from, each omino. We
239 * don't take account of other ominoes in this process, so
240 * we will often end up knowing that a square can be
241 * poached from one omino by another.
243 * For each square, there may be up to four ominoes to
244 * which it can be added (those to which it is
247 for (y
= 0; y
< h
; y
++) {
248 for (x
= 0; x
< w
; x
++) {
254 removable
[yx
] = FALSE
; /* can't remove if not owned! */
255 } else if (sizes
[curr
] == 1) {
256 removable
[yx
] = TRUE
; /* can always remove a singleton */
259 * See if this square can be removed from its
260 * omino without disconnecting it.
262 removable
[yx
] = addremcommon(w
, h
, x
, y
, own
, curr
);
265 for (dir
= 0; dir
< 4; dir
++) {
266 int dx
= (dir
== 0 ?
-1 : dir
== 1 ?
+1 : 0);
267 int dy
= (dir
== 2 ?
-1 : dir
== 3 ?
+1 : 0);
268 int sx
= x
+ dx
, sy
= y
+ dy
;
271 addable
[yx
*4+dir
] = -1;
273 if (sx
< 0 || sx
>= w
|| sy
< 0 || sy
>= h
)
274 continue; /* no omino here! */
276 continue; /* also no omino here */
277 if (own
[syx
] == own
[yx
])
278 continue; /* we already got one */
279 if (!addremcommon(w
, h
, x
, y
, own
, own
[syx
]))
280 continue; /* would non-simply connect the omino */
282 addable
[yx
*4+dir
] = own
[syx
];
287 for (i
= j
= 0; i
< n
; i
++)
291 break; /* all ominoes are complete! */
292 j
= tmp
[random_upto(rs
, j
)];
293 #ifdef DIVVY_DIAGNOSTICS
294 printf("Trying to extend %d\n", j
);
298 * So we're trying to expand omino j. We breadth-first
299 * search out from j across the space of ominoes.
301 * For bfs purposes, we use two elements of tmp per omino:
302 * tmp[2*i+0] tells us which omino we got to i from, and
303 * tmp[2*i+1] numbers the grid square that omino stole
306 * This requires that wh (the size of tmp) is at least 2n,
307 * i.e. k is at least 2. There would have been nothing to
308 * stop a user calling this function with k=1, but if they
309 * did then we wouldn't have got to _here_ in the code -
310 * we would have noticed above that all ominoes were
311 * already at their target sizes, and terminated :-)
314 for (i
= 0; i
< n
; i
++)
315 tmp
[2*i
] = tmp
[2*i
+1] = -1;
318 tmp
[2*j
] = tmp
[2*j
+1] = -2; /* special value: `starting point' */
320 while (qhead
< qtail
) {
326 * We wish to expand omino j. However, we might have
327 * got here by omino j having a square stolen from it,
328 * so first of all we must temporarily mark that
329 * square as not belonging to j, so that our adjacency
330 * calculations don't assume j _does_ belong to us.
334 assert(own
[tmpsq
] == j
);
339 * OK. Now begin by seeing if we can find any
340 * unclaimed square into which we can expand omino j.
341 * If we find one, the entire bfs terminates.
343 for (i
= 0; i
< wh
; i
++) {
346 if (own
[order
[i
]] != -1)
347 continue; /* this square is claimed */
350 * Special case: if our current omino was size 1
351 * and then had a square stolen from it, it's now
352 * size zero, which means it's valid to `expand'
353 * it into _any_ unclaimed square.
355 if (sizes
[j
] == 1 && tmpsq
>= 0)
359 * Failing that, we must do the full test for
362 for (dir
= 0; dir
< 4; dir
++)
363 if (addable
[order
[i
]*4+dir
] == j
) {
365 * We know this square is addable to this
366 * omino with the grid in the state it had
367 * at the top of the loop. However, we
368 * must now check that it's _still_
369 * addable to this omino when the omino is
370 * missing a square. To do this it's only
371 * necessary to re-check addremcommon.
373 if (!addremcommon(w
, h
, order
[i
]%w
, order
[i
]/w
,
379 continue; /* we can't add this square to j */
381 break; /* got one! */
387 * Restore the temporarily removed square _before_
388 * we start shifting ownerships about.
394 * We are done. We can add square i to omino j,
395 * and then backtrack along the trail in tmp
396 * moving squares between ominoes, ending up
397 * expanding our starting omino by one.
399 #ifdef DIVVY_DIAGNOSTICS
400 printf("(%d,%d)", i
%w
, i
/w
);
404 #ifdef DIVVY_DIAGNOSTICS
411 #ifdef DIVVY_DIAGNOSTICS
412 printf("; (%d,%d)", i
%w
, i
/w
);
415 #ifdef DIVVY_DIAGNOSTICS
420 * Increment the size of the starting omino.
425 * Terminate the bfs loop.
431 * If we get here, we haven't been able to expand
432 * omino j into an unclaimed square. So now we begin
433 * to investigate expanding it into squares which are
434 * claimed by ominoes the bfs has not yet visited.
436 for (i
= 0; i
< wh
; i
++) {
440 if (nj
< 0 || tmp
[2*nj
] != -1)
441 continue; /* unclaimed, or owned by wrong omino */
442 if (!removable
[order
[i
]])
443 continue; /* its omino won't let it go */
445 for (dir
= 0; dir
< 4; dir
++)
446 if (addable
[order
[i
]*4+dir
] == j
) {
448 * As above, re-check addremcommon.
450 if (!addremcommon(w
, h
, order
[i
]%w
, order
[i
]/w
,
455 * We have found a square we can use to
456 * expand omino j, at the expense of the
457 * as-yet unvisited omino nj. So add this
463 tmp
[2*nj
+1] = order
[i
];
466 * Now terminate the loop over dir, to
467 * ensure we don't accidentally add the
468 * same omino twice to the queue.
475 * Restore the temporarily removed square.
481 * Advance the queue head.
486 if (qhead
== qtail
) {
488 * We have finished the bfs and not found any way to
489 * expand omino j. Panic, and return failure.
491 * FIXME: or should we loop over all ominoes before we
494 #ifdef DIVVY_DIAGNOSTICS
502 #ifdef DIVVY_DIAGNOSTICS
505 printf("SUCCESS! Final grid:\n");
506 for (y
= 0; y
< h
; y
++) {
507 for (x
= 0; x
< w
; x
++)
508 printf("%3d", own
[y
*w
+x
]);
515 * Construct the output dsf.
517 for (i
= 0; i
< wh
; i
++) {
518 assert(own
[i
] >= 0 && own
[i
] < n
);
521 retdsf
= snew_dsf(wh
);
522 for (i
= 0; i
< wh
; i
++) {
523 dsf_merge(retdsf
, i
, tmp
[own
[i
]]);
527 * Construct the output dsf a different way, to verify that
528 * the ominoes really are k-ominoes and we haven't
529 * accidentally split one into two disconnected pieces.
532 for (y
= 0; y
< h
; y
++)
533 for (x
= 0; x
+1 < w
; x
++)
534 if (own
[y
*w
+x
] == own
[y
*w
+(x
+1)])
535 dsf_merge(tmp
, y
*w
+x
, y
*w
+(x
+1));
536 for (x
= 0; x
< w
; x
++)
537 for (y
= 0; y
+1 < h
; y
++)
538 if (own
[y
*w
+x
] == own
[(y
+1)*w
+x
])
539 dsf_merge(tmp
, y
*w
+x
, (y
+1)*w
+x
);
540 for (i
= 0; i
< wh
; i
++) {
541 j
= dsf_canonify(retdsf
, i
);
542 assert(dsf_canonify(tmp
, j
) == dsf_canonify(tmp
, i
));
548 * Free our temporary working space.
565 static int fail_counter
= 0;
568 int *divvy_rectangle(int w
, int h
, int k
, random_state
*rs
)
573 ret
= divvy_internal(w
, h
, k
, rs
);
588 * gcc -g -O0 -DTESTMODE -I.. -o divvy divvy.c ../random.c ../malloc.c ../dsf.c ../misc.c ../nullfe.c
592 * gcc -g -O0 -DDIVVY_DIAGNOSTICS -DTESTMODE -I.. -o divvy divvy.c ../random.c ../malloc.c ../dsf.c ../misc.c ../nullfe.c
595 int main(int argc
, char **argv
)
599 int w
= 9, h
= 4, k
= 6, tries
= 100;
602 rs
= random_new("123456", 6);
611 tries
= atoi(argv
[4]);
613 for (i
= 0; i
< tries
; i
++) {
616 dsf
= divvy_rectangle(w
, h
, k
, rs
);
619 for (y
= 0; y
<= 2*h
; y
++) {
620 for (x
= 0; x
<= 2*w
; x
++) {
621 int miny
= y
/2 - 1, maxy
= y
/2;
622 int minx
= x
/2 - 1, maxx
= x
/2;
623 int classes
[4], tx
, ty
;
624 for (ty
= 0; ty
< 2; ty
++)
625 for (tx
= 0; tx
< 2; tx
++) {
626 int cx
= minx
+tx
, cy
= miny
+ty
;
627 if (cx
< 0 || cx
>= w
|| cy
< 0 || cy
>= h
)
628 classes
[ty
*2+tx
] = -1;
630 classes
[ty
*2+tx
] = dsf_canonify(dsf
, cy
*w
+cx
);
632 switch (y
%2 * 2 + x
%2) {
635 * Cases for the corner:
637 * - if all four surrounding squares belong
638 * to the same omino, we print a space.
640 * - if the top two are the same and the
641 * bottom two are the same, we print a
644 * - if the left two are the same and the
645 * right two are the same, we print a
648 * - otherwise, we print a cross.
650 if (classes
[0] == classes
[1] &&
651 classes
[1] == classes
[2] &&
652 classes
[2] == classes
[3])
654 else if (classes
[0] == classes
[1] &&
655 classes
[2] == classes
[3])
657 else if (classes
[0] == classes
[2] &&
658 classes
[1] == classes
[3])
663 case 1: /* horiz edge */
664 if (classes
[1] == classes
[3])
669 case 2: /* vert edge */
670 if (classes
[2] == classes
[3])
675 case 3: /* square centre */
686 printf("%d retries needed for %d successes\n", fail_counter
, tries
);