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 | |
10 | #include <assert.h> |
11 | #include <stdio.h> |
12 | #include <stdlib.h> |
13 | #include <stddef.h> |
14 | |
15 | #include "puzzles.h" |
16 | |
17 | /* |
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. |
21 | * |
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. |
26 | * |
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.) |
34 | * |
35 | * When removing a square from an omino, the _same_ criterion |
36 | * tells us that removing the square won't disconnect the omino. |
37 | */ |
38 | static int addremcommon(int w, int h, int x, int y, int *own, int val) |
39 | { |
40 | int neighbours[8]; |
41 | int dir, count; |
42 | |
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; |
47 | |
48 | if (sx < 0 || sx >= w || sy < 0 || sy >= h) |
49 | neighbours[dir] = -1; /* outside the grid */ |
50 | else |
51 | neighbours[dir] = own[sy*w+sx]; |
52 | } |
53 | |
54 | /* |
55 | * To begin with, check 4-adjacency. |
56 | */ |
57 | if (neighbours[0] != val && neighbours[2] != val && |
58 | neighbours[4] != val && neighbours[6] != val) |
59 | return FALSE; |
60 | |
61 | count = 0; |
62 | |
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); |
67 | |
68 | if (gotthis != gotnext) |
69 | count++; |
70 | } |
71 | |
72 | return (count == 2); |
73 | } |
74 | |
75 | /* |
76 | * w and h are the dimensions of the rectangle. |
77 | * |
78 | * k is the size of the required ominoes. (So k must divide w*h, |
79 | * of course.) |
80 | * |
81 | * The returned result is a w*h-sized dsf. |
82 | * |
83 | * In both of the above suggested use cases, the user would |
84 | * probably want w==h==k, but that isn't a requirement. |
85 | */ |
86 | int *divvy_rectangle(int w, int h, int k, random_state *rs) |
87 | { |
88 | int *order, *queue, *tmp, *own, *sizes, *addable, *removable, *retdsf; |
89 | int wh = w*h; |
90 | int i, j, n, x, y, qhead, qtail; |
91 | |
92 | n = wh / k; |
93 | assert(wh == k*n); |
94 | |
95 | order = snewn(wh, int); |
96 | tmp = snewn(wh, int); |
97 | own = snewn(wh, int); |
98 | sizes = snewn(n, int); |
99 | queue = snewn(n, int); |
100 | addable = snewn(wh*4, int); |
101 | removable = snewn(wh, int); |
102 | |
103 | /* |
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. |
108 | */ |
109 | for (i = 0; i < wh; i++) |
110 | order[i] = i; |
111 | shuffle(order, wh, sizeof(*order), rs); |
112 | |
113 | /* |
114 | * Begin by choosing a starting square at random for each |
115 | * omino. |
116 | */ |
117 | for (i = 0; i < wh; i++) { |
118 | own[i] = -1; |
119 | } |
120 | for (i = 0; i < n; i++) { |
121 | own[order[i]] = i; |
122 | sizes[i] = 1; |
123 | } |
124 | |
125 | /* |
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. |
134 | */ |
135 | while (1) { |
136 | |
137 | #ifdef DIVVY_DIAGNOSTICS |
138 | { |
139 | int x, y; |
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]); |
144 | printf("\n"); |
145 | } |
146 | } |
147 | #endif |
148 | |
149 | /* |
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. |
155 | * |
156 | * For each square, there may be up to four ominoes to |
157 | * which it can be added (those to which it is |
158 | * 4-adjacent). |
159 | */ |
160 | for (y = 0; y < h; y++) { |
161 | for (x = 0; x < w; x++) { |
162 | int yx = y*w+x; |
163 | int curr = own[yx]; |
164 | int dir; |
165 | |
166 | if (curr < 0) { |
167 | removable[yx] = 0; /* can't remove if it's not owned! */ |
168 | } else { |
169 | /* |
170 | * See if this square can be removed from its |
171 | * omino without disconnecting it. |
172 | */ |
173 | removable[yx] = addremcommon(w, h, x, y, own, curr); |
174 | } |
175 | |
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; |
180 | int syx = sy*w+sx; |
181 | |
182 | addable[yx*4+dir] = -1; |
183 | |
184 | if (sx < 0 || sx >= w || sy < 0 || sy >= h) |
185 | continue; /* no omino here! */ |
186 | if (own[syx] < 0) |
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 */ |
192 | |
193 | addable[yx*4+dir] = own[syx]; |
194 | } |
195 | } |
196 | } |
197 | |
198 | for (i = j = 0; i < n; i++) |
199 | if (sizes[i] < k) |
200 | tmp[j++] = i; |
201 | if (j == 0) |
202 | break; /* all ominoes are complete! */ |
203 | j = tmp[random_upto(rs, j)]; |
f40d37bd |
204 | #ifdef DIVVY_DIAGNOSTICS |
205 | printf("Trying to extend %d\n", j); |
206 | #endif |
11d273f7 |
207 | |
208 | /* |
209 | * So we're trying to expand omino j. We breadth-first |
210 | * search out from j across the space of ominoes. |
211 | * |
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 |
215 | * from us. |
216 | * |
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 :-) |
223 | */ |
224 | assert(wh >= 2*n); |
225 | for (i = 0; i < n; i++) |
226 | tmp[2*i] = tmp[2*i+1] = -1; |
227 | qhead = qtail = 0; |
228 | queue[qtail++] = j; |
229 | tmp[2*j] = tmp[2*j+1] = -2; /* special value: `starting point' */ |
230 | |
231 | while (qhead < qtail) { |
232 | int tmpsq; |
233 | |
234 | j = queue[qhead]; |
235 | |
236 | /* |
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. |
242 | */ |
243 | tmpsq = tmp[2*j+1]; |
244 | if (tmpsq >= 0) { |
245 | assert(own[tmpsq] == j); |
246 | own[tmpsq] = -1; |
247 | } |
248 | |
249 | /* |
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. |
253 | */ |
254 | for (i = 0; i < wh; i++) { |
255 | int dir; |
256 | |
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) { |
261 | /* |
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. |
f40d37bd |
269 | */ |
11d273f7 |
270 | if (!addremcommon(w, h, order[i]%w, order[i]/w, |
271 | own, j)) |
272 | continue; |
273 | break; |
274 | } |
275 | if (dir == 4) |
276 | continue; /* we can't add this square to j */ |
277 | break; /* got one! */ |
278 | } |
279 | if (i < wh) { |
280 | i = order[i]; |
281 | |
282 | /* |
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. |
287 | */ |
f40d37bd |
288 | #ifdef DIVVY_DIAGNOSTICS |
289 | printf("(%d,%d)", i%w, i/w); |
290 | #endif |
11d273f7 |
291 | while (1) { |
292 | own[i] = j; |
f40d37bd |
293 | #ifdef DIVVY_DIAGNOSTICS |
294 | printf(" -> %d", j); |
295 | #endif |
11d273f7 |
296 | if (tmp[2*j] == -2) |
297 | break; |
298 | i = tmp[2*j+1]; |
299 | j = tmp[2*j]; |
f40d37bd |
300 | #ifdef DIVVY_DIAGNOSTICS |
301 | printf("; (%d,%d)", i%w, i/w); |
302 | #endif |
11d273f7 |
303 | } |
f40d37bd |
304 | #ifdef DIVVY_DIAGNOSTICS |
305 | printf("\n"); |
306 | #endif |
11d273f7 |
307 | |
308 | /* |
309 | * Increment the size of the starting omino. |
310 | */ |
311 | sizes[j]++; |
312 | |
313 | /* |
314 | * Terminate the bfs loop. |
315 | */ |
316 | break; |
317 | } |
318 | |
319 | /* |
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. |
324 | */ |
325 | for (i = 0; i < wh; i++) { |
326 | int dir, nj; |
327 | |
328 | nj = own[order[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 */ |
333 | |
334 | for (dir = 0; dir < 4; dir++) |
335 | if (addable[order[i]*4+dir] == j) { |
336 | /* |
337 | * As above, re-check addremcommon. |
338 | */ |
339 | if (!addremcommon(w, h, order[i]%w, order[i]/w, |
340 | own, j)) |
341 | continue; |
342 | |
343 | /* |
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 |
347 | * to the bfs queue. |
348 | */ |
349 | assert(qtail < n); |
350 | queue[qtail++] = nj; |
351 | tmp[2*nj] = j; |
352 | tmp[2*nj+1] = order[i]; |
353 | |
354 | /* |
355 | * Now terminate the loop over dir, to |
356 | * ensure we don't accidentally add the |
357 | * same omino twice to the queue. |
358 | */ |
359 | break; |
360 | } |
361 | } |
362 | |
363 | /* |
364 | * Restore the temporarily removed square. |
365 | */ |
366 | if (tmpsq >= 0) |
367 | own[tmpsq] = j; |
368 | |
369 | /* |
370 | * Advance the queue head. |
371 | */ |
372 | qhead++; |
373 | } |
374 | |
375 | if (qhead == qtail) { |
376 | /* |
377 | * We have finished the bfs and not found any way to |
378 | * expand omino j. Panic, and return failure. |
379 | * |
380 | * FIXME: or should we loop over all ominoes before we |
381 | * give up? |
382 | */ |
f40d37bd |
383 | #ifdef DIVVY_DIAGNOSTICS |
384 | printf("FAIL!\n"); |
385 | #endif |
11d273f7 |
386 | retdsf = NULL; |
387 | goto cleanup; |
388 | } |
389 | } |
390 | |
f40d37bd |
391 | #ifdef DIVVY_DIAGNOSTICS |
392 | { |
393 | int x, y; |
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]); |
398 | printf("\n"); |
399 | } |
400 | } |
401 | #endif |
402 | |
11d273f7 |
403 | /* |
404 | * Construct the output dsf. |
405 | */ |
406 | for (i = 0; i < wh; i++) { |
407 | assert(own[i] >= 0 && own[i] < n); |
408 | tmp[own[i]] = i; |
409 | } |
410 | retdsf = snew_dsf(wh); |
411 | for (i = 0; i < wh; i++) { |
412 | dsf_merge(retdsf, i, tmp[own[i]]); |
413 | } |
414 | |
415 | /* |
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. |
419 | */ |
420 | dsf_init(tmp, wh); |
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)); |
432 | } |
433 | |
434 | cleanup: |
435 | |
436 | /* |
437 | * Free our temporary working space. |
438 | */ |
439 | sfree(order); |
440 | sfree(tmp); |
441 | sfree(own); |
442 | sfree(sizes); |
443 | sfree(queue); |
444 | sfree(addable); |
445 | sfree(removable); |
446 | |
447 | /* |
448 | * And we're done. |
449 | */ |
450 | return retdsf; |
451 | } |
452 | |
453 | #ifdef TESTMODE |
454 | |
455 | /* |
456 | * gcc -g -O0 -DTESTMODE -I.. -o divvy divvy.c ../random.c ../malloc.c ../dsf.c ../misc.c ../nullfe.c |
457 | * |
458 | * or to debug |
459 | * |
460 | * gcc -g -O0 -DDIVVY_DIAGNOSTICS -DTESTMODE -I.. -o divvy divvy.c ../random.c ../malloc.c ../dsf.c ../misc.c ../nullfe.c |
461 | */ |
462 | |
463 | int main(int argc, char **argv) |
464 | { |
465 | int *dsf; |
466 | int i, successes; |
467 | int w = 9, h = 4, k = 6, tries = 100; |
468 | random_state *rs; |
469 | |
470 | rs = random_new("123456", 6); |
471 | |
472 | if (argc > 1) |
473 | w = atoi(argv[1]); |
474 | if (argc > 2) |
475 | h = atoi(argv[2]); |
476 | if (argc > 3) |
477 | k = atoi(argv[3]); |
478 | if (argc > 4) |
479 | tries = atoi(argv[4]); |
480 | |
481 | successes = 0; |
482 | for (i = 0; i < tries; i++) { |
483 | dsf = divvy_rectangle(w, h, k, rs); |
484 | if (dsf) { |
485 | int x, y; |
486 | |
487 | successes++; |
488 | |
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; |
499 | else |
500 | classes[ty*2+tx] = dsf_canonify(dsf, cy*w+cx); |
501 | } |
502 | switch (y%2 * 2 + x%2) { |
503 | case 0: /* corner */ |
504 | /* |
505 | * Cases for the corner: |
506 | * |
507 | * - if all four surrounding squares |
508 | * belong to the same omino, we print a |
509 | * space. |
510 | * |
511 | * - if the top two are the same and the |
512 | * bottom two are the same, we print a |
513 | * horizontal line. |
514 | * |
515 | * - if the left two are the same and the |
516 | * right two are the same, we print a |
517 | * vertical line. |
518 | * |
519 | * - otherwise, we print a cross. |
520 | */ |
521 | if (classes[0] == classes[1] && |
522 | classes[1] == classes[2] && |
523 | classes[2] == classes[3]) |
524 | printf(" "); |
525 | else if (classes[0] == classes[1] && |
526 | classes[2] == classes[3]) |
527 | printf("-"); |
528 | else if (classes[0] == classes[2] && |
529 | classes[1] == classes[3]) |
530 | printf("|"); |
531 | else |
532 | printf("+"); |
533 | break; |
534 | case 1: /* horiz edge */ |
535 | if (classes[1] == classes[3]) |
536 | printf(" "); |
537 | else |
538 | printf("--"); |
539 | break; |
540 | case 2: /* vert edge */ |
541 | if (classes[2] == classes[3]) |
542 | printf(" "); |
543 | else |
544 | printf("|"); |
545 | break; |
546 | case 3: /* square centre */ |
547 | printf(" "); |
548 | break; |
549 | } |
550 | } |
551 | printf("\n"); |
552 | } |
553 | printf("\n"); |
554 | sfree(dsf); |
555 | } |
556 | } |
557 | |
558 | printf("%d successes out of %d tries\n", successes, tries); |
559 | |
560 | return 0; |
561 | } |
562 | |
563 | #endif |