From: simon Date: Sat, 25 Aug 2007 14:10:49 +0000 (+0000) Subject: Commit my work so far on a generator for Nikoli's `Block Puzzle'. It X-Git-Url: https://git.distorted.org.uk/~mdw/sgt/puzzles/commitdiff_plain/213d24956e6fe87462164c79fbcca6ed3e8c82a4 Commit my work so far on a generator for Nikoli's `Block Puzzle'. It works, but it's slow, and the puzzles are currently at a relatively low level of difficulty. Also this is a generator only: no UI yet (because I'm waiting to see if I can make the generator practical before bothering to write the rest). git-svn-id: svn://svn.tartarus.org/sgt/puzzles@7700 cda61777-01e9-0310-a592-d414129be87e --- diff --git a/unfinished/separate.R b/unfinished/separate.R new file mode 100644 index 0000000..53b6e85 --- /dev/null +++ b/unfinished/separate.R @@ -0,0 +1,21 @@ +# -*- makefile -*- + +SEPARATE = separate divvy dsf + +separate : [X] GTK COMMON SEPARATE separate-icon|no-icon + +separate : [G] WINDOWS COMMON SEPARATE separate.res|noicon.res + +ALL += separate + +!begin gtk +GAMES += separate +!end + +!begin >list.c + A(separate) \ +!end + +!begin >wingames.lst +separate.exe:Separate +!end diff --git a/unfinished/separate.c b/unfinished/separate.c new file mode 100644 index 0000000..d6542a1 --- /dev/null +++ b/unfinished/separate.c @@ -0,0 +1,845 @@ +/* + * separate.c: Implementation of `Block Puzzle', a Japanese-only + * Nikoli puzzle seen at + * http://www.nikoli.co.jp/ja/puzzles/block_puzzle/ + * + * It's difficult to be absolutely sure of the rules since online + * Japanese translators are so bad, but looking at the sample + * puzzle it seems fairly clear that the rules of this one are + * very simple. You have an mxn grid in which every square + * contains a letter, there are k distinct letters with k dividing + * mn, and every letter occurs the same number of times; your aim + * is to find a partition of the grid into disjoint k-ominoes such + * that each k-omino contains exactly one of each letter. + * + * (It may be that Nikoli always have m,n,k equal to one another. + * However, I don't see that that's critical to the puzzle; k|mn + * is the only really important constraint, and even that could + * probably be dispensed with if some squares were marked as + * unused.) + */ + +/* + * Current status: only the solver/generator is yet written, and + * although working in principle it's _very_ slow. It generates + * 5x5n5 or 6x6n4 readily enough, 6x6n6 with a bit of effort, and + * 7x7n7 only with a serious strain. I haven't dared try it higher + * than that yet. + * + * One idea to speed it up is to implement more of the solver. + * Ideas I've so far had include: + * + * - Generalise the deduction currently expressed as `an + * undersized chain with only one direction to extend must take + * it'. More generally, the deduction should say `if all the + * possible k-ominoes containing a given chain also contain + * square x, then mark square x as part of that k-omino'. + * + For example, consider this case: + * + * a ? b This represents the top left of a board; the letters + * ? ? ? a,b,c do not represent the letters used in the puzzle, + * c ? ? but indicate that those three squares are known to be + * of different ominoes. Now if k >= 4, we can immediately + * deduce that the square midway between b and c belongs to the + * same omino as a, because there is no way we can make a 4-or- + * more-omino containing a which does not also contain that square. + * (Most easily seen by imagining cutting that square out of the + * grid; then, clearly, the omino containing a has only two + * squares to expand into, and needs at least three.) + * + * The key difficulty with this mode of reasoning is + * identifying such squares. I can't immediately think of a + * simple algorithm for finding them on a wholesale basis. + * + * - Bfs out from a chain looking for the letters it lacks. For + * example, in this situation (top three rows of a 7x7n7 grid): + * + * +-----------+-+ + * |E-A-F-B-C D|D| + * +------- || + * |E-C-G-D G|G E| + * +-+--- | + * |E|E G A B F A| + * + * In this situation we can be sure that the top left chain + * E-A-F-B-C does extend rightwards to the D, because there is + * no other D within reach of that chain. Note also that the + * bfs can skip squares which are known to belong to other + * ominoes than this one. + * + * (This deduction, I fear, should only be used in an + * emergency, because it relies on _all_ squares within range + * of the bfs having particular values and so using it during + * incremental generation rather nails down a lot of the grid.) + * + * It's conceivable that another thing we could do would be to + * increase the flexibility in the grid generator: instead of + * nailing down the _value_ of any square depended on, merely nail + * down its equivalence to other squares. Unfortunately this turns + * the letter-selection phase of generation into a general graph + * colouring problem (we must draw a graph with equivalence + * classes of squares as the vertices, and an edge between any two + * vertices representing equivalence classes which contain squares + * that share an omino, and then k-colour the result) and hence + * requires recursion, which bodes ill for something we're doing + * that many times per generation. + * + * I suppose a simple thing I could try would be tuning the retry + * count, just in case it's set too high or too low for efficient + * generation. + */ + +#include +#include +#include +#include +#include +#include + +#include "puzzles.h" + +enum { + COL_BACKGROUND, + NCOLOURS +}; + +struct game_params { + int w, h, k; +}; + +struct game_state { + int FIXME; +}; + +static game_params *default_params(void) +{ + game_params *ret = snew(game_params); + + ret->w = ret->h = ret->k = 5; /* FIXME: a bit bigger? */ + + return ret; +} + +static int game_fetch_preset(int i, char **name, game_params **params) +{ + return FALSE; +} + +static void free_params(game_params *params) +{ + sfree(params); +} + +static game_params *dup_params(game_params *params) +{ + game_params *ret = snew(game_params); + *ret = *params; /* structure copy */ + return ret; +} + +static void decode_params(game_params *params, char const *string) +{ + params->w = params->h = params->k = atoi(string); + while (*string && isdigit((unsigned char)*string)) string++; + if (*string == 'x') { + string++; + params->h = atoi(string); + while (*string && isdigit((unsigned char)*string)) string++; + } + if (*string == 'n') { + string++; + params->k = atoi(string); + while (*string && isdigit((unsigned char)*string)) string++; + } +} + +static char *encode_params(game_params *params, int full) +{ + char buf[256]; + sprintf(buf, "%dx%dn%d", params->w, params->h, params->k); + return dupstr(buf); +} + +static config_item *game_configure(game_params *params) +{ + return NULL; +} + +static game_params *custom_params(config_item *cfg) +{ + return NULL; +} + +static char *validate_params(game_params *params, int full) +{ + return NULL; +} + +/* ---------------------------------------------------------------------- + * Solver and generator. + */ + +struct solver_scratch { + int w, h, k; + + /* + * Tracks connectedness between squares. + */ + int *dsf; + + /* + * size[dsf_canonify(dsf, yx)] tracks the size of the + * connected component containing yx. + */ + int *size; + + /* + * contents[dsf_canonify(dsf, yx)*k+i] tracks whether or not + * the connected component containing yx includes letter i. If + * the value is -1, it doesn't; otherwise its value is the + * index in the main grid of the square which contributes that + * letter to the component. + */ + int *contents; + + /* + * disconnect[dsf_canonify(dsf, yx1)*w*h + dsf_canonify(dsf, yx2)] + * tracks whether or not the connected components containing + * yx1 and yx2 are known to be distinct. + */ + unsigned char *disconnect; + + /* + * Temporary space used only inside particular solver loops. + */ + int *tmp; +}; + +struct solver_scratch *solver_scratch_new(int w, int h, int k) +{ + int wh = w*h; + struct solver_scratch *sc = snew(struct solver_scratch); + + sc->w = w; + sc->h = h; + sc->k = k; + + sc->dsf = snew_dsf(wh); + sc->size = snewn(wh, int); + sc->contents = snewn(wh * k, int); + sc->disconnect = snewn(wh*wh, unsigned char); + sc->tmp = snewn(wh, int); + + return sc; +} + +void solver_scratch_free(struct solver_scratch *sc) +{ + sfree(sc->dsf); + sfree(sc->size); + sfree(sc->contents); + sfree(sc->disconnect); + sfree(sc->tmp); + sfree(sc); +} + +void solver_connect(struct solver_scratch *sc, int yx1, int yx2) +{ + int w = sc->w, h = sc->h, k = sc->k; + int wh = w*h; + int i, yxnew; + + yx1 = dsf_canonify(sc->dsf, yx1); + yx2 = dsf_canonify(sc->dsf, yx2); + assert(yx1 != yx2); + + /* + * To connect two components together into a bigger one, we + * start by merging them in the dsf itself. + */ + dsf_merge(sc->dsf, yx1, yx2); + yxnew = dsf_canonify(sc->dsf, yx2); + + /* + * The size of the new component is the sum of the sizes of the + * old ones. + */ + sc->size[yxnew] = sc->size[yx1] + sc->size[yx2]; + + /* + * The contents bitmap of the new component is the union of the + * contents of the old ones. + * + * Given two numbers at most one of which is not -1, we can + * find the other one by adding the two and adding 1; this + * will yield -1 if both were -1 to begin with, otherwise the + * other. + * + * (A neater approach would be to take their bitwise AND, but + * this is unfortunately not well-defined standard C when done + * to signed integers.) + */ + for (i = 0; i < k; i++) { + assert(sc->contents[yx1*k+i] < 0 || sc->contents[yx2*k+i] < 0); + sc->contents[yxnew*k+i] = (sc->contents[yx1*k+i] + + sc->contents[yx2*k+i] + 1); + } + + /* + * We must combine the rows _and_ the columns in the disconnect + * matrix. + */ + for (i = 0; i < wh; i++) + sc->disconnect[yxnew*wh+i] = (sc->disconnect[yx1*wh+i] || + sc->disconnect[yx2*wh+i]); + for (i = 0; i < wh; i++) + sc->disconnect[i*wh+yxnew] = (sc->disconnect[i*wh+yx1] || + sc->disconnect[i*wh+yx2]); +} + +void solver_disconnect(struct solver_scratch *sc, int yx1, int yx2) +{ + int w = sc->w, h = sc->h; + int wh = w*h; + + yx1 = dsf_canonify(sc->dsf, yx1); + yx2 = dsf_canonify(sc->dsf, yx2); + assert(yx1 != yx2); + assert(!sc->disconnect[yx1*wh+yx2]); + assert(!sc->disconnect[yx2*wh+yx1]); + + /* + * Mark the components as disconnected from each other in the + * disconnect matrix. + */ + sc->disconnect[yx1*wh+yx2] = sc->disconnect[yx2*wh+yx1] = 1; +} + +void solver_init(struct solver_scratch *sc) +{ + int w = sc->w, h = sc->h; + int wh = w*h; + int i; + + /* + * Set up most of the scratch space. We don't set up the + * contents array, however, because this will change if we + * adjust the letter arrangement and re-run the solver. + */ + dsf_init(sc->dsf, wh); + for (i = 0; i < wh; i++) sc->size[i] = 1; + memset(sc->disconnect, 0, wh*wh); +} + +int solver_attempt(struct solver_scratch *sc, const unsigned char *grid, + unsigned char *gen_lock) +{ + int w = sc->w, h = sc->h, k = sc->k; + int wh = w*h; + int i, x, y; + int done_something_overall = FALSE; + + /* + * Set up the contents array from the grid. + */ + for (i = 0; i < wh*k; i++) + sc->contents[i] = -1; + for (i = 0; i < wh; i++) + sc->contents[dsf_canonify(sc->dsf, i)*k+grid[i]] = i; + + while (1) { + int done_something = FALSE; + + /* + * Go over the grid looking for reasons to add to the + * disconnect matrix. We're after pairs of squares which: + * + * - are adjacent in the grid + * - belong to distinct dsf components + * - their components are not already marked as + * disconnected + * - their components share a letter in common. + */ + for (y = 0; y < h; y++) { + for (x = 0; x < w; x++) { + int dir; + for (dir = 0; dir < 2; dir++) { + int x2 = x + dir, y2 = y + 1 - dir; + int yx = y*w+x, yx2 = y2*w+x2; + + if (x2 >= w || y2 >= h) + continue; /* one square is outside the grid */ + + yx = dsf_canonify(sc->dsf, yx); + yx2 = dsf_canonify(sc->dsf, yx2); + if (yx == yx2) + continue; /* same dsf component */ + + if (sc->disconnect[yx*wh+yx2]) + continue; /* already known disconnected */ + + for (i = 0; i < k; i++) + if (sc->contents[yx*k+i] >= 0 && + sc->contents[yx2*k+i] >= 0) + break; + if (i == k) + continue; /* no letter in common */ + + /* + * We've found one. Mark yx and yx2 as + * disconnected from each other. + */ +#ifdef SOLVER_DIAGNOSTICS + printf("Disconnecting %d and %d (%c)\n", yx, yx2, 'A'+i); +#endif + solver_disconnect(sc, yx, yx2); + done_something = done_something_overall = TRUE; + + /* + * We have just made a deduction which hinges + * on two particular grid squares being the + * same. If we are feeding back to a generator + * loop, we must therefore mark those squares + * as fixed in the generator, so that future + * rearrangement of the grid will not break + * the information on which we have already + * based deductions. + */ + if (gen_lock) { + gen_lock[sc->contents[yx*k+i]] = 1; + gen_lock[sc->contents[yx2*k+i]] = 1; + } + } + } + } + + /* + * Now go over the grid looking for dsf components which + * are below maximum size and only have one way to extend, + * and extending them. + */ + for (i = 0; i < wh; i++) + sc->tmp[i] = -1; + for (y = 0; y < h; y++) { + for (x = 0; x < w; x++) { + int yx = dsf_canonify(sc->dsf, y*w+x); + int dir; + + if (sc->size[yx] == k) + continue; + + for (dir = 0; dir < 4; dir++) { + int x2 = x + (dir==0 ? -1 : dir==2 ? 1 : 0); + int y2 = y + (dir==1 ? -1 : dir==3 ? 1 : 0); + int yx2, yx2c; + + if (y2 < 0 || y2 >= h || x2 < 0 || x2 >= w) + continue; + yx2 = y2*w+x2; + yx2c = dsf_canonify(sc->dsf, yx2); + + if (yx2c != yx && !sc->disconnect[yx2c*wh+yx]) { + /* + * Component yx can be extended into square + * yx2. + */ + if (sc->tmp[yx] == -1) + sc->tmp[yx] = yx2; + else if (sc->tmp[yx] != yx2) + sc->tmp[yx] = -2; /* multiple choices found */ + } + } + } + } + for (i = 0; i < wh; i++) { + if (sc->tmp[i] >= 0) { + /* + * Make sure we haven't connected the two already + * during this loop (which could happen if for + * _both_ components this was the only way to + * extend them). + */ + if (dsf_canonify(sc->dsf, i) == + dsf_canonify(sc->dsf, sc->tmp[i])) + continue; + +#ifdef SOLVER_DIAGNOSTICS + printf("Connecting %d and %d\n", i, sc->tmp[i]); +#endif + solver_connect(sc, i, sc->tmp[i]); + done_something = done_something_overall = TRUE; + break; + } + } + + if (!done_something) + break; + } + + /* + * Return 0 if we haven't made any progress; 1 if we've done + * something but not solved it completely; 2 if we've solved + * it completely. + */ + for (i = 0; i < wh; i++) + if (sc->size[dsf_canonify(sc->dsf, i)] != k) + break; + if (i == wh) + return 2; + if (done_something_overall) + return 1; + return 0; +} + +unsigned char *generate(int w, int h, int k, random_state *rs) +{ + int wh = w*h; + int n = wh/k; + struct solver_scratch *sc; + unsigned char *grid; + unsigned char *shuffled; + int i, j, m, retries; + int *permutation; + unsigned char *gen_lock; + extern int *divvy_rectangle(int w, int h, int k, random_state *rs); + + sc = solver_scratch_new(w, h, k); + grid = snewn(wh, unsigned char); + shuffled = snewn(k, unsigned char); + permutation = snewn(wh, int); + gen_lock = snewn(wh, unsigned char); + + do { + int *dsf = divvy_rectangle(w, h, k, rs); + + /* + * Go through the dsf and find the indices of all the + * squares involved in each omino, in a manner conducive + * to per-omino indexing. We set permutation[i*k+j] to be + * the index of the jth square (ordered arbitrarily) in + * omino i. + */ + for (i = j = 0; i < wh; i++) + if (dsf_canonify(dsf, i) == i) { + sc->tmp[i] = j; + /* + * During this loop and the following one, we use + * the last element of each row of permutation[] + * as a counter of the number of indices so far + * placed in it. When we place the final index of + * an omino, that counter is overwritten, but that + * doesn't matter because we'll never use it + * again. Of course this depends critically on + * divvy_rectangle() having returned correct + * results, or else chaos would ensue. + */ + permutation[j*k+k-1] = 0; + j++; + } + for (i = 0; i < wh; i++) { + j = sc->tmp[dsf_canonify(dsf, i)]; + m = permutation[j*k+k-1]++; + permutation[j*k+m] = i; + } + + /* + * Track which squares' letters we have already depended + * on for deductions. This is gradually updated by + * solver_attempt(). + */ + memset(gen_lock, 0, wh); + + /* + * Now repeatedly fill the grid with letters, and attempt + * to solve it. If the solver makes progress but does not + * fail completely, then gen_lock will have been updated + * and we try again. On a complete failure, though, we + * have no option but to give up and abandon this set of + * ominoes. + */ + solver_init(sc); + retries = k*k; + while (1) { + /* + * Fill the grid with letters. We can safely use + * sc->tmp to hold the set of letters required at each + * stage, since it's at least size k and is currently + * unused. + */ + for (i = 0; i < n; i++) { + /* + * First, determine the set of letters already + * placed in this omino by gen_lock. + */ + for (j = 0; j < k; j++) + sc->tmp[j] = j; + for (j = 0; j < k; j++) { + int index = permutation[i*k+j]; + int letter = grid[index]; + if (gen_lock[index]) + sc->tmp[letter] = -1; + } + /* + * Now collect together all the remaining letters + * and randomly shuffle them. + */ + for (j = m = 0; j < k; j++) + if (sc->tmp[j] >= 0) + sc->tmp[m++] = sc->tmp[j]; + shuffle(sc->tmp, m, sizeof(*sc->tmp), rs); + /* + * Finally, write the shuffled letters into the + * grid. + */ + for (j = 0; j < k; j++) { + int index = permutation[i*k+j]; + if (!gen_lock[index]) + grid[index] = sc->tmp[--m]; + } + assert(m == 0); + } + + /* + * Now we have a candidate grid. Attempt to progress + * the solution. + */ + m = solver_attempt(sc, grid, gen_lock); + if (m == 2 || /* success */ + (m == 0 && retries-- <= 0)) /* failure */ + break; + if (m == 1) + retries = k*k; /* reset this counter, and continue */ + } + + sfree(dsf); + } while (m == 0); + + sfree(gen_lock); + sfree(permutation); + sfree(shuffled); + solver_scratch_free(sc); + + return grid; +} + +/* ---------------------------------------------------------------------- + * End of solver/generator code. + */ + +static char *new_game_desc(game_params *params, random_state *rs, + char **aux, int interactive) +{ + int w = params->w, h = params->h, wh = w*h, k = params->k; + unsigned char *grid; + char *desc; + int i; + + grid = generate(w, h, k, rs); + + desc = snewn(wh+1, char); + for (i = 0; i < wh; i++) + desc[i] = 'A' + grid[i]; + desc[wh] = '\0'; + + sfree(grid); + + return desc; +} + +static char *validate_desc(game_params *params, char *desc) +{ + return NULL; +} + +static game_state *new_game(midend *me, game_params *params, char *desc) +{ + game_state *state = snew(game_state); + + state->FIXME = 0; + + return state; +} + +static game_state *dup_game(game_state *state) +{ + game_state *ret = snew(game_state); + + ret->FIXME = state->FIXME; + + return ret; +} + +static void free_game(game_state *state) +{ + sfree(state); +} + +static char *solve_game(game_state *state, game_state *currstate, + char *aux, char **error) +{ + return NULL; +} + +static char *game_text_format(game_state *state) +{ + return NULL; +} + +static game_ui *new_ui(game_state *state) +{ + return NULL; +} + +static void free_ui(game_ui *ui) +{ +} + +static char *encode_ui(game_ui *ui) +{ + return NULL; +} + +static void decode_ui(game_ui *ui, char *encoding) +{ +} + +static void game_changed_state(game_ui *ui, game_state *oldstate, + game_state *newstate) +{ +} + +struct game_drawstate { + int tilesize; + int FIXME; +}; + +static char *interpret_move(game_state *state, game_ui *ui, game_drawstate *ds, + int x, int y, int button) +{ + return NULL; +} + +static game_state *execute_move(game_state *state, char *move) +{ + return NULL; +} + +/* ---------------------------------------------------------------------- + * Drawing routines. + */ + +static void game_compute_size(game_params *params, int tilesize, + int *x, int *y) +{ + *x = *y = 10 * tilesize; /* FIXME */ +} + +static void game_set_size(drawing *dr, game_drawstate *ds, + game_params *params, int tilesize) +{ + ds->tilesize = tilesize; +} + +static float *game_colours(frontend *fe, int *ncolours) +{ + float *ret = snewn(3 * NCOLOURS, float); + + frontend_default_colour(fe, &ret[COL_BACKGROUND * 3]); + + *ncolours = NCOLOURS; + return ret; +} + +static game_drawstate *game_new_drawstate(drawing *dr, game_state *state) +{ + struct game_drawstate *ds = snew(struct game_drawstate); + + ds->tilesize = 0; + ds->FIXME = 0; + + return ds; +} + +static void game_free_drawstate(drawing *dr, game_drawstate *ds) +{ + sfree(ds); +} + +static void game_redraw(drawing *dr, game_drawstate *ds, game_state *oldstate, + game_state *state, int dir, game_ui *ui, + float animtime, float flashtime) +{ + /* + * The initial contents of the window are not guaranteed and + * can vary with front ends. To be on the safe side, all games + * should start by drawing a big background-colour rectangle + * covering the whole window. + */ + draw_rect(dr, 0, 0, 10*ds->tilesize, 10*ds->tilesize, COL_BACKGROUND); +} + +static float game_anim_length(game_state *oldstate, game_state *newstate, + int dir, game_ui *ui) +{ + return 0.0F; +} + +static float game_flash_length(game_state *oldstate, game_state *newstate, + int dir, game_ui *ui) +{ + return 0.0F; +} + +static int game_timing_state(game_state *state, game_ui *ui) +{ + return TRUE; +} + +static void game_print_size(game_params *params, float *x, float *y) +{ +} + +static void game_print(drawing *dr, game_state *state, int tilesize) +{ +} + +#ifdef COMBINED +#define thegame nullgame +#endif + +const struct game thegame = { + "Null Game", NULL, NULL, + default_params, + game_fetch_preset, + decode_params, + encode_params, + free_params, + dup_params, + FALSE, game_configure, custom_params, + validate_params, + new_game_desc, + validate_desc, + new_game, + dup_game, + free_game, + FALSE, solve_game, + FALSE, game_text_format, + new_ui, + free_ui, + encode_ui, + decode_ui, + game_changed_state, + interpret_move, + execute_move, + 20 /* FIXME */, game_compute_size, game_set_size, + game_colours, + game_new_drawstate, + game_free_drawstate, + game_redraw, + game_anim_length, + game_flash_length, + FALSE, FALSE, game_print_size, game_print, + FALSE, /* wants_statusbar */ + FALSE, game_timing_state, + 0, /* flags */ +};