2 * Experimental grid generator for Nikoli's `Number Link' puzzle.
11 * 2005-07-08: This is currently a Path grid generator which will
12 * construct valid grids at a plausible speed. However, the grids
13 * are not of suitable quality to be used directly as puzzles.
15 * The basic strategy is to start with an empty grid, and
16 * repeatedly either (a) add a new path to it, or (b) extend one
17 * end of a path by one square in some direction and push other
18 * paths into new shapes in the process. The effect of this is that
19 * we are able to construct a set of paths which between them fill
22 * Quality issues: if we set the main loop to do (a) where possible
23 * and (b) only where necessary, we end up with a grid containing a
24 * few too many small paths, which therefore doesn't make for an
25 * interesting puzzle. If we reverse the priority so that we do (b)
26 * where possible and (a) only where necessary, we end up with some
27 * staggeringly interwoven grids with very very few separate paths,
28 * but the result of this is that there's invariably a solution
29 * other than the intended one which leaves many grid squares
30 * unfilled. There's also a separate problem which is that many
31 * grids have really boring and obvious paths in them, such as the
32 * entire bottom row of the grid being taken up by a single path.
34 * It's not impossible that a few tweaks might eliminate or reduce
35 * the incidence of boring paths, and might also find a happy
36 * medium between too many and too few. There remains the question
37 * of unique solutions, however. I fear there is no alternative but
38 * to write - somehow! - a solver.
40 * While I'm here, some notes on UI strategy for the parts of the
41 * puzzle implementation that _aren't_ the generator:
43 * - data model is to track connections between adjacent squares,
44 * so that you aren't limited to extending a path out from each
45 * number but can also mark sections of path which you know
46 * _will_ come in handy later.
48 * - user interface is to click in one square and drag to an
49 * adjacent one, thus creating a link between them. We can
50 * probably tolerate rapid mouse motion causing a drag directly
51 * to a square which is a rook move away, but any other rapid
52 * motion is ambiguous and probably the best option is to wait
53 * until the mouse returns to a square we know how to reach.
55 * - a drag causing the current path to backtrack has the effect
56 * of removing bits of it.
58 * - the UI should enforce at all times the constraint that at
59 * most two links can come into any square.
61 * - my Cunning Plan for actually implementing this: the game_ui
62 * contains a grid-sized array, which is copied from the current
63 * game_state on starting a drag. While a drag is active, the
64 * contents of the game_ui is adjusted with every mouse motion,
65 * and is displayed _in place_ of the game_state itself. On
66 * termination of a drag, the game_ui array is copied back into
67 * the new game_state (or rather, a string move is encoded which
68 * has precisely the set of link changes to cause that effect).
72 * Standard notation for directions.
78 #define DX(dir) ( (dir)==L ? -1 : (dir)==R ? +1 : 0)
79 #define DY(dir) ( (dir)==U ? -1 : (dir)==D ? +1 : 0)
82 * Perform a breadth-first search over a grid of squares with the
83 * colour of square (X,Y) given by grid[Y*w+X]. The search begins
84 * at (x,y), and finds all squares which are the same colour as
85 * (x,y) and reachable from it by orthogonal moves. On return:
86 * - dist[Y*w+X] gives the distance of (X,Y) from (x,y), or -1 if
87 * unreachable or a different colour
88 * - the returned value is the number of reachable squares,
89 * including (x,y) itself
90 * - list[0] up to list[returned value - 1] list those squares, in
91 * increasing order of distance from (x,y) (and in arbitrary
94 static int bfs(int w, int h, int *grid, int x, int y, int *dist, int *list)
96 int i, j, c, listsize, listdone;
99 * Start by clearing the output arrays.
101 for (i = 0; i < w*h; i++)
102 dist[i] = list[i] = -1;
105 * Set up the initial list.
114 * Repeatedly process a square and add any extra squares to the
117 while (listdone < listsize) {
118 i = list[listdone++];
121 for (j = 0; j < 4; j++) {
128 if (xx >= 0 && xx < w && yy >= 0 && yy < h &&
129 grid[ii] == c && dist[ii] == -1) {
130 dist[ii] = dist[i] + 1;
131 assert(listsize < w*h);
132 list[listsize++] = ii;
142 int *grid, *sparegrid, *sparegrid2, *sparegrid3;
145 int npaths, pathsize;
146 int *pathends, *sparepathends; /* 2*npaths entries */
147 int *pathspare; /* npaths entries */
148 int *extends; /* 8*npaths entries */
151 static struct genctx *new_genctx(int w, int h)
153 struct genctx *ctx = snew(struct genctx);
156 ctx->grid = snewn(w * h, int);
157 ctx->sparegrid = snewn(w * h, int);
158 ctx->sparegrid2 = snewn(w * h, int);
159 ctx->sparegrid3 = snewn(w * h, int);
160 ctx->dist = snewn(w * h, int);
161 ctx->list = snewn(w * h, int);
162 ctx->npaths = ctx->pathsize = 0;
163 ctx->pathends = ctx->sparepathends = ctx->pathspare = ctx->extends = NULL;
167 static void free_genctx(struct genctx *ctx)
170 sfree(ctx->sparegrid);
171 sfree(ctx->sparegrid2);
172 sfree(ctx->sparegrid3);
175 sfree(ctx->pathends);
176 sfree(ctx->sparepathends);
177 sfree(ctx->pathspare);
181 static int newpath(struct genctx *ctx)
186 if (ctx->npaths > ctx->pathsize) {
188 ctx->pathends = sresize(ctx->pathends, ctx->pathsize*2, int);
189 ctx->sparepathends = sresize(ctx->sparepathends, ctx->pathsize*2, int);
190 ctx->pathspare = sresize(ctx->pathspare, ctx->pathsize, int);
191 ctx->extends = sresize(ctx->extends, ctx->pathsize*8, int);
196 static int is_endpoint(struct genctx *ctx, int x, int y)
198 int w = ctx->w, h = ctx->h, c;
200 assert(x >= 0 && x < w && y >= 0 && y < h);
202 c = ctx->grid[y*w+x];
204 return FALSE; /* empty square is not an endpoint! */
205 assert(c >= 0 && c < ctx->npaths);
206 if (ctx->pathends[c*2] == y*w+x || ctx->pathends[c*2+1] == y*w+x)
212 * Tries to extend a path by one square in the given direction,
213 * pushing other paths around if necessary. Returns TRUE on success
214 * or FALSE on failure.
216 static int extend_path(struct genctx *ctx, int path, int end, int direction)
218 int w = ctx->w, h = ctx->h;
219 int x, y, xe, ye, cut;
220 int i, j, jp, n, first, last;
222 assert(path >= 0 && path < ctx->npaths);
223 assert(end == 0 || end == 1);
226 * Find the endpoint of the path and the point we plan to
229 y = ctx->pathends[path * 2 + end] / w;
230 x = ctx->pathends[path * 2 + end] % w;
231 assert(x >= 0 && x < w && y >= 0 && y < h);
233 xe = x + DX(direction);
234 ye = y + DY(direction);
235 if (xe < 0 || xe >= w || ye < 0 || ye >= h)
236 return FALSE; /* could not extend in this direction */
239 * We don't extend paths _directly_ into endpoints of other
240 * paths, although we don't mind too much if a knock-on effect
241 * of an extension is to push part of another path into a third
244 if (is_endpoint(ctx, xe, ye))
248 * We can't extend a path back the way it came.
250 if (ctx->grid[ye*w+xe] == path)
254 * Paths may not double back on themselves. Check if the new
255 * point is adjacent to any point of this path other than (x,y).
257 for (j = 0; j < 4; j++) {
263 if (xf >= 0 && xf < w && yf >= 0 && yf < h &&
264 (xf != x || yf != y) && ctx->grid[yf*w+xf] == path)
269 * Now we're convinced it's valid to _attempt_ the extension.
270 * It may still fail if we run out of space to push other paths
273 * So now we can set up our temporary data structures. We will
276 * - a spare copy of the grid on which to gradually move paths
279 * - a second spare copy with which to remember how paths
280 * looked just before being cut (sparegrid2). FIXME: is
281 * sparegrid2 necessary? right now it's never different from
284 * - a third spare copy with which to do the internal
285 * calculations involved in reconstituting a cut path
288 * - something to track which paths currently need
289 * reconstituting after being cut, and which have already
290 * been cut (pathspare)
292 * - a spare copy of pathends to store the altered states in
295 memcpy(ctx->sparegrid, ctx->grid, w*h*sizeof(int));
296 memcpy(ctx->sparegrid2, ctx->grid, w*h*sizeof(int));
297 memcpy(ctx->sparepathends, ctx->pathends, ctx->npaths*2*sizeof(int));
298 for (i = 0; i < ctx->npaths; i++)
299 ctx->pathspare[i] = 0; /* 0=untouched, 1=broken, 2=fixed */
302 * Working in sparegrid, actually extend the path. If it cuts
303 * another, begin a loop in which we restore any cut path by
304 * moving it out of the way.
306 cut = ctx->sparegrid[ye*w+xe];
307 ctx->sparegrid[ye*w+xe] = path;
308 ctx->sparepathends[path*2+end] = ye*w+xe;
309 ctx->pathspare[path] = 2; /* this one is sacrosanct */
311 assert(cut >= 0 && cut < ctx->npaths);
312 ctx->pathspare[cut] = 1; /* broken */
315 for (i = 0; i < ctx->npaths; i++)
316 if (ctx->pathspare[i] == 1)
318 if (i == ctx->npaths)
319 break; /* we're done */
322 * Path i needs restoring. So walk along its original
323 * track (as given in sparegrid2) and see where it's
324 * been cut. Where it has, surround the cut points in
325 * the same colour, without overwriting already-fixed
328 memcpy(ctx->sparegrid3, ctx->sparegrid, w*h*sizeof(int));
329 n = bfs(w, h, ctx->sparegrid2,
330 ctx->pathends[i*2] % w, ctx->pathends[i*2] / w,
331 ctx->dist, ctx->list);
333 if (ctx->sparegrid3[ctx->pathends[i*2]] != i ||
334 ctx->sparegrid3[ctx->pathends[i*2+1]] != i) return FALSE;/* FIXME */
335 for (j = 0; j < n; j++) {
337 assert(ctx->dist[jp] == j);
338 assert(ctx->sparegrid2[jp] == i);
341 * Wipe out the original path in sparegrid.
343 if (ctx->sparegrid[jp] == i)
344 ctx->sparegrid[jp] = -1;
347 * Be prepared to shorten the path at either end if
348 * the endpoints have been stomped on.
350 if (ctx->sparegrid3[jp] == i) {
356 if (ctx->sparegrid3[jp] != i) {
357 int jx = jp % w, jy = jp / w;
359 for (dy = -1; dy <= +1; dy++)
360 for (dx = -1; dx <= +1; dx++) {
363 continue; /* central square */
364 if (jx+dx < 0 || jx+dx >= w ||
365 jy+dy < 0 || jy+dy >= h)
366 continue; /* out of range */
367 newp = (jy+dy)*w+(jx+dx);
368 newv = ctx->sparegrid3[newp];
369 if (newv >= 0 && (newv == i ||
370 ctx->pathspare[newv] == 2))
371 continue; /* can't use this square */
372 ctx->sparegrid3[newp] = i;
377 if (first < 0 || last < 0)
378 return FALSE; /* path is completely wiped out! */
381 * Now we've covered sparegrid3 in possible squares for
382 * the new layout of path i. Find the actual layout
383 * we're going to use by bfs: we want the shortest path
384 * from one endpoint to the other.
386 n = bfs(w, h, ctx->sparegrid3, first % w, first / w,
387 ctx->dist, ctx->list);
388 if (ctx->dist[last] < 2) {
390 * Either there is no way to get between the path's
391 * endpoints, or the remaining endpoints simply
392 * aren't far enough apart to make the path viable
393 * any more. This means the entire push operation
400 * Write the new path into sparegrid. Also save the new
401 * endpoint locations, in case they've changed.
408 if (ctx->sparegrid[jp] >= 0) {
409 if (ctx->pathspare[ctx->sparegrid[jp]] == 2)
410 return FALSE; /* somehow we've hit a fixed path */
411 ctx->pathspare[ctx->sparegrid[jp]] = 1; /* broken */
413 ctx->sparegrid[jp] = i;
419 * Now look at the neighbours of jp to find one
420 * which has dist[] one less.
422 for (d = 0; d < 4; d++) {
423 int jx = (jp % w) + DX(d), jy = (jp / w) + DY(d);
424 if (jx >= 0 && jx < w && jy >= 0 && jy < w &&
425 ctx->dist[jy*w+jx] == j-1) {
434 ctx->sparepathends[i*2] = first;
435 ctx->sparepathends[i*2+1] = last;
436 //printf("new ends of path %d: %d,%d\n", i, first, last);
437 ctx->pathspare[i] = 2; /* fixed */
442 * If we got here, the extension was successful!
444 memcpy(ctx->grid, ctx->sparegrid, w*h*sizeof(int));
445 memcpy(ctx->pathends, ctx->sparepathends, ctx->npaths*2*sizeof(int));
450 * Tries to add a new path to the grid.
452 static int add_path(struct genctx *ctx, random_state *rs)
454 int w = ctx->w, h = ctx->h;
459 * - randomly choose an empty square in the grid
460 * - do a BFS from that point to find a long path starting
462 * - if we run out of viable empty squares, return failure.
466 * Use `sparegrid' to collect a list of empty squares.
469 for (i = 0; i < w*h; i++)
470 if (ctx->grid[i] == -1)
471 ctx->sparegrid[n++] = i;
476 for (i = n; i-- > 1 ;) {
477 int k = random_upto(rs, i+1);
479 int t = ctx->sparegrid[i];
480 ctx->sparegrid[i] = ctx->sparegrid[k];
481 ctx->sparegrid[k] = t;
486 * Loop over it trying to add paths. This looks like a
487 * horrifying N^4 algorithm (that is, (w*h)^2), but I predict
488 * that in fact the worst case will very rarely arise because
489 * when there's lots of grid space an attempt will succeed very
492 for (ii = 0; ii < n; ii++) {
493 int i = ctx->sparegrid[ii];
494 int y = i / w, x = i % w, nsq;
498 * BFS from here to find long paths.
500 nsq = bfs(w, h, ctx->grid, x, y, ctx->dist, ctx->list);
503 * If there aren't any long enough, give up immediately.
505 assert(nsq > 0); /* must be the start square at least! */
506 if (ctx->dist[ctx->list[nsq-1]] < 3)
510 * Find the first viable endpoint in ctx->list (i.e. the
511 * first point with distance at least three). I could
512 * binary-search for this, but that would be O(log N)
513 * whereas in fact I can get a constant time bound by just
514 * searching up from the start - after all, there can be at
515 * most 13 points at _less_ than distance 3 from the
518 for (j = 0; j < nsq; j++)
519 if (ctx->dist[ctx->list[j]] >= 3)
521 assert(j < nsq); /* we tested above that there was one */
524 * Now we know that any element of `list' between j and nsq
525 * would be valid in principle. However, we want a few long
526 * paths rather than many small ones, so select only those
527 * elements which are either the maximum length or one
530 while (ctx->dist[ctx->list[j]] + 1 < ctx->dist[ctx->list[nsq-1]])
532 r = j + random_upto(rs, nsq - j);
536 * And that's our endpoint. Mark the new path on the grid.
539 ctx->pathends[c*2] = i;
540 ctx->pathends[c*2+1] = j;
543 int d, np, index, pts[4];
545 for (d = 0; d < 4; d++) {
546 int xn = (j % w) + DX(d), yn = (j / w) + DY(d);
547 if (xn >= 0 && xn < w && yn >= 0 && yn < w &&
548 ctx->dist[yn*w+xn] == ctx->dist[j] - 1)
552 index = random_upto(rs, np);
566 * The main grid generation loop.
568 static void gridgen_mainloop(struct genctx *ctx, random_state *rs)
570 int w = ctx->w, h = ctx->h;
574 * The generation algorithm doesn't always converge. Loop round
578 for (i = 0; i < w*h; i++)
584 * See if the grid is full.
586 for (i = 0; i < w*h; i++)
587 if (ctx->grid[i] < 0)
592 #ifdef GENERATION_DIAGNOSTICS
595 for (y = 0; y < h; y++) {
597 for (x = 0; x < w; x++) {
598 if (ctx->grid[y*w+x] >= 0)
599 printf("%2d", ctx->grid[y*w+x]);
610 if (add_path(ctx, rs)) {
611 #ifdef GENERATION_DIAGNOSTICS
612 printf("added path\n");
618 * Try extending a path. First list all the possible
621 for (i = 0; i < ctx->npaths * 8; i++)
626 * Then shuffle the list.
628 for (i = n; i-- > 1 ;) {
629 int k = random_upto(rs, i+1);
631 int t = ctx->extends[i];
632 ctx->extends[i] = ctx->extends[k];
638 * Now try each one in turn until one works.
640 for (i = 0; i < n; i++) {
648 #ifdef GENERATION_DIAGNOSTICS
649 printf("trying to extend path %d end %d (%d,%d) in dir %d\n", p, e,
650 ctx->pathends[p*2+e] % w,
651 ctx->pathends[p*2+e] / w, d);
653 if (extend_path(ctx, p, e, d)) {
654 #ifdef GENERATION_DIAGNOSTICS
655 printf("extended path %d end %d (%d,%d) in dir %d\n", p, e,
656 ctx->pathends[p*2+e] % w,
657 ctx->pathends[p*2+e] / w, d);
672 * Wrapper function which deals with the boring bits such as
673 * removing the solution from the generated grid, shuffling the
674 * numeric labels and creating/disposing of the context structure.
676 static int *gridgen(int w, int h, random_state *rs)
682 ctx = new_genctx(w, h);
684 gridgen_mainloop(ctx, rs);
687 * There is likely to be an ordering bias in the numbers
688 * (longer paths on lower numbers due to there having been more
689 * grid space when laying them down). So we must shuffle the
690 * numbers. We use ctx->pathspare for this.
692 * This is also as good a time as any to shift to numbering
693 * from 1, for display to the user.
695 for (i = 0; i < ctx->npaths; i++)
696 ctx->pathspare[i] = i+1;
697 for (i = ctx->npaths; i-- > 1 ;) {
698 int k = random_upto(rs, i+1);
700 int t = ctx->pathspare[i];
701 ctx->pathspare[i] = ctx->pathspare[k];
702 ctx->pathspare[k] = t;
706 /* FIXME: remove this at some point! */
709 for (y = 0; y < h; y++) {
711 for (x = 0; x < w; x++) {
712 assert(ctx->grid[y*w+x] >= 0);
713 printf("%2d", ctx->pathspare[ctx->grid[y*w+x]]);
721 * Clear the grid, and write in just the endpoints.
723 for (i = 0; i < w*h; i++)
725 for (i = 0; i < ctx->npaths; i++) {
726 ctx->grid[ctx->pathends[i*2]] =
727 ctx->grid[ctx->pathends[i*2+1]] = ctx->pathspare[i];
745 random_state *rs = random_init("12345", 5);
748 for (i = 0; i < 10; i++) {
749 grid = gridgen(w, h, rs);
751 for (y = 0; y < h; y++) {
753 for (x = 0; x < w; x++) {
755 printf("%2d", grid[y*w+x]);
773 void fatal(char *fmt, ...)
777 fprintf(stderr, "fatal error: ");
780 vfprintf(stderr, fmt, ap);
783 fprintf(stderr, "\n");