puzzles: refactor and resync with upstream

This brings puzzles up-to-date with upstream revision
2d333750272c3967cfd5cd3677572cddeaad5932, though certain changes made
by me, including cursor-only Untangle and some compilation fixes
remain. Upstream code has been moved to its separate subdirectory and
future syncs can be done by simply copying over the new sources.

Change-Id: Ia6506ca5f78c3627165ea6791d38db414ace0804

1 files changed, 3995 insertions, 0 deletions

diff --git a/apps/plugins/puzzles/src/galaxies.c b/apps/plugins/puzzles/src/galaxies.c
new file mode 100644
index 0000000000..f4f75c629c
--- /dev/null
+++ b/apps/plugins/puzzles/src/galaxies.c
@@ -0,0 +1,3995 @@
+/*
+ * galaxies.c: implementation of 'Tentai Show' from Nikoli,
+ *             also sometimes called 'Spiral Galaxies'.
+ *
+ * Notes:
+ *
+ * Grid is stored as size (2n-1), holding edges as well as spaces
+ * (and thus vertices too, at edge intersections).
+ *
+ * Any dot will thus be positioned at one of our grid points,
+ * which saves any faffing with half-of-a-square stuff.
+ *
+ * Edges have on/off state; obviously the actual edges of the
+ * board are fixed to on, and everything else starts as off.
+ *
+ * TTD:
+   * Cleverer solver
+   * Think about how to display remote groups of tiles?
+ *
+ * Bugs:
+ *
+ * Notable puzzle IDs:
+ *
+ * Nikoli's example [web site has wrong highlighting]
+ * (at http://www.nikoli.co.jp/en/puzzles/astronomical_show/):
+ *  5x5:eBbbMlaBbOEnf
+ *
+ * The 'spiral galaxies puzzles are NP-complete' paper
+ * (at http://www.stetson.edu/~efriedma/papers/spiral.pdf):
+ *  7x7:chpgdqqqoezdddki
+ *
+ * Puzzle competition pdf examples
+ * (at http://www.puzzleratings.org/Yurekli2006puz.pdf):
+ *  6x6:EDbaMucCohbrecEi
+ *  10x10:beFbufEEzowDlxldibMHezBQzCdcFzjlci
+ *  13x13:dCemIHFFkJajjgDfdbdBzdzEgjccoPOcztHjBczLDjczqktJjmpreivvNcggFi
+ *
+ */
+
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+#include <assert.h>
+#include <ctype.h>
+#include <math.h>
+
+#include "puzzles.h"
+
+#ifdef DEBUGGING
+#define solvep debug
+#else
+int solver_show_working;
+#define solvep(x) do { if (solver_show_working) { printf x; } } while(0)
+#endif
+
+#ifdef STANDALONE_PICTURE_GENERATOR
+/*
+ * Dirty hack to enable the generator to construct a game ID which
+ * solves to a specified black-and-white bitmap. We define a global
+ * variable here which gives the desired colour of each square, and
+ * we arrange that the grid generator never merges squares of
+ * different colours.
+ *
+ * The bitmap as stored here is a simple int array (at these sizes
+ * it isn't worth doing fiddly bit-packing). picture[y*w+x] is 1
+ * iff the pixel at (x,y) is intended to be black.
+ *
+ * (It might be nice to be able to specify some pixels as
+ * don't-care, to give the generator more leeway. But that might be
+ * fiddly.)
+ */
+static int *picture;
+#endif
+
+enum {
+    COL_BACKGROUND,
+    COL_WHITEBG,
+    COL_BLACKBG,
+    COL_WHITEDOT,
+    COL_BLACKDOT,
+    COL_GRID,
+    COL_EDGE,
+    COL_ARROW,
+    COL_CURSOR,
+    NCOLOURS
+};
+
+#define DIFFLIST(A)             \
+    A(NORMAL,Normal,n)          \
+    A(UNREASONABLE,Unreasonable,u)
+
+#define ENUM(upper,title,lower) DIFF_ ## upper,
+#define TITLE(upper,title,lower) #title,
+#define ENCODE(upper,title,lower) #lower
+#define CONFIG(upper,title,lower) ":" #title
+enum { DIFFLIST(ENUM)
+    DIFF_IMPOSSIBLE, DIFF_AMBIGUOUS, DIFF_UNFINISHED, DIFF_MAX };
+static char const *const galaxies_diffnames[] = {
+    DIFFLIST(TITLE) "Impossible", "Ambiguous", "Unfinished" };
+static char const galaxies_diffchars[] = DIFFLIST(ENCODE);
+#define DIFFCONFIG DIFFLIST(CONFIG)
+
+struct game_params {
+    /* X and Y is the area of the board as seen by
+     * the user, not the (2n+1) area the game uses. */
+    int w, h, diff;
+};
+
+enum { s_tile, s_edge, s_vertex };
+
+#define F_DOT           1       /* there's a dot here */
+#define F_EDGE_SET      2       /* the edge is set */
+#define F_TILE_ASSOC    4       /* this tile is associated with a dot. */
+#define F_DOT_BLACK     8       /* (ui only) dot is black. */
+#define F_MARK          16      /* scratch flag */
+#define F_REACHABLE     32
+#define F_SCRATCH       64
+#define F_MULTIPLE      128
+#define F_DOT_HOLD      256
+#define F_GOOD          512
+
+typedef struct space {
+    int x, y;           /* its position */
+    int type;
+    unsigned int flags;
+    int dotx, doty;     /* if flags & F_TILE_ASSOC */
+    int nassoc;         /* if flags & F_DOT */
+} space;
+
+#define INGRID(s,x,y) ((x) >= 0 && (y) >= 0 &&                  \
+                       (x) < (state)->sx && (y) < (state)->sy)
+#define INUI(s,x,y)   ((x) > 0 && (y) > 0 &&                  \
+                       (x) < ((state)->sx-1) && (y) < ((state)->sy-1))
+
+#define GRID(s,g,x,y) ((s)->g[((y)*(s)->sx)+(x)])
+#define SPACE(s,x,y) GRID(s,grid,x,y)
+
+struct game_state {
+    int w, h;           /* size from params */
+    int sx, sy;         /* allocated size, (2x-1)*(2y-1) */
+    space *grid;
+    int completed, used_solve;
+    int ndots;
+    space **dots;
+
+    midend *me;         /* to call supersede_game_desc */
+    int cdiff;          /* difficulty of current puzzle (for status bar),
+                           or -1 if stale. */
+};
+
+static int check_complete(const game_state *state, int *dsf, int *colours);
+static int solver_state(game_state *state, int maxdiff);
+static int solver_obvious(game_state *state);
+static int solver_obvious_dot(game_state *state, space *dot);
+static space *space_opposite_dot(const game_state *state, const space *sp,
+                                 const space *dot);
+static space *tile_opposite(const game_state *state, const space *sp);
+
+/* ----------------------------------------------------------
+ * Game parameters and presets
+ */
+
+/* make up some sensible default sizes */
+
+#define DEFAULT_PRESET 0
+
+static const game_params galaxies_presets[] = {
+    {  7,  7, DIFF_NORMAL },
+    {  7,  7, DIFF_UNREASONABLE },
+    { 10, 10, DIFF_NORMAL },
+    { 15, 15, DIFF_NORMAL },
+};
+
+static int game_fetch_preset(int i, char **name, game_params **params)
+{
+    game_params *ret;
+    char buf[80];
+
+    if (i < 0 || i >= lenof(galaxies_presets))
+        return FALSE;
+
+    ret = snew(game_params);
+    *ret = galaxies_presets[i]; /* structure copy */
+
+    sprintf(buf, "%dx%d %s", ret->w, ret->h,
+            galaxies_diffnames[ret->diff]);
+
+    if (name) *name = dupstr(buf);
+    *params = ret;
+    return TRUE;
+}
+
+static game_params *default_params(void)
+{
+    game_params *ret;
+    game_fetch_preset(DEFAULT_PRESET, NULL, &ret);
+    return ret;
+}
+
+static void free_params(game_params *params)
+{
+    sfree(params);
+}
+
+static game_params *dup_params(const 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->h = params->w = atoi(string);
+    params->diff = DIFF_NORMAL;
+    while (*string && isdigit((unsigned char)*string)) string++;
+    if (*string == 'x') {
+        string++;
+        params->h = atoi(string);
+        while (*string && isdigit((unsigned char)*string)) string++;
+    }
+    if (*string == 'd') {
+        int i;
+        string++;
+        for (i = 0; i <= DIFF_UNREASONABLE; i++)
+            if (*string == galaxies_diffchars[i])
+                params->diff = i;
+        if (*string) string++;
+    }
+}
+
+static char *encode_params(const game_params *params, int full)
+{
+    char str[80];
+    sprintf(str, "%dx%d", params->w, params->h);
+    if (full)
+        sprintf(str + strlen(str), "d%c", galaxies_diffchars[params->diff]);
+    return dupstr(str);
+}
+
+static config_item *game_configure(const game_params *params)
+{
+    config_item *ret;
+    char buf[80];
+
+    ret = snewn(4, config_item);
+
+    ret[0].name = "Width";
+    ret[0].type = C_STRING;
+    sprintf(buf, "%d", params->w);
+    ret[0].sval = dupstr(buf);
+    ret[0].ival = 0;
+
+    ret[1].name = "Height";
+    ret[1].type = C_STRING;
+    sprintf(buf, "%d", params->h);
+    ret[1].sval = dupstr(buf);
+    ret[1].ival = 0;
+
+    ret[2].name = "Difficulty";
+    ret[2].type = C_CHOICES;
+    ret[2].sval = DIFFCONFIG;
+    ret[2].ival = params->diff;
+
+    ret[3].name = NULL;
+    ret[3].type = C_END;
+    ret[3].sval = NULL;
+    ret[3].ival = 0;
+
+    return ret;
+}
+
+static game_params *custom_params(const config_item *cfg)
+{
+    game_params *ret = snew(game_params);
+
+    ret->w = atoi(cfg[0].sval);
+    ret->h = atoi(cfg[1].sval);
+    ret->diff = cfg[2].ival;
+
+    return ret;
+}
+
+static char *validate_params(const game_params *params, int full)
+{
+    if (params->w < 3 || params->h < 3)
+        return "Width and height must both be at least 3";
+    /*
+     * This shouldn't be able to happen at all, since decode_params
+     * and custom_params will never generate anything that isn't
+     * within range.
+     */
+    assert(params->diff <= DIFF_UNREASONABLE);
+
+    return NULL;
+}
+
+/* ----------------------------------------------------------
+ * Game utility functions.
+ */
+
+static void add_dot(space *space) {
+    assert(!(space->flags & F_DOT));
+    space->flags |= F_DOT;
+    space->nassoc = 0;
+}
+
+static void remove_dot(space *space) {
+    assert(space->flags & F_DOT);
+    space->flags &= ~F_DOT;
+}
+
+static void remove_assoc(const game_state *state, space *tile) {
+    if (tile->flags & F_TILE_ASSOC) {
+        SPACE(state, tile->dotx, tile->doty).nassoc--;
+        tile->flags &= ~F_TILE_ASSOC;
+        tile->dotx = -1;
+        tile->doty = -1;
+    }
+}
+
+static void remove_assoc_with_opposite(game_state *state, space *tile) {
+    space *opposite;
+
+    if (!(tile->flags & F_TILE_ASSOC)) {
+        return;
+    }
+
+    opposite = tile_opposite(state, tile);
+    remove_assoc(state, tile);
+
+    if (opposite != NULL && opposite != tile) {
+        remove_assoc(state, opposite);
+    }
+}
+
+static void add_assoc(const game_state *state, space *tile, space *dot) {
+    remove_assoc(state, tile);
+
+#ifdef STANDALONE_PICTURE_GENERATOR
+    if (picture)
+        assert(!picture[(tile->y/2) * state->w + (tile->x/2)] ==
+               !(dot->flags & F_DOT_BLACK));
+#endif
+    tile->flags |= F_TILE_ASSOC;
+    tile->dotx = dot->x;
+    tile->doty = dot->y;
+    dot->nassoc++;
+    /*debug(("add_assoc sp %d %d --> dot %d,%d, new nassoc %d.\n",
+           tile->x, tile->y, dot->x, dot->y, dot->nassoc));*/
+}
+
+static void add_assoc_with_opposite(game_state *state, space *tile, space *dot) {
+    int *colors;
+    space *opposite = space_opposite_dot(state, tile, dot);
+
+    if (opposite == NULL) {
+        return;
+    }
+    if (opposite->flags & F_DOT) {
+        return;
+    }
+
+    colors = snewn(state->w * state->h, int);
+    check_complete(state, NULL, colors);
+    if (colors[(tile->y - 1)/2 * state->w + (tile->x - 1)/2]) {
+        sfree(colors);
+        return;
+    }
+    if (colors[(opposite->y - 1)/2 * state->w + (opposite->x - 1)/2]) {
+        sfree(colors);
+        return;
+    }
+
+    sfree(colors);
+    remove_assoc_with_opposite(state, tile);
+    add_assoc(state, tile, dot);
+    remove_assoc_with_opposite(state, opposite);
+    add_assoc(state, opposite, dot);
+}
+
+static space *sp2dot(const game_state *state, int x, int y)
+{
+    space *sp = &SPACE(state, x, y);
+    if (!(sp->flags & F_TILE_ASSOC)) return NULL;
+    return &SPACE(state, sp->dotx, sp->doty);
+}
+
+#define IS_VERTICAL_EDGE(x) ((x % 2) == 0)
+
+static int game_can_format_as_text_now(const game_params *params)
+{
+    return TRUE;
+}
+
+static char *game_text_format(const game_state *state)
+{
+    int maxlen = (state->sx+1)*state->sy, x, y;
+    char *ret, *p;
+    space *sp;
+
+    ret = snewn(maxlen+1, char);
+    p = ret;
+
+    for (y = 0; y < state->sy; y++) {
+        for (x = 0; x < state->sx; x++) {
+            sp = &SPACE(state, x, y);
+            if (sp->flags & F_DOT)
+                *p++ = 'o';
+#if 0
+            else if (sp->flags & (F_REACHABLE|F_MULTIPLE|F_MARK))
+                *p++ = (sp->flags & F_MULTIPLE) ? 'M' :
+                    (sp->flags & F_REACHABLE) ? 'R' : 'X';
+#endif
+            else {
+                switch (sp->type) {
+                case s_tile:
+                    if (sp->flags & F_TILE_ASSOC) {
+                        space *dot = sp2dot(state, sp->x, sp->y);
+                        if (dot && dot->flags & F_DOT)
+                            *p++ = (dot->flags & F_DOT_BLACK) ? 'B' : 'W';
+                        else
+                            *p++ = '?'; /* association with not-a-dot. */
+                    } else
+                        *p++ = ' ';
+                    break;
+
+                case s_vertex:
+                    *p++ = '+';
+                    break;
+
+                case s_edge:
+                    if (sp->flags & F_EDGE_SET)
+                        *p++ = (IS_VERTICAL_EDGE(x)) ? '|' : '-';
+                    else
+                        *p++ = ' ';
+                    break;
+
+                default:
+                    assert(!"shouldn't get here!");
+                }
+            }
+        }
+        *p++ = '\n';
+    }
+
+    assert(p - ret == maxlen);
+    *p = '\0';
+
+    return ret;
+}
+
+static void dbg_state(const game_state *state)
+{
+#ifdef DEBUGGING
+    char *temp = game_text_format(state);
+    debug(("%s\n", temp));
+    sfree(temp);
+#endif
+}
+
+/* Space-enumeration callbacks should all return 1 for 'progress made',
+ * -1 for 'impossible', and 0 otherwise. */
+typedef int (*space_cb)(game_state *state, space *sp, void *ctx);
+
+#define IMPOSSIBLE_QUITS        1
+
+static int foreach_sub(game_state *state, space_cb cb, unsigned int f,
+                       void *ctx, int startx, int starty)
+{
+    int x, y, progress = 0, impossible = 0, ret;
+    space *sp;
+
+    for (y = starty; y < state->sy; y += 2) {
+        sp = &SPACE(state, startx, y);
+        for (x = startx; x < state->sx; x += 2) {
+            ret = cb(state, sp, ctx);
+            if (ret == -1) {
+                if (f & IMPOSSIBLE_QUITS) return -1;
+                impossible = -1;
+            } else if (ret == 1) {
+                progress = 1;
+            }
+            sp += 2;
+        }
+    }
+    return impossible ? -1 : progress;
+}
+
+static int foreach_tile(game_state *state, space_cb cb, unsigned int f,
+                        void *ctx)
+{
+    return foreach_sub(state, cb, f, ctx, 1, 1);
+}
+
+static int foreach_edge(game_state *state, space_cb cb, unsigned int f,
+                        void *ctx)
+{
+    int ret1, ret2;
+
+    ret1 = foreach_sub(state, cb, f, ctx, 0, 1);
+    ret2 = foreach_sub(state, cb, f, ctx, 1, 0);
+
+    if (ret1 == -1 || ret2 == -1) return -1;
+    return (ret1 || ret2) ? 1 : 0;
+}
+
+#if 0
+static int foreach_vertex(game_state *state, space_cb cb, unsigned int f,
+                          void *ctx)
+{
+    return foreach_sub(state, cb, f, ctx, 0, 0);
+}
+#endif
+
+#if 0
+static int is_same_assoc(game_state *state,
+                         int x1, int y1, int x2, int y2)
+{
+    space *s1, *s2;
+
+    if (!INGRID(state, x1, y1) || !INGRID(state, x2, y2))
+        return 0;
+
+    s1 = &SPACE(state, x1, y1);
+    s2 = &SPACE(state, x2, y2);
+    assert(s1->type == s_tile && s2->type == s_tile);
+    if ((s1->flags & F_TILE_ASSOC) && (s2->flags & F_TILE_ASSOC) &&
+        s1->dotx == s2->dotx && s1->doty == s2->doty)
+        return 1;
+    return 0; /* 0 if not same or not both associated. */
+}
+#endif
+
+#if 0
+static int edges_into_vertex(game_state *state,
+                             int x, int y)
+{
+    int dx, dy, nx, ny, count = 0;
+
+    assert(SPACE(state, x, y).type == s_vertex);
+    for (dx = -1; dx <= 1; dx++) {
+        for (dy = -1; dy <= 1; dy++) {
+            if (dx != 0 && dy != 0) continue;
+            if (dx == 0 && dy == 0) continue;
+
+            nx = x+dx; ny = y+dy;
+            if (!INGRID(state, nx, ny)) continue;
+            assert(SPACE(state, nx, ny).type == s_edge);
+            if (SPACE(state, nx, ny).flags & F_EDGE_SET)
+                count++;
+        }
+    }
+    return count;
+}
+#endif
+
+static space *space_opposite_dot(const game_state *state, const space *sp,
+                                 const space *dot)
+{
+    int dx, dy, tx, ty;
+    space *sp2;
+
+    dx = sp->x - dot->x;
+    dy = sp->y - dot->y;
+    tx = dot->x - dx;
+    ty = dot->y - dy;
+    if (!INGRID(state, tx, ty)) return NULL;
+
+    sp2 = &SPACE(state, tx, ty);
+    assert(sp2->type == sp->type);
+    return sp2;
+}
+
+static space *tile_opposite(const game_state *state, const space *sp)
+{
+    space *dot;
+
+    assert(sp->flags & F_TILE_ASSOC);
+    dot = &SPACE(state, sp->dotx, sp->doty);
+    return space_opposite_dot(state, sp, dot);
+}
+
+static int dotfortile(game_state *state, space *tile, space *dot)
+{
+    space *tile_opp = space_opposite_dot(state, tile, dot);
+
+    if (!tile_opp) return 0; /* opposite would be off grid */
+    if (tile_opp->flags & F_TILE_ASSOC &&
+            (tile_opp->dotx != dot->x || tile_opp->doty != dot->y))
+            return 0; /* opposite already associated with diff. dot */
+    return 1;
+}
+
+static void adjacencies(game_state *state, space *sp, space **a1s, space **a2s)
+{
+    int dxs[4] = {-1, 1, 0, 0}, dys[4] = {0, 0, -1, 1};
+    int n, x, y;
+
+    /* this function needs optimising. */
+
+    for (n = 0; n < 4; n++) {
+        x = sp->x+dxs[n];
+        y = sp->y+dys[n];
+
+        if (INGRID(state, x, y)) {
+            a1s[n] = &SPACE(state, x, y);
+
+            x += dxs[n]; y += dys[n];
+
+            if (INGRID(state, x, y))
+                a2s[n] = &SPACE(state, x, y);
+            else
+                a2s[n] = NULL;
+        } else {
+            a1s[n] = a2s[n] = NULL;
+        }
+    }
+}
+
+static int outline_tile_fordot(game_state *state, space *tile, int mark)
+{
+    space *tadj[4], *eadj[4];
+    int i, didsth = 0, edge, same;
+
+    assert(tile->type == s_tile);
+    adjacencies(state, tile, eadj, tadj);
+    for (i = 0; i < 4; i++) {
+        if (!eadj[i]) continue;
+
+        edge = (eadj[i]->flags & F_EDGE_SET) ? 1 : 0;
+        if (tadj[i]) {
+            if (!(tile->flags & F_TILE_ASSOC))
+                same = (tadj[i]->flags & F_TILE_ASSOC) ? 0 : 1;
+            else
+                same = ((tadj[i]->flags & F_TILE_ASSOC) &&
+                    tile->dotx == tadj[i]->dotx &&
+                    tile->doty == tadj[i]->doty) ? 1 : 0;
+        } else
+            same = 0;
+
+        if (!edge && !same) {
+            if (mark) eadj[i]->flags |= F_EDGE_SET;
+            didsth = 1;
+        } else if (edge && same) {
+            if (mark) eadj[i]->flags &= ~F_EDGE_SET;
+            didsth = 1;
+        }
+    }
+    return didsth;
+}
+
+static void tiles_from_edge(game_state *state, space *sp, space **ts)
+{
+    int xs[2], ys[2];
+
+    if (IS_VERTICAL_EDGE(sp->x)) {
+        xs[0] = sp->x-1; ys[0] = sp->y;
+        xs[1] = sp->x+1; ys[1] = sp->y;
+    } else {
+        xs[0] = sp->x; ys[0] = sp->y-1;
+        xs[1] = sp->x; ys[1] = sp->y+1;
+    }
+    ts[0] = INGRID(state, xs[0], ys[0]) ? &SPACE(state, xs[0], ys[0]) : NULL;
+    ts[1] = INGRID(state, xs[1], ys[1]) ? &SPACE(state, xs[1], ys[1]) : NULL;
+}
+
+/* Returns a move string for use by 'solve', including the initial
+ * 'S' if issolve is true. */
+static char *diff_game(const game_state *src, const game_state *dest,
+                       int issolve)
+{
+    int movelen = 0, movesize = 256, x, y, len;
+    char *move = snewn(movesize, char), buf[80], *sep = "";
+    char achar = issolve ? 'a' : 'A';
+    space *sps, *spd;
+
+    assert(src->sx == dest->sx && src->sy == dest->sy);
+
+    if (issolve) {
+        move[movelen++] = 'S';
+        sep = ";";
+    }
+    move[movelen] = '\0';
+    for (x = 0; x < src->sx; x++) {
+        for (y = 0; y < src->sy; y++) {
+            sps = &SPACE(src, x, y);
+            spd = &SPACE(dest, x, y);
+
+            assert(sps->type == spd->type);
+
+            len = 0;
+            if (sps->type == s_tile) {
+                if ((sps->flags & F_TILE_ASSOC) &&
+                    (spd->flags & F_TILE_ASSOC)) {
+                    if (sps->dotx != spd->dotx ||
+                        sps->doty != spd->doty)
+                    /* Both associated; change association, if different */
+                        len = sprintf(buf, "%s%c%d,%d,%d,%d", sep,
+                                      (int)achar, x, y, spd->dotx, spd->doty);
+                } else if (sps->flags & F_TILE_ASSOC)
+                    /* Only src associated; remove. */
+                    len = sprintf(buf, "%sU%d,%d", sep, x, y);
+                else if (spd->flags & F_TILE_ASSOC)
+                    /* Only dest associated; add. */
+                    len = sprintf(buf, "%s%c%d,%d,%d,%d", sep,
+                                  (int)achar, x, y, spd->dotx, spd->doty);
+            } else if (sps->type == s_edge) {
+                if ((sps->flags & F_EDGE_SET) != (spd->flags & F_EDGE_SET))
+                    /* edge flags are different; flip them. */
+                    len = sprintf(buf, "%sE%d,%d", sep, x, y);
+            }
+            if (len) {
+                if (movelen + len >= movesize) {
+                    movesize = movelen + len + 256;
+                    move = sresize(move, movesize, char);
+                }
+                strcpy(move + movelen, buf);
+                movelen += len;
+                sep = ";";
+            }
+        }
+    }
+    debug(("diff_game src then dest:\n"));
+    dbg_state(src);
+    dbg_state(dest);
+    debug(("diff string %s\n", move));
+    return move;
+}
+
+/* Returns 1 if a dot here would not be too close to any other dots
+ * (and would avoid other game furniture). */
+static int dot_is_possible(game_state *state, space *sp, int allow_assoc)
+{
+    int bx = 0, by = 0, dx, dy;
+    space *adj;
+#ifdef STANDALONE_PICTURE_GENERATOR
+    int col = -1;
+#endif
+
+    switch (sp->type) {
+    case s_tile:
+        bx = by = 1; break;
+    case s_edge:
+        if (IS_VERTICAL_EDGE(sp->x)) {
+            bx = 2; by = 1;
+        } else {
+            bx = 1; by = 2;
+        }
+        break;
+    case s_vertex:
+        bx = by = 2; break;
+    }
+
+    for (dx = -bx; dx <= bx; dx++) {
+        for (dy = -by; dy <= by; dy++) {
+            if (!INGRID(state, sp->x+dx, sp->y+dy)) continue;
+
+            adj = &SPACE(state, sp->x+dx, sp->y+dy);
+
+#ifdef STANDALONE_PICTURE_GENERATOR
+            /*
+             * Check that all the squares we're looking at have the
+             * same colour.
+             */
+            if (picture) {
+                if (adj->type == s_tile) {
+                    int c = picture[(adj->y / 2) * state->w + (adj->x / 2)];
+                    if (col < 0)
+                        col = c;
+                    if (c != col)
+                        return 0;          /* colour mismatch */
+                }
+            }
+#endif
+
+            if (!allow_assoc && (adj->flags & F_TILE_ASSOC))
+                return 0;
+
+            if (dx != 0 || dy != 0) {
+                /* Other than our own square, no dots nearby. */
+                if (adj->flags & (F_DOT))
+                    return 0;
+            }
+
+            /* We don't want edges within our rectangle
+             * (but don't care about edges on the edge) */
+            if (abs(dx) < bx && abs(dy) < by &&
+                adj->flags & F_EDGE_SET)
+                return 0;
+        }
+    }
+    return 1;
+}
+
+/* ----------------------------------------------------------
+ * Game generation, structure creation, and descriptions.
+ */
+
+static game_state *blank_game(int w, int h)
+{
+    game_state *state = snew(game_state);
+    int x, y;
+
+    state->w = w;
+    state->h = h;
+
+    state->sx = (w*2)+1;
+    state->sy = (h*2)+1;
+    state->grid = snewn(state->sx * state->sy, space);
+    state->completed = state->used_solve = 0;
+
+    for (x = 0; x < state->sx; x++) {
+        for (y = 0; y < state->sy; y++) {
+            space *sp = &SPACE(state, x, y);
+            memset(sp, 0, sizeof(space));
+            sp->x = x;
+            sp->y = y;
+            if ((x % 2) == 0 && (y % 2) == 0)
+                sp->type = s_vertex;
+            else if ((x % 2) == 0 || (y % 2) == 0) {
+                sp->type = s_edge;
+                if (x == 0 || y == 0 || x == state->sx-1 || y == state->sy-1)
+                    sp->flags |= F_EDGE_SET;
+            } else
+                sp->type = s_tile;
+        }
+    }
+
+    state->ndots = 0;
+    state->dots = NULL;
+
+    state->me = NULL; /* filled in by new_game. */
+    state->cdiff = -1;
+
+    return state;
+}
+
+static void game_update_dots(game_state *state)
+{
+    int i, n, sz = state->sx * state->sy;
+
+    if (state->dots) sfree(state->dots);
+    state->ndots = 0;
+
+    for (i = 0; i < sz; i++) {
+        if (state->grid[i].flags & F_DOT) state->ndots++;
+    }
+    state->dots = snewn(state->ndots, space *);
+    n = 0;
+    for (i = 0; i < sz; i++) {
+        if (state->grid[i].flags & F_DOT)
+            state->dots[n++] = &state->grid[i];
+    }
+}
+
+static void clear_game(game_state *state, int cleardots)
+{
+    int x, y;
+
+    /* don't erase edge flags around outline! */
+    for (x = 1; x < state->sx-1; x++) {
+        for (y = 1; y < state->sy-1; y++) {
+            if (cleardots)
+                SPACE(state, x, y).flags = 0;
+            else
+                SPACE(state, x, y).flags &= (F_DOT|F_DOT_BLACK);
+        }
+    }
+    if (cleardots) game_update_dots(state);
+}
+
+static game_state *dup_game(const game_state *state)
+{
+    game_state *ret = blank_game(state->w, state->h);
+
+    ret->completed = state->completed;
+    ret->used_solve = state->used_solve;
+
+    memcpy(ret->grid, state->grid,
+           ret->sx*ret->sy*sizeof(space));
+
+    game_update_dots(ret);
+
+    ret->me = state->me;
+    ret->cdiff = state->cdiff;
+
+    return ret;
+}
+
+static void free_game(game_state *state)
+{
+    if (state->dots) sfree(state->dots);
+    sfree(state->grid);
+    sfree(state);
+}
+
+/* Game description is a sequence of letters representing the number
+ * of spaces (a = 0, y = 24) before the next dot; a-y for a white dot,
+ * and A-Y for a black dot. 'z' is 25 spaces (and no dot).
+ *
+ * I know it's a bitch to generate by hand, so we provide
+ * an edit mode.
+ */
+
+static char *encode_game(game_state *state)
+{
+    char *desc, *p;
+    int run, x, y, area;
+    unsigned int f;
+
+    area = (state->sx-2) * (state->sy-2);
+
+    desc = snewn(area, char);
+    p = desc;
+    run = 0;
+    for (y = 1; y < state->sy-1; y++) {
+        for (x = 1; x < state->sx-1; x++) {
+            f = SPACE(state, x, y).flags;
+
+            /* a/A is 0 spaces between, b/B is 1 space, ...
+             * y/Y is 24 spaces, za/zA is 25 spaces, ...
+             * It's easier to count from 0 because we then
+             * don't have to special-case the top left-hand corner
+             * (which could be a dot with 0 spaces before it). */
+            if (!(f & F_DOT))
+                run++;
+            else {
+                while (run > 24) {
+                    *p++ = 'z';
+                    run -= 25;
+                }
+                *p++ = ((f & F_DOT_BLACK) ? 'A' : 'a') + run;
+                run = 0;
+            }
+        }
+    }
+    assert(p - desc < area);
+    *p++ = '\0';
+    desc = sresize(desc, p - desc, char);
+
+    return desc;
+}
+
+struct movedot {
+    int op;
+    space *olddot, *newdot;
+};
+
+enum { MD_CHECK, MD_MOVE };
+
+static int movedot_cb(game_state *state, space *tile, void *vctx)
+{
+   struct movedot *md = (struct movedot *)vctx;
+   space *newopp = NULL;
+
+   assert(tile->type == s_tile);
+   assert(md->olddot && md->newdot);
+
+   if (!(tile->flags & F_TILE_ASSOC)) return 0;
+   if (tile->dotx != md->olddot->x || tile->doty != md->olddot->y)
+       return 0;
+
+   newopp = space_opposite_dot(state, tile, md->newdot);
+
+   switch (md->op) {
+   case MD_CHECK:
+       /* If the tile is associated with the old dot, check its
+        * opposite wrt the _new_ dot is empty or same assoc. */
+       if (!newopp) return -1; /* no new opposite */
+       if (newopp->flags & F_TILE_ASSOC) {
+           if (newopp->dotx != md->olddot->x ||
+               newopp->doty != md->olddot->y)
+               return -1; /* associated, but wrong dot. */
+       }
+#ifdef STANDALONE_PICTURE_GENERATOR
+       if (picture) {
+           /*
+            * Reject if either tile and the dot don't match in colour.
+            */
+           if (!(picture[(tile->y/2) * state->w + (tile->x/2)]) ^
+               !(md->newdot->flags & F_DOT_BLACK))
+               return -1;
+           if (!(picture[(newopp->y/2) * state->w + (newopp->x/2)]) ^
+               !(md->newdot->flags & F_DOT_BLACK))
+               return -1;
+       }
+#endif
+       break;
+
+   case MD_MOVE:
+       /* Move dot associations: anything that was associated
+        * with the old dot, and its opposite wrt the new dot,
+        * become associated with the new dot. */
+       assert(newopp);
+       debug(("Associating %d,%d and %d,%d with new dot %d,%d.\n",
+              tile->x, tile->y, newopp->x, newopp->y,
+              md->newdot->x, md->newdot->y));
+       add_assoc(state, tile, md->newdot);
+       add_assoc(state, newopp, md->newdot);
+       return 1; /* we did something! */
+   }
+   return 0;
+}
+
+/* For the given dot, first see if we could expand it into all the given
+ * extra spaces (by checking for empty spaces on the far side), and then
+ * see if we can move the dot to shift the CoG to include the new spaces.
+ */
+static int dot_expand_or_move(game_state *state, space *dot,
+                              space **toadd, int nadd)
+{
+    space *tileopp;
+    int i, ret, nnew, cx, cy;
+    struct movedot md;
+
+    debug(("dot_expand_or_move: %d tiles for dot %d,%d\n",
+           nadd, dot->x, dot->y));
+    for (i = 0; i < nadd; i++)
+        debug(("dot_expand_or_move:   dot %d,%d\n",
+               toadd[i]->x, toadd[i]->y));
+    assert(dot->flags & F_DOT);
+
+#ifdef STANDALONE_PICTURE_GENERATOR
+    if (picture) {
+        /*
+         * Reject the expansion totally if any of the new tiles are
+         * the wrong colour.
+         */
+        for (i = 0; i < nadd; i++) {
+            if (!(picture[(toadd[i]->y/2) * state->w + (toadd[i]->x/2)]) ^
+                !(dot->flags & F_DOT_BLACK))
+                return 0;
+        }
+    }
+#endif
+
+    /* First off, could we just expand the current dot's tile to cover
+     * the space(s) passed in and their opposites? */
+    for (i = 0; i < nadd; i++) {
+        tileopp = space_opposite_dot(state, toadd[i], dot);
+        if (!tileopp) goto noexpand;
+        if (tileopp->flags & F_TILE_ASSOC) goto noexpand;
+#ifdef STANDALONE_PICTURE_GENERATOR
+        if (picture) {
+            /*
+             * The opposite tiles have to be the right colour as well.
+             */
+            if (!(picture[(tileopp->y/2) * state->w + (tileopp->x/2)]) ^
+                !(dot->flags & F_DOT_BLACK))
+                goto noexpand;
+        }
+#endif
+    }
+    /* OK, all spaces have valid empty opposites: associate spaces and
+     * opposites with our dot. */
+    for (i = 0; i < nadd; i++) {
+        tileopp = space_opposite_dot(state, toadd[i], dot);
+        add_assoc(state, toadd[i], dot);
+        add_assoc(state, tileopp, dot);
+        debug(("Added associations %d,%d and %d,%d --> %d,%d\n",
+               toadd[i]->x, toadd[i]->y,
+               tileopp->x, tileopp->y,
+               dot->x, dot->y));
+        dbg_state(state);
+    }
+    return 1;
+
+noexpand:
+    /* Otherwise, try to move dot so as to encompass given spaces: */
+    /* first, calculate the 'centre of gravity' of the new dot. */
+    nnew = dot->nassoc + nadd; /* number of tiles assoc. with new dot. */
+    cx = dot->x * dot->nassoc;
+    cy = dot->y * dot->nassoc;
+    for (i = 0; i < nadd; i++) {
+        cx += toadd[i]->x;
+        cy += toadd[i]->y;
+    }
+    /* If the CoG isn't a whole number, it's not possible. */
+    if ((cx % nnew) != 0 || (cy % nnew) != 0) {
+        debug(("Unable to move dot %d,%d, CoG not whole number.\n",
+               dot->x, dot->y));
+        return 0;
+    }
+    cx /= nnew; cy /= nnew;
+
+    /* Check whether all spaces in the old tile would have a good
+     * opposite wrt the new dot. */
+    md.olddot = dot;
+    md.newdot = &SPACE(state, cx, cy);
+    md.op = MD_CHECK;
+    ret = foreach_tile(state, movedot_cb, IMPOSSIBLE_QUITS, &md);
+    if (ret == -1) {
+        debug(("Unable to move dot %d,%d, new dot not symmetrical.\n",
+               dot->x, dot->y));
+        return 0;
+    }
+    /* Also check whether all spaces we're adding would have a good
+     * opposite wrt the new dot. */
+    for (i = 0; i < nadd; i++) {
+        tileopp = space_opposite_dot(state, toadd[i], md.newdot);
+        if (tileopp && (tileopp->flags & F_TILE_ASSOC) &&
+            (tileopp->dotx != dot->x || tileopp->doty != dot->y)) {
+            tileopp = NULL;
+        }
+        if (!tileopp) {
+            debug(("Unable to move dot %d,%d, new dot not symmetrical.\n",
+               dot->x, dot->y));
+            return 0;
+        }
+#ifdef STANDALONE_PICTURE_GENERATOR
+        if (picture) {
+            if (!(picture[(tileopp->y/2) * state->w + (tileopp->x/2)]) ^
+                !(dot->flags & F_DOT_BLACK))
+                return 0;
+        }
+#endif
+    }
+
+    /* If we've got here, we're ok. First, associate all of 'toadd'
+     * with the _old_ dot (so they'll get fixed up, with their opposites,
+     * in the next step). */
+    for (i = 0; i < nadd; i++) {
+        debug(("Associating to-add %d,%d with old dot %d,%d.\n",
+               toadd[i]->x, toadd[i]->y, dot->x, dot->y));
+        add_assoc(state, toadd[i], dot);
+    }
+
+    /* Finally, move the dot and fix up all the old associations. */
+    debug(("Moving dot at %d,%d to %d,%d\n",
+           dot->x, dot->y, md.newdot->x, md.newdot->y));
+    {
+#ifdef STANDALONE_PICTURE_GENERATOR
+        int f = dot->flags & F_DOT_BLACK;
+#endif
+        remove_dot(dot);
+        add_dot(md.newdot);
+#ifdef STANDALONE_PICTURE_GENERATOR
+        md.newdot->flags |= f;
+#endif
+    }
+
+    md.op = MD_MOVE;
+    ret = foreach_tile(state, movedot_cb, 0, &md);
+    assert(ret == 1);
+    dbg_state(state);
+
+    return 1;
+}
+
+/* Hard-code to a max. of 2x2 squares, for speed (less malloc) */
+#define MAX_TOADD 4
+#define MAX_OUTSIDE 8
+
+#define MAX_TILE_PERC 20
+
+static int generate_try_block(game_state *state, random_state *rs,
+                              int x1, int y1, int x2, int y2)
+{
+    int x, y, nadd = 0, nout = 0, i, maxsz;
+    space *sp, *toadd[MAX_TOADD], *outside[MAX_OUTSIDE], *dot;
+
+    if (!INGRID(state, x1, y1) || !INGRID(state, x2, y2)) return 0;
+
+    /* We limit the maximum size of tiles to be ~2*sqrt(area); so,
+     * a 5x5 grid shouldn't have anything >10 tiles, a 20x20 grid
+     * nothing >40 tiles. */
+    maxsz = (int)sqrt((double)(state->w * state->h)) * 2;
+    debug(("generate_try_block, maxsz %d\n", maxsz));
+
+    /* Make a static list of the spaces; if any space is already
+     * associated then quit immediately. */
+    for (x = x1; x <= x2; x += 2) {
+        for (y = y1; y <= y2; y += 2) {
+            assert(nadd < MAX_TOADD);
+            sp = &SPACE(state, x, y);
+            assert(sp->type == s_tile);
+            if (sp->flags & F_TILE_ASSOC) return 0;
+            toadd[nadd++] = sp;
+        }
+    }
+
+    /* Make a list of the spaces outside of our block, and shuffle it. */
+#define OUTSIDE(x, y) do {                              \
+    if (INGRID(state, (x), (y))) {                      \
+        assert(nout < MAX_OUTSIDE);                     \
+        outside[nout++] = &SPACE(state, (x), (y));      \
+    }                                                   \
+} while(0)
+    for (x = x1; x <= x2; x += 2) {
+        OUTSIDE(x, y1-2);
+        OUTSIDE(x, y2+2);
+    }
+    for (y = y1; y <= y2; y += 2) {
+        OUTSIDE(x1-2, y);
+        OUTSIDE(x2+2, y);
+    }
+    shuffle(outside, nout, sizeof(space *), rs);
+
+    for (i = 0; i < nout; i++) {
+        if (!(outside[i]->flags & F_TILE_ASSOC)) continue;
+        dot = &SPACE(state, outside[i]->dotx, outside[i]->doty);
+        if (dot->nassoc >= maxsz) {
+            debug(("Not adding to dot %d,%d, large enough (%d) already.\n",
+                   dot->x, dot->y, dot->nassoc));
+            continue;
+        }
+        if (dot_expand_or_move(state, dot, toadd, nadd)) return 1;
+    }
+    return 0;
+}
+
+#ifdef STANDALONE_SOLVER
+int maxtries;
+#define MAXTRIES maxtries
+#else
+#define MAXTRIES 50
+#endif
+
+#define GP_DOTS   1
+
+static void generate_pass(game_state *state, random_state *rs, int *scratch,
+                         int perc, unsigned int flags)
+{
+    int sz = state->sx*state->sy, nspc, i, ret;
+
+    shuffle(scratch, sz, sizeof(int), rs);
+
+    /* This bug took me a, er, little while to track down. On PalmOS,
+     * which has 16-bit signed ints, puzzles over about 9x9 started
+     * failing to generate because the nspc calculation would start
+     * to overflow, causing the dots not to be filled in properly. */
+    nspc = (int)(((long)perc * (long)sz) / 100L);
+    debug(("generate_pass: %d%% (%d of %dx%d) squares, flags 0x%x\n",
+           perc, nspc, state->sx, state->sy, flags));
+
+    for (i = 0; i < nspc; i++) {
+        space *sp = &state->grid[scratch[i]];
+        int x1 = sp->x, y1 = sp->y, x2 = sp->x, y2 = sp->y;
+
+        if (sp->type == s_edge) {
+            if (IS_VERTICAL_EDGE(sp->x)) {
+                x1--; x2++;
+            } else {
+                y1--; y2++;
+            }
+        }
+        if (sp->type != s_vertex) {
+            /* heuristic; expanding from vertices tends to generate lots of
+             * too-big regions of tiles. */
+            if (generate_try_block(state, rs, x1, y1, x2, y2))
+                continue; /* we expanded successfully. */
+        }
+
+        if (!(flags & GP_DOTS)) continue;
+
+        if ((sp->type == s_edge) && (i % 2)) {
+            debug(("Omitting edge %d,%d as half-of.\n", sp->x, sp->y));
+            continue;
+        }
+
+        /* If we've got here we might want to put a dot down. Check
+         * if we can, and add one if so. */
+        if (dot_is_possible(state, sp, 0)) {
+            add_dot(sp);
+#ifdef STANDALONE_PICTURE_GENERATOR
+            if (picture) {
+                if (picture[(sp->y/2) * state->w + (sp->x/2)])
+                    sp->flags |= F_DOT_BLACK;
+            }
+#endif
+            ret = solver_obvious_dot(state, sp);
+            assert(ret != -1);
+            debug(("Added dot (and obvious associations) at %d,%d\n",
+                   sp->x, sp->y));
+            dbg_state(state);
+        }
+    }
+    dbg_state(state);
+}
+
+static char *new_game_desc(const game_params *params, random_state *rs,
+                           char **aux, int interactive)
+{
+    game_state *state = blank_game(params->w, params->h), *copy;
+    char *desc;
+    int *scratch, sz = state->sx*state->sy, i;
+    int diff, ntries = 0, cc;
+
+    /* Random list of squares to try and process, one-by-one. */
+    scratch = snewn(sz, int);
+    for (i = 0; i < sz; i++) scratch[i] = i;
+
+generate:
+    clear_game(state, 1);
+    ntries++;
+
+    /* generate_pass(state, rs, scratch, 10, GP_DOTS); */
+    /* generate_pass(state, rs, scratch, 100, 0); */
+    generate_pass(state, rs, scratch, 100, GP_DOTS);
+
+    game_update_dots(state);
+
+    if (state->ndots == 1) goto generate;
+
+#ifdef DEBUGGING
+    {
+        char *tmp = encode_game(state);
+        debug(("new_game_desc state %dx%d:%s\n", params->w, params->h, tmp));
+        sfree(tmp);
+    }
+#endif
+
+    for (i = 0; i < state->sx*state->sy; i++)
+        if (state->grid[i].type == s_tile)
+            outline_tile_fordot(state, &state->grid[i], TRUE);
+    cc = check_complete(state, NULL, NULL);
+    assert(cc);
+
+    copy = dup_game(state);
+    clear_game(copy, 0);
+    dbg_state(copy);
+    diff = solver_state(copy, params->diff);
+    free_game(copy);
+
+    assert(diff != DIFF_IMPOSSIBLE);
+    if (diff != params->diff) {
+        /*
+         * We'll grudgingly accept a too-easy puzzle, but we must
+         * _not_ permit a too-hard one (one which the solver
+         * couldn't handle at all).
+         */
+        if (diff > params->diff ||
+            ntries < MAXTRIES) goto generate;
+    }
+
+#ifdef STANDALONE_PICTURE_GENERATOR
+    /*
+     * Postprocessing pass to prevent excessive numbers of adjacent
+     * singletons. Iterate over all edges in random shuffled order;
+     * for each edge that separates two regions, investigate
+     * whether removing that edge and merging the regions would
+     * still yield a valid and soluble puzzle. (The two regions
+     * must also be the same colour, of course.) If so, do it.
+     * 
+     * This postprocessing pass is slow (due to repeated solver
+     * invocations), and seems to be unnecessary during normal
+     * unconstrained game generation. However, when generating a
+     * game under colour constraints, excessive singletons seem to
+     * turn up more often, so it's worth doing this.
+     */
+    {
+        int *posns, nposns;
+        int i, j, newdiff;
+        game_state *copy2;
+
+        nposns = params->w * (params->h+1) + params->h * (params->w+1);
+        posns = snewn(nposns, int);
+        for (i = j = 0; i < state->sx*state->sy; i++)
+            if (state->grid[i].type == s_edge)
+                posns[j++] = i;
+        assert(j == nposns);
+
+        shuffle(posns, nposns, sizeof(*posns), rs);
+
+        for (i = 0; i < nposns; i++) {
+            int x, y, x0, y0, x1, y1, cx, cy, cn, cx0, cy0, cx1, cy1, tx, ty;
+            space *s0, *s1, *ts, *d0, *d1, *dn;
+            int ok;
+
+            /* Coordinates of edge space */
+            x = posns[i] % state->sx;
+            y = posns[i] / state->sx;
+
+            /* Coordinates of square spaces on either side of edge */
+            x0 = ((x+1) & ~1) - 1;     /* round down to next odd number */
+            y0 = ((y+1) & ~1) - 1;
+            x1 = 2*x-x0;               /* and reflect about x to get x1 */
+            y1 = 2*y-y0;
+
+            if (!INGRID(state, x0, y0) || !INGRID(state, x1, y1))
+                continue;              /* outermost edge of grid */
+            s0 = &SPACE(state, x0, y0);
+            s1 = &SPACE(state, x1, y1);
+            assert(s0->type == s_tile && s1->type == s_tile);
+
+            if (s0->dotx == s1->dotx && s0->doty == s1->doty)
+                continue;              /* tiles _already_ owned by same dot */
+
+            d0 = &SPACE(state, s0->dotx, s0->doty);
+            d1 = &SPACE(state, s1->dotx, s1->doty);
+
+            if ((d0->flags ^ d1->flags) & F_DOT_BLACK)
+                continue;              /* different colours: cannot merge */
+
+            /*
+             * Work out where the centre of gravity of the new
+             * region would be.
+             */
+            cx = d0->nassoc * d0->x + d1->nassoc * d1->x;
+            cy = d0->nassoc * d0->y + d1->nassoc * d1->y;
+            cn = d0->nassoc + d1->nassoc;
+            if (cx % cn || cy % cn)
+                continue;              /* CoG not at integer coordinates */
+            cx /= cn;
+            cy /= cn;
+            assert(INUI(state, cx, cy));
+
+            /*
+             * Ensure that the CoG would actually be _in_ the new
+             * region, by verifying that all its surrounding tiles
+             * belong to one or other of our two dots.
+             */
+            cx0 = ((cx+1) & ~1) - 1;   /* round down to next odd number */
+            cy0 = ((cy+1) & ~1) - 1;
+            cx1 = 2*cx-cx0;            /* and reflect about cx to get cx1 */
+            cy1 = 2*cy-cy0;
+            ok = TRUE;
+            for (ty = cy0; ty <= cy1; ty += 2)
+                for (tx = cx0; tx <= cx1; tx += 2) {
+                    ts = &SPACE(state, tx, ty);
+                    assert(ts->type == s_tile);
+                    if ((ts->dotx != d0->x || ts->doty != d0->y) &&
+                        (ts->dotx != d1->x || ts->doty != d1->y))
+                        ok = FALSE;
+                }
+            if (!ok)
+                continue;
+
+            /*
+             * Verify that for every tile in either source region,
+             * that tile's image in the new CoG is also in one of
+             * the two source regions.
+             */
+            for (ty = 1; ty < state->sy; ty += 2) {
+                for (tx = 1; tx < state->sx; tx += 2) {
+                    int tx1, ty1;
+
+                    ts = &SPACE(state, tx, ty);
+                    assert(ts->type == s_tile);
+                    if ((ts->dotx != d0->x || ts->doty != d0->y) &&
+                        (ts->dotx != d1->x || ts->doty != d1->y))
+                        continue;      /* not part of these tiles anyway */
+                    tx1 = 2*cx-tx;
+                    ty1 = 2*cy-ty;
+                    if (!INGRID(state, tx1, ty1)) {
+                        ok = FALSE;
+                        break;
+                    }
+                    ts = &SPACE(state, cx+cx-tx, cy+cy-ty);
+                    if ((ts->dotx != d0->x || ts->doty != d0->y) &&
+                        (ts->dotx != d1->x || ts->doty != d1->y)) {
+                        ok = FALSE;
+                        break;
+                    }
+                }
+                if (!ok)
+                    break;
+            }
+            if (!ok)
+                continue;
+
+            /*
+             * Now we're clear to attempt the merge. We take a copy
+             * of the game state first, so we can revert it easily
+             * if the resulting puzzle turns out to have become
+             * insoluble.
+             */
+            copy2 = dup_game(state);
+
+            remove_dot(d0);
+            remove_dot(d1);
+            dn = &SPACE(state, cx, cy);
+            add_dot(dn);
+            dn->flags |= (d0->flags & F_DOT_BLACK);
+            for (ty = 1; ty < state->sy; ty += 2) {
+                for (tx = 1; tx < state->sx; tx += 2) {
+                    ts = &SPACE(state, tx, ty);
+                    assert(ts->type == s_tile);
+                    if ((ts->dotx != d0->x || ts->doty != d0->y) &&
+                        (ts->dotx != d1->x || ts->doty != d1->y))
+                        continue;      /* not part of these tiles anyway */
+                    add_assoc(state, ts, dn);
+                }
+            }
+
+            copy = dup_game(state);
+            clear_game(copy, 0);
+            dbg_state(copy);
+            newdiff = solver_state(copy, params->diff);
+            free_game(copy);
+            if (diff == newdiff) {
+                /* Still just as soluble. Let the merge stand. */
+                free_game(copy2);
+            } else {
+                /* Became insoluble. Revert. */
+                free_game(state);
+                state = copy2;
+            }
+        }
+        sfree(posns);
+    }
+#endif
+
+    desc = encode_game(state);
+#ifndef STANDALONE_SOLVER
+    debug(("new_game_desc generated: \n"));
+    dbg_state(state);
+#endif
+
+    free_game(state);
+    sfree(scratch);
+
+    return desc;
+}
+
+static int dots_too_close(game_state *state)
+{
+    /* Quick-and-dirty check, using half the solver:
+     * solver_obvious will only fail if the dots are
+     * too close together, so dot-proximity associations
+     * overlap. */
+    game_state *tmp = dup_game(state);
+    int ret = solver_obvious(tmp);
+    free_game(tmp);
+    return (ret == -1) ? 1 : 0;
+}
+
+static game_state *load_game(const game_params *params, const char *desc,
+                             char **why_r)
+{
+    game_state *state = blank_game(params->w, params->h);
+    char *why = NULL;
+    int i, x, y, n;
+    unsigned int df;
+
+    i = 0;
+    while (*desc) {
+        n = *desc++;
+        if (n == 'z') {
+            i += 25;
+            continue;
+        }
+        if (n >= 'a' && n <= 'y') {
+            i += n - 'a';
+            df = 0;
+        } else if (n >= 'A' && n <= 'Y') {
+            i += n - 'A';
+            df = F_DOT_BLACK;
+        } else {
+            why = "Invalid characters in game description"; goto fail;
+        }
+        /* if we got here we incremented i and have a dot to add. */
+        y = (i / (state->sx-2)) + 1;
+        x = (i % (state->sx-2)) + 1;
+        if (!INUI(state, x, y)) {
+            why = "Too much data to fit in grid"; goto fail;
+        }
+        add_dot(&SPACE(state, x, y));
+        SPACE(state, x, y).flags |= df;
+        i++;
+    }
+    game_update_dots(state);
+
+    if (dots_too_close(state)) {
+        why = "Dots too close together"; goto fail;
+    }
+
+    return state;
+
+fail:
+    free_game(state);
+    if (why_r) *why_r = why;
+    return NULL;
+}
+
+static char *validate_desc(const game_params *params, const char *desc)
+{
+    char *why = NULL;
+    game_state *dummy = load_game(params, desc, &why);
+    if (dummy) {
+        free_game(dummy);
+        assert(!why);
+    } else
+        assert(why);
+    return why;
+}
+
+static game_state *new_game(midend *me, const game_params *params,
+                            const char *desc)
+{
+    game_state *state = load_game(params, desc, NULL);
+    if (!state) {
+        assert("Unable to load ?validated game.");
+        return NULL;
+    }
+#ifdef EDITOR
+    state->me = me;
+#endif
+    return state;
+}
+
+/* ----------------------------------------------------------
+ * Solver and all its little wizards.
+ */
+
+int solver_recurse_depth;
+
+typedef struct solver_ctx {
+    game_state *state;
+    int sz;             /* state->sx * state->sy */
+    space **scratch;    /* size sz */
+
+} solver_ctx;
+
+static solver_ctx *new_solver(game_state *state)
+{
+    solver_ctx *sctx = snew(solver_ctx);
+    sctx->state = state;
+    sctx->sz = state->sx*state->sy;
+    sctx->scratch = snewn(sctx->sz, space *);
+    return sctx;
+}
+
+static void free_solver(solver_ctx *sctx)
+{
+    sfree(sctx->scratch);
+    sfree(sctx);
+}
+
+    /* Solver ideas so far:
+     *
+     * For any empty space, work out how many dots it could associate
+     * with:
+       * it needs line-of-sight
+       * it needs an empty space on the far side
+       * any adjacent lines need corresponding line possibilities.
+     */
+
+/* The solver_ctx should keep a list of dot positions, for quicker looping.
+ *
+ * Solver techniques, in order of difficulty:
+   * obvious adjacency to dots
+   * transferring tiles to opposite side
+   * transferring lines to opposite side
+   * one possible dot for a given tile based on opposite availability
+   * tile with 3 definite edges next to an associated tile must associate
+      with same dot.
+   *
+   * one possible dot for a given tile based on line-of-sight
+ */
+
+static int solver_add_assoc(game_state *state, space *tile, int dx, int dy,
+                            const char *why)
+{
+    space *dot, *tile_opp;
+
+    dot = &SPACE(state, dx, dy);
+    tile_opp = space_opposite_dot(state, tile, dot);
+
+    assert(tile->type == s_tile);
+    if (tile->flags & F_TILE_ASSOC) {
+        if ((tile->dotx != dx) || (tile->doty != dy)) {
+            solvep(("%*sSet %d,%d --> %d,%d (%s) impossible; "
+                    "already --> %d,%d.\n",
+                    solver_recurse_depth*4, "",
+                    tile->x, tile->y, dx, dy, why,
+                    tile->dotx, tile->doty));
+            return -1;
+        }
+        return 0; /* no-op */
+    }
+    if (!tile_opp) {
+        solvep(("%*s%d,%d --> %d,%d impossible, no opposite tile.\n",
+                solver_recurse_depth*4, "", tile->x, tile->y, dx, dy));
+        return -1;
+    }
+    if (tile_opp->flags & F_TILE_ASSOC &&
+        (tile_opp->dotx != dx || tile_opp->doty != dy)) {
+        solvep(("%*sSet %d,%d --> %d,%d (%s) impossible; "
+                "opposite already --> %d,%d.\n",
+                solver_recurse_depth*4, "",
+                tile->x, tile->y, dx, dy, why,
+                tile_opp->dotx, tile_opp->doty));
+        return -1;
+    }
+
+    add_assoc(state, tile, dot);
+    add_assoc(state, tile_opp, dot);
+    solvep(("%*sSetting %d,%d --> %d,%d (%s).\n",
+            solver_recurse_depth*4, "",
+            tile->x, tile->y,dx, dy, why));
+    solvep(("%*sSetting %d,%d --> %d,%d (%s, opposite).\n",
+            solver_recurse_depth*4, "",
+            tile_opp->x, tile_opp->y, dx, dy, why));
+    return 1;
+}
+
+static int solver_obvious_dot(game_state *state, space *dot)
+{
+    int dx, dy, ret, didsth = 0;
+    space *tile;
+
+    debug(("%*ssolver_obvious_dot for %d,%d.\n",
+           solver_recurse_depth*4, "", dot->x, dot->y));
+
+    assert(dot->flags & F_DOT);
+    for (dx = -1; dx <= 1; dx++) {
+        for (dy = -1; dy <= 1; dy++) {
+            if (!INGRID(state, dot->x+dx, dot->y+dy)) continue;
+
+            tile = &SPACE(state, dot->x+dx, dot->y+dy);
+            if (tile->type == s_tile) {
+                ret = solver_add_assoc(state, tile, dot->x, dot->y,
+                                       "next to dot");
+                if (ret < 0) return -1;
+                if (ret > 0) didsth = 1;
+            }
+        }
+    }
+    return didsth;
+}
+
+static int solver_obvious(game_state *state)
+{
+    int i, didsth = 0, ret;
+
+    debug(("%*ssolver_obvious.\n", solver_recurse_depth*4, ""));
+
+    for (i = 0; i < state->ndots; i++) {
+        ret = solver_obvious_dot(state, state->dots[i]);
+        if (ret < 0) return -1;
+        if (ret > 0) didsth = 1;
+    }
+    return didsth;
+}
+
+static int solver_lines_opposite_cb(game_state *state, space *edge, void *ctx)
+{
+    int didsth = 0, n, dx, dy;
+    space *tiles[2], *tile_opp, *edge_opp;
+
+    assert(edge->type == s_edge);
+
+    tiles_from_edge(state, edge, tiles);
+
+    /* if tiles[0] && tiles[1] && they're both associated
+     * and they're both associated with different dots,
+     * ensure the line is set. */
+    if (!(edge->flags & F_EDGE_SET) &&
+        tiles[0] && tiles[1] &&
+        (tiles[0]->flags & F_TILE_ASSOC) &&
+        (tiles[1]->flags & F_TILE_ASSOC) &&
+        (tiles[0]->dotx != tiles[1]->dotx ||
+         tiles[0]->doty != tiles[1]->doty)) {
+        /* No edge, but the two adjacent tiles are both
+         * associated with different dots; add the edge. */
+        solvep(("%*sSetting edge %d,%d - tiles different dots.\n",
+               solver_recurse_depth*4, "", edge->x, edge->y));
+        edge->flags |= F_EDGE_SET;
+        didsth = 1;
+    }
+
+    if (!(edge->flags & F_EDGE_SET)) return didsth;
+    for (n = 0; n < 2; n++) {
+        if (!tiles[n]) continue;
+        assert(tiles[n]->type == s_tile);
+        if (!(tiles[n]->flags & F_TILE_ASSOC)) continue;
+
+        tile_opp = tile_opposite(state, tiles[n]);
+        if (!tile_opp) {
+            solvep(("%*simpossible: edge %d,%d has assoc. tile %d,%d"
+                   " with no opposite.\n",
+                   solver_recurse_depth*4, "",
+                   edge->x, edge->y, tiles[n]->x, tiles[n]->y));
+            /* edge of tile has no opposite edge (off grid?);
+             * this is impossible. */
+            return -1;
+        }
+
+        dx = tiles[n]->x - edge->x;
+        dy = tiles[n]->y - edge->y;
+        assert(INGRID(state, tile_opp->x+dx, tile_opp->y+dy));
+        edge_opp = &SPACE(state, tile_opp->x+dx, tile_opp->y+dy);
+        if (!(edge_opp->flags & F_EDGE_SET)) {
+            solvep(("%*sSetting edge %d,%d as opposite %d,%d\n",
+                   solver_recurse_depth*4, "",
+                   tile_opp->x-dx, tile_opp->y-dy, edge->x, edge->y));
+            edge_opp->flags |= F_EDGE_SET;
+            didsth = 1;
+        }
+    }
+    return didsth;
+}
+
+static int solver_spaces_oneposs_cb(game_state *state, space *tile, void *ctx)
+{
+    int n, eset, ret;
+    space *edgeadj[4], *tileadj[4];
+    int dotx, doty;
+
+    assert(tile->type == s_tile);
+    if (tile->flags & F_TILE_ASSOC) return 0;
+
+    adjacencies(state, tile, edgeadj, tileadj);
+
+    /* Empty tile. If each edge is either set, or associated with
+     * the same dot, we must also associate with dot. */
+    eset = 0; dotx = -1; doty = -1;
+    for (n = 0; n < 4; n++) {
+        assert(edgeadj[n]);
+        assert(edgeadj[n]->type == s_edge);
+        if (edgeadj[n]->flags & F_EDGE_SET) {
+            eset++;
+        } else {
+            assert(tileadj[n]);
+            assert(tileadj[n]->type == s_tile);
+
+            /* If an adjacent tile is empty we can't make any deductions.*/
+            if (!(tileadj[n]->flags & F_TILE_ASSOC))
+                return 0;
+
+            /* If an adjacent tile is assoc. with a different dot
+             * we can't make any deductions. */
+            if (dotx != -1 && doty != -1 &&
+                (tileadj[n]->dotx != dotx ||
+                 tileadj[n]->doty != doty))
+                return 0;
+
+            dotx = tileadj[n]->dotx;
+            doty = tileadj[n]->doty;
+        }
+    }
+    if (eset == 4) {
+        solvep(("%*simpossible: empty tile %d,%d has 4 edges\n",
+               solver_recurse_depth*4, "",
+               tile->x, tile->y));
+        return -1;
+    }
+    assert(dotx != -1 && doty != -1);
+
+    ret = solver_add_assoc(state, tile, dotx, doty, "rest are edges");
+    if (ret == -1) return -1;
+    assert(ret != 0); /* really should have done something. */
+
+    return 1;
+}
+
+/* Improved algorithm for tracking line-of-sight from dots, and not spaces.
+ *
+ * The solver_ctx already stores a list of dots: the algorithm proceeds by
+ * expanding outwards from each dot in turn, expanding first to the boundary
+ * of its currently-connected tile and then to all empty tiles that could see
+ * it. Empty tiles will be flagged with a 'can see dot <x,y>' sticker.
+ *
+ * Expansion will happen by (symmetrically opposite) pairs of squares; if
+ * a square hasn't an opposite number there's no point trying to expand through
+ * it. Empty tiles will therefore also be tagged in pairs.
+ *
+ * If an empty tile already has a 'can see dot <x,y>' tag from a previous dot,
+ * it (and its partner) gets untagged (or, rather, a 'can see two dots' tag)
+ * because we're looking for single-dot possibilities.
+ *
+ * Once we've gone through all the dots, any which still have a 'can see dot'
+ * tag get associated with that dot (because it must have been the only one);
+ * any without any tag (i.e. that could see _no_ dots) cause an impossibility
+ * marked.
+ *
+ * The expansion will happen each time with a stored list of (space *) pairs,
+ * rather than a mark-and-sweep idea; that's horrifically inefficient.
+ *
+ * expansion algorithm:
+ *
+ * * allocate list of (space *) the size of s->sx*s->sy.
+ * * allocate second grid for (flags, dotx, doty) size of sx*sy.
+ *
+ * clear second grid (flags = 0, all dotx and doty = 0)
+ * flags: F_REACHABLE, F_MULTIPLE
+ *
+ *
+ * * for each dot, start with one pair of tiles that are associated with it --
+ *   * vertex --> (dx+1, dy+1), (dx-1, dy-1)
+ *   * edge --> (adj1, adj2)
+ *   * tile --> (tile, tile) ???
+ * * mark that pair of tiles with F_MARK, clear all other F_MARKs.
+ * * add two tiles to start of list.
+ *
+ * set start = 0, end = next = 2
+ *
+ * from (start to end-1, step 2) {
+ * * we have two tiles (t1, t2), opposites wrt our dot.
+ * * for each (at1) sensible adjacent tile to t1 (i.e. not past an edge):
+ *   * work out at2 as the opposite to at1
+ *   * assert at1 and at2 have the same F_MARK values.
+ *   * if at1 & F_MARK ignore it (we've been there on a previous sweep)
+ *   * if either are associated with a different dot
+ *     * mark both with F_MARK (so we ignore them later)
+ *   * otherwise (assoc. with our dot, or empty):
+ *     * mark both with F_MARK
+ *     * add their space * values to the end of the list, set next += 2.
+ * }
+ *
+ * if (end == next)
+ * * we didn't add any new squares; exit the loop.
+ * else
+ * * set start = next+1, end = next. go round again
+ *
+ * We've finished expanding from the dot. Now, for each square we have
+ * in our list (--> each square with F_MARK):
+ * * if the tile is empty:
+ *   * if F_REACHABLE was already set
+ *     * set F_MULTIPLE
+ *   * otherwise
+ *     * set F_REACHABLE, set dotx and doty to our dot.
+ *
+ * Then, continue the whole thing for each dot in turn.
+ *
+ * Once we've done for each dot, go through the entire grid looking for
+ * empty tiles: for each empty tile:
+   * if F_REACHABLE and not F_MULTIPLE, set that dot (and its double)
+   * if !F_REACHABLE, return as impossible.
+ *
+ */
+
+/* Returns 1 if this tile is either already associated with this dot,
+ * or blank. */
+static int solver_expand_checkdot(space *tile, space *dot)
+{
+    if (!(tile->flags & F_TILE_ASSOC)) return 1;
+    if (tile->dotx == dot->x && tile->doty == dot->y) return 1;
+    return 0;
+}
+
+static void solver_expand_fromdot(game_state *state, space *dot, solver_ctx *sctx)
+{
+    int i, j, x, y, start, end, next;
+    space *sp;
+
+    /* Clear the grid of the (space) flags we'll use. */
+
+    /* This is well optimised; analysis showed that:
+        for (i = 0; i < sctx->sz; i++) state->grid[i].flags &= ~F_MARK;
+       took up ~85% of the total function time! */
+    for (y = 1; y < state->sy; y += 2) {
+        sp = &SPACE(state, 1, y);
+        for (x = 1; x < state->sx; x += 2, sp += 2)
+            sp->flags &= ~F_MARK;
+    }
+
+    /* Seed the list of marked squares with two that must be associated
+     * with our dot (possibly the same space) */
+    if (dot->type == s_tile) {
+        sctx->scratch[0] = sctx->scratch[1] = dot;
+    } else if (dot->type == s_edge) {
+        tiles_from_edge(state, dot, sctx->scratch);
+    } else if (dot->type == s_vertex) {
+        /* pick two of the opposite ones arbitrarily. */
+        sctx->scratch[0] = &SPACE(state, dot->x-1, dot->y-1);
+        sctx->scratch[1] = &SPACE(state, dot->x+1, dot->y+1);
+    }
+    assert(sctx->scratch[0]->flags & F_TILE_ASSOC);
+    assert(sctx->scratch[1]->flags & F_TILE_ASSOC);
+
+    sctx->scratch[0]->flags |= F_MARK;
+    sctx->scratch[1]->flags |= F_MARK;
+
+    debug(("%*sexpand from dot %d,%d seeded with %d,%d and %d,%d.\n",
+           solver_recurse_depth*4, "", dot->x, dot->y,
+           sctx->scratch[0]->x, sctx->scratch[0]->y,
+           sctx->scratch[1]->x, sctx->scratch[1]->y));
+
+    start = 0; end = 2; next = 2;
+
+expand:
+    debug(("%*sexpand: start %d, end %d, next %d\n",
+           solver_recurse_depth*4, "", start, end, next));
+    for (i = start; i < end; i += 2) {
+        space *t1 = sctx->scratch[i]/*, *t2 = sctx->scratch[i+1]*/;
+        space *edges[4], *tileadj[4], *tileadj2;
+
+        adjacencies(state, t1, edges, tileadj);
+
+        for (j = 0; j < 4; j++) {
+            assert(edges[j]);
+            if (edges[j]->flags & F_EDGE_SET) continue;
+            assert(tileadj[j]);
+
+            if (tileadj[j]->flags & F_MARK) continue; /* seen before. */
+
+            /* We have a tile adjacent to t1; find its opposite. */
+            tileadj2 = space_opposite_dot(state, tileadj[j], dot);
+            if (!tileadj2) {
+                debug(("%*sMarking %d,%d, no opposite.\n",
+                       solver_recurse_depth*4, "",
+                       tileadj[j]->x, tileadj[j]->y));
+                tileadj[j]->flags |= F_MARK;
+                continue; /* no opposite, so mark for next time. */
+            }
+            /* If the tile had an opposite we should have either seen both of
+             * these, or neither of these, before. */
+            assert(!(tileadj2->flags & F_MARK));
+
+            if (solver_expand_checkdot(tileadj[j], dot) &&
+                solver_expand_checkdot(tileadj2, dot)) {
+                /* Both tiles could associate with this dot; add them to
+                 * our list. */
+                debug(("%*sAdding %d,%d and %d,%d to possibles list.\n",
+                       solver_recurse_depth*4, "",
+                       tileadj[j]->x, tileadj[j]->y, tileadj2->x, tileadj2->y));
+                sctx->scratch[next++] = tileadj[j];
+                sctx->scratch[next++] = tileadj2;
+            }
+            /* Either way, we've seen these tiles already so mark them. */
+            debug(("%*sMarking %d,%d and %d,%d.\n",
+                   solver_recurse_depth*4, "",
+                       tileadj[j]->x, tileadj[j]->y, tileadj2->x, tileadj2->y));
+            tileadj[j]->flags |= F_MARK;
+            tileadj2->flags |= F_MARK;
+        }
+    }
+    if (next > end) {
+        /* We added more squares; go back and try again. */
+        start = end; end = next; goto expand;
+    }
+
+    /* We've expanded as far as we can go. Now we update the main flags
+     * on all tiles we've expanded into -- if they were empty, we have
+     * found possible associations for this dot. */
+    for (i = 0; i < end; i++) {
+        if (sctx->scratch[i]->flags & F_TILE_ASSOC) continue;
+        if (sctx->scratch[i]->flags & F_REACHABLE) {
+            /* This is (at least) the second dot this tile could
+             * associate with. */
+            debug(("%*sempty tile %d,%d could assoc. other dot %d,%d\n",
+                   solver_recurse_depth*4, "",
+                   sctx->scratch[i]->x, sctx->scratch[i]->y, dot->x, dot->y));
+            sctx->scratch[i]->flags |= F_MULTIPLE;
+        } else {
+            /* This is the first (possibly only) dot. */
+            debug(("%*sempty tile %d,%d could assoc. 1st dot %d,%d\n",
+                   solver_recurse_depth*4, "",
+                   sctx->scratch[i]->x, sctx->scratch[i]->y, dot->x, dot->y));
+            sctx->scratch[i]->flags |= F_REACHABLE;
+            sctx->scratch[i]->dotx = dot->x;
+            sctx->scratch[i]->doty = dot->y;
+        }
+    }
+    dbg_state(state);
+}
+
+static int solver_expand_postcb(game_state *state, space *tile, void *ctx)
+{
+    assert(tile->type == s_tile);
+
+    if (tile->flags & F_TILE_ASSOC) return 0;
+
+    if (!(tile->flags & F_REACHABLE)) {
+        solvep(("%*simpossible: space (%d,%d) can reach no dots.\n",
+                solver_recurse_depth*4, "", tile->x, tile->y));
+        return -1;
+    }
+    if (tile->flags & F_MULTIPLE) return 0;
+
+    return solver_add_assoc(state, tile, tile->dotx, tile->doty,
+                            "single possible dot after expansion");
+}
+
+static int solver_expand_dots(game_state *state, solver_ctx *sctx)
+{
+    int i;
+
+    for (i = 0; i < sctx->sz; i++)
+        state->grid[i].flags &= ~(F_REACHABLE|F_MULTIPLE);
+
+    for (i = 0; i < state->ndots; i++)
+        solver_expand_fromdot(state, state->dots[i], sctx);
+
+    return foreach_tile(state, solver_expand_postcb, IMPOSSIBLE_QUITS, sctx);
+}
+
+struct recurse_ctx {
+    space *best;
+    int bestn;
+};
+
+static int solver_recurse_cb(game_state *state, space *tile, void *ctx)
+{
+    struct recurse_ctx *rctx = (struct recurse_ctx *)ctx;
+    int i, n = 0;
+
+    assert(tile->type == s_tile);
+    if (tile->flags & F_TILE_ASSOC) return 0;
+
+    /* We're unassociated: count up all the dots we could associate with. */
+    for (i = 0; i < state->ndots; i++) {
+        if (dotfortile(state, tile, state->dots[i]))
+            n++;
+    }
+    if (n > rctx->bestn) {
+        rctx->bestn = n;
+        rctx->best = tile;
+    }
+    return 0;
+}
+
+#define MAXRECURSE 5
+
+static int solver_recurse(game_state *state, int maxdiff)
+{
+    int diff = DIFF_IMPOSSIBLE, ret, n, gsz = state->sx * state->sy;
+    space *ingrid, *outgrid = NULL, *bestopp;
+    struct recurse_ctx rctx;
+
+    if (solver_recurse_depth >= MAXRECURSE) {
+        solvep(("Limiting recursion to %d, returning.", MAXRECURSE));
+        return DIFF_UNFINISHED;
+    }
+
+    /* Work out the cell to recurse on; go through all unassociated tiles
+     * and find which one has the most possible dots it could associate
+     * with. */
+    rctx.best = NULL;
+    rctx.bestn = 0;
+
+    foreach_tile(state, solver_recurse_cb, 0, &rctx);
+    if (rctx.bestn == 0) return DIFF_IMPOSSIBLE; /* or assert? */
+    assert(rctx.best);
+
+    solvep(("%*sRecursing around %d,%d, with %d possible dots.\n",
+           solver_recurse_depth*4, "",
+           rctx.best->x, rctx.best->y, rctx.bestn));
+
+#ifdef STANDALONE_SOLVER
+    solver_recurse_depth++;
+#endif
+
+    ingrid = snewn(gsz, space);
+    memcpy(ingrid, state->grid, gsz * sizeof(space));
+
+    for (n = 0; n < state->ndots; n++) {
+        memcpy(state->grid, ingrid, gsz * sizeof(space));
+
+        if (!dotfortile(state, rctx.best, state->dots[n])) continue;
+
+        /* set cell (temporarily) pointing to that dot. */
+        solver_add_assoc(state, rctx.best,
+                         state->dots[n]->x, state->dots[n]->y,
+                         "Attempting for recursion");
+
+        ret = solver_state(state, maxdiff);
+
+        if (diff == DIFF_IMPOSSIBLE && ret != DIFF_IMPOSSIBLE) {
+            /* we found our first solved grid; copy it away. */
+            assert(!outgrid);
+            outgrid = snewn(gsz, space);
+            memcpy(outgrid, state->grid, gsz * sizeof(space));
+        }
+        /* reset cell back to unassociated. */
+        bestopp = tile_opposite(state, rctx.best);
+        assert(bestopp && bestopp->flags & F_TILE_ASSOC);
+
+        remove_assoc(state, rctx.best);
+        remove_assoc(state, bestopp);
+
+        if (ret == DIFF_AMBIGUOUS || ret == DIFF_UNFINISHED)
+            diff = ret;
+        else if (ret == DIFF_IMPOSSIBLE)
+            /* no change */;
+        else {
+            /* precisely one solution */
+            if (diff == DIFF_IMPOSSIBLE)
+                diff = DIFF_UNREASONABLE;
+            else
+                diff = DIFF_AMBIGUOUS;
+        }
+        /* if we've found >1 solution, or ran out of recursion,
+         * give up immediately. */
+        if (diff == DIFF_AMBIGUOUS || diff == DIFF_UNFINISHED)
+            break;
+    }
+
+#ifdef STANDALONE_SOLVER
+    solver_recurse_depth--;
+#endif
+
+    if (outgrid) {
+        /* we found (at least one) soln; copy it back to state */
+        memcpy(state->grid, outgrid, gsz * sizeof(space));
+        sfree(outgrid);
+    }
+    sfree(ingrid);
+    return diff;
+}
+
+static int solver_state(game_state *state, int maxdiff)
+{
+    solver_ctx *sctx = new_solver(state);
+    int ret, diff = DIFF_NORMAL;
+
+#ifdef STANDALONE_PICTURE_GENERATOR
+    /* hack, hack: set picture to NULL during solving so that add_assoc
+     * won't complain when we attempt recursive guessing and guess wrong */
+    int *savepic = picture;
+    picture = NULL;
+#endif
+
+    ret = solver_obvious(state);
+    if (ret < 0) {
+        diff = DIFF_IMPOSSIBLE;
+        goto got_result;
+    }
+
+#define CHECKRET(d) do {                                        \
+    if (ret < 0) { diff = DIFF_IMPOSSIBLE; goto got_result; }   \
+    if (ret > 0) { diff = max(diff, (d)); goto cont; }          \
+} while(0)
+
+    while (1) {
+cont:
+        ret = foreach_edge(state, solver_lines_opposite_cb,
+                           IMPOSSIBLE_QUITS, sctx);
+        CHECKRET(DIFF_NORMAL);
+
+        ret = foreach_tile(state, solver_spaces_oneposs_cb,
+                           IMPOSSIBLE_QUITS, sctx);
+        CHECKRET(DIFF_NORMAL);
+
+        ret = solver_expand_dots(state, sctx);
+        CHECKRET(DIFF_NORMAL);
+
+        if (maxdiff <= DIFF_NORMAL)
+            break;
+
+        /* harder still? */
+
+        /* if we reach here, we've made no deductions, so we terminate. */
+        break;
+    }
+
+    if (check_complete(state, NULL, NULL)) goto got_result;
+
+    diff = (maxdiff >= DIFF_UNREASONABLE) ?
+        solver_recurse(state, maxdiff) : DIFF_UNFINISHED;
+
+got_result:
+    free_solver(sctx);
+#ifndef STANDALONE_SOLVER
+    debug(("solver_state ends, diff %s:\n", galaxies_diffnames[diff]));
+    dbg_state(state);
+#endif
+
+#ifdef STANDALONE_PICTURE_GENERATOR
+    picture = savepic;
+#endif
+
+    return diff;
+}
+
+#ifndef EDITOR
+static char *solve_game(const game_state *state, const game_state *currstate,
+                        const char *aux, char **error)
+{
+    game_state *tosolve;
+    char *ret;
+    int i;
+    int diff;
+
+    tosolve = dup_game(currstate);
+    diff = solver_state(tosolve, DIFF_UNREASONABLE);
+    if (diff != DIFF_UNFINISHED && diff != DIFF_IMPOSSIBLE) {
+        debug(("solve_game solved with current state.\n"));
+        goto solved;
+    }
+    free_game(tosolve);
+
+    tosolve = dup_game(state);
+    diff = solver_state(tosolve, DIFF_UNREASONABLE);
+    if (diff != DIFF_UNFINISHED && diff != DIFF_IMPOSSIBLE) {
+        debug(("solve_game solved with original state.\n"));
+        goto solved;
+    }
+    free_game(tosolve);
+
+    return NULL;
+
+solved:
+    /*
+     * Clear tile associations: the solution will only include the
+     * edges.
+     */
+    for (i = 0; i < tosolve->sx*tosolve->sy; i++)
+        tosolve->grid[i].flags &= ~F_TILE_ASSOC;
+    ret = diff_game(currstate, tosolve, 1);
+    free_game(tosolve);
+    return ret;
+}
+#endif
+
+/* ----------------------------------------------------------
+ * User interface.
+ */
+
+struct game_ui {
+    int dragging;
+    int dx, dy;         /* pixel coords of drag pos. */
+    int dotx, doty;     /* grid coords of dot we're dragging from. */
+    int srcx, srcy;     /* grid coords of drag start */
+    int cur_x, cur_y, cur_visible;
+};
+
+static game_ui *new_ui(const game_state *state)
+{
+    game_ui *ui = snew(game_ui);
+    ui->dragging = FALSE;
+    ui->cur_x = ui->cur_y = 1;
+    ui->cur_visible = 0;
+    return ui;
+}
+
+static void free_ui(game_ui *ui)
+{
+    sfree(ui);
+}
+
+static char *encode_ui(const game_ui *ui)
+{
+    return NULL;
+}
+
+static void decode_ui(game_ui *ui, const char *encoding)
+{
+}
+
+static void game_changed_state(game_ui *ui, const game_state *oldstate,
+                               const game_state *newstate)
+{
+}
+
+#define FLASH_TIME 0.15F
+
+#define PREFERRED_TILE_SIZE 32
+#define TILE_SIZE (ds->tilesize)
+#define DOT_SIZE        (TILE_SIZE / 4)
+#define EDGE_THICKNESS (max(TILE_SIZE / 16, 2))
+#define BORDER TILE_SIZE
+
+#define COORD(x) ( (x) * TILE_SIZE + BORDER )
+#define SCOORD(x) ( ((x) * TILE_SIZE)/2 + BORDER )
+#define FROMCOORD(x) ( ((x) - BORDER) / TILE_SIZE )
+
+#define DRAW_WIDTH      (BORDER * 2 + ds->w * TILE_SIZE)
+#define DRAW_HEIGHT     (BORDER * 2 + ds->h * TILE_SIZE)
+
+#define CURSOR_SIZE DOT_SIZE
+
+struct game_drawstate {
+    int started;
+    int w, h;
+    int tilesize;
+    unsigned long *grid;
+    int *dx, *dy;
+    blitter *bl;
+    blitter *blmirror;
+
+    int dragging, dragx, dragy;
+
+    int *colour_scratch;
+
+    int cx, cy, cur_visible;
+    blitter *cur_bl;
+};
+
+#define CORNER_TOLERANCE 0.15F
+#define CENTRE_TOLERANCE 0.15F
+
+/*
+ * Round FP coordinates to the centre of the nearest edge.
+ */
+#ifndef EDITOR
+static void coord_round_to_edge(float x, float y, int *xr, int *yr)
+{
+    float xs, ys, xv, yv, dx, dy;
+
+    /*
+     * Find the nearest square-centre.
+     */
+    xs = (float)floor(x) + 0.5F;
+    ys = (float)floor(y) + 0.5F;
+
+    /*
+     * Find the nearest grid vertex.
+     */
+    xv = (float)floor(x + 0.5F);
+    yv = (float)floor(y + 0.5F);
+
+    /*
+     * Determine whether the horizontal or vertical edge from that
+     * vertex alongside that square is closer to us, by comparing
+     * distances from the square cente.
+     */
+    dx = (float)fabs(x - xs);
+    dy = (float)fabs(y - ys);
+    if (dx > dy) {
+        /* Vertical edge: x-coord of corner,
+         * y-coord of square centre. */
+        *xr = 2 * (int)xv;
+        *yr = 1 + 2 * (int)floor(ys);
+    } else {
+        /* Horizontal edge: x-coord of square centre,
+         * y-coord of corner. */
+        *xr = 1 + 2 * (int)floor(xs);
+        *yr = 2 * (int)yv;
+    }
+}
+#endif
+
+#ifdef EDITOR
+static char *interpret_move(const game_state *state, game_ui *ui,
+                            const game_drawstate *ds,
+                            int x, int y, int button)
+{
+    char buf[80];
+    int px, py;
+    space *sp;
+
+    px = 2*FROMCOORD((float)x) + 0.5;
+    py = 2*FROMCOORD((float)y) + 0.5;
+
+    state->cdiff = -1;
+
+    if (button == 'C' || button == 'c') return dupstr("C");
+
+    if (button == 'S' || button == 's') {
+        char *ret;
+        game_state *tmp = dup_game(state);
+        state->cdiff = solver_state(tmp, DIFF_UNREASONABLE-1);
+        ret = diff_game(state, tmp, 0);
+        free_game(tmp);
+        return ret;
+    }
+
+    if (button == LEFT_BUTTON || button == RIGHT_BUTTON) {
+        if (!INUI(state, px, py)) return NULL;
+        sp = &SPACE(state, px, py);
+        if (!dot_is_possible(state, sp, 1)) return NULL;
+        sprintf(buf, "%c%d,%d",
+                (char)((button == LEFT_BUTTON) ? 'D' : 'd'), px, py);
+        return dupstr(buf);
+    }
+
+    return NULL;
+}
+#else
+static char *interpret_move(const game_state *state, game_ui *ui,
+                            const game_drawstate *ds,
+                            int x, int y, int button)
+{
+    /* UI operations (play mode):
+     *
+     * Toggle edge (set/unset) (left-click on edge)
+     * Associate space with dot (left-drag from dot)
+     * Unassociate space (left-drag from space off grid)
+     * Autofill lines around shape? (right-click?)
+     *
+     * (edit mode; will clear all lines/associations)
+     *
+     * Add or remove dot (left-click)
+     */
+    char buf[80];
+    const char *sep = "";
+    int px, py;
+    space *sp, *dot;
+
+    buf[0] = '\0';
+
+    if (button == 'H' || button == 'h') {
+        char *ret;
+        game_state *tmp = dup_game(state);
+        solver_obvious(tmp);
+        ret = diff_game(state, tmp, 0);
+        free_game(tmp);
+        return ret;
+    }
+
+    if (button == LEFT_BUTTON) {
+        ui->cur_visible = 0;
+        coord_round_to_edge(FROMCOORD((float)x), FROMCOORD((float)y),
+                            &px, &py);
+
+        if (!INUI(state, px, py)) return NULL;
+
+        sp = &SPACE(state, px, py);
+        assert(sp->type == s_edge);
+        {
+            sprintf(buf, "E%d,%d", px, py);
+            return dupstr(buf);
+        }
+    } else if (button == RIGHT_BUTTON) {
+        int px1, py1;
+
+        ui->cur_visible = 0;
+
+        px = (int)(2*FROMCOORD((float)x) + 0.5);
+        py = (int)(2*FROMCOORD((float)y) + 0.5);
+
+        dot = NULL;
+
+        /*
+         * If there's a dot anywhere nearby, we pick up an arrow
+         * pointing at that dot.
+         */
+        for (py1 = py-1; py1 <= py+1; py1++)
+            for (px1 = px-1; px1 <= px+1; px1++) {
+                if (px1 >= 0 && px1 < state->sx &&
+                    py1 >= 0 && py1 < state->sy &&
+                    x >= SCOORD(px1-1) && x < SCOORD(px1+1) &&
+                    y >= SCOORD(py1-1) && y < SCOORD(py1+1) &&
+                    SPACE(state, px1, py1).flags & F_DOT) {
+                    /*
+                     * Found a dot. Begin a drag from it.
+                     */
+                    dot = &SPACE(state, px1, py1);
+                    ui->srcx = px1;
+                    ui->srcy = py1;
+                    goto done;         /* multi-level break */
+                }
+            }
+
+        /*
+         * Otherwise, find the nearest _square_, and pick up the
+         * same arrow as it's got on it, if any.
+         */
+        if (!dot) {
+            px = 2*FROMCOORD(x+TILE_SIZE) - 1;
+            py = 2*FROMCOORD(y+TILE_SIZE) - 1;
+            if (px >= 0 && px < state->sx && py >= 0 && py < state->sy) {
+                sp = &SPACE(state, px, py);
+                if (sp->flags & F_TILE_ASSOC) {
+                    dot = &SPACE(state, sp->dotx, sp->doty);
+                    ui->srcx = px;
+                    ui->srcy = py;
+                }
+            }
+        }
+
+        done:
+        /*
+         * Now, if we've managed to find a dot, begin a drag.
+         */
+        if (dot) {
+            ui->dragging = TRUE;
+            ui->dx = x;
+            ui->dy = y;
+            ui->dotx = dot->x;
+            ui->doty = dot->y;
+            return "";
+        }
+    } else if (button == RIGHT_DRAG && ui->dragging) {
+        /* just move the drag coords. */
+        ui->dx = x;
+        ui->dy = y;
+        return "";
+    } else if (button == RIGHT_RELEASE && ui->dragging) {
+        ui->dragging = FALSE;
+
+        /*
+         * Drags are always targeted at a single square.
+         */
+        px = 2*FROMCOORD(x+TILE_SIZE) - 1;
+        py = 2*FROMCOORD(y+TILE_SIZE) - 1;
+
+        /*
+         * Dragging an arrow on to the same square it started from
+         * is a null move; just update the ui and finish.
+         */
+        if (px == ui->srcx && py == ui->srcy)
+            return "";
+
+        /*
+         * Otherwise, we remove the arrow from its starting
+         * square if we didn't start from a dot...
+         */
+        if ((ui->srcx != ui->dotx || ui->srcy != ui->doty) &&
+            SPACE(state, ui->srcx, ui->srcy).flags & F_TILE_ASSOC) {
+            sprintf(buf + strlen(buf), "%sU%d,%d", sep, ui->srcx, ui->srcy);
+            sep = ";";
+        }
+
+        /*
+         * ... and if the square we're moving it _to_ is valid, we
+         * add one there instead.
+         */
+        if (INUI(state, px, py)) {
+            sp = &SPACE(state, px, py);
+
+            if (!(sp->flags & F_DOT))
+                sprintf(buf + strlen(buf), "%sA%d,%d,%d,%d",
+                        sep, px, py, ui->dotx, ui->doty);
+        }
+
+        if (buf[0])
+            return dupstr(buf);
+        else
+            return "";
+    } else if (IS_CURSOR_MOVE(button)) {
+        move_cursor(button, &ui->cur_x, &ui->cur_y, state->sx-1, state->sy-1, 0);
+        if (ui->cur_x < 1) ui->cur_x = 1;
+        if (ui->cur_y < 1) ui->cur_y = 1;
+        ui->cur_visible = 1;
+        if (ui->dragging) {
+            ui->dx = SCOORD(ui->cur_x);
+            ui->dy = SCOORD(ui->cur_y);
+        }
+        return "";
+    } else if (IS_CURSOR_SELECT(button)) {
+        if (!ui->cur_visible) {
+            ui->cur_visible = 1;
+            return "";
+        }
+        sp = &SPACE(state, ui->cur_x, ui->cur_y);
+        if (ui->dragging) {
+            ui->dragging = FALSE;
+
+            if ((ui->srcx != ui->dotx || ui->srcy != ui->doty) &&
+                SPACE(state, ui->srcx, ui->srcy).flags & F_TILE_ASSOC) {
+                sprintf(buf, "%sU%d,%d", sep, ui->srcx, ui->srcy);
+                sep = ";";
+            }
+            if (sp->type == s_tile && !(sp->flags & F_DOT) && !(sp->flags & F_TILE_ASSOC)) {
+                sprintf(buf + strlen(buf), "%sA%d,%d,%d,%d",
+                        sep, ui->cur_x, ui->cur_y, ui->dotx, ui->doty);
+            }
+            return dupstr(buf);
+        } else if (sp->flags & F_DOT) {
+            ui->dragging = TRUE;
+            ui->dx = SCOORD(ui->cur_x);
+            ui->dy = SCOORD(ui->cur_y);
+            ui->dotx = ui->srcx = ui->cur_x;
+            ui->doty = ui->srcy = ui->cur_y;
+            return "";
+        } else if (sp->flags & F_TILE_ASSOC) {
+            assert(sp->type == s_tile);
+            ui->dragging = TRUE;
+            ui->dx = SCOORD(ui->cur_x);
+            ui->dy = SCOORD(ui->cur_y);
+            ui->dotx = sp->dotx;
+            ui->doty = sp->doty;
+            ui->srcx = ui->cur_x;
+            ui->srcy = ui->cur_y;
+            return "";
+        } else if (sp->type == s_edge) {
+            sprintf(buf, "E%d,%d", ui->cur_x, ui->cur_y);
+            return dupstr(buf);
+        }
+    }
+
+    return NULL;
+}
+#endif
+
+static int check_complete(const game_state *state, int *dsf, int *colours)
+{
+    int w = state->w, h = state->h;
+    int x, y, i, ret;
+
+    int free_dsf;
+    struct sqdata {
+        int minx, miny, maxx, maxy;
+        int cx, cy;
+        int valid, colour;
+    } *sqdata;
+
+    if (!dsf) {
+        dsf = snew_dsf(w*h);
+        free_dsf = TRUE;
+    } else {
+        dsf_init(dsf, w*h);
+        free_dsf = FALSE;
+    }
+
+    /*
+     * During actual game play, completion checking is done on the
+     * basis of the edges rather than the square associations. So
+     * first we must go through the grid figuring out the connected
+     * components into which the edges divide it.
+     */
+    for (y = 0; y < h; y++)
+        for (x = 0; x < w; x++) {
+            if (y+1 < h && !(SPACE(state, 2*x+1, 2*y+2).flags & F_EDGE_SET))
+                dsf_merge(dsf, y*w+x, (y+1)*w+x);
+            if (x+1 < w && !(SPACE(state, 2*x+2, 2*y+1).flags & F_EDGE_SET))
+                dsf_merge(dsf, y*w+x, y*w+(x+1));
+        }
+
+    /*
+     * That gives us our connected components. Now, for each
+     * component, decide whether it's _valid_. A valid component is
+     * one which:
+     *
+     *  - is 180-degree rotationally symmetric
+     *  - has a dot at its centre of symmetry
+     *  - has no other dots anywhere within it (including on its
+     *    boundary)
+     *  - contains no internal edges (i.e. edges separating two
+     *    squares which are both part of the component).
+     */
+
+    /*
+     * First, go through the grid finding the bounding box of each
+     * component.
+     */
+    sqdata = snewn(w*h, struct sqdata);
+    for (i = 0; i < w*h; i++) {
+        sqdata[i].minx = w+1;
+        sqdata[i].miny = h+1;
+        sqdata[i].maxx = sqdata[i].maxy = -1;
+        sqdata[i].valid = FALSE;
+    }
+    for (y = 0; y < h; y++)
+        for (x = 0; x < w; x++) {
+            i = dsf_canonify(dsf, y*w+x);
+            if (sqdata[i].minx > x)
+                sqdata[i].minx = x;
+            if (sqdata[i].maxx < x)
+                sqdata[i].maxx = x;
+            if (sqdata[i].miny > y)
+                sqdata[i].miny = y;
+            if (sqdata[i].maxy < y)
+                sqdata[i].maxy = y;
+            sqdata[i].valid = TRUE;
+        }
+
+    /*
+     * Now we're in a position to loop over each actual component
+     * and figure out where its centre of symmetry has to be if
+     * it's anywhere.
+     */
+    for (i = 0; i < w*h; i++)
+        if (sqdata[i].valid) {
+            int cx, cy;
+            cx = sqdata[i].cx = sqdata[i].minx + sqdata[i].maxx + 1;
+            cy = sqdata[i].cy = sqdata[i].miny + sqdata[i].maxy + 1;
+            if (!(SPACE(state, sqdata[i].cx, sqdata[i].cy).flags & F_DOT))
+                sqdata[i].valid = FALSE;   /* no dot at centre of symmetry */
+            if (dsf_canonify(dsf, (cy-1)/2*w+(cx-1)/2) != i ||
+                dsf_canonify(dsf, (cy)/2*w+(cx-1)/2) != i ||
+                dsf_canonify(dsf, (cy-1)/2*w+(cx)/2) != i ||
+                dsf_canonify(dsf, (cy)/2*w+(cx)/2) != i)
+                sqdata[i].valid = FALSE;   /* dot at cx,cy isn't ours */
+            if (SPACE(state, sqdata[i].cx, sqdata[i].cy).flags & F_DOT_BLACK)
+                sqdata[i].colour = 2;
+            else
+                sqdata[i].colour = 1;
+        }
+
+    /*
+     * Now we loop over the whole grid again, this time finding
+     * extraneous dots (any dot which wholly or partially overlaps
+     * a square and is not at the centre of symmetry of that
+     * square's component disqualifies the component from validity)
+     * and extraneous edges (any edge separating two squares
+     * belonging to the same component also disqualifies that
+     * component).
+     */
+    for (y = 1; y < state->sy-1; y++)
+        for (x = 1; x < state->sx-1; x++) {
+            space *sp = &SPACE(state, x, y);
+
+            if (sp->flags & F_DOT) {
+                /*
+                 * There's a dot here. Use it to disqualify any
+                 * component which deserves it.
+                 */
+                int cx, cy;
+                for (cy = (y-1) >> 1; cy <= y >> 1; cy++)
+                    for (cx = (x-1) >> 1; cx <= x >> 1; cx++) {
+                        i = dsf_canonify(dsf, cy*w+cx);
+                        if (x != sqdata[i].cx || y != sqdata[i].cy)
+                            sqdata[i].valid = FALSE;
+                    }
+            }
+
+            if (sp->flags & F_EDGE_SET) {
+                /*
+                 * There's an edge here. Use it to disqualify a
+                 * component if necessary.
+                 */
+                int cx1 = (x-1) >> 1, cx2 = x >> 1;
+                int cy1 = (y-1) >> 1, cy2 = y >> 1;
+                assert((cx1==cx2) ^ (cy1==cy2));
+                i = dsf_canonify(dsf, cy1*w+cx1);
+                if (i == dsf_canonify(dsf, cy2*w+cx2))
+                    sqdata[i].valid = FALSE;
+            }
+        }
+
+    /*
+     * And finally we test rotational symmetry: for each square in
+     * the grid, find which component it's in, test that that
+     * component also has a square in the symmetric position, and
+     * disqualify it if it doesn't.
+     */
+    for (y = 0; y < h; y++)
+        for (x = 0; x < w; x++) {
+            int x2, y2;
+
+            i = dsf_canonify(dsf, y*w+x);
+
+            x2 = sqdata[i].cx - 1 - x;
+            y2 = sqdata[i].cy - 1 - y;
+            if (i != dsf_canonify(dsf, y2*w+x2))
+                sqdata[i].valid = FALSE;
+        }
+
+    /*
+     * That's it. We now have all the connected components marked
+     * as valid or not valid. So now we return a `colours' array if
+     * we were asked for one, and also we return an overall
+     * true/false value depending on whether _every_ square in the
+     * grid is part of a valid component.
+     */
+    ret = TRUE;
+    for (i = 0; i < w*h; i++) {
+        int ci = dsf_canonify(dsf, i);
+        int thisok = sqdata[ci].valid;
+        if (colours)
+            colours[i] = thisok ? sqdata[ci].colour : 0;
+        ret = ret && thisok;
+    }
+
+    sfree(sqdata);
+    if (free_dsf)
+        sfree(dsf);
+
+    return ret;
+}
+
+static game_state *execute_move(const game_state *state, const char *move)
+{
+    int x, y, ax, ay, n, dx, dy;
+    game_state *ret = dup_game(state);
+    space *sp, *dot;
+    int currently_solving = FALSE;
+
+    debug(("%s\n", move));
+
+    while (*move) {
+        char c = *move;
+        if (c == 'E' || c == 'U' || c == 'M'
+#ifdef EDITOR
+            || c == 'D' || c == 'd'
+#endif
+            ) {
+            move++;
+            if (sscanf(move, "%d,%d%n", &x, &y, &n) != 2 ||
+                !INUI(ret, x, y))
+                goto badmove;
+
+            sp = &SPACE(ret, x, y);
+#ifdef EDITOR
+            if (c == 'D' || c == 'd') {
+                unsigned int currf, newf, maskf;
+
+                if (!dot_is_possible(ret, sp, 1)) goto badmove;
+
+                newf = F_DOT | (c == 'd' ? F_DOT_BLACK : 0);
+                currf = GRID(ret, grid, x, y).flags;
+                maskf = F_DOT | F_DOT_BLACK;
+                /* if we clicked 'white dot':
+                 *   white --> empty, empty --> white, black --> white.
+                 * if we clicked 'black dot':
+                 *   black --> empty, empty --> black, white --> black.
+                 */
+                if (currf & maskf) {
+                    sp->flags &= ~maskf;
+                    if ((currf & maskf) != newf)
+                        sp->flags |= newf;
+                } else
+                    sp->flags |= newf;
+                sp->nassoc = 0; /* edit-mode disallows associations. */
+                game_update_dots(ret);
+            } else
+#endif
+                   if (c == 'E') {
+                if (sp->type != s_edge) goto badmove;
+                sp->flags ^= F_EDGE_SET;
+            } else if (c == 'U') {
+                if (sp->type != s_tile || !(sp->flags & F_TILE_ASSOC))
+                    goto badmove;
+                /* The solver doesn't assume we'll mirror things */
+                if (currently_solving)
+                    remove_assoc(ret, sp);
+                else
+                    remove_assoc_with_opposite(ret, sp);
+            } else if (c == 'M') {
+                if (!(sp->flags & F_DOT)) goto badmove;
+                sp->flags ^= F_DOT_HOLD;
+            }
+            move += n;
+        } else if (c == 'A' || c == 'a') {
+            move++;
+            if (sscanf(move, "%d,%d,%d,%d%n", &x, &y, &ax, &ay, &n) != 4 ||
+                x < 1 || y < 1 || x >= (ret->sx-1) || y >= (ret->sy-1) ||
+                ax < 1 || ay < 1 || ax >= (ret->sx-1) || ay >= (ret->sy-1))
+                goto badmove;
+
+            dot = &GRID(ret, grid, ax, ay);
+            if (!(dot->flags & F_DOT))goto badmove;
+            if (dot->flags & F_DOT_HOLD) goto badmove;
+
+            for (dx = -1; dx <= 1; dx++) {
+                for (dy = -1; dy <= 1; dy++) {
+                    sp = &GRID(ret, grid, x+dx, y+dy);
+                    if (sp->type != s_tile) continue;
+                    if (sp->flags & F_TILE_ASSOC) {
+                        space *dot = &SPACE(ret, sp->dotx, sp->doty);
+                        if (dot->flags & F_DOT_HOLD) continue;
+                    }
+                    /* The solver doesn't assume we'll mirror things */
+                    if (currently_solving)
+                        add_assoc(ret, sp, dot);
+                    else
+                        add_assoc_with_opposite(ret, sp, dot);
+                }
+            }
+            move += n;
+#ifdef EDITOR
+        } else if (c == 'C') {
+            move++;
+            clear_game(ret, 1);
+#endif
+        } else if (c == 'S') {
+            move++;
+            ret->used_solve = 1;
+            currently_solving = TRUE;
+        } else
+            goto badmove;
+
+        if (*move == ';')
+            move++;
+        else if (*move)
+            goto badmove;
+    }
+    if (check_complete(ret, NULL, NULL))
+        ret->completed = 1;
+    return ret;
+
+badmove:
+    free_game(ret);
+    return NULL;
+}
+
+/* ----------------------------------------------------------------------
+ * Drawing routines.
+ */
+
+/* Lines will be much smaller size than squares; say, 1/8 the size?
+ *
+ * Need a 'top-left corner of location XxY' to take this into account;
+ * alternaticaly, that could give the middle of that location, and the
+ * drawing code would just know the expected dimensions.
+ *
+ * We also need something to take a click and work out what it was
+ * we were interested in. Clicking on vertices is required because
+ * we may want to drag from them, for example.
+ */
+
+static void game_compute_size(const game_params *params, int sz,
+                              int *x, int *y)
+{
+    struct { int tilesize, w, h; } ads, *ds = &ads;
+
+    ds->tilesize = sz;
+    ds->w = params->w;
+    ds->h = params->h;
+
+    *x = DRAW_WIDTH;
+    *y = DRAW_HEIGHT;
+}
+
+static void game_set_size(drawing *dr, game_drawstate *ds,
+                          const game_params *params, int sz)
+{
+    ds->tilesize = sz;
+
+    assert(TILE_SIZE > 0);
+
+    assert(!ds->bl);
+    ds->bl = blitter_new(dr, TILE_SIZE, TILE_SIZE);
+
+    assert(!ds->blmirror);
+    ds->blmirror = blitter_new(dr, TILE_SIZE, TILE_SIZE);
+
+    assert(!ds->cur_bl);
+    ds->cur_bl = blitter_new(dr, TILE_SIZE, TILE_SIZE);
+}
+
+static float *game_colours(frontend *fe, int *ncolours)
+{
+    float *ret = snewn(3 * NCOLOURS, float);
+    int i;
+
+    /*
+     * We call game_mkhighlight to ensure the background colour
+     * isn't completely white. We don't actually use the high- and
+     * lowlight colours it generates.
+     */
+    game_mkhighlight(fe, ret, COL_BACKGROUND, COL_WHITEBG, COL_BLACKBG);
+
+    for (i = 0; i < 3; i++) {
+        /*
+         * Currently, white dots and white-background squares are
+         * both pure white.
+         */
+        ret[COL_WHITEDOT * 3 + i] = 1.0F;
+        ret[COL_WHITEBG * 3 + i] = 1.0F;
+
+        /*
+         * But black-background squares are a dark grey, whereas
+         * black dots are really black.
+         */
+        ret[COL_BLACKDOT * 3 + i] = 0.0F;
+        ret[COL_BLACKBG * 3 + i] = ret[COL_BACKGROUND * 3 + i] * 0.3F;
+
+        /*
+         * In unfilled squares, we draw a faint gridwork.
+         */
+        ret[COL_GRID * 3 + i] = ret[COL_BACKGROUND * 3 + i] * 0.8F;
+
+        /*
+         * Edges and arrows are filled in in pure black.
+         */
+        ret[COL_EDGE * 3 + i] = 0.0F;
+        ret[COL_ARROW * 3 + i] = 0.0F;
+    }
+
+#ifdef EDITOR
+    /* tinge the edit background to bluey */
+    ret[COL_BACKGROUND * 3 + 0] = ret[COL_BACKGROUND * 3 + 0] * 0.8F;
+    ret[COL_BACKGROUND * 3 + 1] = ret[COL_BACKGROUND * 3 + 0] * 0.8F;
+    ret[COL_BACKGROUND * 3 + 2] = min(ret[COL_BACKGROUND * 3 + 0] * 1.4F, 1.0F);
+#endif
+
+    ret[COL_CURSOR * 3 + 0] = min(ret[COL_BACKGROUND * 3 + 0] * 1.4F, 1.0F);
+    ret[COL_CURSOR * 3 + 1] = ret[COL_BACKGROUND * 3 + 0] * 0.8F;
+    ret[COL_CURSOR * 3 + 2] = ret[COL_BACKGROUND * 3 + 0] * 0.8F;
+
+    *ncolours = NCOLOURS;
+    return ret;
+}
+
+static game_drawstate *game_new_drawstate(drawing *dr, const game_state *state)
+{
+    struct game_drawstate *ds = snew(struct game_drawstate);
+    int i;
+
+    ds->started = 0;
+    ds->w = state->w;
+    ds->h = state->h;
+
+    ds->grid = snewn(ds->w*ds->h, unsigned long);
+    for (i = 0; i < ds->w*ds->h; i++)
+        ds->grid[i] = 0xFFFFFFFFUL;
+    ds->dx = snewn(ds->w*ds->h, int);
+    ds->dy = snewn(ds->w*ds->h, int);
+
+    ds->bl = NULL;
+    ds->blmirror = NULL;
+    ds->dragging = FALSE;
+    ds->dragx = ds->dragy = 0;
+
+    ds->colour_scratch = snewn(ds->w * ds->h, int);
+
+    ds->cur_bl = NULL;
+    ds->cx = ds->cy = 0;
+    ds->cur_visible = 0;
+
+    return ds;
+}
+
+static void game_free_drawstate(drawing *dr, game_drawstate *ds)
+{
+    if (ds->cur_bl) blitter_free(dr, ds->cur_bl);
+    sfree(ds->colour_scratch);
+    if (ds->blmirror) blitter_free(dr, ds->blmirror);
+    if (ds->bl) blitter_free(dr, ds->bl);
+    sfree(ds->dx);
+    sfree(ds->dy);
+    sfree(ds->grid);
+    sfree(ds);
+}
+
+#define DRAW_EDGE_L    0x0001
+#define DRAW_EDGE_R    0x0002
+#define DRAW_EDGE_U    0x0004
+#define DRAW_EDGE_D    0x0008
+#define DRAW_CORNER_UL 0x0010
+#define DRAW_CORNER_UR 0x0020
+#define DRAW_CORNER_DL 0x0040
+#define DRAW_CORNER_DR 0x0080
+#define DRAW_WHITE     0x0100
+#define DRAW_BLACK     0x0200
+#define DRAW_ARROW     0x0400
+#define DRAW_CURSOR    0x0800
+#define DOT_SHIFT_C    12
+#define DOT_SHIFT_M    2
+#define DOT_WHITE      1UL
+#define DOT_BLACK      2UL
+
+/*
+ * Draw an arrow centred on (cx,cy), pointing in the direction
+ * (ddx,ddy). (I.e. pointing at the point (cx+ddx, cy+ddy).
+ */
+static void draw_arrow(drawing *dr, game_drawstate *ds,
+                       int cx, int cy, int ddx, int ddy, int col)
+{
+    float vlen = (float)sqrt(ddx*ddx+ddy*ddy);
+    float xdx = ddx/vlen, xdy = ddy/vlen;
+    float ydx = -xdy, ydy = xdx;
+    int e1x = cx + (int)(xdx*TILE_SIZE/3), e1y = cy + (int)(xdy*TILE_SIZE/3);
+    int e2x = cx - (int)(xdx*TILE_SIZE/3), e2y = cy - (int)(xdy*TILE_SIZE/3);
+    int adx = (int)((ydx-xdx)*TILE_SIZE/8), ady = (int)((ydy-xdy)*TILE_SIZE/8);
+    int adx2 = (int)((-ydx-xdx)*TILE_SIZE/8), ady2 = (int)((-ydy-xdy)*TILE_SIZE/8);
+
+    draw_line(dr, e1x, e1y, e2x, e2y, col);
+    draw_line(dr, e1x, e1y, e1x+adx, e1y+ady, col);
+    draw_line(dr, e1x, e1y, e1x+adx2, e1y+ady2, col);
+}
+
+static void draw_square(drawing *dr, game_drawstate *ds, int x, int y,
+                        unsigned long flags, int ddx, int ddy)
+{
+    int lx = COORD(x), ly = COORD(y);
+    int dx, dy;
+    int gridcol;
+
+    clip(dr, lx, ly, TILE_SIZE, TILE_SIZE);
+
+    /*
+     * Draw the tile background.
+     */
+    draw_rect(dr, lx, ly, TILE_SIZE, TILE_SIZE,
+              (flags & DRAW_WHITE ? COL_WHITEBG :
+               flags & DRAW_BLACK ? COL_BLACKBG : COL_BACKGROUND));
+
+    /*
+     * Draw the grid.
+     */
+    gridcol = (flags & DRAW_BLACK ? COL_BLACKDOT : COL_GRID);
+    draw_rect(dr, lx, ly, 1, TILE_SIZE, gridcol);
+    draw_rect(dr, lx, ly, TILE_SIZE, 1, gridcol);
+
+    /*
+     * Draw the arrow, if present, or the cursor, if here.
+     */
+    if (flags & DRAW_ARROW)
+        draw_arrow(dr, ds, lx + TILE_SIZE/2, ly + TILE_SIZE/2, ddx, ddy,
+                   (flags & DRAW_CURSOR) ? COL_CURSOR : COL_ARROW);
+    else if (flags & DRAW_CURSOR)
+        draw_rect_outline(dr,
+                          lx + TILE_SIZE/2 - CURSOR_SIZE,
+                          ly + TILE_SIZE/2 - CURSOR_SIZE,
+                          2*CURSOR_SIZE+1, 2*CURSOR_SIZE+1,
+                          COL_CURSOR);
+
+    /*
+     * Draw the edges.
+     */
+    if (flags & DRAW_EDGE_L)
+        draw_rect(dr, lx, ly, EDGE_THICKNESS, TILE_SIZE, COL_EDGE);
+    if (flags & DRAW_EDGE_R)
+        draw_rect(dr, lx + TILE_SIZE - EDGE_THICKNESS + 1, ly,
+                  EDGE_THICKNESS - 1, TILE_SIZE, COL_EDGE);
+    if (flags & DRAW_EDGE_U)
+        draw_rect(dr, lx, ly, TILE_SIZE, EDGE_THICKNESS, COL_EDGE);
+    if (flags & DRAW_EDGE_D)
+        draw_rect(dr, lx, ly + TILE_SIZE - EDGE_THICKNESS + 1,
+                  TILE_SIZE, EDGE_THICKNESS - 1, COL_EDGE);
+    if (flags & DRAW_CORNER_UL)
+        draw_rect(dr, lx, ly, EDGE_THICKNESS, EDGE_THICKNESS, COL_EDGE);
+    if (flags & DRAW_CORNER_UR)
+        draw_rect(dr, lx + TILE_SIZE - EDGE_THICKNESS + 1, ly,
+                  EDGE_THICKNESS - 1, EDGE_THICKNESS, COL_EDGE);
+    if (flags & DRAW_CORNER_DL)
+        draw_rect(dr, lx, ly + TILE_SIZE - EDGE_THICKNESS + 1,
+                  EDGE_THICKNESS, EDGE_THICKNESS - 1, COL_EDGE);
+    if (flags & DRAW_CORNER_DR)
+        draw_rect(dr, lx + TILE_SIZE - EDGE_THICKNESS + 1,
+                  ly + TILE_SIZE - EDGE_THICKNESS + 1,
+                  EDGE_THICKNESS - 1, EDGE_THICKNESS - 1, COL_EDGE);
+
+    /*
+     * Draw the dots.
+     */
+    for (dy = 0; dy < 3; dy++)
+        for (dx = 0; dx < 3; dx++) {
+            int dotval = (flags >> (DOT_SHIFT_C + DOT_SHIFT_M*(dy*3+dx)));
+            dotval &= (1 << DOT_SHIFT_M)-1;
+
+            if (dotval)
+                draw_circle(dr, lx+dx*TILE_SIZE/2, ly+dy*TILE_SIZE/2,
+                            DOT_SIZE,
+                            (dotval == 1 ? COL_WHITEDOT : COL_BLACKDOT),
+                            COL_BLACKDOT);
+        }
+
+    unclip(dr);
+    draw_update(dr, lx, ly, TILE_SIZE, TILE_SIZE);
+}
+
+static void calculate_opposite_point(const game_ui *ui,
+                                     const game_drawstate *ds, const int x,
+                                     const int y, int *oppositex,
+                                     int *oppositey)
+{
+    /* oppositex - dotx = dotx - x <=> oppositex = 2 * dotx - x */
+    *oppositex = 2 * SCOORD(ui->dotx) - x;
+    *oppositey = 2 * SCOORD(ui->doty) - y;
+}
+
+static void game_redraw(drawing *dr, game_drawstate *ds,
+                        const game_state *oldstate, const game_state *state,
+                        int dir, const game_ui *ui,
+                        float animtime, float flashtime)
+{
+    int w = ds->w, h = ds->h;
+    int x, y, flashing = FALSE;
+    int oppx, oppy;
+
+    if (flashtime > 0) {
+        int frame = (int)(flashtime / FLASH_TIME);
+        flashing = (frame % 2 == 0);
+    }
+
+    if (ds->dragging) {
+        assert(ds->bl);
+        assert(ds->blmirror);
+        calculate_opposite_point(ui, ds, ds->dragx + TILE_SIZE/2,
+                                 ds->dragy + TILE_SIZE/2, &oppx, &oppy);
+        oppx -= TILE_SIZE/2;
+        oppy -= TILE_SIZE/2;
+        blitter_load(dr, ds->bl, ds->dragx, ds->dragy);
+        draw_update(dr, ds->dragx, ds->dragy, TILE_SIZE, TILE_SIZE);
+        blitter_load(dr, ds->blmirror, oppx, oppy);
+        draw_update(dr, oppx, oppy, TILE_SIZE, TILE_SIZE);
+        ds->dragging = FALSE;
+    }
+    if (ds->cur_visible) {
+        assert(ds->cur_bl);
+        blitter_load(dr, ds->cur_bl, ds->cx, ds->cy);
+        draw_update(dr, ds->cx, ds->cy, CURSOR_SIZE*2+1, CURSOR_SIZE*2+1);
+        ds->cur_visible = FALSE;
+    }
+
+    if (!ds->started) {
+        draw_rect(dr, 0, 0, DRAW_WIDTH, DRAW_HEIGHT, COL_BACKGROUND);
+        draw_rect(dr, BORDER - EDGE_THICKNESS + 1, BORDER - EDGE_THICKNESS + 1,
+                  w*TILE_SIZE + EDGE_THICKNESS*2 - 1,
+                  h*TILE_SIZE + EDGE_THICKNESS*2 - 1, COL_EDGE);
+        draw_update(dr, 0, 0, DRAW_WIDTH, DRAW_HEIGHT);
+        ds->started = TRUE;
+    }
+
+    check_complete(state, NULL, ds->colour_scratch);
+
+    for (y = 0; y < h; y++)
+        for (x = 0; x < w; x++) {
+            unsigned long flags = 0;
+            int ddx = 0, ddy = 0;
+            space *sp, *opp;
+            int dx, dy;
+
+            /*
+             * Set up the flags for this square. Firstly, see if we
+             * have edges.
+             */
+            if (SPACE(state, x*2, y*2+1).flags & F_EDGE_SET)
+                flags |= DRAW_EDGE_L;
+            if (SPACE(state, x*2+2, y*2+1).flags & F_EDGE_SET)
+                flags |= DRAW_EDGE_R;
+            if (SPACE(state, x*2+1, y*2).flags & F_EDGE_SET)
+                flags |= DRAW_EDGE_U;
+            if (SPACE(state, x*2+1, y*2+2).flags & F_EDGE_SET)
+                flags |= DRAW_EDGE_D;
+
+            /*
+             * Also, mark corners of neighbouring edges.
+             */
+            if ((x > 0 && SPACE(state, x*2-1, y*2).flags & F_EDGE_SET) ||
+                (y > 0 && SPACE(state, x*2, y*2-1).flags & F_EDGE_SET))
+                flags |= DRAW_CORNER_UL;
+            if ((x+1 < w && SPACE(state, x*2+3, y*2).flags & F_EDGE_SET) ||
+                (y > 0 && SPACE(state, x*2+2, y*2-1).flags & F_EDGE_SET))
+                flags |= DRAW_CORNER_UR;
+            if ((x > 0 && SPACE(state, x*2-1, y*2+2).flags & F_EDGE_SET) ||
+                (y+1 < h && SPACE(state, x*2, y*2+3).flags & F_EDGE_SET))
+                flags |= DRAW_CORNER_DL;
+            if ((x+1 < w && SPACE(state, x*2+3, y*2+2).flags & F_EDGE_SET) ||
+                (y+1 < h && SPACE(state, x*2+2, y*2+3).flags & F_EDGE_SET))
+                flags |= DRAW_CORNER_DR;
+
+            /*
+             * If this square is part of a valid region, paint it
+             * that region's colour. Exception: if we're flashing,
+             * everything goes briefly back to background colour.
+             */
+            sp = &SPACE(state, x*2+1, y*2+1);
+            if (sp->flags & F_TILE_ASSOC) {
+                opp = tile_opposite(state, sp);
+            } else {
+                opp = NULL;
+            }
+            if (ds->colour_scratch[y*w+x] && !flashing) {
+                flags |= (ds->colour_scratch[y*w+x] == 2 ?
+                          DRAW_BLACK : DRAW_WHITE);
+            }
+
+            /*
+             * If this square is associated with a dot but it isn't
+             * part of a valid region, draw an arrow in it pointing
+             * in the direction of that dot.
+             * 
+             * Exception: if this is the source point of an active
+             * drag, we don't draw the arrow.
+             */
+            if ((sp->flags & F_TILE_ASSOC) && !ds->colour_scratch[y*w+x]) {
+                if (ui->dragging && ui->srcx == x*2+1 && ui->srcy == y*2+1) {
+                    /* tile is the source, don't do it */
+                } else if (ui->dragging && opp && ui->srcx == opp->x && ui->srcy == opp->y) {
+                    /* opposite tile is the source, don't do it */
+                } else if (sp->doty != y*2+1 || sp->dotx != x*2+1) {
+                    flags |= DRAW_ARROW;
+                    ddy = sp->doty - (y*2+1);
+                    ddx = sp->dotx - (x*2+1);
+                }
+            }
+
+            /*
+             * Now go through the nine possible places we could
+             * have dots.
+             */
+            for (dy = 0; dy < 3; dy++)
+                for (dx = 0; dx < 3; dx++) {
+                    sp = &SPACE(state, x*2+dx, y*2+dy);
+                    if (sp->flags & F_DOT) {
+                        unsigned long dotval = (sp->flags & F_DOT_BLACK ?
+                                                DOT_BLACK : DOT_WHITE);
+                        flags |= dotval << (DOT_SHIFT_C +
+                                            DOT_SHIFT_M*(dy*3+dx));
+                    }
+                }
+
+            /*
+             * Now work out if we have to draw a cursor for this square;
+             * cursors-on-lines are taken care of below.
+             */
+            if (ui->cur_visible &&
+                ui->cur_x == x*2+1 && ui->cur_y == y*2+1 &&
+                !(SPACE(state, x*2+1, y*2+1).flags & F_DOT))
+                flags |= DRAW_CURSOR;
+
+            /*
+             * Now we have everything we're going to need. Draw the
+             * square.
+             */
+            if (ds->grid[y*w+x] != flags ||
+                ds->dx[y*w+x] != ddx ||
+                ds->dy[y*w+x] != ddy) {
+                draw_square(dr, ds, x, y, flags, ddx, ddy);
+                ds->grid[y*w+x] = flags;
+                ds->dx[y*w+x] = ddx;
+                ds->dy[y*w+x] = ddy;
+            }
+        }
+
+    /*
+     * Draw a cursor. This secondary blitter is much less invasive than trying
+     * to fix up all of the rest of the code with sufficient flags to be able to
+     * display this sensibly.
+     */
+    if (ui->cur_visible) {
+        space *sp = &SPACE(state, ui->cur_x, ui->cur_y);
+        ds->cur_visible = TRUE;
+        ds->cx = SCOORD(ui->cur_x) - CURSOR_SIZE;
+        ds->cy = SCOORD(ui->cur_y) - CURSOR_SIZE;
+        blitter_save(dr, ds->cur_bl, ds->cx, ds->cy);
+        if (sp->flags & F_DOT) {
+            /* draw a red dot (over the top of whatever would be there already) */
+            draw_circle(dr, SCOORD(ui->cur_x), SCOORD(ui->cur_y), DOT_SIZE,
+                        COL_CURSOR, COL_BLACKDOT);
+        } else if (sp->type != s_tile) {
+            /* draw an edge/vertex square; tile cursors are dealt with above. */
+            int dx = (ui->cur_x % 2) ? CURSOR_SIZE : CURSOR_SIZE/3;
+            int dy = (ui->cur_y % 2) ? CURSOR_SIZE : CURSOR_SIZE/3;
+            int x1 = SCOORD(ui->cur_x)-dx, y1 = SCOORD(ui->cur_y)-dy;
+            int xs = dx*2+1, ys = dy*2+1;
+
+            draw_rect(dr, x1, y1, xs, ys, COL_CURSOR);
+        }
+        draw_update(dr, ds->cx, ds->cy, CURSOR_SIZE*2+1, CURSOR_SIZE*2+1);
+    }
+
+    if (ui->dragging) {
+        ds->dragging = TRUE;
+        ds->dragx = ui->dx - TILE_SIZE/2;
+        ds->dragy = ui->dy - TILE_SIZE/2;
+        calculate_opposite_point(ui, ds, ui->dx, ui->dy, &oppx, &oppy);
+        blitter_save(dr, ds->bl, ds->dragx, ds->dragy);
+        blitter_save(dr, ds->blmirror, oppx - TILE_SIZE/2, oppy - TILE_SIZE/2);
+        draw_arrow(dr, ds, ui->dx, ui->dy, SCOORD(ui->dotx) - ui->dx,
+                   SCOORD(ui->doty) - ui->dy, COL_ARROW);
+        draw_arrow(dr, ds, oppx, oppy, SCOORD(ui->dotx) - oppx,
+                   SCOORD(ui->doty) - oppy, COL_ARROW);
+    }
+#ifdef EDITOR
+    {
+        char buf[256];
+        if (state->cdiff != -1)
+            sprintf(buf, "Puzzle is %s.", galaxies_diffnames[state->cdiff]);
+        else
+            buf[0] = '\0';
+        status_bar(dr, buf);
+    }
+#endif
+}
+
+static float game_anim_length(const game_state *oldstate,
+                              const game_state *newstate, int dir, game_ui *ui)
+{
+    return 0.0F;
+}
+
+static float game_flash_length(const game_state *oldstate,
+                               const game_state *newstate, int dir, game_ui *ui)
+{
+    if ((!oldstate->completed && newstate->completed) &&
+        !(newstate->used_solve))
+        return 3 * FLASH_TIME;
+    else
+        return 0.0F;
+}
+
+static int game_status(const game_state *state)
+{
+    return state->completed ? +1 : 0;
+}
+
+static int game_timing_state(const game_state *state, game_ui *ui)
+{
+    return TRUE;
+}
+
+#ifndef EDITOR
+static void game_print_size(const game_params *params, float *x, float *y)
+{
+   int pw, ph;
+
+   /*
+    * 8mm squares by default. (There isn't all that much detail
+    * that needs to go in each square.)
+    */
+   game_compute_size(params, 800, &pw, &ph);
+   *x = pw / 100.0F;
+   *y = ph / 100.0F;
+}
+
+static void game_print(drawing *dr, const game_state *state, int sz)
+{
+    int w = state->w, h = state->h;
+    int white, black, blackish;
+    int x, y, i, j;
+    int *colours, *dsf;
+    int *coords = NULL;
+    int ncoords = 0, coordsize = 0;
+
+    /* Ick: fake up `ds->tilesize' for macro expansion purposes */
+    game_drawstate ads, *ds = &ads;
+    ds->tilesize = sz;
+
+    white = print_mono_colour(dr, 1);
+    black = print_mono_colour(dr, 0);
+    blackish = print_hatched_colour(dr, HATCH_X);
+
+    /*
+     * Get the completion information.
+     */
+    dsf = snewn(w * h, int);
+    colours = snewn(w * h, int);
+    check_complete(state, dsf, colours);
+
+    /*
+     * Draw the grid.
+     */
+    print_line_width(dr, TILE_SIZE / 64);
+    for (x = 1; x < w; x++)
+        draw_line(dr, COORD(x), COORD(0), COORD(x), COORD(h), black);
+    for (y = 1; y < h; y++)
+        draw_line(dr, COORD(0), COORD(y), COORD(w), COORD(y), black);
+
+    /*
+     * Shade the completed regions. Just in case any particular
+     * printing platform deals badly with adjacent
+     * similarly-hatched regions, we'll fill each one as a single
+     * polygon.
+     */
+    for (i = 0; i < w*h; i++) {
+        j = dsf_canonify(dsf, i);
+        if (colours[j] != 0) {
+            int dx, dy, t;
+
+            /*
+             * This is the first square we've run into belonging to
+             * this polyomino, which means an edge of the polyomino
+             * is certain to be to our left. (After we finish
+             * tracing round it, we'll set the colours[] entry to
+             * zero to prevent accidentally doing it again.)
+             */
+
+            x = i % w;
+            y = i / w;
+            dx = -1;
+            dy = 0;
+            ncoords = 0;
+            while (1) {
+                /*
+                 * We are currently sitting on square (x,y), which
+                 * we know to be in our polyomino, and we also know
+                 * that (x+dx,y+dy) is not. The way I visualise
+                 * this is that we're standing to the right of a
+                 * boundary line, stretching our left arm out to
+                 * point to the exterior square on the far side.
+                 */
+
+                /*
+                 * First, check if we've gone round the entire
+                 * polyomino.
+                 */
+                if (ncoords > 0 &&
+                    (x == i%w && y == i/w && dx == -1 && dy == 0))
+                    break;
+
+                /*
+                 * Add to our coordinate list the coordinate
+                 * backwards and to the left of where we are.
+                 */
+                if (ncoords + 2 > coordsize) {
+                    coordsize = (ncoords * 3 / 2) + 64;
+                    coords = sresize(coords, coordsize, int);
+                }
+                coords[ncoords++] = COORD((2*x+1 + dx + dy) / 2);
+                coords[ncoords++] = COORD((2*y+1 + dy - dx) / 2);
+
+                /*
+                 * Follow the edge round. If the square directly in
+                 * front of us is not part of the polyomino, we
+                 * turn right; if it is and so is the square in
+                 * front of (x+dx,y+dy), we turn left; otherwise we
+                 * go straight on.
+                 */
+                if (x-dy < 0 || x-dy >= w || y+dx < 0 || y+dx >= h ||
+                    dsf_canonify(dsf, (y+dx)*w+(x-dy)) != j) {
+                    /* Turn right. */
+                    t = dx;
+                    dx = -dy;
+                    dy = t;
+                } else if (x+dx-dy >= 0 && x+dx-dy < w &&
+                           y+dy+dx >= 0 && y+dy+dx < h &&
+                           dsf_canonify(dsf, (y+dy+dx)*w+(x+dx-dy)) == j) {
+                    /* Turn left. */
+                    x += dx;
+                    y += dy;
+                    t = dx;
+                    dx = dy;
+                    dy = -t;
+                    x -= dx;
+                    y -= dy;
+                } else {
+                    /* Straight on. */
+                    x -= dy;
+                    y += dx;
+                }
+            }
+
+            /*
+             * Now we have our polygon complete, so fill it.
+             */
+            draw_polygon(dr, coords, ncoords/2,
+                         colours[j] == 2 ? blackish : -1, black);
+
+            /*
+             * And mark this polyomino as done.
+             */
+            colours[j] = 0;
+        }
+    }
+
+    /*
+     * Draw the edges.
+     */
+    for (y = 0; y <= h; y++)
+        for (x = 0; x <= w; x++) {
+            if (x < w && SPACE(state, x*2+1, y*2).flags & F_EDGE_SET)
+                draw_rect(dr, COORD(x)-EDGE_THICKNESS, COORD(y)-EDGE_THICKNESS,
+                          EDGE_THICKNESS * 2 + TILE_SIZE, EDGE_THICKNESS * 2,
+                          black);
+            if (y < h && SPACE(state, x*2, y*2+1).flags & F_EDGE_SET)
+                draw_rect(dr, COORD(x)-EDGE_THICKNESS, COORD(y)-EDGE_THICKNESS,
+                          EDGE_THICKNESS * 2, EDGE_THICKNESS * 2 + TILE_SIZE,
+                          black);
+        }
+
+    /*
+     * Draw the dots.
+     */
+    for (y = 0; y <= 2*h; y++)
+        for (x = 0; x <= 2*w; x++)
+            if (SPACE(state, x, y).flags & F_DOT) {
+                draw_circle(dr, (int)COORD(x/2.0), (int)COORD(y/2.0), DOT_SIZE,
+                            (SPACE(state, x, y).flags & F_DOT_BLACK ?
+                             black : white), black);
+            }
+
+    sfree(dsf);
+    sfree(colours);
+    sfree(coords);
+}
+#endif
+
+#ifdef COMBINED
+#define thegame galaxies
+#endif
+
+const struct game thegame = {
+    "Galaxies", "games.galaxies", "galaxies",
+    default_params,
+    game_fetch_preset, NULL,
+    decode_params,
+    encode_params,
+    free_params,
+    dup_params,
+    TRUE, game_configure, custom_params,
+    validate_params,
+    new_game_desc,
+    validate_desc,
+    new_game,
+    dup_game,
+    free_game,
+#ifdef EDITOR
+    FALSE, NULL,
+#else
+    TRUE, solve_game,
+#endif
+    TRUE, game_can_format_as_text_now, game_text_format,
+    new_ui,
+    free_ui,
+    encode_ui,
+    decode_ui,
+    game_changed_state,
+    interpret_move,
+    execute_move,
+    PREFERRED_TILE_SIZE, game_compute_size, game_set_size,
+    game_colours,
+    game_new_drawstate,
+    game_free_drawstate,
+    game_redraw,
+    game_anim_length,
+    game_flash_length,
+    game_status,
+#ifdef EDITOR
+    FALSE, FALSE, NULL, NULL,
+    TRUE,                              /* wants_statusbar */
+#else
+    TRUE, FALSE, game_print_size, game_print,
+    FALSE,                             /* wants_statusbar */
+#endif
+    FALSE, game_timing_state,
+    REQUIRE_RBUTTON,                   /* flags */
+};
+
+#ifdef STANDALONE_SOLVER
+
+const char *quis;
+
+#include <time.h>
+
+static void usage_exit(const char *msg)
+{
+    if (msg)
+        fprintf(stderr, "%s: %s\n", quis, msg);
+    fprintf(stderr, "Usage: %s [--seed SEED] --soak <params> | [game_id [game_id ...]]\n", quis);
+    exit(1);
+}
+
+static void dump_state(game_state *state)
+{
+    char *temp = game_text_format(state);
+    printf("%s\n", temp);
+    sfree(temp);
+}
+
+static int gen(game_params *p, random_state *rs, int debug)
+{
+    char *desc;
+    int diff;
+    game_state *state;
+
+#ifndef DEBUGGING
+    solver_show_working = debug;
+#endif
+    printf("Generating a %dx%d %s puzzle.\n",
+           p->w, p->h, galaxies_diffnames[p->diff]);
+
+    desc = new_game_desc(p, rs, NULL, 0);
+    state = new_game(NULL, p, desc);
+    dump_state(state);
+
+    diff = solver_state(state, DIFF_UNREASONABLE);
+    printf("Generated %s game %dx%d:%s\n",
+           galaxies_diffnames[diff], p->w, p->h, desc);
+    dump_state(state);
+
+    free_game(state);
+    sfree(desc);
+
+    return diff;
+}
+
+static void soak(game_params *p, random_state *rs)
+{
+    time_t tt_start, tt_now, tt_last;
+    char *desc;
+    game_state *st;
+    int diff, n = 0, i, diffs[DIFF_MAX], ndots = 0, nspaces = 0;
+
+#ifndef DEBUGGING
+    solver_show_working = 0;
+#endif
+    tt_start = tt_now = time(NULL);
+    for (i = 0; i < DIFF_MAX; i++) diffs[i] = 0;
+    maxtries = 1;
+
+    printf("Soak-generating a %dx%d grid, max. diff %s.\n",
+           p->w, p->h, galaxies_diffnames[p->diff]);
+    printf("   [");
+    for (i = 0; i < DIFF_MAX; i++)
+        printf("%s%s", (i == 0) ? "" : ", ", galaxies_diffnames[i]);
+    printf("]\n");
+
+    while (1) {
+        desc = new_game_desc(p, rs, NULL, 0);
+        st = new_game(NULL, p, desc);
+        diff = solver_state(st, p->diff);
+        nspaces += st->w*st->h;
+        for (i = 0; i < st->sx*st->sy; i++)
+            if (st->grid[i].flags & F_DOT) ndots++;
+        free_game(st);
+        sfree(desc);
+
+        diffs[diff]++;
+        n++;
+        tt_last = time(NULL);
+        if (tt_last > tt_now) {
+            tt_now = tt_last;
+            printf("%d total, %3.1f/s, [",
+                   n, (double)n / ((double)tt_now - tt_start));
+            for (i = 0; i < DIFF_MAX; i++)
+                printf("%s%.1f%%", (i == 0) ? "" : ", ",
+                       100.0 * ((double)diffs[i] / (double)n));
+            printf("], %.1f%% dots\n",
+                   100.0 * ((double)ndots / (double)nspaces));
+        }
+    }
+}
+
+int main(int argc, char **argv)
+{
+    game_params *p;
+    char *id = NULL, *desc, *err;
+    game_state *s;
+    int diff, do_soak = 0, verbose = 0;
+    random_state *rs;
+    time_t seed = time(NULL);
+
+    quis = argv[0];
+    while (--argc > 0) {
+        char *p = *++argv;
+        if (!strcmp(p, "-v")) {
+            verbose = 1;
+        } else if (!strcmp(p, "--seed")) {
+            if (argc == 0) usage_exit("--seed needs an argument");
+            seed = (time_t)atoi(*++argv);
+            argc--;
+        } else if (!strcmp(p, "--soak")) {
+            do_soak = 1;
+        } else if (*p == '-') {
+            usage_exit("unrecognised option");
+        } else {
+            id = p;
+        }
+    }
+
+    maxtries = 50;
+
+    p = default_params();
+    rs = random_new((void*)&seed, sizeof(time_t));
+
+    if (do_soak) {
+        if (!id) usage_exit("need one argument for --soak");
+        decode_params(p, *argv);
+        soak(p, rs);
+        return 0;
+    }
+
+    if (!id) {
+        while (1) {
+            p->w = random_upto(rs, 15) + 3;
+            p->h = random_upto(rs, 15) + 3;
+            p->diff = random_upto(rs, DIFF_UNREASONABLE);
+            diff = gen(p, rs, 0);
+        }
+        return 0;
+    }
+
+    desc = strchr(id, ':');
+    if (!desc) {
+        decode_params(p, id);
+        gen(p, rs, verbose);
+    } else {
+#ifndef DEBUGGING
+        solver_show_working = 1;
+#endif
+        *desc++ = '\0';
+        decode_params(p, id);
+        err = validate_desc(p, desc);
+        if (err) {
+            fprintf(stderr, "%s: %s\n", argv[0], err);
+            exit(1);
+        }
+        s = new_game(NULL, p, desc);
+        diff = solver_state(s, DIFF_UNREASONABLE);
+        dump_state(s);
+        printf("Puzzle is %s.\n", galaxies_diffnames[diff]);
+        free_game(s);
+    }
+
+    free_params(p);
+
+    return 0;
+}
+
+#endif
+
+#ifdef STANDALONE_PICTURE_GENERATOR
+
+/*
+ * Main program for the standalone picture generator. To use it,
+ * simply provide it with an XBM-format bitmap file (note XBM, not
+ * XPM) on standard input, and it will output a game ID in return.
+ * For example:
+ *
+ *   $ ./galaxiespicture < badly-drawn-cat.xbm
+ *   11x11:eloMBLzFeEzLNMWifhaWYdDbixCymBbBMLoDdewGg
+ *
+ * If you want a puzzle with a non-standard difficulty level, pass
+ * a partial parameters string as a command-line argument (e.g.
+ * `./galaxiespicture du < foo.xbm', where `du' is the same suffix
+ * which if it appeared in a random-seed game ID would set the
+ * difficulty level to Unreasonable). However, be aware that if the
+ * generator fails to produce an adequately difficult puzzle too
+ * many times then it will give up and return an easier one (just
+ * as it does during normal GUI play). To be sure you really have
+ * the difficulty you asked for, use galaxiessolver to
+ * double-check.
+ * 
+ * (Perhaps I ought to include an option to make this standalone
+ * generator carry on looping until it really does get the right
+ * difficulty. Hmmm.)
+ */
+
+#include <time.h>
+
+int main(int argc, char **argv)
+{
+    game_params *par;
+    char *params, *desc;
+    random_state *rs;
+    time_t seed = time(NULL);
+    char buf[4096];
+    int i;
+    int x, y;
+
+    par = default_params();
+    if (argc > 1)
+        decode_params(par, argv[1]);   /* get difficulty */
+    par->w = par->h = -1;
+
+    /*
+     * Now read an XBM file from standard input. This is simple and
+     * hacky and will do very little error detection, so don't feed
+     * it bogus data.
+     */
+    picture = NULL;
+    x = y = 0;
+    while (fgets(buf, sizeof(buf), stdin)) {
+        buf[strcspn(buf, "\r\n")] = '\0';
+        if (!strncmp(buf, "#define", 7)) {
+            /*
+             * Lines starting `#define' give the width and height.
+             */
+            char *num = buf + strlen(buf);
+            char *symend;
+
+            while (num > buf && isdigit((unsigned char)num[-1]))
+                num--;
+            symend = num;
+            while (symend > buf && isspace((unsigned char)symend[-1]))
+                symend--;
+
+            if (symend-5 >= buf && !strncmp(symend-5, "width", 5))
+                par->w = atoi(num);
+            else if (symend-6 >= buf && !strncmp(symend-6, "height", 6))
+                par->h = atoi(num);
+        } else {
+            /*
+             * Otherwise, break the string up into words and take
+             * any word of the form `0x' plus hex digits to be a
+             * byte.
+             */
+            char *p, *wordstart;
+
+            if (!picture) {
+                if (par->w < 0 || par->h < 0) {
+                    printf("failed to read width and height\n");
+                    return 1;
+                }
+                picture = snewn(par->w * par->h, int);
+                for (i = 0; i < par->w * par->h; i++)
+                    picture[i] = -1;
+            }
+
+            p = buf;
+            while (*p) {
+                while (*p && (*p == ',' || isspace((unsigned char)*p)))
+                    p++;
+                wordstart = p;
+                while (*p && !(*p == ',' || *p == '}' ||
+                               isspace((unsigned char)*p)))
+                    p++;
+                if (*p)
+                    *p++ = '\0';
+
+                if (wordstart[0] == '0' &&
+                    (wordstart[1] == 'x' || wordstart[1] == 'X') &&
+                    !wordstart[2 + strspn(wordstart+2,
+                                          "0123456789abcdefABCDEF")]) {
+                    unsigned long byte = strtoul(wordstart+2, NULL, 16);
+                    for (i = 0; i < 8; i++) {
+                        int bit = (byte >> i) & 1;
+                        if (y < par->h && x < par->w)
+                            picture[y * par->w + x] = bit;
+                        x++;
+                    }
+
+                    if (x >= par->w) {
+                        x = 0;
+                        y++;
+                    }
+                }
+            }
+        }
+    }
+
+    for (i = 0; i < par->w * par->h; i++)
+        if (picture[i] < 0) {
+            fprintf(stderr, "failed to read enough bitmap data\n");
+            return 1;
+        }
+
+    rs = random_new((void*)&seed, sizeof(time_t));
+
+    desc = new_game_desc(par, rs, NULL, FALSE);
+    params = encode_params(par, FALSE);
+    printf("%s:%s\n", params, desc);
+
+    sfree(desc);
+    sfree(params);
+    free_params(par);
+    random_free(rs);
+
+    return 0;
+}
+
+#endif
+
+/* vim: set shiftwidth=4 tabstop=8: */