f35afc826f5ce6b4516485c531e34c7cc53cb4ea
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.
18 * Subroutine which implements a function used in computing both
19 * whether a square can safely be added to an omino, and whether
20 * it can safely be removed.
22 * We enumerate the eight squares 8-adjacent to this one, in
23 * cyclic order. We go round that loop and count the number of
24 * times we find a square owned by the target omino next to one
25 * not owned by it. We then return success iff that count is 2.
27 * When adding a square to an omino, this is precisely the
28 * criterion which tells us that adding the square won't leave a
29 * hole in the middle of the omino. (There's no explicit
30 * requirement in the statement of our problem that the ominoes be
31 * simply connected, but we do know they must be all of equal size
32 * and so it's clear that we must avoid leaving holes, since a
33 * hole would necessarily be smaller than the maximum omino size.)
35 * When removing a square from an omino, the _same_ criterion
36 * tells us that removing the square won't disconnect the omino.
38 static int addremcommon(int w
, int h
, int x
, int y
, int *own
, int val
)
43 for (dir
= 0; dir
< 8; dir
++) {
44 int dx
= ((dir
& 3) == 2 ?
0 : dir
> 2 && dir
< 6 ?
+1 : -1);
45 int dy
= ((dir
& 3) == 0 ?
0 : dir
< 4 ?
-1 : +1);
46 int sx
= x
+dx
, sy
= y
+dy
;
48 if (sx
< 0 || sx
>= w
|| sy
< 0 || sy
>= h
)
49 neighbours
[dir
] = -1; /* outside the grid */
51 neighbours
[dir
] = own
[sy
*w
+sx
];
55 * To begin with, check 4-adjacency.
57 if (neighbours
[0] != val
&& neighbours
[2] != val
&&
58 neighbours
[4] != val
&& neighbours
[6] != val
)
63 for (dir
= 0; dir
< 8; dir
++) {
64 int next
= (dir
+ 1) & 7;
65 int gotthis
= (neighbours
[dir
] == val
);
66 int gotnext
= (neighbours
[next
] == val
);
68 if (gotthis
!= gotnext
)
76 * w and h are the dimensions of the rectangle.
78 * k is the size of the required ominoes. (So k must divide w*h,
81 * The returned result is a w*h-sized dsf.
83 * In both of the above suggested use cases, the user would
84 * probably want w==h==k, but that isn't a requirement.
86 int *divvy_rectangle(int w
, int h
, int k
, random_state
*rs
)
88 int *order
, *queue
, *tmp
, *own
, *sizes
, *addable
, *removable
, *retdsf
;
90 int i
, j
, n
, x
, y
, qhead
, qtail
;
95 order
= snewn(wh
, int);
98 sizes
= snewn(n
, int);
99 queue
= snewn(n
, int);
100 addable
= snewn(wh
*4, int);
101 removable
= snewn(wh
, int);
104 * Permute the grid squares into a random order, which will be
105 * used for iterating over the grid whenever we need to search
106 * for something. This prevents directional bias and arranges
107 * for the answer to be non-deterministic.
109 for (i
= 0; i
< wh
; i
++)
111 shuffle(order
, wh
, sizeof(*order
), rs
);
114 * Begin by choosing a starting square at random for each
117 for (i
= 0; i
< wh
; i
++) {
120 for (i
= 0; i
< n
; i
++) {
126 * Now repeatedly pick a random omino which isn't already at
127 * the target size, and find a way to expand it by one. This
128 * may involve stealing a square from another omino, in which
129 * case we then re-expand that omino, forming a chain of
130 * square-stealing which terminates in an as yet unclaimed
131 * square. Hence every successful iteration around this loop
132 * causes the number of unclaimed squares to drop by one, and
133 * so the process is bounded in duration.
137 #ifdef DIVVY_DIAGNOSTICS
140 printf("Top of loop. Current grid:\n");
141 for (y
= 0; y
< h
; y
++) {
142 for (x
= 0; x
< w
; x
++)
143 printf("%3d", own
[y
*w
+x
]);
150 * Go over the grid and figure out which squares can
151 * safely be added to, or removed from, each omino. We
152 * don't take account of other ominoes in this process, so
153 * we will often end up knowing that a square can be
154 * poached from one omino by another.
156 * For each square, there may be up to four ominoes to
157 * which it can be added (those to which it is
160 for (y
= 0; y
< h
; y
++) {
161 for (x
= 0; x
< w
; x
++) {
167 removable
[yx
] = 0; /* can't remove if it's not owned! */
170 * See if this square can be removed from its
171 * omino without disconnecting it.
173 removable
[yx
] = addremcommon(w
, h
, x
, y
, own
, curr
);
176 for (dir
= 0; dir
< 4; dir
++) {
177 int dx
= (dir
== 0 ?
-1 : dir
== 1 ?
+1 : 0);
178 int dy
= (dir
== 2 ?
-1 : dir
== 3 ?
+1 : 0);
179 int sx
= x
+ dx
, sy
= y
+ dy
;
182 addable
[yx
*4+dir
] = -1;
184 if (sx
< 0 || sx
>= w
|| sy
< 0 || sy
>= h
)
185 continue; /* no omino here! */
187 continue; /* also no omino here */
188 if (own
[syx
] == own
[yx
])
189 continue; /* we already got one */
190 if (!addremcommon(w
, h
, x
, y
, own
, own
[syx
]))
191 continue; /* would non-simply connect the omino */
193 addable
[yx
*4+dir
] = own
[syx
];
198 for (i
= j
= 0; i
< n
; i
++)
202 break; /* all ominoes are complete! */
203 j
= tmp
[random_upto(rs
, j
)];
204 #ifdef DIVVY_DIAGNOSTICS
205 printf("Trying to extend %d\n", j
);
209 * So we're trying to expand omino j. We breadth-first
210 * search out from j across the space of ominoes.
212 * For bfs purposes, we use two elements of tmp per omino:
213 * tmp[2*i+0] tells us which omino we got to i from, and
214 * tmp[2*i+1] numbers the grid square that omino stole
217 * This requires that wh (the size of tmp) is at least 2n,
218 * i.e. k is at least 2. There would have been nothing to
219 * stop a user calling this function with k=1, but if they
220 * did then we wouldn't have got to _here_ in the code -
221 * we would have noticed above that all ominoes were
222 * already at their target sizes, and terminated :-)
225 for (i
= 0; i
< n
; i
++)
226 tmp
[2*i
] = tmp
[2*i
+1] = -1;
229 tmp
[2*j
] = tmp
[2*j
+1] = -2; /* special value: `starting point' */
231 while (qhead
< qtail
) {
237 * We wish to expand omino j. However, we might have
238 * got here by omino j having a square stolen from it,
239 * so first of all we must temporarily mark that
240 * square as not belonging to j, so that our adjacency
241 * calculations don't assume j _does_ belong to us.
245 assert(own
[tmpsq
] == j
);
250 * OK. Now begin by seeing if we can find any
251 * unclaimed square into which we can expand omino j.
252 * If we find one, the entire bfs terminates.
254 for (i
= 0; i
< wh
; i
++) {
257 if (own
[order
[i
]] >= 0)
258 continue; /* this square is claimed */
259 for (dir
= 0; dir
< 4; dir
++)
260 if (addable
[order
[i
]*4+dir
] == j
) {
262 * We know this square is addable to this
263 * omino with the grid in the state it had
264 * at the top of the loop. However, we
265 * must now check that it's _still_
266 * addable to this omino when the omino is
267 * missing a square. To do this it's only
268 * necessary to re-check addremcommon.
270 if (!addremcommon(w
, h
, order
[i
]%w
, order
[i
]/w
,
276 continue; /* we can't add this square to j */
277 break; /* got one! */
283 * We are done. We can add square i to omino j,
284 * and then backtrack along the trail in tmp
285 * moving squares between ominoes, ending up
286 * expanding our starting omino by one.
288 #ifdef DIVVY_DIAGNOSTICS
289 printf("(%d,%d)", i
%w
, i
/w
);
293 #ifdef DIVVY_DIAGNOSTICS
300 #ifdef DIVVY_DIAGNOSTICS
301 printf("; (%d,%d)", i
%w
, i
/w
);
304 #ifdef DIVVY_DIAGNOSTICS
309 * Increment the size of the starting omino.
314 * Terminate the bfs loop.
320 * If we get here, we haven't been able to expand
321 * omino j into an unclaimed square. So now we begin
322 * to investigate expanding it into squares which are
323 * claimed by ominoes the bfs has not yet visited.
325 for (i
= 0; i
< wh
; i
++) {
329 if (nj
< 0 || tmp
[2*nj
] != -1)
330 continue; /* unclaimed, or owned by wrong omino */
331 if (!removable
[order
[i
]])
332 continue; /* its omino won't let it go */
334 for (dir
= 0; dir
< 4; dir
++)
335 if (addable
[order
[i
]*4+dir
] == j
) {
337 * As above, re-check addremcommon.
339 if (!addremcommon(w
, h
, order
[i
]%w
, order
[i
]/w
,
344 * We have found a square we can use to
345 * expand omino j, at the expense of the
346 * as-yet unvisited omino nj. So add this
352 tmp
[2*nj
+1] = order
[i
];
355 * Now terminate the loop over dir, to
356 * ensure we don't accidentally add the
357 * same omino twice to the queue.
364 * Restore the temporarily removed square.
370 * Advance the queue head.
375 if (qhead
== qtail
) {
377 * We have finished the bfs and not found any way to
378 * expand omino j. Panic, and return failure.
380 * FIXME: or should we loop over all ominoes before we
383 #ifdef DIVVY_DIAGNOSTICS
391 #ifdef DIVVY_DIAGNOSTICS
394 printf("SUCCESS! Final grid:\n");
395 for (y
= 0; y
< h
; y
++) {
396 for (x
= 0; x
< w
; x
++)
397 printf("%3d", own
[y
*w
+x
]);
404 * Construct the output dsf.
406 for (i
= 0; i
< wh
; i
++) {
407 assert(own
[i
] >= 0 && own
[i
] < n
);
410 retdsf
= snew_dsf(wh
);
411 for (i
= 0; i
< wh
; i
++) {
412 dsf_merge(retdsf
, i
, tmp
[own
[i
]]);
416 * Construct the output dsf a different way, to verify that
417 * the ominoes really are k-ominoes and we haven't
418 * accidentally split one into two disconnected pieces.
421 for (y
= 0; y
< h
; y
++)
422 for (x
= 0; x
+1 < w
; x
++)
423 if (own
[y
*w
+x
] == own
[y
*w
+(x
+1)])
424 dsf_merge(tmp
, y
*w
+x
, y
*w
+(x
+1));
425 for (x
= 0; x
< w
; x
++)
426 for (y
= 0; y
+1 < h
; y
++)
427 if (own
[y
*w
+x
] == own
[(y
+1)*w
+x
])
428 dsf_merge(tmp
, y
*w
+x
, (y
+1)*w
+x
);
429 for (i
= 0; i
< wh
; i
++) {
430 j
= dsf_canonify(retdsf
, i
);
431 assert(dsf_canonify(tmp
, j
) == dsf_canonify(tmp
, i
));
437 * Free our temporary working space.
456 * gcc -g -O0 -DTESTMODE -I.. -o divvy divvy.c ../random.c ../malloc.c ../dsf.c ../misc.c ../nullfe.c
460 * gcc -g -O0 -DDIVVY_DIAGNOSTICS -DTESTMODE -I.. -o divvy divvy.c ../random.c ../malloc.c ../dsf.c ../misc.c ../nullfe.c
463 int main(int argc
, char **argv
)
467 int w
= 9, h
= 4, k
= 6, tries
= 100;
470 rs
= random_new("123456", 6);
479 tries
= atoi(argv
[4]);
482 for (i
= 0; i
< tries
; i
++) {
483 dsf
= divvy_rectangle(w
, h
, k
, rs
);
489 for (y
= 0; y
<= 2*h
; y
++) {
490 for (x
= 0; x
<= 2*w
; x
++) {
491 int miny
= y
/2 - 1, maxy
= y
/2;
492 int minx
= x
/2 - 1, maxx
= x
/2;
493 int classes
[4], tx
, ty
;
494 for (ty
= 0; ty
< 2; ty
++)
495 for (tx
= 0; tx
< 2; tx
++) {
496 int cx
= minx
+tx
, cy
= miny
+ty
;
497 if (cx
< 0 || cx
>= w
|| cy
< 0 || cy
>= h
)
498 classes
[ty
*2+tx
] = -1;
500 classes
[ty
*2+tx
] = dsf_canonify(dsf
, cy
*w
+cx
);
502 switch (y
%2 * 2 + x
%2) {
505 * Cases for the corner:
507 * - if all four surrounding squares
508 * belong to the same omino, we print a
511 * - if the top two are the same and the
512 * bottom two are the same, we print a
515 * - if the left two are the same and the
516 * right two are the same, we print a
519 * - otherwise, we print a cross.
521 if (classes
[0] == classes
[1] &&
522 classes
[1] == classes
[2] &&
523 classes
[2] == classes
[3])
525 else if (classes
[0] == classes
[1] &&
526 classes
[2] == classes
[3])
528 else if (classes
[0] == classes
[2] &&
529 classes
[1] == classes
[3])
534 case 1: /* horiz edge */
535 if (classes
[1] == classes
[3])
540 case 2: /* vert edge */
541 if (classes
[2] == classes
[3])
546 case 3: /* square centre */
558 printf("%d successes out of %d tries\n", successes
, tries
);