2 * separate.c: Implementation of `Block Puzzle', a Japanese-only
3 * Nikoli puzzle seen at
4 * http://www.nikoli.co.jp/ja/puzzles/block_puzzle/
6 * It's difficult to be absolutely sure of the rules since online
7 * Japanese translators are so bad, but looking at the sample
8 * puzzle it seems fairly clear that the rules of this one are
9 * very simple. You have an mxn grid in which every square
10 * contains a letter, there are k distinct letters with k dividing
11 * mn, and every letter occurs the same number of times; your aim
12 * is to find a partition of the grid into disjoint k-ominoes such
13 * that each k-omino contains exactly one of each letter.
15 * (It may be that Nikoli always have m,n,k equal to one another.
16 * However, I don't see that that's critical to the puzzle; k|mn
17 * is the only really important constraint, and even that could
18 * probably be dispensed with if some squares were marked as
23 * Current status: only the solver/generator is yet written, and
24 * although working in principle it's _very_ slow. It generates
25 * 5x5n5 or 6x6n4 readily enough, 6x6n6 with a bit of effort, and
26 * 7x7n7 only with a serious strain. I haven't dared try it higher
29 * One idea to speed it up is to implement more of the solver.
30 * Ideas I've so far had include:
32 * - Generalise the deduction currently expressed as `an
33 * undersized chain with only one direction to extend must take
34 * it'. More generally, the deduction should say `if all the
35 * possible k-ominoes containing a given chain also contain
36 * square x, then mark square x as part of that k-omino'.
37 * + For example, consider this case:
39 * a ? b This represents the top left of a board; the letters
40 * ? ? ? a,b,c do not represent the letters used in the puzzle,
41 * c ? ? but indicate that those three squares are known to be
42 * of different ominoes. Now if k >= 4, we can immediately
43 * deduce that the square midway between b and c belongs to the
44 * same omino as a, because there is no way we can make a 4-or-
45 * more-omino containing a which does not also contain that square.
46 * (Most easily seen by imagining cutting that square out of the
47 * grid; then, clearly, the omino containing a has only two
48 * squares to expand into, and needs at least three.)
50 * The key difficulty with this mode of reasoning is
51 * identifying such squares. I can't immediately think of a
52 * simple algorithm for finding them on a wholesale basis.
54 * - Bfs out from a chain looking for the letters it lacks. For
55 * example, in this situation (top three rows of a 7x7n7 grid):
64 * In this situation we can be sure that the top left chain
65 * E-A-F-B-C does extend rightwards to the D, because there is
66 * no other D within reach of that chain. Note also that the
67 * bfs can skip squares which are known to belong to other
68 * ominoes than this one.
70 * (This deduction, I fear, should only be used in an
71 * emergency, because it relies on _all_ squares within range
72 * of the bfs having particular values and so using it during
73 * incremental generation rather nails down a lot of the grid.)
75 * It's conceivable that another thing we could do would be to
76 * increase the flexibility in the grid generator: instead of
77 * nailing down the _value_ of any square depended on, merely nail
78 * down its equivalence to other squares. Unfortunately this turns
79 * the letter-selection phase of generation into a general graph
80 * colouring problem (we must draw a graph with equivalence
81 * classes of squares as the vertices, and an edge between any two
82 * vertices representing equivalence classes which contain squares
83 * that share an omino, and then k-colour the result) and hence
84 * requires recursion, which bodes ill for something we're doing
85 * that many times per generation.
87 * I suppose a simple thing I could try would be tuning the retry
88 * count, just in case it's set too high or too low for efficient
114 static game_params *default_params(void)
116 game_params *ret = snew(game_params);
118 ret->w = ret->h = ret->k = 5; /* FIXME: a bit bigger? */
123 static int game_fetch_preset(int i, char **name, game_params **params)
128 static void free_params(game_params *params)
133 static game_params *dup_params(const game_params *params)
135 game_params *ret = snew(game_params);
136 *ret = *params; /* structure copy */
140 static void decode_params(game_params *params, char const *string)
142 params->w = params->h = params->k = atoi(string);
143 while (*string && isdigit((unsigned char)*string)) string++;
144 if (*string == 'x') {
146 params->h = atoi(string);
147 while (*string && isdigit((unsigned char)*string)) string++;
149 if (*string == 'n') {
151 params->k = atoi(string);
152 while (*string && isdigit((unsigned char)*string)) string++;
156 static char *encode_params(const game_params *params, int full)
159 sprintf(buf, "%dx%dn%d", params->w, params->h, params->k);
163 static config_item *game_configure(const game_params *params)
168 static game_params *custom_params(const config_item *cfg)
173 static char *validate_params(const game_params *params, int full)
178 /* ----------------------------------------------------------------------
179 * Solver and generator.
182 struct solver_scratch {
186 * Tracks connectedness between squares.
191 * size[dsf_canonify(dsf, yx)] tracks the size of the
192 * connected component containing yx.
197 * contents[dsf_canonify(dsf, yx)*k+i] tracks whether or not
198 * the connected component containing yx includes letter i. If
199 * the value is -1, it doesn't; otherwise its value is the
200 * index in the main grid of the square which contributes that
201 * letter to the component.
206 * disconnect[dsf_canonify(dsf, yx1)*w*h + dsf_canonify(dsf, yx2)]
207 * tracks whether or not the connected components containing
208 * yx1 and yx2 are known to be distinct.
210 unsigned char *disconnect;
213 * Temporary space used only inside particular solver loops.
218 struct solver_scratch *solver_scratch_new(int w, int h, int k)
221 struct solver_scratch *sc = snew(struct solver_scratch);
227 sc->dsf = snew_dsf(wh);
228 sc->size = snewn(wh, int);
229 sc->contents = snewn(wh * k, int);
230 sc->disconnect = snewn(wh*wh, unsigned char);
231 sc->tmp = snewn(wh, int);
236 void solver_scratch_free(struct solver_scratch *sc)
241 sfree(sc->disconnect);
246 void solver_connect(struct solver_scratch *sc, int yx1, int yx2)
248 int w = sc->w, h = sc->h, k = sc->k;
252 yx1 = dsf_canonify(sc->dsf, yx1);
253 yx2 = dsf_canonify(sc->dsf, yx2);
257 * To connect two components together into a bigger one, we
258 * start by merging them in the dsf itself.
260 dsf_merge(sc->dsf, yx1, yx2);
261 yxnew = dsf_canonify(sc->dsf, yx2);
264 * The size of the new component is the sum of the sizes of the
267 sc->size[yxnew] = sc->size[yx1] + sc->size[yx2];
270 * The contents bitmap of the new component is the union of the
271 * contents of the old ones.
273 * Given two numbers at most one of which is not -1, we can
274 * find the other one by adding the two and adding 1; this
275 * will yield -1 if both were -1 to begin with, otherwise the
278 * (A neater approach would be to take their bitwise AND, but
279 * this is unfortunately not well-defined standard C when done
280 * to signed integers.)
282 for (i = 0; i < k; i++) {
283 assert(sc->contents[yx1*k+i] < 0 || sc->contents[yx2*k+i] < 0);
284 sc->contents[yxnew*k+i] = (sc->contents[yx1*k+i] +
285 sc->contents[yx2*k+i] + 1);
289 * We must combine the rows _and_ the columns in the disconnect
292 for (i = 0; i < wh; i++)
293 sc->disconnect[yxnew*wh+i] = (sc->disconnect[yx1*wh+i] ||
294 sc->disconnect[yx2*wh+i]);
295 for (i = 0; i < wh; i++)
296 sc->disconnect[i*wh+yxnew] = (sc->disconnect[i*wh+yx1] ||
297 sc->disconnect[i*wh+yx2]);
300 void solver_disconnect(struct solver_scratch *sc, int yx1, int yx2)
302 int w = sc->w, h = sc->h;
305 yx1 = dsf_canonify(sc->dsf, yx1);
306 yx2 = dsf_canonify(sc->dsf, yx2);
308 assert(!sc->disconnect[yx1*wh+yx2]);
309 assert(!sc->disconnect[yx2*wh+yx1]);
312 * Mark the components as disconnected from each other in the
315 sc->disconnect[yx1*wh+yx2] = sc->disconnect[yx2*wh+yx1] = 1;
318 void solver_init(struct solver_scratch *sc)
320 int w = sc->w, h = sc->h;
325 * Set up most of the scratch space. We don't set up the
326 * contents array, however, because this will change if we
327 * adjust the letter arrangement and re-run the solver.
329 dsf_init(sc->dsf, wh);
330 for (i = 0; i < wh; i++) sc->size[i] = 1;
331 memset(sc->disconnect, 0, wh*wh);
334 int solver_attempt(struct solver_scratch *sc, const unsigned char *grid,
335 unsigned char *gen_lock)
337 int w = sc->w, h = sc->h, k = sc->k;
340 int done_something_overall = FALSE;
343 * Set up the contents array from the grid.
345 for (i = 0; i < wh*k; i++)
346 sc->contents[i] = -1;
347 for (i = 0; i < wh; i++)
348 sc->contents[dsf_canonify(sc->dsf, i)*k+grid[i]] = i;
351 int done_something = FALSE;
354 * Go over the grid looking for reasons to add to the
355 * disconnect matrix. We're after pairs of squares which:
357 * - are adjacent in the grid
358 * - belong to distinct dsf components
359 * - their components are not already marked as
361 * - their components share a letter in common.
363 for (y = 0; y < h; y++) {
364 for (x = 0; x < w; x++) {
366 for (dir = 0; dir < 2; dir++) {
367 int x2 = x + dir, y2 = y + 1 - dir;
368 int yx = y*w+x, yx2 = y2*w+x2;
370 if (x2 >= w || y2 >= h)
371 continue; /* one square is outside the grid */
373 yx = dsf_canonify(sc->dsf, yx);
374 yx2 = dsf_canonify(sc->dsf, yx2);
376 continue; /* same dsf component */
378 if (sc->disconnect[yx*wh+yx2])
379 continue; /* already known disconnected */
381 for (i = 0; i < k; i++)
382 if (sc->contents[yx*k+i] >= 0 &&
383 sc->contents[yx2*k+i] >= 0)
386 continue; /* no letter in common */
389 * We've found one. Mark yx and yx2 as
390 * disconnected from each other.
392 #ifdef SOLVER_DIAGNOSTICS
393 printf("Disconnecting %d and %d (%c)\n", yx, yx2, 'A'+i);
395 solver_disconnect(sc, yx, yx2);
396 done_something = done_something_overall = TRUE;
399 * We have just made a deduction which hinges
400 * on two particular grid squares being the
401 * same. If we are feeding back to a generator
402 * loop, we must therefore mark those squares
403 * as fixed in the generator, so that future
404 * rearrangement of the grid will not break
405 * the information on which we have already
409 gen_lock[sc->contents[yx*k+i]] = 1;
410 gen_lock[sc->contents[yx2*k+i]] = 1;
417 * Now go over the grid looking for dsf components which
418 * are below maximum size and only have one way to extend,
419 * and extending them.
421 for (i = 0; i < wh; i++)
423 for (y = 0; y < h; y++) {
424 for (x = 0; x < w; x++) {
425 int yx = dsf_canonify(sc->dsf, y*w+x);
428 if (sc->size[yx] == k)
431 for (dir = 0; dir < 4; dir++) {
432 int x2 = x + (dir==0 ? -1 : dir==2 ? 1 : 0);
433 int y2 = y + (dir==1 ? -1 : dir==3 ? 1 : 0);
436 if (y2 < 0 || y2 >= h || x2 < 0 || x2 >= w)
439 yx2c = dsf_canonify(sc->dsf, yx2);
441 if (yx2c != yx && !sc->disconnect[yx2c*wh+yx]) {
443 * Component yx can be extended into square
446 if (sc->tmp[yx] == -1)
448 else if (sc->tmp[yx] != yx2)
449 sc->tmp[yx] = -2; /* multiple choices found */
454 for (i = 0; i < wh; i++) {
455 if (sc->tmp[i] >= 0) {
457 * Make sure we haven't connected the two already
458 * during this loop (which could happen if for
459 * _both_ components this was the only way to
462 if (dsf_canonify(sc->dsf, i) ==
463 dsf_canonify(sc->dsf, sc->tmp[i]))
466 #ifdef SOLVER_DIAGNOSTICS
467 printf("Connecting %d and %d\n", i, sc->tmp[i]);
469 solver_connect(sc, i, sc->tmp[i]);
470 done_something = done_something_overall = TRUE;
480 * Return 0 if we haven't made any progress; 1 if we've done
481 * something but not solved it completely; 2 if we've solved
484 for (i = 0; i < wh; i++)
485 if (sc->size[dsf_canonify(sc->dsf, i)] != k)
489 if (done_something_overall)
494 unsigned char *generate(int w, int h, int k, random_state *rs)
498 struct solver_scratch *sc;
500 unsigned char *shuffled;
501 int i, j, m, retries;
503 unsigned char *gen_lock;
504 extern int *divvy_rectangle(int w, int h, int k, random_state *rs);
506 sc = solver_scratch_new(w, h, k);
507 grid = snewn(wh, unsigned char);
508 shuffled = snewn(k, unsigned char);
509 permutation = snewn(wh, int);
510 gen_lock = snewn(wh, unsigned char);
513 int *dsf = divvy_rectangle(w, h, k, rs);
516 * Go through the dsf and find the indices of all the
517 * squares involved in each omino, in a manner conducive
518 * to per-omino indexing. We set permutation[i*k+j] to be
519 * the index of the jth square (ordered arbitrarily) in
522 for (i = j = 0; i < wh; i++)
523 if (dsf_canonify(dsf, i) == i) {
526 * During this loop and the following one, we use
527 * the last element of each row of permutation[]
528 * as a counter of the number of indices so far
529 * placed in it. When we place the final index of
530 * an omino, that counter is overwritten, but that
531 * doesn't matter because we'll never use it
532 * again. Of course this depends critically on
533 * divvy_rectangle() having returned correct
534 * results, or else chaos would ensue.
536 permutation[j*k+k-1] = 0;
539 for (i = 0; i < wh; i++) {
540 j = sc->tmp[dsf_canonify(dsf, i)];
541 m = permutation[j*k+k-1]++;
542 permutation[j*k+m] = i;
546 * Track which squares' letters we have already depended
547 * on for deductions. This is gradually updated by
550 memset(gen_lock, 0, wh);
553 * Now repeatedly fill the grid with letters, and attempt
554 * to solve it. If the solver makes progress but does not
555 * fail completely, then gen_lock will have been updated
556 * and we try again. On a complete failure, though, we
557 * have no option but to give up and abandon this set of
564 * Fill the grid with letters. We can safely use
565 * sc->tmp to hold the set of letters required at each
566 * stage, since it's at least size k and is currently
569 for (i = 0; i < n; i++) {
571 * First, determine the set of letters already
572 * placed in this omino by gen_lock.
574 for (j = 0; j < k; j++)
576 for (j = 0; j < k; j++) {
577 int index = permutation[i*k+j];
578 int letter = grid[index];
580 sc->tmp[letter] = -1;
583 * Now collect together all the remaining letters
584 * and randomly shuffle them.
586 for (j = m = 0; j < k; j++)
588 sc->tmp[m++] = sc->tmp[j];
589 shuffle(sc->tmp, m, sizeof(*sc->tmp), rs);
591 * Finally, write the shuffled letters into the
594 for (j = 0; j < k; j++) {
595 int index = permutation[i*k+j];
596 if (!gen_lock[index])
597 grid[index] = sc->tmp[--m];
603 * Now we have a candidate grid. Attempt to progress
606 m = solver_attempt(sc, grid, gen_lock);
607 if (m == 2 || /* success */
608 (m == 0 && retries-- <= 0)) /* failure */
611 retries = k*k; /* reset this counter, and continue */
620 solver_scratch_free(sc);
625 /* ----------------------------------------------------------------------
626 * End of solver/generator code.
629 static char *new_game_desc(const game_params *params, random_state *rs,
630 char **aux, int interactive)
632 int w = params->w, h = params->h, wh = w*h, k = params->k;
637 grid = generate(w, h, k, rs);
639 desc = snewn(wh+1, char);
640 for (i = 0; i < wh; i++)
641 desc[i] = 'A' + grid[i];
649 static char *validate_desc(const game_params *params, const char *desc)
654 static game_state *new_game(midend *me, const game_params *params,
657 game_state *state = snew(game_state);
664 static game_state *dup_game(const game_state *state)
666 game_state *ret = snew(game_state);
668 ret->FIXME = state->FIXME;
673 static void free_game(game_state *state)
678 static char *solve_game(const game_state *state, const game_state *currstate,
679 const char *aux, char **error)
684 static int game_can_format_as_text_now(const game_params *params)
689 static char *game_text_format(const game_state *state)
694 static game_ui *new_ui(const game_state *state)
699 static void free_ui(game_ui *ui)
703 static char *encode_ui(const game_ui *ui)
708 static void decode_ui(game_ui *ui, const char *encoding)
712 static void game_changed_state(game_ui *ui, const game_state *oldstate,
713 const game_state *newstate)
717 struct game_drawstate {
722 static char *interpret_move(const game_state *state, game_ui *ui,
723 const game_drawstate *ds,
724 int x, int y, int button)
729 static game_state *execute_move(const game_state *state, const char *move)
734 /* ----------------------------------------------------------------------
738 static void game_compute_size(const game_params *params, int tilesize,
741 *x = *y = 10 * tilesize; /* FIXME */
744 static void game_set_size(drawing *dr, game_drawstate *ds,
745 const game_params *params, int tilesize)
747 ds->tilesize = tilesize;
750 static float *game_colours(frontend *fe, int *ncolours)
752 float *ret = snewn(3 * NCOLOURS, float);
754 frontend_default_colour(fe, &ret[COL_BACKGROUND * 3]);
756 *ncolours = NCOLOURS;
760 static game_drawstate *game_new_drawstate(drawing *dr, const game_state *state)
762 struct game_drawstate *ds = snew(struct game_drawstate);
770 static void game_free_drawstate(drawing *dr, game_drawstate *ds)
775 static void game_redraw(drawing *dr, game_drawstate *ds,
776 const game_state *oldstate, const game_state *state,
777 int dir, const game_ui *ui,
778 float animtime, float flashtime)
781 * The initial contents of the window are not guaranteed and
782 * can vary with front ends. To be on the safe side, all games
783 * should start by drawing a big background-colour rectangle
784 * covering the whole window.
786 draw_rect(dr, 0, 0, 10*ds->tilesize, 10*ds->tilesize, COL_BACKGROUND);
789 static float game_anim_length(const game_state *oldstate,
790 const game_state *newstate, int dir, game_ui *ui)
795 static float game_flash_length(const game_state *oldstate,
796 const game_state *newstate, int dir, game_ui *ui)
801 static int game_status(const game_state *state)
806 static int game_timing_state(const game_state *state, game_ui *ui)
811 static void game_print_size(const game_params *params, float *x, float *y)
815 static void game_print(drawing *dr, const game_state *state, int tilesize)
820 #define thegame separate
823 const struct game thegame = {
824 "Separate", NULL, NULL,
831 FALSE, game_configure, custom_params,
839 FALSE, game_can_format_as_text_now, game_text_format,
847 20 /* FIXME */, game_compute_size, game_set_size,
855 FALSE, FALSE, game_print_size, game_print,
856 FALSE, /* wants_statusbar */
857 FALSE, game_timing_state,