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 claim the smallest k which can manage this is 23. More
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.
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.
55
* The first of those claims:
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
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).
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.
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.
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.
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
110
* where N and E are in P, and X is in Q.
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
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.
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.
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.
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,
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
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.
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.
171
* Possible improvements which might cut the fail rate:
173
* - instead of picking one omino to extend in an iteration, try
174
* them all in succession (in a randomised order)
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
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
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.
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.
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
207
* hole in the middle of the omino. (If it did, then things get
208
* more complicated; see above.)
210
* When removing a square from an omino, the _same_ criterion
211
* tells us that removing the square won't disconnect the omino.
212
* (This only works _because_ we've ensured the omino is simply
215
static int addremcommon(int w, int h, int x, int y, int *own, int val)
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;
225
if (sx < 0 || sx >= w || sy < 0 || sy >= h)
226
neighbours[dir] = -1; /* outside the grid */
228
neighbours[dir] = own[sy*w+sx];
232
* To begin with, check 4-adjacency.
234
if (neighbours[0] != val && neighbours[2] != val &&
235
neighbours[4] != val && neighbours[6] != val)
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);
245
if (gotthis != gotnext)
253
* w and h are the dimensions of the rectangle.
255
* k is the size of the required ominoes. (So k must divide w*h,
258
* The returned result is a w*h-sized dsf.
260
* In both of the above suggested use cases, the user would
261
* probably want w==h==k, but that isn't a requirement.
263
static int *divvy_internal(int w, int h, int k, random_state *rs)
265
int *order, *queue, *tmp, *own, *sizes, *addable, *removable, *retdsf;
267
int i, j, n, x, y, qhead, qtail;
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);
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.
286
for (i = 0; i < wh; i++)
288
shuffle(order, wh, sizeof(*order), rs);
291
* Begin by choosing a starting square at random for each
294
for (i = 0; i < wh; i++) {
297
for (i = 0; i < n; i++) {
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.
314
#ifdef DIVVY_DIAGNOSTICS
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]);
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.
333
* For each square, there may be up to four ominoes to
334
* which it can be added (those to which it is
337
for (y = 0; y < h; y++) {
338
for (x = 0; x < w; x++) {
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 */
349
* See if this square can be removed from its
350
* omino without disconnecting it.
352
removable[yx] = addremcommon(w, h, x, y, own, curr);
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;
361
addable[yx*4+dir] = -1;
363
if (sx < 0 || sx >= w || sy < 0 || sy >= h)
364
continue; /* no omino here! */
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 */
372
addable[yx*4+dir] = own[syx];
377
for (i = j = 0; i < n; i++)
381
break; /* all ominoes are complete! */
382
j = tmp[random_upto(rs, j)];
383
#ifdef DIVVY_DIAGNOSTICS
384
printf("Trying to extend %d\n", j);
388
* So we're trying to expand omino j. We breadth-first
389
* search out from j across the space of ominoes.
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
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 :-)
404
for (i = 0; i < n; i++)
405
tmp[2*i] = tmp[2*i+1] = -1;
408
tmp[2*j] = tmp[2*j+1] = -2; /* special value: `starting point' */
410
while (qhead < qtail) {
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.
424
assert(own[tmpsq] == j);
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.
433
for (i = 0; i < wh; i++) {
436
if (own[order[i]] != -1)
437
continue; /* this square is claimed */
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.
445
if (sizes[j] == 1 && tmpsq >= 0)
449
* Failing that, we must do the full test for
452
for (dir = 0; dir < 4; dir++)
453
if (addable[order[i]*4+dir] == j) {
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.
463
if (!addremcommon(w, h, order[i]%w, order[i]/w,
469
continue; /* we can't add this square to j */
471
break; /* got one! */
477
* Restore the temporarily removed square _before_
478
* we start shifting ownerships about.
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.
489
#ifdef DIVVY_DIAGNOSTICS
490
printf("(%d,%d)", i%w, i/w);
494
#ifdef DIVVY_DIAGNOSTICS
501
#ifdef DIVVY_DIAGNOSTICS
502
printf("; (%d,%d)", i%w, i/w);
505
#ifdef DIVVY_DIAGNOSTICS
510
* Increment the size of the starting omino.
515
* Terminate the bfs loop.
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.
526
for (i = 0; i < wh; 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 */
535
for (dir = 0; dir < 4; dir++)
536
if (addable[order[i]*4+dir] == j) {
538
* As above, re-check addremcommon.
540
if (!addremcommon(w, h, order[i]%w, order[i]/w,
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
553
tmp[2*nj+1] = order[i];
556
* Now terminate the loop over dir, to
557
* ensure we don't accidentally add the
558
* same omino twice to the queue.
565
* Restore the temporarily removed square.
571
* Advance the queue head.
576
if (qhead == qtail) {
578
* We have finished the bfs and not found any way to
579
* expand omino j. Panic, and return failure.
581
* FIXME: or should we loop over all ominoes before we
584
#ifdef DIVVY_DIAGNOSTICS
592
#ifdef DIVVY_DIAGNOSTICS
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]);
605
* Construct the output dsf.
607
for (i = 0; i < wh; i++) {
608
assert(own[i] >= 0 && own[i] < n);
611
retdsf = snew_dsf(wh);
612
for (i = 0; i < wh; i++) {
613
dsf_merge(retdsf, i, tmp[own[i]]);
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.
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));
638
* Free our temporary working space.
655
static int fail_counter = 0;
658
int *divvy_rectangle(int w, int h, int k, random_state *rs)
663
ret = divvy_internal(w, h, k, rs);
678
* gcc -g -O0 -DTESTMODE -I.. -o divvy divvy.c ../random.c ../malloc.c ../dsf.c ../misc.c ../nullfe.c
682
* gcc -g -O0 -DDIVVY_DIAGNOSTICS -DTESTMODE -I.. -o divvy divvy.c ../random.c ../malloc.c ../dsf.c ../misc.c ../nullfe.c
685
int main(int argc, char **argv)
689
int w = 9, h = 4, k = 6, tries = 100;
692
rs = random_new("123456", 6);
701
tries = atoi(argv[4]);
703
for (i = 0; i < tries; i++) {
706
dsf = divvy_rectangle(w, h, k, rs);
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;
720
classes[ty*2+tx] = dsf_canonify(dsf, cy*w+cx);
722
switch (y%2 * 2 + x%2) {
725
* Cases for the corner:
727
* - if all four surrounding squares belong
728
* to the same omino, we print a space.
730
* - if the top two are the same and the
731
* bottom two are the same, we print a
734
* - if the left two are the same and the
735
* right two are the same, we print a
738
* - otherwise, we print a cross.
740
if (classes[0] == classes[1] &&
741
classes[1] == classes[2] &&
742
classes[2] == classes[3])
744
else if (classes[0] == classes[1] &&
745
classes[2] == classes[3])
747
else if (classes[0] == classes[2] &&
748
classes[1] == classes[3])
753
case 1: /* horiz edge */
754
if (classes[1] == classes[3])
759
case 2: /* vert edge */
760
if (classes[2] == classes[3])
765
case 3: /* square centre */
776
printf("%d retries needed for %d successes\n", fail_counter, tries);
added
removed
divvy.c
