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, 3250 insertions, 0 deletions

diff --git a/apps/plugins/puzzles/src/mines.c b/apps/plugins/puzzles/src/mines.c
new file mode 100644
index 0000000..6a5ce02
--- /dev/null
+++ b/apps/plugins/puzzles/src/mines.c
@@ -0,0 +1,3250 @@
+/*
+ * mines.c: Minesweeper clone with sophisticated grid generation.
+ * 
+ * Still TODO:
+ *
+ *  - think about configurably supporting question marks. Once,
+ *    that is, we've thought about configurability in general!
+ */
+
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+#include <assert.h>
+#include <ctype.h>
+#include <math.h>
+
+#include "tree234.h"
+#include "puzzles.h"
+
+enum {
+    COL_BACKGROUND, COL_BACKGROUND2,
+    COL_1, COL_2, COL_3, COL_4, COL_5, COL_6, COL_7, COL_8,
+    COL_MINE, COL_BANG, COL_CROSS, COL_FLAG, COL_FLAGBASE, COL_QUERY,
+    COL_HIGHLIGHT, COL_LOWLIGHT,
+    COL_WRONGNUMBER,
+    COL_CURSOR,
+    NCOLOURS
+};
+
+#define PREFERRED_TILE_SIZE 20
+#define TILE_SIZE (ds->tilesize)
+#ifdef SMALL_SCREEN
+#define BORDER 8
+#else
+#define BORDER (TILE_SIZE * 3 / 2)
+#endif
+#define HIGHLIGHT_WIDTH (TILE_SIZE / 10)
+#define OUTER_HIGHLIGHT_WIDTH (BORDER / 10)
+#define COORD(x)  ( (x) * TILE_SIZE + BORDER )
+#define FROMCOORD(x)  ( ((x) - BORDER + TILE_SIZE) / TILE_SIZE - 1 )
+
+#define FLASH_FRAME 0.13F
+
+struct game_params {
+    int w, h, n;
+    int unique;
+};
+
+struct mine_layout {
+    /*
+     * This structure is shared between all the game_states for a
+     * given instance of the puzzle, so we reference-count it.
+     */
+    int refcount;
+    char *mines;
+    /*
+     * If we haven't yet actually generated the mine layout, here's
+     * all the data we will need to do so.
+     */
+    int n, unique;
+    random_state *rs;
+    midend *me;		       /* to give back the new game desc */
+};
+
+struct game_state {
+    int w, h, n, dead, won;
+    int used_solve;
+    struct mine_layout *layout;	       /* real mine positions */
+    signed char *grid;			       /* player knowledge */
+    /*
+     * Each item in the `grid' array is one of the following values:
+     * 
+     * 	- 0 to 8 mean the square is open and has a surrounding mine
+     * 	  count.
+     * 
+     *  - -1 means the square is marked as a mine.
+     * 
+     *  - -2 means the square is unknown.
+     * 
+     * 	- -3 means the square is marked with a question mark
+     * 	  (FIXME: do we even want to bother with this?).
+     * 
+     * 	- 64 means the square has had a mine revealed when the game
+     * 	  was lost.
+     * 
+     * 	- 65 means the square had a mine revealed and this was the
+     * 	  one the player hits.
+     * 
+     * 	- 66 means the square has a crossed-out mine because the
+     * 	  player had incorrectly marked it.
+     */
+};
+
+static game_params *default_params(void)
+{
+    game_params *ret = snew(game_params);
+
+    ret->w = ret->h = 9;
+    ret->n = 10;
+    ret->unique = TRUE;
+
+    return ret;
+}
+
+static const struct game_params mines_presets[] = {
+  {9, 9, 10, TRUE},
+  {9, 9, 35, TRUE},
+  {16, 16, 40, TRUE},
+  {16, 16, 99, TRUE},
+#ifndef SMALL_SCREEN
+  {30, 16, 99, TRUE},
+  {30, 16, 170, TRUE},
+#endif
+};
+
+static int game_fetch_preset(int i, char **name, game_params **params)
+{
+    game_params *ret;
+    char str[80];
+
+    if (i < 0 || i >= lenof(mines_presets))
+        return FALSE;
+
+    ret = snew(game_params);
+    *ret = mines_presets[i];
+
+    sprintf(str, "%dx%d, %d mines", ret->w, ret->h, ret->n);
+
+    *name = dupstr(str);
+    *params = ret;
+    return TRUE;
+}
+
+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)
+{
+    char const *p = string;
+
+    params->w = atoi(p);
+    while (*p && isdigit((unsigned char)*p)) p++;
+    if (*p == 'x') {
+        p++;
+        params->h = atoi(p);
+        while (*p && isdigit((unsigned char)*p)) p++;
+    } else {
+        params->h = params->w;
+    }
+    if (*p == 'n') {
+	p++;
+	params->n = atoi(p);
+	while (*p && (*p == '.' || isdigit((unsigned char)*p))) p++;
+    } else {
+	params->n = params->w * params->h / 10;
+    }
+
+    while (*p) {
+	if (*p == 'a') {
+            p++;
+	    params->unique = FALSE;
+	} else
+	    p++;		       /* skip any other gunk */
+    }
+}
+
+static char *encode_params(const game_params *params, int full)
+{
+    char ret[400];
+    int len;
+
+    len = sprintf(ret, "%dx%d", params->w, params->h);
+    /*
+     * Mine count is a generation-time parameter, since it can be
+     * deduced from the mine bitmap!
+     */
+    if (full)
+	len += sprintf(ret+len, "n%d", params->n);
+    if (full && !params->unique)
+        ret[len++] = 'a';
+    assert(len < lenof(ret));
+    ret[len] = '\0';
+
+    return dupstr(ret);
+}
+
+static config_item *game_configure(const game_params *params)
+{
+    config_item *ret;
+    char buf[80];
+
+    ret = snewn(5, 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 = "Mines";
+    ret[2].type = C_STRING;
+    sprintf(buf, "%d", params->n);
+    ret[2].sval = dupstr(buf);
+    ret[2].ival = 0;
+
+    ret[3].name = "Ensure solubility";
+    ret[3].type = C_BOOLEAN;
+    ret[3].sval = NULL;
+    ret[3].ival = params->unique;
+
+    ret[4].name = NULL;
+    ret[4].type = C_END;
+    ret[4].sval = NULL;
+    ret[4].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->n = atoi(cfg[2].sval);
+    if (strchr(cfg[2].sval, '%'))
+	ret->n = ret->n * (ret->w * ret->h) / 100;
+    ret->unique = cfg[3].ival;
+
+    return ret;
+}
+
+static char *validate_params(const game_params *params, int full)
+{
+    /*
+     * Lower limit on grid size: each dimension must be at least 3.
+     * 1 is theoretically workable if rather boring, but 2 is a
+     * real problem: there is often _no_ way to generate a uniquely
+     * solvable 2xn Mines grid. You either run into two mines
+     * blocking the way and no idea what's behind them, or one mine
+     * and no way to know which of the two rows it's in. If the
+     * mine count is even you can create a soluble grid by packing
+     * all the mines at one end (so what when you hit a two-mine
+     * wall there are only as many covered squares left as there
+     * are mines); but if it's odd, you are doomed, because you
+     * _have_ to have a gap somewhere which you can't determine the
+     * position of.
+     */
+    if (full && params->unique && (params->w <= 2 || params->h <= 2))
+	return "Width and height must both be greater than two";
+    if (params->n > params->w * params->h - 9)
+	return "Too many mines for grid size";
+
+    /*
+     * FIXME: Need more constraints here. Not sure what the
+     * sensible limits for Minesweeper actually are. The limits
+     * probably ought to change, however, depending on uniqueness.
+     */
+
+    return NULL;
+}
+
+/* ----------------------------------------------------------------------
+ * Minesweeper solver, used to ensure the generated grids are
+ * solvable without having to take risks.
+ */
+
+/*
+ * Count the bits in a word. Only needs to cope with 16 bits.
+ */
+static int bitcount16(int inword)
+{
+    unsigned int word = inword;
+
+    word = ((word & 0xAAAA) >> 1) + (word & 0x5555);
+    word = ((word & 0xCCCC) >> 2) + (word & 0x3333);
+    word = ((word & 0xF0F0) >> 4) + (word & 0x0F0F);
+    word = ((word & 0xFF00) >> 8) + (word & 0x00FF);
+
+    return (int)word;
+}
+
+/*
+ * We use a tree234 to store a large number of small localised
+ * sets, each with a mine count. We also keep some of those sets
+ * linked together into a to-do list.
+ */
+struct set {
+    short x, y, mask, mines;
+    int todo;
+    struct set *prev, *next;
+};
+
+static int setcmp(void *av, void *bv)
+{
+    struct set *a = (struct set *)av;
+    struct set *b = (struct set *)bv;
+
+    if (a->y < b->y)
+	return -1;
+    else if (a->y > b->y)
+	return +1;
+    else if (a->x < b->x)
+	return -1;
+    else if (a->x > b->x)
+	return +1;
+    else if (a->mask < b->mask)
+	return -1;
+    else if (a->mask > b->mask)
+	return +1;
+    else
+	return 0;
+}
+
+struct setstore {
+    tree234 *sets;
+    struct set *todo_head, *todo_tail;
+};
+
+static struct setstore *ss_new(void)
+{
+    struct setstore *ss = snew(struct setstore);
+    ss->sets = newtree234(setcmp);
+    ss->todo_head = ss->todo_tail = NULL;
+    return ss;
+}
+
+/*
+ * Take two input sets, in the form (x,y,mask). Munge the first by
+ * taking either its intersection with the second or its difference
+ * with the second. Return the new mask part of the first set.
+ */
+static int setmunge(int x1, int y1, int mask1, int x2, int y2, int mask2,
+		    int diff)
+{
+    /*
+     * Adjust the second set so that it has the same x,y
+     * coordinates as the first.
+     */
+    if (abs(x2-x1) >= 3 || abs(y2-y1) >= 3) {
+	mask2 = 0;
+    } else {
+	while (x2 > x1) {
+	    mask2 &= ~(4|32|256);
+	    mask2 <<= 1;
+	    x2--;
+	}
+	while (x2 < x1) {
+	    mask2 &= ~(1|8|64);
+	    mask2 >>= 1;
+	    x2++;
+	}
+	while (y2 > y1) {
+	    mask2 &= ~(64|128|256);
+	    mask2 <<= 3;
+	    y2--;
+	}
+	while (y2 < y1) {
+	    mask2 &= ~(1|2|4);
+	    mask2 >>= 3;
+	    y2++;
+	}
+    }
+
+    /*
+     * Invert the second set if `diff' is set (we're after A &~ B
+     * rather than A & B).
+     */
+    if (diff)
+	mask2 ^= 511;
+
+    /*
+     * Now all that's left is a logical AND.
+     */
+    return mask1 & mask2;
+}
+
+static void ss_add_todo(struct setstore *ss, struct set *s)
+{
+    if (s->todo)
+	return;			       /* already on it */
+
+#ifdef SOLVER_DIAGNOSTICS
+    printf("adding set on todo list: %d,%d %03x %d\n",
+	   s->x, s->y, s->mask, s->mines);
+#endif
+
+    s->prev = ss->todo_tail;
+    if (s->prev)
+	s->prev->next = s;
+    else
+	ss->todo_head = s;
+    ss->todo_tail = s;
+    s->next = NULL;
+    s->todo = TRUE;
+}
+
+static void ss_add(struct setstore *ss, int x, int y, int mask, int mines)
+{
+    struct set *s;
+
+    assert(mask != 0);
+
+    /*
+     * Normalise so that x and y are genuinely the bounding
+     * rectangle.
+     */
+    while (!(mask & (1|8|64)))
+	mask >>= 1, x++;
+    while (!(mask & (1|2|4)))
+	mask >>= 3, y++;
+
+    /*
+     * Create a set structure and add it to the tree.
+     */
+    s = snew(struct set);
+    s->x = x;
+    s->y = y;
+    s->mask = mask;
+    s->mines = mines;
+    s->todo = FALSE;
+    if (add234(ss->sets, s) != s) {
+	/*
+	 * This set already existed! Free it and return.
+	 */
+	sfree(s);
+	return;
+    }
+
+    /*
+     * We've added a new set to the tree, so put it on the todo
+     * list.
+     */
+    ss_add_todo(ss, s);
+}
+
+static void ss_remove(struct setstore *ss, struct set *s)
+{
+    struct set *next = s->next, *prev = s->prev;
+
+#ifdef SOLVER_DIAGNOSTICS
+    printf("removing set %d,%d %03x\n", s->x, s->y, s->mask);
+#endif
+    /*
+     * Remove s from the todo list.
+     */
+    if (prev)
+	prev->next = next;
+    else if (s == ss->todo_head)
+	ss->todo_head = next;
+
+    if (next)
+	next->prev = prev;
+    else if (s == ss->todo_tail)
+	ss->todo_tail = prev;
+
+    s->todo = FALSE;
+
+    /*
+     * Remove s from the tree.
+     */
+    del234(ss->sets, s);
+
+    /*
+     * Destroy the actual set structure.
+     */
+    sfree(s);
+}
+
+/*
+ * Return a dynamically allocated list of all the sets which
+ * overlap a provided input set.
+ */
+static struct set **ss_overlap(struct setstore *ss, int x, int y, int mask)
+{
+    struct set **ret = NULL;
+    int nret = 0, retsize = 0;
+    int xx, yy;
+
+    for (xx = x-3; xx < x+3; xx++)
+	for (yy = y-3; yy < y+3; yy++) {
+	    struct set stmp, *s;
+	    int pos;
+
+	    /*
+	     * Find the first set with these top left coordinates.
+	     */
+	    stmp.x = xx;
+	    stmp.y = yy;
+	    stmp.mask = 0;
+
+	    if (findrelpos234(ss->sets, &stmp, NULL, REL234_GE, &pos)) {
+		while ((s = index234(ss->sets, pos)) != NULL &&
+		       s->x == xx && s->y == yy) {
+		    /*
+		     * This set potentially overlaps the input one.
+		     * Compute the intersection to see if they
+		     * really overlap, and add it to the list if
+		     * so.
+		     */
+		    if (setmunge(x, y, mask, s->x, s->y, s->mask, FALSE)) {
+			/*
+			 * There's an overlap.
+			 */
+			if (nret >= retsize) {
+			    retsize = nret + 32;
+			    ret = sresize(ret, retsize, struct set *);
+			}
+			ret[nret++] = s;
+		    }
+
+		    pos++;
+		}
+	    }
+	}
+
+    ret = sresize(ret, nret+1, struct set *);
+    ret[nret] = NULL;
+
+    return ret;
+}
+
+/*
+ * Get an element from the head of the set todo list.
+ */
+static struct set *ss_todo(struct setstore *ss)
+{
+    if (ss->todo_head) {
+	struct set *ret = ss->todo_head;
+	ss->todo_head = ret->next;
+	if (ss->todo_head)
+	    ss->todo_head->prev = NULL;
+	else
+	    ss->todo_tail = NULL;
+	ret->next = ret->prev = NULL;
+	ret->todo = FALSE;
+	return ret;
+    } else {
+	return NULL;
+    }
+}
+
+struct squaretodo {
+    int *next;
+    int head, tail;
+};
+
+static void std_add(struct squaretodo *std, int i)
+{
+    if (std->tail >= 0)
+	std->next[std->tail] = i;
+    else
+	std->head = i;
+    std->tail = i;
+    std->next[i] = -1;
+}
+
+typedef int (*open_cb)(void *, int, int);
+
+static void known_squares(int w, int h, struct squaretodo *std,
+                          signed char *grid,
+			  open_cb open, void *openctx,
+			  int x, int y, int mask, int mine)
+{
+    int xx, yy, bit;
+
+    bit = 1;
+
+    for (yy = 0; yy < 3; yy++)
+	for (xx = 0; xx < 3; xx++) {
+	    if (mask & bit) {
+		int i = (y + yy) * w + (x + xx);
+
+		/*
+		 * It's possible that this square is _already_
+		 * known, in which case we don't try to add it to
+		 * the list twice.
+		 */
+		if (grid[i] == -2) {
+
+		    if (mine) {
+			grid[i] = -1;   /* and don't open it! */
+		    } else {
+			grid[i] = open(openctx, x + xx, y + yy);
+			assert(grid[i] != -1);   /* *bang* */
+		    }
+		    std_add(std, i);
+
+		}
+	    }
+	    bit <<= 1;
+	}
+}
+
+/*
+ * This is data returned from the `perturb' function. It details
+ * which squares have become mines and which have become clear. The
+ * solver is (of course) expected to honourably not use that
+ * knowledge directly, but to efficently adjust its internal data
+ * structures and proceed based on only the information it
+ * legitimately has.
+ */
+struct perturbation {
+    int x, y;
+    int delta;			       /* +1 == become a mine; -1 == cleared */
+};
+struct perturbations {
+    int n;
+    struct perturbation *changes;
+};
+
+/*
+ * Main solver entry point. You give it a grid of existing
+ * knowledge (-1 for a square known to be a mine, 0-8 for empty
+ * squares with a given number of neighbours, -2 for completely
+ * unknown), plus a function which you can call to open new squares
+ * once you're confident of them. It fills in as much more of the
+ * grid as it can.
+ * 
+ * Return value is:
+ * 
+ *  - -1 means deduction stalled and nothing could be done
+ *  - 0 means deduction succeeded fully
+ *  - >0 means deduction succeeded but some number of perturbation
+ *    steps were required; the exact return value is the number of
+ *    perturb calls.
+ */
+
+typedef struct perturbations *(*perturb_cb) (void *, signed char *, int, int, int);
+
+static int minesolve(int w, int h, int n, signed char *grid,
+		     open_cb open,
+                     perturb_cb perturb,
+		     void *ctx, random_state *rs)
+{
+    struct setstore *ss = ss_new();
+    struct set **list;
+    struct squaretodo astd, *std = &astd;
+    int x, y, i, j;
+    int nperturbs = 0;
+
+    /*
+     * Set up a linked list of squares with known contents, so that
+     * we can process them one by one.
+     */
+    std->next = snewn(w*h, int);
+    std->head = std->tail = -1;
+
+    /*
+     * Initialise that list with all known squares in the input
+     * grid.
+     */
+    for (y = 0; y < h; y++) {
+	for (x = 0; x < w; x++) {
+	    i = y*w+x;
+	    if (grid[i] != -2)
+		std_add(std, i);
+	}
+    }
+
+    /*
+     * Main deductive loop.
+     */
+    while (1) {
+	int done_something = FALSE;
+	struct set *s;
+
+	/*
+	 * If there are any known squares on the todo list, process
+	 * them and construct a set for each.
+	 */
+	while (std->head != -1) {
+	    i = std->head;
+#ifdef SOLVER_DIAGNOSTICS
+	    printf("known square at %d,%d [%d]\n", i%w, i/w, grid[i]);
+#endif
+	    std->head = std->next[i];
+	    if (std->head == -1)
+		std->tail = -1;
+
+	    x = i % w;
+	    y = i / w;
+
+	    if (grid[i] >= 0) {
+		int dx, dy, mines, bit, val;
+#ifdef SOLVER_DIAGNOSTICS
+		printf("creating set around this square\n");
+#endif
+		/*
+		 * Empty square. Construct the set of non-known squares
+		 * around this one, and determine its mine count.
+		 */
+		mines = grid[i];
+		bit = 1;
+		val = 0;
+		for (dy = -1; dy <= +1; dy++) {
+		    for (dx = -1; dx <= +1; dx++) {
+#ifdef SOLVER_DIAGNOSTICS
+			printf("grid %d,%d = %d\n", x+dx, y+dy, grid[i+dy*w+dx]);
+#endif
+			if (x+dx < 0 || x+dx >= w || y+dy < 0 || y+dy >= h)
+			    /* ignore this one */;
+			else if (grid[i+dy*w+dx] == -1)
+			    mines--;
+			else if (grid[i+dy*w+dx] == -2)
+			    val |= bit;
+			bit <<= 1;
+		    }
+		}
+		if (val)
+		    ss_add(ss, x-1, y-1, val, mines);
+	    }
+
+	    /*
+	     * Now, whether the square is empty or full, we must
+	     * find any set which contains it and replace it with
+	     * one which does not.
+	     */
+	    {
+#ifdef SOLVER_DIAGNOSTICS
+		printf("finding sets containing known square %d,%d\n", x, y);
+#endif
+		list = ss_overlap(ss, x, y, 1);
+
+		for (j = 0; list[j]; j++) {
+		    int newmask, newmines;
+
+		    s = list[j];
+
+		    /*
+		     * Compute the mask for this set minus the
+		     * newly known square.
+		     */
+		    newmask = setmunge(s->x, s->y, s->mask, x, y, 1, TRUE);
+
+		    /*
+		     * Compute the new mine count.
+		     */
+		    newmines = s->mines - (grid[i] == -1);
+
+		    /*
+		     * Insert the new set into the collection,
+		     * unless it's been whittled right down to
+		     * nothing.
+		     */
+		    if (newmask)
+			ss_add(ss, s->x, s->y, newmask, newmines);
+
+		    /*
+		     * Destroy the old one; it is actually obsolete.
+		     */
+		    ss_remove(ss, s);
+		}
+
+		sfree(list);
+	    }
+
+	    /*
+	     * Marking a fresh square as known certainly counts as
+	     * doing something.
+	     */
+	    done_something = TRUE;
+	}
+
+	/*
+	 * Now pick a set off the to-do list and attempt deductions
+	 * based on it.
+	 */
+	if ((s = ss_todo(ss)) != NULL) {
+
+#ifdef SOLVER_DIAGNOSTICS
+	    printf("set to do: %d,%d %03x %d\n", s->x, s->y, s->mask, s->mines);
+#endif
+	    /*
+	     * Firstly, see if this set has a mine count of zero or
+	     * of its own cardinality.
+	     */
+	    if (s->mines == 0 || s->mines == bitcount16(s->mask)) {
+		/*
+		 * If so, we can immediately mark all the squares
+		 * in the set as known.
+		 */
+#ifdef SOLVER_DIAGNOSTICS
+		printf("easy\n");
+#endif
+		known_squares(w, h, std, grid, open, ctx,
+			      s->x, s->y, s->mask, (s->mines != 0));
+
+		/*
+		 * Having done that, we need do nothing further
+		 * with this set; marking all the squares in it as
+		 * known will eventually eliminate it, and will
+		 * also permit further deductions about anything
+		 * that overlaps it.
+		 */
+		continue;
+	    }
+
+	    /*
+	     * Failing that, we now search through all the sets
+	     * which overlap this one.
+	     */
+	    list = ss_overlap(ss, s->x, s->y, s->mask);
+
+	    for (j = 0; list[j]; j++) {
+		struct set *s2 = list[j];
+		int swing, s2wing, swc, s2wc;
+
+		/*
+		 * Find the non-overlapping parts s2-s and s-s2,
+		 * and their cardinalities.
+		 * 
+		 * I'm going to refer to these parts as `wings'
+		 * surrounding the central part common to both
+		 * sets. The `s wing' is s-s2; the `s2 wing' is
+		 * s2-s.
+		 */
+		swing = setmunge(s->x, s->y, s->mask, s2->x, s2->y, s2->mask,
+				 TRUE);
+		s2wing = setmunge(s2->x, s2->y, s2->mask, s->x, s->y, s->mask,
+				 TRUE);
+		swc = bitcount16(swing);
+		s2wc = bitcount16(s2wing);
+
+		/*
+		 * If one set has more mines than the other, and
+		 * the number of extra mines is equal to the
+		 * cardinality of that set's wing, then we can mark
+		 * every square in the wing as a known mine, and
+		 * every square in the other wing as known clear.
+		 */
+		if (swc == s->mines - s2->mines ||
+		    s2wc == s2->mines - s->mines) {
+		    known_squares(w, h, std, grid, open, ctx,
+				  s->x, s->y, swing,
+				  (swc == s->mines - s2->mines));
+		    known_squares(w, h, std, grid, open, ctx,
+				  s2->x, s2->y, s2wing,
+				  (s2wc == s2->mines - s->mines));
+		    continue;
+		}
+
+		/*
+		 * Failing that, see if one set is a subset of the
+		 * other. If so, we can divide up the mine count of
+		 * the larger set between the smaller set and its
+		 * complement, even if neither smaller set ends up
+		 * being immediately clearable.
+		 */
+		if (swc == 0 && s2wc != 0) {
+		    /* s is a subset of s2. */
+		    assert(s2->mines > s->mines);
+		    ss_add(ss, s2->x, s2->y, s2wing, s2->mines - s->mines);
+		} else if (s2wc == 0 && swc != 0) {
+		    /* s2 is a subset of s. */
+		    assert(s->mines > s2->mines);
+		    ss_add(ss, s->x, s->y, swing, s->mines - s2->mines);
+		}
+	    }
+
+	    sfree(list);
+
+	    /*
+	     * In this situation we have definitely done
+	     * _something_, even if it's only reducing the size of
+	     * our to-do list.
+	     */
+	    done_something = TRUE;
+	} else if (n >= 0) {
+	    /*
+	     * We have nothing left on our todo list, which means
+	     * all localised deductions have failed. Our next step
+	     * is to resort to global deduction based on the total
+	     * mine count. This is computationally expensive
+	     * compared to any of the above deductions, which is
+	     * why we only ever do it when all else fails, so that
+	     * hopefully it won't have to happen too often.
+	     * 
+	     * If you pass n<0 into this solver, that informs it
+	     * that you do not know the total mine count, so it
+	     * won't even attempt these deductions.
+	     */
+
+	    int minesleft, squaresleft;
+	    int nsets, setused[10], cursor;
+
+	    /*
+	     * Start by scanning the current grid state to work out
+	     * how many unknown squares we still have, and how many
+	     * mines are to be placed in them.
+	     */
+	    squaresleft = 0;
+	    minesleft = n;
+	    for (i = 0; i < w*h; i++) {
+		if (grid[i] == -1)
+		    minesleft--;
+		else if (grid[i] == -2)
+		    squaresleft++;
+	    }
+
+#ifdef SOLVER_DIAGNOSTICS
+	    printf("global deduction time: squaresleft=%d minesleft=%d\n",
+		   squaresleft, minesleft);
+	    for (y = 0; y < h; y++) {
+		for (x = 0; x < w; x++) {
+		    int v = grid[y*w+x];
+		    if (v == -1)
+			putchar('*');
+		    else if (v == -2)
+			putchar('?');
+		    else if (v == 0)
+			putchar('-');
+		    else
+			putchar('0' + v);
+		}
+		putchar('\n');
+	    }
+#endif
+
+	    /*
+	     * If there _are_ no unknown squares, we have actually
+	     * finished.
+	     */
+	    if (squaresleft == 0) {
+		assert(minesleft == 0);
+		break;
+	    }
+
+	    /*
+	     * First really simple case: if there are no more mines
+	     * left, or if there are exactly as many mines left as
+	     * squares to play them in, then it's all easy.
+	     */
+	    if (minesleft == 0 || minesleft == squaresleft) {
+		for (i = 0; i < w*h; i++)
+		    if (grid[i] == -2)
+			known_squares(w, h, std, grid, open, ctx,
+				      i % w, i / w, 1, minesleft != 0);
+		continue;	       /* now go back to main deductive loop */
+	    }
+
+	    /*
+	     * Failing that, we have to do some _real_ work.
+	     * Ideally what we do here is to try every single
+	     * combination of the currently available sets, in an
+	     * attempt to find a disjoint union (i.e. a set of
+	     * squares with a known mine count between them) such
+	     * that the remaining unknown squares _not_ contained
+	     * in that union either contain no mines or are all
+	     * mines.
+	     * 
+	     * Actually enumerating all 2^n possibilities will get
+	     * a bit slow for large n, so I artificially cap this
+	     * recursion at n=10 to avoid too much pain.
+	     */
+	    nsets = count234(ss->sets);
+	    if (nsets <= lenof(setused)) {
+		/*
+		 * Doing this with actual recursive function calls
+		 * would get fiddly because a load of local
+		 * variables from this function would have to be
+		 * passed down through the recursion. So instead
+		 * I'm going to use a virtual recursion within this
+		 * function. The way this works is:
+		 * 
+		 *  - we have an array `setused', such that
+		 *    setused[n] is 0 or 1 depending on whether set
+		 *    n is currently in the union we are
+		 *    considering.
+		 * 
+		 *  - we have a value `cursor' which indicates how
+		 *    much of `setused' we have so far filled in.
+		 *    It's conceptually the recursion depth.
+		 * 
+		 * We begin by setting `cursor' to zero. Then:
+		 * 
+		 *  - if cursor can advance, we advance it by one.
+		 *    We set the value in `setused' that it went
+		 *    past to 1 if that set is disjoint from
+		 *    anything else currently in `setused', or to 0
+		 *    otherwise.
+		 * 
+		 *  - If cursor cannot advance because it has
+		 *    reached the end of the setused list, then we
+		 *    have a maximal disjoint union. Check to see
+		 *    whether its mine count has any useful
+		 *    properties. If so, mark all the squares not
+		 *    in the union as known and terminate.
+		 * 
+		 *  - If cursor has reached the end of setused and
+		 *    the algorithm _hasn't_ terminated, back
+		 *    cursor up to the nearest 1, turn it into a 0
+		 *    and advance cursor just past it.
+		 * 
+		 *  - If we attempt to back up to the nearest 1 and
+		 *    there isn't one at all, then we have gone
+		 *    through all disjoint unions of sets in the
+		 *    list and none of them has been helpful, so we
+		 *    give up.
+		 */
+		struct set *sets[lenof(setused)];
+		for (i = 0; i < nsets; i++)
+		    sets[i] = index234(ss->sets, i);
+
+		cursor = 0;
+		while (1) {
+
+		    if (cursor < nsets) {
+			int ok = TRUE;
+
+			/* See if any existing set overlaps this one. */
+			for (i = 0; i < cursor; i++)
+			    if (setused[i] &&
+				setmunge(sets[cursor]->x,
+					 sets[cursor]->y,
+					 sets[cursor]->mask,
+					 sets[i]->x, sets[i]->y, sets[i]->mask,
+					 FALSE)) {
+				ok = FALSE;
+				break;
+			    }
+
+			if (ok) {
+			    /*
+			     * We're adding this set to our union,
+			     * so adjust minesleft and squaresleft
+			     * appropriately.
+			     */
+			    minesleft -= sets[cursor]->mines;
+			    squaresleft -= bitcount16(sets[cursor]->mask);
+			}
+
+			setused[cursor++] = ok;
+		    } else {
+#ifdef SOLVER_DIAGNOSTICS
+			printf("trying a set combination with %d %d\n",
+			       squaresleft, minesleft);
+#endif /* SOLVER_DIAGNOSTICS */
+
+			/*
+			 * We've reached the end. See if we've got
+			 * anything interesting.
+			 */
+			if (squaresleft > 0 &&
+			    (minesleft == 0 || minesleft == squaresleft)) {
+			    /*
+			     * We have! There is at least one
+			     * square not contained within the set
+			     * union we've just found, and we can
+			     * deduce that either all such squares
+			     * are mines or all are not (depending
+			     * on whether minesleft==0). So now all
+			     * we have to do is actually go through
+			     * the grid, find those squares, and
+			     * mark them.
+			     */
+			    for (i = 0; i < w*h; i++)
+				if (grid[i] == -2) {
+				    int outside = TRUE;
+				    y = i / w;
+				    x = i % w;
+				    for (j = 0; j < nsets; j++)
+					if (setused[j] &&
+					    setmunge(sets[j]->x, sets[j]->y,
+						     sets[j]->mask, x, y, 1,
+						     FALSE)) {
+					    outside = FALSE;
+					    break;
+					}
+				    if (outside)
+					known_squares(w, h, std, grid,
+						      open, ctx,
+						      x, y, 1, minesleft != 0);
+				}
+
+			    done_something = TRUE;
+			    break;     /* return to main deductive loop */
+			}
+
+			/*
+			 * If we reach here, then this union hasn't
+			 * done us any good, so move on to the
+			 * next. Backtrack cursor to the nearest 1,
+			 * change it to a 0 and continue.
+			 */
+			while (--cursor >= 0 && !setused[cursor]);
+			if (cursor >= 0) {
+			    assert(setused[cursor]);
+
+			    /*
+			     * We're removing this set from our
+			     * union, so re-increment minesleft and
+			     * squaresleft.
+			     */
+			    minesleft += sets[cursor]->mines;
+			    squaresleft += bitcount16(sets[cursor]->mask);
+
+			    setused[cursor++] = 0;
+			} else {
+			    /*
+			     * We've backtracked all the way to the
+			     * start without finding a single 1,
+			     * which means that our virtual
+			     * recursion is complete and nothing
+			     * helped.
+			     */
+			    break;
+			}
+		    }
+
+		}
+
+	    }
+	}
+
+	if (done_something)
+	    continue;
+
+#ifdef SOLVER_DIAGNOSTICS
+	/*
+	 * Dump the current known state of the grid.
+	 */
+	printf("solver ran out of steam, ret=%d, grid:\n", nperturbs);
+	for (y = 0; y < h; y++) {
+	    for (x = 0; x < w; x++) {
+		int v = grid[y*w+x];
+		if (v == -1)
+		    putchar('*');
+		else if (v == -2)
+		    putchar('?');
+		else if (v == 0)
+		    putchar('-');
+		else
+		    putchar('0' + v);
+	    }
+	    putchar('\n');
+	}
+
+	{
+	    struct set *s;
+
+	    for (i = 0; (s = index234(ss->sets, i)) != NULL; i++)
+		printf("remaining set: %d,%d %03x %d\n", s->x, s->y, s->mask, s->mines);
+	}
+#endif
+
+	/*
+	 * Now we really are at our wits' end as far as solving
+	 * this grid goes. Our only remaining option is to call
+	 * a perturb function and ask it to modify the grid to
+	 * make it easier.
+	 */
+	if (perturb) {
+	    struct perturbations *ret;
+	    struct set *s;
+
+	    nperturbs++;
+
+	    /*
+	     * Choose a set at random from the current selection,
+	     * and ask the perturb function to either fill or empty
+	     * it.
+	     * 
+	     * If we have no sets at all, we must give up.
+	     */
+	    if (count234(ss->sets) == 0) {
+#ifdef SOLVER_DIAGNOSTICS
+		printf("perturbing on entire unknown set\n");
+#endif
+		ret = perturb(ctx, grid, 0, 0, 0);
+	    } else {
+		s = index234(ss->sets, random_upto(rs, count234(ss->sets)));
+#ifdef SOLVER_DIAGNOSTICS
+		printf("perturbing on set %d,%d %03x\n", s->x, s->y, s->mask);
+#endif
+		ret = perturb(ctx, grid, s->x, s->y, s->mask);
+	    }
+
+	    if (ret) {
+		assert(ret->n > 0);    /* otherwise should have been NULL */
+
+		/*
+		 * A number of squares have been fiddled with, and
+		 * the returned structure tells us which. Adjust
+		 * the mine count in any set which overlaps one of
+		 * those squares, and put them back on the to-do
+		 * list. Also, if the square itself is marked as a
+		 * known non-mine, put it back on the squares-to-do
+		 * list.
+		 */
+		for (i = 0; i < ret->n; i++) {
+#ifdef SOLVER_DIAGNOSTICS
+		    printf("perturbation %s mine at %d,%d\n",
+			   ret->changes[i].delta > 0 ? "added" : "removed",
+			   ret->changes[i].x, ret->changes[i].y);
+#endif
+
+		    if (ret->changes[i].delta < 0 &&
+			grid[ret->changes[i].y*w+ret->changes[i].x] != -2) {
+			std_add(std, ret->changes[i].y*w+ret->changes[i].x);
+		    }
+
+		    list = ss_overlap(ss,
+				      ret->changes[i].x, ret->changes[i].y, 1);
+
+		    for (j = 0; list[j]; j++) {
+			list[j]->mines += ret->changes[i].delta;
+			ss_add_todo(ss, list[j]);
+		    }
+
+		    sfree(list);
+		}
+
+		/*
+		 * Now free the returned data.
+		 */
+		sfree(ret->changes);
+		sfree(ret);
+
+#ifdef SOLVER_DIAGNOSTICS
+		/*
+		 * Dump the current known state of the grid.
+		 */
+		printf("state after perturbation:\n");
+		for (y = 0; y < h; y++) {
+		    for (x = 0; x < w; x++) {
+			int v = grid[y*w+x];
+			if (v == -1)
+			    putchar('*');
+			else if (v == -2)
+			    putchar('?');
+			else if (v == 0)
+			    putchar('-');
+			else
+			    putchar('0' + v);
+		    }
+		    putchar('\n');
+		}
+
+		{
+		    struct set *s;
+
+		    for (i = 0; (s = index234(ss->sets, i)) != NULL; i++)
+			printf("remaining set: %d,%d %03x %d\n", s->x, s->y, s->mask, s->mines);
+		}
+#endif
+
+		/*
+		 * And now we can go back round the deductive loop.
+		 */
+		continue;
+	    }
+	}
+
+	/*
+	 * If we get here, even that didn't work (either we didn't
+	 * have a perturb function or it returned failure), so we
+	 * give up entirely.
+	 */
+	break;
+    }
+
+    /*
+     * See if we've got any unknown squares left.
+     */
+    for (y = 0; y < h; y++)
+	for (x = 0; x < w; x++)
+	    if (grid[y*w+x] == -2) {
+		nperturbs = -1;	       /* failed to complete */
+		break;
+	    }
+
+    /*
+     * Free the set list and square-todo list.
+     */
+    {
+	struct set *s;
+	while ((s = delpos234(ss->sets, 0)) != NULL)
+	    sfree(s);
+	freetree234(ss->sets);
+	sfree(ss);
+	sfree(std->next);
+    }
+
+    return nperturbs;
+}
+
+/* ----------------------------------------------------------------------
+ * Grid generator which uses the above solver.
+ */
+
+struct minectx {
+    char *grid;
+    int w, h;
+    int sx, sy;
+    int allow_big_perturbs;
+    random_state *rs;
+};
+
+static int mineopen(void *vctx, int x, int y)
+{
+    struct minectx *ctx = (struct minectx *)vctx;
+    int i, j, n;
+
+    assert(x >= 0 && x < ctx->w && y >= 0 && y < ctx->h);
+    if (ctx->grid[y * ctx->w + x])
+	return -1;		       /* *bang* */
+
+    n = 0;
+    for (i = -1; i <= +1; i++) {
+	if (x + i < 0 || x + i >= ctx->w)
+	    continue;
+	for (j = -1; j <= +1; j++) {
+	    if (y + j < 0 || y + j >= ctx->h)
+		continue;
+	    if (i == 0 && j == 0)
+		continue;
+	    if (ctx->grid[(y+j) * ctx->w + (x+i)])
+		n++;
+	}
+    }
+
+    return n;
+}
+
+/* Structure used internally to mineperturb(). */
+struct square {
+    int x, y, type, random;
+};
+static int squarecmp(const void *av, const void *bv)
+{
+    const struct square *a = (const struct square *)av;
+    const struct square *b = (const struct square *)bv;
+    if (a->type < b->type)
+	return -1;
+    else if (a->type > b->type)
+	return +1;
+    else if (a->random < b->random)
+	return -1;
+    else if (a->random > b->random)
+	return +1;
+    else if (a->y < b->y)
+	return -1;
+    else if (a->y > b->y)
+	return +1;
+    else if (a->x < b->x)
+	return -1;
+    else if (a->x > b->x)
+	return +1;
+    return 0;
+}
+
+/*
+ * Normally this function is passed an (x,y,mask) set description.
+ * On occasions, though, there is no _localised_ set being used,
+ * and the set being perturbed is supposed to be the entirety of
+ * the unreachable area. This is signified by the special case
+ * mask==0: in this case, anything labelled -2 in the grid is part
+ * of the set.
+ * 
+ * Allowing perturbation in this special case appears to make it
+ * guaranteeably possible to generate a workable grid for any mine
+ * density, but they tend to be a bit boring, with mines packed
+ * densely into far corners of the grid and the remainder being
+ * less dense than one might like. Therefore, to improve overall
+ * grid quality I disable this feature for the first few attempts,
+ * and fall back to it after no useful grid has been generated.
+ */
+static struct perturbations *mineperturb(void *vctx, signed char *grid,
+					 int setx, int sety, int mask)
+{
+    struct minectx *ctx = (struct minectx *)vctx;
+    struct square *sqlist;
+    int x, y, dx, dy, i, n, nfull, nempty;
+    struct square **tofill, **toempty, **todo;
+    int ntofill, ntoempty, ntodo, dtodo, dset;
+    struct perturbations *ret;
+    int *setlist;
+
+    if (!mask && !ctx->allow_big_perturbs)
+	return NULL;
+
+    /*
+     * Make a list of all the squares in the grid which we can
+     * possibly use. This list should be in preference order, which
+     * means
+     * 
+     *  - first, unknown squares on the boundary of known space
+     *  - next, unknown squares beyond that boundary
+     * 	- as a very last resort, known squares, but not within one
+     * 	  square of the starting position.
+     * 
+     * Each of these sections needs to be shuffled independently.
+     * We do this by preparing list of all squares and then sorting
+     * it with a random secondary key.
+     */
+    sqlist = snewn(ctx->w * ctx->h, struct square);
+    n = 0;
+    for (y = 0; y < ctx->h; y++)
+	for (x = 0; x < ctx->w; x++) {
+	    /*
+	     * If this square is too near the starting position,
+	     * don't put it on the list at all.
+	     */
+	    if (abs(y - ctx->sy) <= 1 && abs(x - ctx->sx) <= 1)
+		continue;
+
+	    /*
+	     * If this square is in the input set, also don't put
+	     * it on the list!
+	     */
+	    if ((mask == 0 && grid[y*ctx->w+x] == -2) ||
+		(x >= setx && x < setx + 3 &&
+		 y >= sety && y < sety + 3 &&
+		 mask & (1 << ((y-sety)*3+(x-setx)))))
+		continue;
+
+	    sqlist[n].x = x;
+	    sqlist[n].y = y;
+
+	    if (grid[y*ctx->w+x] != -2) {
+		sqlist[n].type = 3;    /* known square */
+	    } else {
+		/*
+		 * Unknown square. Examine everything around it and
+		 * see if it borders on any known squares. If it
+		 * does, it's class 1, otherwise it's 2.
+		 */
+
+		sqlist[n].type = 2;
+
+		for (dy = -1; dy <= +1; dy++)
+		    for (dx = -1; dx <= +1; dx++)
+			if (x+dx >= 0 && x+dx < ctx->w &&
+			    y+dy >= 0 && y+dy < ctx->h &&
+			    grid[(y+dy)*ctx->w+(x+dx)] != -2) {
+			    sqlist[n].type = 1;
+			    break;
+			}
+	    }
+
+	    /*
+	     * Finally, a random number to cause qsort to
+	     * shuffle within each group.
+	     */
+	    sqlist[n].random = random_bits(ctx->rs, 31);
+
+	    n++;
+	}
+
+    qsort(sqlist, n, sizeof(struct square), squarecmp);
+
+    /*
+     * Now count up the number of full and empty squares in the set
+     * we've been provided.
+     */
+    nfull = nempty = 0;
+    if (mask) {
+	for (dy = 0; dy < 3; dy++)
+	    for (dx = 0; dx < 3; dx++)
+		if (mask & (1 << (dy*3+dx))) {
+		    assert(setx+dx <= ctx->w);
+		    assert(sety+dy <= ctx->h);
+		    if (ctx->grid[(sety+dy)*ctx->w+(setx+dx)])
+			nfull++;
+		    else
+			nempty++;
+		}
+    } else {
+	for (y = 0; y < ctx->h; y++)
+	    for (x = 0; x < ctx->w; x++)
+		if (grid[y*ctx->w+x] == -2) {
+		    if (ctx->grid[y*ctx->w+x])
+			nfull++;
+		    else
+			nempty++;
+		}
+    }
+
+    /*
+     * Now go through our sorted list until we find either `nfull'
+     * empty squares, or `nempty' full squares; these will be
+     * swapped with the appropriate squares in the set to either
+     * fill or empty the set while keeping the same number of mines
+     * overall.
+     */
+    ntofill = ntoempty = 0;
+    if (mask) {
+	tofill = snewn(9, struct square *);
+	toempty = snewn(9, struct square *);
+    } else {
+	tofill = snewn(ctx->w * ctx->h, struct square *);
+	toempty = snewn(ctx->w * ctx->h, struct square *);
+    }
+    for (i = 0; i < n; i++) {
+	struct square *sq = &sqlist[i];
+	if (ctx->grid[sq->y * ctx->w + sq->x])
+	    toempty[ntoempty++] = sq;
+	else
+	    tofill[ntofill++] = sq;
+	if (ntofill == nfull || ntoempty == nempty)
+	    break;
+    }
+
+    /*
+     * If we haven't found enough empty squares outside the set to
+     * empty it into _or_ enough full squares outside it to fill it
+     * up with, we'll have to settle for doing only a partial job.
+     * In this case we choose to always _fill_ the set (because
+     * this case will tend to crop up when we're working with very
+     * high mine densities and the only way to get a solvable grid
+     * is going to be to pack most of the mines solidly around the
+     * edges). So now our job is to make a list of the empty
+     * squares in the set, and shuffle that list so that we fill a
+     * random selection of them.
+     */
+    if (ntofill != nfull && ntoempty != nempty) {
+	int k;
+
+	assert(ntoempty != 0);
+
+	setlist = snewn(ctx->w * ctx->h, int);
+	i = 0;
+	if (mask) {
+	    for (dy = 0; dy < 3; dy++)
+		for (dx = 0; dx < 3; dx++)
+		    if (mask & (1 << (dy*3+dx))) {
+			assert(setx+dx <= ctx->w);
+			assert(sety+dy <= ctx->h);
+			if (!ctx->grid[(sety+dy)*ctx->w+(setx+dx)])
+			    setlist[i++] = (sety+dy)*ctx->w+(setx+dx);
+		    }
+	} else {
+	    for (y = 0; y < ctx->h; y++)
+		for (x = 0; x < ctx->w; x++)
+		    if (grid[y*ctx->w+x] == -2) {
+			if (!ctx->grid[y*ctx->w+x])
+			    setlist[i++] = y*ctx->w+x;
+		    }
+	}
+	assert(i > ntoempty);
+	/*
+	 * Now pick `ntoempty' items at random from the list.
+	 */
+	for (k = 0; k < ntoempty; k++) {
+	    int index = k + random_upto(ctx->rs, i - k);
+	    int tmp;
+
+	    tmp = setlist[k];
+	    setlist[k] = setlist[index];
+	    setlist[index] = tmp;
+	}
+    } else
+	setlist = NULL;
+
+    /*
+     * Now we're pretty much there. We need to either
+     * 	(a) put a mine in each of the empty squares in the set, and
+     * 	    take one out of each square in `toempty'
+     * 	(b) take a mine out of each of the full squares in the set,
+     * 	    and put one in each square in `tofill'
+     * depending on which one we've found enough squares to do.
+     * 
+     * So we start by constructing our list of changes to return to
+     * the solver, so that it can update its data structures
+     * efficiently rather than having to rescan the whole grid.
+     */
+    ret = snew(struct perturbations);
+    if (ntofill == nfull) {
+	todo = tofill;
+	ntodo = ntofill;
+	dtodo = +1;
+	dset = -1;
+	sfree(toempty);
+    } else {
+	/*
+	 * (We also fall into this case if we've constructed a
+	 * setlist.)
+	 */
+	todo = toempty;
+	ntodo = ntoempty;
+	dtodo = -1;
+	dset = +1;
+	sfree(tofill);
+    }
+    ret->n = 2 * ntodo;
+    ret->changes = snewn(ret->n, struct perturbation);
+    for (i = 0; i < ntodo; i++) {
+	ret->changes[i].x = todo[i]->x;
+	ret->changes[i].y = todo[i]->y;
+	ret->changes[i].delta = dtodo;
+    }
+    /* now i == ntodo */
+    if (setlist) {
+	int j;
+	assert(todo == toempty);
+	for (j = 0; j < ntoempty; j++) {
+	    ret->changes[i].x = setlist[j] % ctx->w;
+	    ret->changes[i].y = setlist[j] / ctx->w;
+	    ret->changes[i].delta = dset;
+	    i++;
+	}
+	sfree(setlist);
+    } else if (mask) {
+	for (dy = 0; dy < 3; dy++)
+	    for (dx = 0; dx < 3; dx++)
+		if (mask & (1 << (dy*3+dx))) {
+		    int currval = (ctx->grid[(sety+dy)*ctx->w+(setx+dx)] ? +1 : -1);
+		    if (dset == -currval) {
+			ret->changes[i].x = setx + dx;
+			ret->changes[i].y = sety + dy;
+			ret->changes[i].delta = dset;
+			i++;
+		    }
+		}
+    } else {
+	for (y = 0; y < ctx->h; y++)
+	    for (x = 0; x < ctx->w; x++)
+		if (grid[y*ctx->w+x] == -2) {
+		    int currval = (ctx->grid[y*ctx->w+x] ? +1 : -1);
+		    if (dset == -currval) {
+			ret->changes[i].x = x;
+			ret->changes[i].y = y;
+			ret->changes[i].delta = dset;
+			i++;
+		    }
+		}
+    }
+    assert(i == ret->n);
+
+    sfree(sqlist);
+    sfree(todo);
+
+    /*
+     * Having set up the precise list of changes we're going to
+     * make, we now simply make them and return.
+     */
+    for (i = 0; i < ret->n; i++) {
+	int delta;
+
+	x = ret->changes[i].x;
+	y = ret->changes[i].y;
+	delta = ret->changes[i].delta;
+
+	/*
+	 * Check we're not trying to add an existing mine or remove
+	 * an absent one.
+	 */
+	assert((delta < 0) ^ (ctx->grid[y*ctx->w+x] == 0));
+
+	/*
+	 * Actually make the change.
+	 */
+	ctx->grid[y*ctx->w+x] = (delta > 0);
+
+	/*
+	 * Update any numbers already present in the grid.
+	 */
+	for (dy = -1; dy <= +1; dy++)
+	    for (dx = -1; dx <= +1; dx++)
+		if (x+dx >= 0 && x+dx < ctx->w &&
+		    y+dy >= 0 && y+dy < ctx->h &&
+		    grid[(y+dy)*ctx->w+(x+dx)] != -2) {
+		    if (dx == 0 && dy == 0) {
+			/*
+			 * The square itself is marked as known in
+			 * the grid. Mark it as a mine if it's a
+			 * mine, or else work out its number.
+			 */
+			if (delta > 0) {
+			    grid[y*ctx->w+x] = -1;
+			} else {
+			    int dx2, dy2, minecount = 0;
+			    for (dy2 = -1; dy2 <= +1; dy2++)
+				for (dx2 = -1; dx2 <= +1; dx2++)
+				    if (x+dx2 >= 0 && x+dx2 < ctx->w &&
+					y+dy2 >= 0 && y+dy2 < ctx->h &&
+					ctx->grid[(y+dy2)*ctx->w+(x+dx2)])
+					minecount++;
+			    grid[y*ctx->w+x] = minecount;
+			}
+		    } else {
+			if (grid[(y+dy)*ctx->w+(x+dx)] >= 0)
+			    grid[(y+dy)*ctx->w+(x+dx)] += delta;
+		    }
+		}
+    }
+
+#ifdef GENERATION_DIAGNOSTICS
+    {
+	int yy, xx;
+	printf("grid after perturbing:\n");
+	for (yy = 0; yy < ctx->h; yy++) {
+	    for (xx = 0; xx < ctx->w; xx++) {
+		int v = ctx->grid[yy*ctx->w+xx];
+		if (yy == ctx->sy && xx == ctx->sx) {
+		    assert(!v);
+		    putchar('S');
+		} else if (v) {
+		    putchar('*');
+		} else {
+		    putchar('-');
+		}
+	    }
+	    putchar('\n');
+	}
+	printf("\n");
+    }
+#endif
+
+    return ret;
+}
+
+static char *minegen(int w, int h, int n, int x, int y, int unique,
+		     random_state *rs)
+{
+    char *ret = snewn(w*h, char);
+    int success;
+    int ntries = 0;
+
+    do {
+	success = FALSE;
+	ntries++;
+
+	memset(ret, 0, w*h);
+
+	/*
+	 * Start by placing n mines, none of which is at x,y or within
+	 * one square of it.
+	 */
+	{
+	    int *tmp = snewn(w*h, int);
+	    int i, j, k, nn;
+
+	    /*
+	     * Write down the list of possible mine locations.
+	     */
+	    k = 0;
+	    for (i = 0; i < h; i++)
+		for (j = 0; j < w; j++)
+		    if (abs(i - y) > 1 || abs(j - x) > 1)
+			tmp[k++] = i*w+j;
+
+	    /*
+	     * Now pick n off the list at random.
+	     */
+	    nn = n;
+	    while (nn-- > 0) {
+		i = random_upto(rs, k);
+		ret[tmp[i]] = 1;
+		tmp[i] = tmp[--k];
+	    }
+
+	    sfree(tmp);
+	}
+
+#ifdef GENERATION_DIAGNOSTICS
+	{
+	    int yy, xx;
+	    printf("grid after initial generation:\n");
+	    for (yy = 0; yy < h; yy++) {
+		for (xx = 0; xx < w; xx++) {
+		    int v = ret[yy*w+xx];
+		    if (yy == y && xx == x) {
+			assert(!v);
+			putchar('S');
+		    } else if (v) {
+			putchar('*');
+		    } else {
+			putchar('-');
+		    }
+		}
+		putchar('\n');
+	    }
+	    printf("\n");
+	}
+#endif
+
+	/*
+	 * Now set up a results grid to run the solver in, and a
+	 * context for the solver to open squares. Then run the solver
+	 * repeatedly; if the number of perturb steps ever goes up or
+	 * it ever returns -1, give up completely.
+	 *
+	 * We bypass this bit if we're not after a unique grid.
+         */
+	if (unique) {
+	    signed char *solvegrid = snewn(w*h, signed char);
+	    struct minectx actx, *ctx = &actx;
+	    int solveret, prevret = -2;
+
+	    ctx->grid = ret;
+	    ctx->w = w;
+	    ctx->h = h;
+	    ctx->sx = x;
+	    ctx->sy = y;
+	    ctx->rs = rs;
+	    ctx->allow_big_perturbs = (ntries > 100);
+
+	    while (1) {
+		memset(solvegrid, -2, w*h);
+		solvegrid[y*w+x] = mineopen(ctx, x, y);
+		assert(solvegrid[y*w+x] == 0); /* by deliberate arrangement */
+
+		solveret =
+		    minesolve(w, h, n, solvegrid, mineopen, mineperturb, ctx, rs);
+		if (solveret < 0 || (prevret >= 0 && solveret >= prevret)) {
+		    success = FALSE;
+		    break;
+		} else if (solveret == 0) {
+		    success = TRUE;
+		    break;
+		}
+	    }
+
+	    sfree(solvegrid);
+	} else {
+	    success = TRUE;
+	}
+
+    } while (!success);
+
+    return ret;
+}
+
+static char *describe_layout(char *grid, int area, int x, int y,
+                             int obfuscate)
+{
+    char *ret, *p;
+    unsigned char *bmp;
+    int i;
+
+    /*
+     * Set up the mine bitmap and obfuscate it.
+     */
+    bmp = snewn((area + 7) / 8, unsigned char);
+    memset(bmp, 0, (area + 7) / 8);
+    for (i = 0; i < area; i++) {
+        if (grid[i])
+            bmp[i / 8] |= 0x80 >> (i % 8);
+    }
+    if (obfuscate)
+        obfuscate_bitmap(bmp, area, FALSE);
+
+    /*
+     * Now encode the resulting bitmap in hex. We can work to
+     * nibble rather than byte granularity, since the obfuscation
+     * function guarantees to return a bit string of the same
+     * length as its input.
+     */
+    ret = snewn((area+3)/4 + 100, char);
+    p = ret + sprintf(ret, "%d,%d,%s", x, y,
+                      obfuscate ? "m" : "u");   /* 'm' == masked */
+    for (i = 0; i < (area+3)/4; i++) {
+        int v = bmp[i/2];
+        if (i % 2 == 0)
+            v >>= 4;
+        *p++ = "0123456789abcdef"[v & 0xF];
+    }
+    *p = '\0';
+
+    sfree(bmp);
+
+    return ret;
+}
+
+static char *new_mine_layout(int w, int h, int n, int x, int y, int unique,
+			     random_state *rs, char **game_desc)
+{
+    char *grid;
+
+#ifdef TEST_OBFUSCATION
+    static int tested_obfuscation = FALSE;
+    if (!tested_obfuscation) {
+	/*
+	 * A few simple test vectors for the obfuscator.
+	 * 
+	 * First test: the 28-bit stream 1234567. This divides up
+	 * into 1234 and 567[0]. The SHA of 56 70 30 (appending
+	 * "0") is 15ce8ab946640340bbb99f3f48fd2c45d1a31d30. Thus,
+	 * we XOR the 16-bit string 15CE into the input 1234 to get
+	 * 07FA. Next, we SHA that with "0": the SHA of 07 FA 30 is
+	 * 3370135c5e3da4fed937adc004a79533962b6391. So we XOR the
+	 * 12-bit string 337 into the input 567 to get 650. Thus
+	 * our output is 07FA650.
+	 */
+	{
+	    unsigned char bmp1[] = "\x12\x34\x56\x70";
+	    obfuscate_bitmap(bmp1, 28, FALSE);
+	    printf("test 1 encode: %s\n",
+		   memcmp(bmp1, "\x07\xfa\x65\x00", 4) ? "failed" : "passed");
+	    obfuscate_bitmap(bmp1, 28, TRUE);
+	    printf("test 1 decode: %s\n",
+		   memcmp(bmp1, "\x12\x34\x56\x70", 4) ? "failed" : "passed");
+	}
+	/*
+	 * Second test: a long string to make sure we switch from
+	 * one SHA to the next correctly. My input string this time
+	 * is simply fifty bytes of zeroes.
+	 */
+	{
+	    unsigned char bmp2[50];
+	    unsigned char bmp2a[50];
+	    memset(bmp2, 0, 50);
+	    memset(bmp2a, 0, 50);
+	    obfuscate_bitmap(bmp2, 50 * 8, FALSE);
+	    /*
+	     * SHA of twenty-five zero bytes plus "0" is
+	     * b202c07b990c01f6ff2d544707f60e506019b671. SHA of
+	     * twenty-five zero bytes plus "1" is
+	     * fcb1d8b5a2f6b592fe6780b36aa9d65dd7aa6db9. Thus our
+	     * first half becomes
+	     * b202c07b990c01f6ff2d544707f60e506019b671fcb1d8b5a2.
+	     * 
+	     * SHA of that lot plus "0" is
+	     * 10b0af913db85d37ca27f52a9f78bba3a80030db. SHA of the
+	     * same string plus "1" is
+	     * 3d01d8df78e76d382b8106f480135a1bc751d725. So the
+	     * second half becomes
+	     * 10b0af913db85d37ca27f52a9f78bba3a80030db3d01d8df78.
+	     */
+	    printf("test 2 encode: %s\n",
+		   memcmp(bmp2, "\xb2\x02\xc0\x7b\x99\x0c\x01\xf6\xff\x2d\x54"
+			  "\x47\x07\xf6\x0e\x50\x60\x19\xb6\x71\xfc\xb1\xd8"
+			  "\xb5\xa2\x10\xb0\xaf\x91\x3d\xb8\x5d\x37\xca\x27"
+			  "\xf5\x2a\x9f\x78\xbb\xa3\xa8\x00\x30\xdb\x3d\x01"
+			  "\xd8\xdf\x78", 50) ? "failed" : "passed");
+	    obfuscate_bitmap(bmp2, 50 * 8, TRUE);
+	    printf("test 2 decode: %s\n",
+		   memcmp(bmp2, bmp2a, 50) ? "failed" : "passed");
+	}
+    }
+#endif
+
+    grid = minegen(w, h, n, x, y, unique, rs);
+
+    if (game_desc)
+        *game_desc = describe_layout(grid, w * h, x, y, TRUE);
+
+    return grid;
+}
+
+static char *new_game_desc(const game_params *params, random_state *rs,
+			   char **aux, int interactive)
+{
+    /*
+     * We generate the coordinates of an initial click even if they
+     * aren't actually used. This has the effect of harmonising the
+     * random number usage between interactive and batch use: if
+     * you use `mines --generate' with an explicit random seed, you
+     * should get exactly the same results as if you type the same
+     * random seed into the interactive game and click in the same
+     * initial location. (Of course you won't get the same grid if
+     * you click in a _different_ initial location, but there's
+     * nothing to be done about that.)
+     */
+    int x = random_upto(rs, params->w);
+    int y = random_upto(rs, params->h);
+
+    if (!interactive) {
+	/*
+	 * For batch-generated grids, pre-open one square.
+	 */
+	char *grid;
+	char *desc;
+
+	grid = new_mine_layout(params->w, params->h, params->n,
+			       x, y, params->unique, rs, &desc);
+	sfree(grid);
+	return desc;
+    } else {
+	char *rsdesc, *desc;
+
+	rsdesc = random_state_encode(rs);
+	desc = snewn(strlen(rsdesc) + 100, char);
+	sprintf(desc, "r%d,%c,%s", params->n, (char)(params->unique ? 'u' : 'a'), rsdesc);
+	sfree(rsdesc);
+	return desc;
+    }
+}
+
+static char *validate_desc(const game_params *params, const char *desc)
+{
+    int wh = params->w * params->h;
+    int x, y;
+
+    if (*desc == 'r') {
+        desc++;
+	if (!*desc || !isdigit((unsigned char)*desc))
+	    return "No initial mine count in game description";
+	while (*desc && isdigit((unsigned char)*desc))
+	    desc++;		       /* skip over mine count */
+	if (*desc != ',')
+	    return "No ',' after initial x-coordinate in game description";
+	desc++;
+	if (*desc != 'u' && *desc != 'a')
+	    return "No uniqueness specifier in game description";
+	desc++;
+	if (*desc != ',')
+	    return "No ',' after uniqueness specifier in game description";
+	/* now ignore the rest */
+    } else {
+	if (*desc && isdigit((unsigned char)*desc)) {
+	    x = atoi(desc);
+	    if (x < 0 || x >= params->w)
+		return "Initial x-coordinate was out of range";
+	    while (*desc && isdigit((unsigned char)*desc))
+		desc++;		       /* skip over x coordinate */
+	    if (*desc != ',')
+		return "No ',' after initial x-coordinate in game description";
+	    desc++;		       /* eat comma */
+	    if (!*desc || !isdigit((unsigned char)*desc))
+		return "No initial y-coordinate in game description";
+	    y = atoi(desc);
+	    if (y < 0 || y >= params->h)
+		return "Initial y-coordinate was out of range";
+	    while (*desc && isdigit((unsigned char)*desc))
+		desc++;		       /* skip over y coordinate */
+	    if (*desc != ',')
+		return "No ',' after initial y-coordinate in game description";
+	    desc++;		       /* eat comma */
+	}
+	/* eat `m' for `masked' or `u' for `unmasked', if present */
+	if (*desc == 'm' || *desc == 'u')
+	    desc++;
+	/* now just check length of remainder */
+	if (strlen(desc) != (wh+3)/4)
+	    return "Game description is wrong length";
+    }
+
+    return NULL;
+}
+
+static int open_square(game_state *state, int x, int y)
+{
+    int w = state->w, h = state->h;
+    int xx, yy, nmines, ncovered;
+
+    if (!state->layout->mines) {
+	/*
+	 * We have a preliminary game in which the mine layout
+	 * hasn't been generated yet. Generate it based on the
+	 * initial click location.
+	 */
+	char *desc, *privdesc;
+	state->layout->mines = new_mine_layout(w, h, state->layout->n,
+					       x, y, state->layout->unique,
+					       state->layout->rs,
+					       &desc);
+	/*
+	 * Find the trailing substring of the game description
+	 * corresponding to just the mine layout; we will use this
+	 * as our second `private' game ID for serialisation.
+	 */
+	privdesc = desc;
+	while (*privdesc && isdigit((unsigned char)*privdesc)) privdesc++;
+	if (*privdesc == ',') privdesc++;
+	while (*privdesc && isdigit((unsigned char)*privdesc)) privdesc++;
+	if (*privdesc == ',') privdesc++;
+	assert(*privdesc == 'm');
+	midend_supersede_game_desc(state->layout->me, desc, privdesc);
+	sfree(desc);
+	random_free(state->layout->rs);
+	state->layout->rs = NULL;
+    }
+
+    if (state->layout->mines[y*w+x]) {
+	/*
+	 * The player has landed on a mine. Bad luck. Expose the
+	 * mine that killed them, but not the rest (in case they
+	 * want to Undo and carry on playing).
+	 */
+	state->dead = TRUE;
+	state->grid[y*w+x] = 65;
+	return -1;
+    }
+
+    /*
+     * Otherwise, the player has opened a safe square. Mark it to-do.
+     */
+    state->grid[y*w+x] = -10;	       /* `todo' value internal to this func */
+
+    /*
+     * Now go through the grid finding all `todo' values and
+     * opening them. Every time one of them turns out to have no
+     * neighbouring mines, we add all its unopened neighbours to
+     * the list as well.
+     * 
+     * FIXME: We really ought to be able to do this better than
+     * using repeated N^2 scans of the grid.
+     */
+    while (1) {
+	int done_something = FALSE;
+
+	for (yy = 0; yy < h; yy++)
+	    for (xx = 0; xx < w; xx++)
+		if (state->grid[yy*w+xx] == -10) {
+		    int dx, dy, v;
+
+		    assert(!state->layout->mines[yy*w+xx]);
+
+		    v = 0;
+
+		    for (dx = -1; dx <= +1; dx++)
+			for (dy = -1; dy <= +1; dy++)
+			    if (xx+dx >= 0 && xx+dx < state->w &&
+				yy+dy >= 0 && yy+dy < state->h &&
+				state->layout->mines[(yy+dy)*w+(xx+dx)])
+				v++;
+
+		    state->grid[yy*w+xx] = v;
+
+		    if (v == 0) {
+			for (dx = -1; dx <= +1; dx++)
+			    for (dy = -1; dy <= +1; dy++)
+				if (xx+dx >= 0 && xx+dx < state->w &&
+				    yy+dy >= 0 && yy+dy < state->h &&
+				    state->grid[(yy+dy)*w+(xx+dx)] == -2)
+				    state->grid[(yy+dy)*w+(xx+dx)] = -10;
+		    }
+
+		    done_something = TRUE;
+		}
+
+	if (!done_something)
+	    break;
+    }
+
+    /*
+     * Finally, scan the grid and see if exactly as many squares
+     * are still covered as there are mines. If so, set the `won'
+     * flag and fill in mine markers on all covered squares.
+     */
+    nmines = ncovered = 0;
+    for (yy = 0; yy < h; yy++)
+	for (xx = 0; xx < w; xx++) {
+	    if (state->grid[yy*w+xx] < 0)
+		ncovered++;
+	    if (state->layout->mines[yy*w+xx])
+		nmines++;
+	}
+    assert(ncovered >= nmines);
+    if (ncovered == nmines) {
+	for (yy = 0; yy < h; yy++)
+	    for (xx = 0; xx < w; xx++) {
+		if (state->grid[yy*w+xx] < 0)
+		    state->grid[yy*w+xx] = -1;
+	}
+	state->won = TRUE;
+    }
+
+    return 0;
+}
+
+static game_state *new_game(midend *me, const game_params *params,
+                            const char *desc)
+{
+    game_state *state = snew(game_state);
+    int i, wh, x, y, masked;
+    unsigned char *bmp;
+
+    state->w = params->w;
+    state->h = params->h;
+    state->n = params->n;
+    state->dead = state->won = FALSE;
+    state->used_solve = FALSE;
+
+    wh = state->w * state->h;
+
+    state->layout = snew(struct mine_layout);
+    memset(state->layout, 0, sizeof(struct mine_layout));
+    state->layout->refcount = 1;
+
+    state->grid = snewn(wh, signed char);
+    memset(state->grid, -2, wh);
+
+    if (*desc == 'r') {
+	desc++;
+	state->layout->n = atoi(desc);
+	while (*desc && isdigit((unsigned char)*desc))
+	    desc++;		       /* skip over mine count */
+	if (*desc) desc++;	       /* eat comma */
+	if (*desc == 'a')
+	    state->layout->unique = FALSE;
+	else
+	    state->layout->unique = TRUE;
+	desc++;
+	if (*desc) desc++;	       /* eat comma */
+
+	state->layout->mines = NULL;
+	state->layout->rs = random_state_decode(desc);
+	state->layout->me = me;
+
+    } else {
+	state->layout->rs = NULL;
+	state->layout->me = NULL;
+	state->layout->mines = snewn(wh, char);
+
+	if (*desc && isdigit((unsigned char)*desc)) {
+	    x = atoi(desc);
+	    while (*desc && isdigit((unsigned char)*desc))
+		desc++;		       /* skip over x coordinate */
+	    if (*desc) desc++;	       /* eat comma */
+	    y = atoi(desc);
+	    while (*desc && isdigit((unsigned char)*desc))
+		desc++;		       /* skip over y coordinate */
+	    if (*desc) desc++;	       /* eat comma */
+	} else {
+	    x = y = -1;
+	}
+
+	if (*desc == 'm') {
+	    masked = TRUE;
+	    desc++;
+	} else {
+	    if (*desc == 'u')
+		desc++;
+	    /*
+	     * We permit game IDs to be entered by hand without the
+	     * masking transformation.
+	     */
+	    masked = FALSE;
+	}
+
+	bmp = snewn((wh + 7) / 8, unsigned char);
+	memset(bmp, 0, (wh + 7) / 8);
+	for (i = 0; i < (wh+3)/4; i++) {
+	    int c = desc[i];
+	    int v;
+
+	    assert(c != 0);	       /* validate_desc should have caught */
+	    if (c >= '0' && c <= '9')
+		v = c - '0';
+	    else if (c >= 'a' && c <= 'f')
+		v = c - 'a' + 10;
+	    else if (c >= 'A' && c <= 'F')
+		v = c - 'A' + 10;
+	    else
+		v = 0;
+
+	    bmp[i / 2] |= v << (4 * (1 - (i % 2)));
+	}
+
+	if (masked)
+	    obfuscate_bitmap(bmp, wh, TRUE);
+
+	memset(state->layout->mines, 0, wh);
+	for (i = 0; i < wh; i++) {
+	    if (bmp[i / 8] & (0x80 >> (i % 8)))
+		state->layout->mines[i] = 1;
+	}
+
+	if (x >= 0 && y >= 0)
+	    open_square(state, x, y);
+        sfree(bmp);
+    }
+
+    return state;
+}
+
+static game_state *dup_game(const game_state *state)
+{
+    game_state *ret = snew(game_state);
+
+    ret->w = state->w;
+    ret->h = state->h;
+    ret->n = state->n;
+    ret->dead = state->dead;
+    ret->won = state->won;
+    ret->used_solve = state->used_solve;
+    ret->layout = state->layout;
+    ret->layout->refcount++;
+    ret->grid = snewn(ret->w * ret->h, signed char);
+    memcpy(ret->grid, state->grid, ret->w * ret->h);
+
+    return ret;
+}
+
+static void free_game(game_state *state)
+{
+    if (--state->layout->refcount <= 0) {
+	sfree(state->layout->mines);
+	if (state->layout->rs)
+	    random_free(state->layout->rs);
+	sfree(state->layout);
+    }
+    sfree(state->grid);
+    sfree(state);
+}
+
+static char *solve_game(const game_state *state, const game_state *currstate,
+                        const char *aux, char **error)
+{
+    if (!state->layout->mines) {
+	*error = "Game has not been started yet";
+	return NULL;
+    }
+
+    return dupstr("S");
+}
+
+static int game_can_format_as_text_now(const game_params *params)
+{
+    return TRUE;
+}
+
+static char *game_text_format(const game_state *state)
+{
+    char *ret;
+    int x, y;
+
+    ret = snewn((state->w + 1) * state->h + 1, char);
+    for (y = 0; y < state->h; y++) {
+	for (x = 0; x < state->w; x++) {
+	    int v = state->grid[y*state->w+x];
+	    if (v == 0)
+		v = '-';
+	    else if (v >= 1 && v <= 8)
+		v = '0' + v;
+	    else if (v == -1)
+		v = '*';
+	    else if (v == -2 || v == -3)
+		v = '?';
+	    else if (v >= 64)
+		v = '!';
+	    ret[y * (state->w+1) + x] = v;
+	}
+	ret[y * (state->w+1) + state->w] = '\n';
+    }
+    ret[(state->w + 1) * state->h] = '\0';
+
+    return ret;
+}
+
+struct game_ui {
+    int hx, hy, hradius;	       /* for mouse-down highlights */
+    int validradius;
+    int flash_is_death;
+    int deaths, completed;
+    int cur_x, cur_y, cur_visible;
+};
+
+static game_ui *new_ui(const game_state *state)
+{
+    game_ui *ui = snew(game_ui);
+    ui->hx = ui->hy = -1;
+    ui->hradius = ui->validradius = 0;
+    ui->deaths = 0;
+    ui->completed = FALSE;
+    ui->flash_is_death = FALSE;	       /* *shrug* */
+    ui->cur_x = ui->cur_y = ui->cur_visible = 0;
+    return ui;
+}
+
+static void free_ui(game_ui *ui)
+{
+    sfree(ui);
+}
+
+static char *encode_ui(const game_ui *ui)
+{
+    char buf[80];
+    /*
+     * The deaths counter and completion status need preserving
+     * across a serialisation.
+     */
+    sprintf(buf, "D%d", ui->deaths);
+    if (ui->completed)
+	strcat(buf, "C");
+    return dupstr(buf);
+}
+
+static void decode_ui(game_ui *ui, const char *encoding)
+{
+    int p= 0;
+    sscanf(encoding, "D%d%n", &ui->deaths, &p);
+    if (encoding[p] == 'C')
+	ui->completed = TRUE;
+}
+
+static void game_changed_state(game_ui *ui, const game_state *oldstate,
+                               const game_state *newstate)
+{
+    if (newstate->won)
+	ui->completed = TRUE;
+}
+
+struct game_drawstate {
+    int w, h, started, tilesize, bg;
+    signed char *grid;
+    /*
+     * Items in this `grid' array have all the same values as in
+     * the game_state grid, and in addition:
+     * 
+     * 	- -10 means the tile was drawn `specially' as a result of a
+     * 	  flash, so it will always need redrawing.
+     * 
+     * 	- -22 and -23 mean the tile is highlighted for a possible
+     * 	  click.
+     */
+    int cur_x, cur_y; /* -1, -1 for no cursor displayed. */
+};
+
+static char *interpret_move(const game_state *from, game_ui *ui,
+                            const game_drawstate *ds,
+                            int x, int y, int button)
+{
+    int cx, cy;
+    char buf[256];
+
+    if (from->dead || from->won)
+	return NULL;		       /* no further moves permitted */
+
+    cx = FROMCOORD(x);
+    cy = FROMCOORD(y);
+
+    if (IS_CURSOR_MOVE(button)) {
+        move_cursor(button, &ui->cur_x, &ui->cur_y, from->w, from->h, 0);
+        ui->cur_visible = 1;
+        return "";
+    }
+    if (IS_CURSOR_SELECT(button)) {
+        int v = from->grid[ui->cur_y * from->w + ui->cur_x];
+
+        if (!ui->cur_visible) {
+            ui->cur_visible = 1;
+            return "";
+        }
+        if (button == CURSOR_SELECT2) {
+            /* As for RIGHT_BUTTON; only works on covered square. */
+            if (v != -2 && v != -1)
+                return NULL;
+            sprintf(buf, "F%d,%d", ui->cur_x, ui->cur_y);
+            return dupstr(buf);
+        }
+        /* Otherwise, treat as LEFT_BUTTON, for a single square. */
+        if (v == -2 || v == -3) {
+            if (from->layout->mines &&
+                from->layout->mines[ui->cur_y * from->w + ui->cur_x])
+                ui->deaths++;
+
+            sprintf(buf, "O%d,%d", ui->cur_x, ui->cur_y);
+            return dupstr(buf);
+        }
+        cx = ui->cur_x; cy = ui->cur_y;
+        ui->validradius = 1;
+        goto uncover;
+    }
+
+    if (button == LEFT_BUTTON || button == LEFT_DRAG ||
+	button == MIDDLE_BUTTON || button == MIDDLE_DRAG) {
+	if (cx < 0 || cx >= from->w || cy < 0 || cy >= from->h)
+	    return NULL;
+
+	/*
+	 * Mouse-downs and mouse-drags just cause highlighting
+	 * updates.
+	 */
+	ui->hx = cx;
+	ui->hy = cy;
+	ui->hradius = (from->grid[cy*from->w+cx] >= 0 ? 1 : 0);
+	if (button == LEFT_BUTTON)
+	    ui->validradius = ui->hradius;
+	else if (button == MIDDLE_BUTTON)
+	    ui->validradius = 1;
+        ui->cur_visible = 0;
+	return "";
+    }
+
+    if (button == RIGHT_BUTTON) {
+	if (cx < 0 || cx >= from->w || cy < 0 || cy >= from->h)
+	    return NULL;
+
+	/*
+	 * Right-clicking only works on a covered square, and it
+	 * toggles between -1 (marked as mine) and -2 (not marked
+	 * as mine).
+	 *
+	 * FIXME: question marks.
+	 */
+	if (from->grid[cy * from->w + cx] != -2 &&
+	    from->grid[cy * from->w + cx] != -1)
+	    return NULL;
+
+	sprintf(buf, "F%d,%d", cx, cy);
+	return dupstr(buf);
+    }
+
+    if (button == LEFT_RELEASE || button == MIDDLE_RELEASE) {
+	ui->hx = ui->hy = -1;
+	ui->hradius = 0;
+
+	/*
+	 * At this stage we must never return NULL: we have adjusted
+	 * the ui, so at worst we return "".
+	 */
+	if (cx < 0 || cx >= from->w || cy < 0 || cy >= from->h)
+	    return "";
+
+	/*
+	 * Left-clicking on a covered square opens a tile. Not
+	 * permitted if the tile is marked as a mine, for safety.
+	 * (Unmark it and _then_ open it.)
+	 */
+	if (button == LEFT_RELEASE &&
+	    (from->grid[cy * from->w + cx] == -2 ||
+	     from->grid[cy * from->w + cx] == -3) &&
+	    ui->validradius == 0) {
+	    /* Check if you've killed yourself. */
+	    if (from->layout->mines && from->layout->mines[cy * from->w + cx])
+		ui->deaths++;
+
+	    sprintf(buf, "O%d,%d", cx, cy);
+	    return dupstr(buf);
+	}
+        goto uncover;
+    }
+    return NULL;
+
+uncover:
+    {
+	/*
+	 * Left-clicking or middle-clicking on an uncovered tile:
+	 * first we check to see if the number of mine markers
+	 * surrounding the tile is equal to its mine count, and if
+	 * so then we open all other surrounding squares.
+	 */
+	if (from->grid[cy * from->w + cx] > 0 && ui->validradius == 1) {
+	    int dy, dx, n;
+
+	    /* Count mine markers. */
+	    n = 0;
+	    for (dy = -1; dy <= +1; dy++)
+		for (dx = -1; dx <= +1; dx++)
+		    if (cx+dx >= 0 && cx+dx < from->w &&
+			cy+dy >= 0 && cy+dy < from->h) {
+			if (from->grid[(cy+dy)*from->w+(cx+dx)] == -1)
+			    n++;
+		    }
+
+	    if (n == from->grid[cy * from->w + cx]) {
+
+		/*
+		 * Now see if any of the squares we're clearing
+		 * contains a mine (which will happen iff you've
+		 * incorrectly marked the mines around the clicked
+		 * square). If so, we open _just_ those squares, to
+		 * reveal as little additional information as we
+		 * can.
+		 */
+		char *p = buf;
+		char *sep = "";
+
+		for (dy = -1; dy <= +1; dy++)
+		    for (dx = -1; dx <= +1; dx++)
+			if (cx+dx >= 0 && cx+dx < from->w &&
+			    cy+dy >= 0 && cy+dy < from->h) {
+			    if (from->grid[(cy+dy)*from->w+(cx+dx)] != -1 &&
+				from->layout->mines &&
+				from->layout->mines[(cy+dy)*from->w+(cx+dx)]) {
+				p += sprintf(p, "%sO%d,%d", sep, cx+dx, cy+dy);
+				sep = ";";
+			    }
+			}
+
+		if (p > buf) {
+		    ui->deaths++;
+		} else {
+		    sprintf(buf, "C%d,%d", cx, cy);
+		}
+
+		return dupstr(buf);
+	    }
+	}
+
+	return "";
+    }
+}
+
+static game_state *execute_move(const game_state *from, const char *move)
+{
+    int cy, cx;
+    game_state *ret;
+
+    if (!strcmp(move, "S")) {
+	int yy, xx;
+
+	ret = dup_game(from);
+        if (!ret->dead) {
+            /*
+             * If the player is still alive at the moment of pressing
+             * Solve, expose the entire grid as if it were a completed
+             * solution.
+             */
+            for (yy = 0; yy < ret->h; yy++)
+                for (xx = 0; xx < ret->w; xx++) {
+
+                    if (ret->layout->mines[yy*ret->w+xx]) {
+                        ret->grid[yy*ret->w+xx] = -1;
+                    } else {
+                        int dx, dy, v;
+
+                        v = 0;
+
+                        for (dx = -1; dx <= +1; dx++)
+                            for (dy = -1; dy <= +1; dy++)
+                                if (xx+dx >= 0 && xx+dx < ret->w &&
+                                    yy+dy >= 0 && yy+dy < ret->h &&
+                                    ret->layout->mines[(yy+dy)*ret->w+(xx+dx)])
+                                    v++;
+
+                        ret->grid[yy*ret->w+xx] = v;
+                    }
+                }
+        } else {
+            /*
+             * If the player pressed Solve _after dying_, show a full
+             * corrections grid in the style of standard Minesweeper.
+             * Players who don't like Mines's behaviour on death of
+             * only showing the mine that killed you (so that in case
+             * of a typo you can undo and carry on without the rest of
+             * the grid being spoiled) can use this to get the display
+             * that ordinary Minesweeper would have given them.
+             */
+            for (yy = 0; yy < ret->h; yy++)
+                for (xx = 0; xx < ret->w; xx++) {
+                    int pos = yy*ret->w+xx;
+                    if ((ret->grid[pos] == -2 || ret->grid[pos] == -3) &&
+                        ret->layout->mines[pos]) {
+                        ret->grid[pos] = 64;
+                    } else if (ret->grid[pos] == -1 &&
+                               !ret->layout->mines[pos]) {
+                        ret->grid[pos] = 66;
+                    }
+                }
+        }
+        ret->used_solve = TRUE;
+
+	return ret;
+    } else {
+	ret = dup_game(from);
+
+	while (*move) {
+	    if (move[0] == 'F' &&
+		sscanf(move+1, "%d,%d", &cx, &cy) == 2 &&
+		cx >= 0 && cx < from->w && cy >= 0 && cy < from->h) {
+		ret->grid[cy * from->w + cx] ^= (-2 ^ -1);
+	    } else if (move[0] == 'O' &&
+		       sscanf(move+1, "%d,%d", &cx, &cy) == 2 &&
+		       cx >= 0 && cx < from->w && cy >= 0 && cy < from->h) {
+		open_square(ret, cx, cy);
+	    } else if (move[0] == 'C' &&
+		       sscanf(move+1, "%d,%d", &cx, &cy) == 2 &&
+		       cx >= 0 && cx < from->w && cy >= 0 && cy < from->h) {
+		int dx, dy;
+
+		for (dy = -1; dy <= +1; dy++)
+		    for (dx = -1; dx <= +1; dx++)
+			if (cx+dx >= 0 && cx+dx < ret->w &&
+			    cy+dy >= 0 && cy+dy < ret->h &&
+			    (ret->grid[(cy+dy)*ret->w+(cx+dx)] == -2 ||
+			     ret->grid[(cy+dy)*ret->w+(cx+dx)] == -3))
+			    open_square(ret, cx+dx, cy+dy);
+	    } else {
+		free_game(ret);
+		return NULL;
+	    }
+
+	    while (*move && *move != ';') move++;
+	    if (*move) move++;
+	}
+
+	return ret;
+    }
+}
+
+/* ----------------------------------------------------------------------
+ * Drawing routines.
+ */
+
+static void game_compute_size(const game_params *params, int tilesize,
+                              int *x, int *y)
+{
+    /* Ick: fake up `ds->tilesize' for macro expansion purposes */
+    struct { int tilesize; } ads, *ds = &ads;
+    ads.tilesize = tilesize;
+
+    *x = BORDER * 2 + TILE_SIZE * params->w;
+    *y = BORDER * 2 + TILE_SIZE * params->h;
+}
+
+static void game_set_size(drawing *dr, game_drawstate *ds,
+                          const game_params *params, int tilesize)
+{
+    ds->tilesize = tilesize;
+}
+
+static float *game_colours(frontend *fe, int *ncolours)
+{
+    float *ret = snewn(3 * NCOLOURS, float);
+
+    frontend_default_colour(fe, &ret[COL_BACKGROUND * 3]);
+
+    ret[COL_BACKGROUND2 * 3 + 0] = ret[COL_BACKGROUND * 3 + 0] * 19.0F / 20.0F;
+    ret[COL_BACKGROUND2 * 3 + 1] = ret[COL_BACKGROUND * 3 + 1] * 19.0F / 20.0F;
+    ret[COL_BACKGROUND2 * 3 + 2] = ret[COL_BACKGROUND * 3 + 2] * 19.0F / 20.0F;
+
+    ret[COL_1 * 3 + 0] = 0.0F;
+    ret[COL_1 * 3 + 1] = 0.0F;
+    ret[COL_1 * 3 + 2] = 1.0F;
+
+    ret[COL_2 * 3 + 0] = 0.0F;
+    ret[COL_2 * 3 + 1] = 0.5F;
+    ret[COL_2 * 3 + 2] = 0.0F;
+
+    ret[COL_3 * 3 + 0] = 1.0F;
+    ret[COL_3 * 3 + 1] = 0.0F;
+    ret[COL_3 * 3 + 2] = 0.0F;
+
+    ret[COL_4 * 3 + 0] = 0.0F;
+    ret[COL_4 * 3 + 1] = 0.0F;
+    ret[COL_4 * 3 + 2] = 0.5F;
+
+    ret[COL_5 * 3 + 0] = 0.5F;
+    ret[COL_5 * 3 + 1] = 0.0F;
+    ret[COL_5 * 3 + 2] = 0.0F;
+
+    ret[COL_6 * 3 + 0] = 0.0F;
+    ret[COL_6 * 3 + 1] = 0.5F;
+    ret[COL_6 * 3 + 2] = 0.5F;
+
+    ret[COL_7 * 3 + 0] = 0.0F;
+    ret[COL_7 * 3 + 1] = 0.0F;
+    ret[COL_7 * 3 + 2] = 0.0F;
+
+    ret[COL_8 * 3 + 0] = 0.5F;
+    ret[COL_8 * 3 + 1] = 0.5F;
+    ret[COL_8 * 3 + 2] = 0.5F;
+
+    ret[COL_MINE * 3 + 0] = 0.0F;
+    ret[COL_MINE * 3 + 1] = 0.0F;
+    ret[COL_MINE * 3 + 2] = 0.0F;
+
+    ret[COL_BANG * 3 + 0] = 1.0F;
+    ret[COL_BANG * 3 + 1] = 0.0F;
+    ret[COL_BANG * 3 + 2] = 0.0F;
+
+    ret[COL_CROSS * 3 + 0] = 1.0F;
+    ret[COL_CROSS * 3 + 1] = 0.0F;
+    ret[COL_CROSS * 3 + 2] = 0.0F;
+
+    ret[COL_FLAG * 3 + 0] = 1.0F;
+    ret[COL_FLAG * 3 + 1] = 0.0F;
+    ret[COL_FLAG * 3 + 2] = 0.0F;
+
+    ret[COL_FLAGBASE * 3 + 0] = 0.0F;
+    ret[COL_FLAGBASE * 3 + 1] = 0.0F;
+    ret[COL_FLAGBASE * 3 + 2] = 0.0F;
+
+    ret[COL_QUERY * 3 + 0] = 0.0F;
+    ret[COL_QUERY * 3 + 1] = 0.0F;
+    ret[COL_QUERY * 3 + 2] = 0.0F;
+
+    ret[COL_HIGHLIGHT * 3 + 0] = 1.0F;
+    ret[COL_HIGHLIGHT * 3 + 1] = 1.0F;
+    ret[COL_HIGHLIGHT * 3 + 2] = 1.0F;
+
+    ret[COL_LOWLIGHT * 3 + 0] = ret[COL_BACKGROUND * 3 + 0] * 2.0F / 3.0F;
+    ret[COL_LOWLIGHT * 3 + 1] = ret[COL_BACKGROUND * 3 + 1] * 2.0F / 3.0F;
+    ret[COL_LOWLIGHT * 3 + 2] = ret[COL_BACKGROUND * 3 + 2] * 2.0F / 3.0F;
+
+    ret[COL_WRONGNUMBER * 3 + 0] = 1.0F;
+    ret[COL_WRONGNUMBER * 3 + 1] = 0.6F;
+    ret[COL_WRONGNUMBER * 3 + 2] = 0.6F;
+
+    /* Red tinge to a light colour, for the cursor. */
+    ret[COL_CURSOR * 3 + 0] = ret[COL_HIGHLIGHT * 3 + 0];
+    ret[COL_CURSOR * 3 + 1] = ret[COL_HIGHLIGHT * 3 + 0] / 2.0F;
+    ret[COL_CURSOR * 3 + 2] = ret[COL_HIGHLIGHT * 3 + 0] / 2.0F;
+
+    *ncolours = NCOLOURS;
+    return ret;
+}
+
+static game_drawstate *game_new_drawstate(drawing *dr, const game_state *state)
+{
+    struct game_drawstate *ds = snew(struct game_drawstate);
+
+    ds->w = state->w;
+    ds->h = state->h;
+    ds->started = FALSE;
+    ds->tilesize = 0;                  /* not decided yet */
+    ds->grid = snewn(ds->w * ds->h, signed char);
+    ds->bg = -1;
+    ds->cur_x = ds->cur_y = -1;
+
+    memset(ds->grid, -99, ds->w * ds->h);
+
+    return ds;
+}
+
+static void game_free_drawstate(drawing *dr, game_drawstate *ds)
+{
+    sfree(ds->grid);
+    sfree(ds);
+}
+
+static void draw_tile(drawing *dr, game_drawstate *ds,
+                      int x, int y, int v, int bg)
+{
+    if (v < 0) {
+        int coords[12];
+	int hl = 0;
+
+	if (v == -22 || v == -23) {
+	    v += 20;
+
+	    /*
+	     * Omit the highlights in this case.
+	     */
+	    draw_rect(dr, x, y, TILE_SIZE, TILE_SIZE,
+                      bg == COL_BACKGROUND ? COL_BACKGROUND2 : bg);
+	    draw_line(dr, x, y, x + TILE_SIZE - 1, y, COL_LOWLIGHT);
+	    draw_line(dr, x, y, x, y + TILE_SIZE - 1, COL_LOWLIGHT);
+	} else {
+	    /*
+	     * Draw highlights to indicate the square is covered.
+	     */
+	    coords[0] = x + TILE_SIZE - 1;
+	    coords[1] = y + TILE_SIZE - 1;
+	    coords[2] = x + TILE_SIZE - 1;
+	    coords[3] = y;
+	    coords[4] = x;
+	    coords[5] = y + TILE_SIZE - 1;
+	    draw_polygon(dr, coords, 3, COL_LOWLIGHT ^ hl, COL_LOWLIGHT ^ hl);
+
+	    coords[0] = x;
+	    coords[1] = y;
+	    draw_polygon(dr, coords, 3, COL_HIGHLIGHT ^ hl,
+			 COL_HIGHLIGHT ^ hl);
+
+	    draw_rect(dr, x + HIGHLIGHT_WIDTH, y + HIGHLIGHT_WIDTH,
+		      TILE_SIZE - 2*HIGHLIGHT_WIDTH, TILE_SIZE - 2*HIGHLIGHT_WIDTH,
+		      bg);
+	}
+
+	if (v == -1) {
+	    /*
+	     * Draw a flag.
+	     */
+#define SETCOORD(n, dx, dy) do { \
+    coords[(n)*2+0] = x + (int)(TILE_SIZE * (dx)); \
+    coords[(n)*2+1] = y + (int)(TILE_SIZE * (dy)); \
+} while (0)
+	    SETCOORD(0, 0.6F,  0.35F);
+	    SETCOORD(1, 0.6F,  0.7F);
+	    SETCOORD(2, 0.8F,  0.8F);
+	    SETCOORD(3, 0.25F, 0.8F);
+	    SETCOORD(4, 0.55F, 0.7F);
+	    SETCOORD(5, 0.55F, 0.35F);
+	    draw_polygon(dr, coords, 6, COL_FLAGBASE, COL_FLAGBASE);
+
+	    SETCOORD(0, 0.6F, 0.2F);
+	    SETCOORD(1, 0.6F, 0.5F);
+	    SETCOORD(2, 0.2F, 0.35F);
+	    draw_polygon(dr, coords, 3, COL_FLAG, COL_FLAG);
+#undef SETCOORD
+
+	} else if (v == -3) {
+	    /*
+	     * Draw a question mark.
+	     */
+	    draw_text(dr, x + TILE_SIZE / 2, y + TILE_SIZE / 2,
+		      FONT_VARIABLE, TILE_SIZE * 6 / 8,
+		      ALIGN_VCENTRE | ALIGN_HCENTRE,
+		      COL_QUERY, "?");
+	}
+    } else {
+	/*
+	 * Clear the square to the background colour, and draw thin
+	 * grid lines along the top and left.
+	 * 
+	 * Exception is that for value 65 (mine we've just trodden
+	 * on), we clear the square to COL_BANG.
+	 */
+        if (v & 32) {
+            bg = COL_WRONGNUMBER;
+            v &= ~32;
+        }
+        draw_rect(dr, x, y, TILE_SIZE, TILE_SIZE,
+		  (v == 65 ? COL_BANG :
+                   bg == COL_BACKGROUND ? COL_BACKGROUND2 : bg));
+	draw_line(dr, x, y, x + TILE_SIZE - 1, y, COL_LOWLIGHT);
+	draw_line(dr, x, y, x, y + TILE_SIZE - 1, COL_LOWLIGHT);
+
+	if (v > 0 && v <= 8) {
+	    /*
+	     * Mark a number.
+	     */
+	    char str[2];
+	    str[0] = v + '0';
+	    str[1] = '\0';
+	    draw_text(dr, x + TILE_SIZE / 2, y + TILE_SIZE / 2,
+		      FONT_VARIABLE, TILE_SIZE * 7 / 8,
+		      ALIGN_VCENTRE | ALIGN_HCENTRE,
+		      (COL_1 - 1) + v, str);
+
+	} else if (v >= 64) {
+	    /*
+	     * Mark a mine.
+	     */
+	    {
+		int cx = x + TILE_SIZE / 2;
+		int cy = y + TILE_SIZE / 2;
+		int r = TILE_SIZE / 2 - 3;
+
+		draw_circle(dr, cx, cy, 5*r/6, COL_MINE, COL_MINE);
+		draw_rect(dr, cx - r/6, cy - r, 2*(r/6)+1, 2*r+1, COL_MINE);
+		draw_rect(dr, cx - r, cy - r/6, 2*r+1, 2*(r/6)+1, COL_MINE);
+		draw_rect(dr, cx-r/3, cy-r/3, r/3, r/4, COL_HIGHLIGHT);
+	    }
+
+	    if (v == 66) {
+		/*
+		 * Cross through the mine.
+		 */
+		int dx;
+		for (dx = -1; dx <= +1; dx++) {
+		    draw_line(dr, x + 3 + dx, y + 2,
+			      x + TILE_SIZE - 3 + dx,
+			      y + TILE_SIZE - 2, COL_CROSS);
+		    draw_line(dr, x + TILE_SIZE - 3 + dx, y + 2,
+			      x + 3 + dx, y + TILE_SIZE - 2,
+			      COL_CROSS);
+		}
+	    }
+	}
+    }
+
+    draw_update(dr, x, y, TILE_SIZE, TILE_SIZE);
+}
+
+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 x, y;
+    int mines, markers, bg;
+    int cx = -1, cy = -1, cmoved;
+
+    if (flashtime) {
+	int frame = (int)(flashtime / FLASH_FRAME);
+	if (frame % 2)
+	    bg = (ui->flash_is_death ? COL_BACKGROUND : COL_LOWLIGHT);
+	else
+	    bg = (ui->flash_is_death ? COL_BANG : COL_HIGHLIGHT);
+    } else
+	bg = COL_BACKGROUND;
+
+    if (!ds->started) {
+        int coords[10];
+
+	draw_rect(dr, 0, 0,
+		  TILE_SIZE * state->w + 2 * BORDER,
+		  TILE_SIZE * state->h + 2 * BORDER, COL_BACKGROUND);
+	draw_update(dr, 0, 0,
+		    TILE_SIZE * state->w + 2 * BORDER,
+		    TILE_SIZE * state->h + 2 * BORDER);
+
+        /*
+         * Recessed area containing the whole puzzle.
+         */
+        coords[0] = COORD(state->w) + OUTER_HIGHLIGHT_WIDTH - 1;
+        coords[1] = COORD(state->h) + OUTER_HIGHLIGHT_WIDTH - 1;
+        coords[2] = COORD(state->w) + OUTER_HIGHLIGHT_WIDTH - 1;
+        coords[3] = COORD(0) - OUTER_HIGHLIGHT_WIDTH;
+        coords[4] = coords[2] - TILE_SIZE;
+        coords[5] = coords[3] + TILE_SIZE;
+        coords[8] = COORD(0) - OUTER_HIGHLIGHT_WIDTH;
+        coords[9] = COORD(state->h) + OUTER_HIGHLIGHT_WIDTH - 1;
+        coords[6] = coords[8] + TILE_SIZE;
+        coords[7] = coords[9] - TILE_SIZE;
+        draw_polygon(dr, coords, 5, COL_HIGHLIGHT, COL_HIGHLIGHT);
+
+        coords[1] = COORD(0) - OUTER_HIGHLIGHT_WIDTH;
+        coords[0] = COORD(0) - OUTER_HIGHLIGHT_WIDTH;
+        draw_polygon(dr, coords, 5, COL_LOWLIGHT, COL_LOWLIGHT);
+
+        ds->started = TRUE;
+    }
+
+    if (ui->cur_visible) cx = ui->cur_x;
+    if (ui->cur_visible) cy = ui->cur_y;
+    cmoved = (cx != ds->cur_x || cy != ds->cur_y);
+
+    /*
+     * Now draw the tiles. Also in this loop, count up the number
+     * of mines and mine markers.
+     */
+    mines = markers = 0;
+    for (y = 0; y < ds->h; y++)
+	for (x = 0; x < ds->w; x++) {
+	    int v = state->grid[y*ds->w+x], cc = 0;
+
+	    if (v == -1)
+		markers++;
+	    if (state->layout->mines && state->layout->mines[y*ds->w+x])
+		mines++;
+
+            if (v >= 0 && v <= 8) {
+                /*
+                 * Count up the flags around this tile, and if
+                 * there are too _many_, highlight the tile.
+                 */
+                int dx, dy, flags = 0;
+
+                for (dy = -1; dy <= +1; dy++)
+                    for (dx = -1; dx <= +1; dx++) {
+                        int nx = x+dx, ny = y+dy;
+                        if (nx >= 0 && nx < ds->w &&
+                            ny >= 0 && ny < ds->h &&
+                            state->grid[ny*ds->w+nx] == -1)
+                            flags++;
+                    }
+
+                if (flags > v)
+                    v |= 32;
+            }
+
+	    if ((v == -2 || v == -3) &&
+		(abs(x-ui->hx) <= ui->hradius && abs(y-ui->hy) <= ui->hradius))
+		v -= 20;
+
+            if (cmoved && /* if cursor has moved, force redraw of curr and prev pos */
+                ((x == cx && y == cy) || (x == ds->cur_x && y == ds->cur_y)))
+              cc = 1;
+
+	    if (ds->grid[y*ds->w+x] != v || bg != ds->bg || cc) {
+		draw_tile(dr, ds, COORD(x), COORD(y), v,
+                          (x == cx && y == cy) ? COL_CURSOR : bg);
+		ds->grid[y*ds->w+x] = v;
+	    }
+	}
+    ds->bg = bg;
+    ds->cur_x = cx; ds->cur_y = cy;
+
+    if (!state->layout->mines)
+	mines = state->layout->n;
+
+    /*
+     * Update the status bar.
+     */
+    {
+	char statusbar[512];
+	if (state->dead) {
+	    sprintf(statusbar, "DEAD!");
+	} else if (state->won) {
+            if (state->used_solve)
+                sprintf(statusbar, "Auto-solved.");
+            else
+                sprintf(statusbar, "COMPLETED!");
+	} else {
+	    sprintf(statusbar, "Marked: %d / %d", markers, mines);
+	}
+        if (ui->deaths)
+            sprintf(statusbar + strlen(statusbar),
+                    "  Deaths: %d", ui->deaths);
+	status_bar(dr, statusbar);
+    }
+}
+
+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->used_solve || newstate->used_solve)
+        return 0.0F;
+
+    if (dir > 0 && !oldstate->dead && !oldstate->won) {
+	if (newstate->dead) {
+	    ui->flash_is_death = TRUE;
+	    return 3 * FLASH_FRAME;
+	}
+	if (newstate->won) {
+	    ui->flash_is_death = FALSE;
+	    return 2 * FLASH_FRAME;
+	}
+    }
+    return 0.0F;
+}
+
+static int game_status(const game_state *state)
+{
+    /*
+     * We report the game as lost only if the player has used the
+     * Solve function to reveal all the mines. Otherwise, we assume
+     * they'll undo and continue play.
+     */
+    return state->won ? (state->used_solve ? -1 : +1) : 0;
+}
+
+static int game_timing_state(const game_state *state, game_ui *ui)
+{
+    if (state->dead || state->won || ui->completed || !state->layout->mines)
+	return FALSE;
+    return TRUE;
+}
+
+static void game_print_size(const game_params *params, float *x, float *y)
+{
+}
+
+static void game_print(drawing *dr, const game_state *state, int tilesize)
+{
+}
+
+#ifdef COMBINED
+#define thegame mines
+#endif
+
+const struct game thegame = {
+    "Mines", "games.mines", "mines",
+    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,
+    TRUE, solve_game,
+    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,
+    FALSE, FALSE, game_print_size, game_print,
+    TRUE,			       /* wants_statusbar */
+    TRUE, game_timing_state,
+    BUTTON_BEATS(LEFT_BUTTON, RIGHT_BUTTON) | REQUIRE_RBUTTON,
+};
+
+#ifdef STANDALONE_OBFUSCATOR
+
+/*
+ * Vaguely useful stand-alone program which translates between
+ * obfuscated and clear Mines game descriptions. Pass in a game
+ * description on the command line, and if it's clear it will be
+ * obfuscated and vice versa. The output text should also be a
+ * valid game ID describing the same game. Like this:
+ *
+ * $ ./mineobfusc 9x9:4,4,mb071b49fbd1cb6a0d5868
+ * 9x9:4,4,004000007c00010022080
+ * $ ./mineobfusc 9x9:4,4,004000007c00010022080
+ * 9x9:4,4,mb071b49fbd1cb6a0d5868
+ */
+
+int main(int argc, char **argv)
+{
+    game_params *p;
+    game_state *s;
+    char *id = NULL, *desc, *err;
+    int y, x;
+
+    while (--argc > 0) {
+        char *p = *++argv;
+	if (*p == '-') {
+            fprintf(stderr, "%s: unrecognised option `%s'\n", argv[0], p);
+            return 1;
+        } else {
+            id = p;
+        }
+    }
+
+    if (!id) {
+        fprintf(stderr, "usage: %s <game_id>\n", argv[0]);
+        return 1;
+    }
+
+    desc = strchr(id, ':');
+    if (!desc) {
+        fprintf(stderr, "%s: game id expects a colon in it\n", argv[0]);
+        return 1;
+    }
+    *desc++ = '\0';
+
+    p = default_params();
+    decode_params(p, id);
+    err = validate_desc(p, desc);
+    if (err) {
+        fprintf(stderr, "%s: %s\n", argv[0], err);
+        return 1;
+    }
+    s = new_game(NULL, p, desc);
+
+    x = atoi(desc);
+    while (*desc && *desc != ',') desc++;
+    if (*desc) desc++;
+    y = atoi(desc);
+    while (*desc && *desc != ',') desc++;
+    if (*desc) desc++;
+
+    printf("%s:%s\n", id, describe_layout(s->layout->mines,
+                                          p->w * p->h,
+                                          x, y,
+                                          (*desc != 'm')));
+
+    return 0;
+}
+
+#endif
+
+/* vim: set shiftwidth=4 tabstop=8: */