ref: 6b9e690c89973e8e98de7dfc768849f0b8b411a0
parent: 0f423f0b3a0bfaaac37fa2dba23794629088836f
author: Simon Tatham <anakin@pobox.com>
date: Mon May 30 06:08:27 EDT 2005
Initial checkin of my Minesweeper clone, which uses a solver during grid generation to arrange a mine layout that never requires guessing. [originally from svn r5859]
--- a/Recipe
+++ b/Recipe
@@ -17,8 +17,10 @@
COMMON = midend misc malloc random version
NET = net tree234
NETSLIDE = netslide tree234
+MINES = mines tree234
ALL = list NET NETSLIDE cube fifteen sixteen rect pattern solo twiddle
+ + MINES
net : [X] gtk COMMON NET
netslide : [X] gtk COMMON NETSLIDE
@@ -29,6 +31,7 @@
pattern : [X] gtk COMMON pattern
solo : [X] gtk COMMON solo
twiddle : [X] gtk COMMON twiddle
+mines : [X] gtk COMMON MINES
# The Windows Net shouldn't be called `net.exe' since Windows
# already has a reasonably important utility program by that name!
@@ -41,6 +44,7 @@
pattern : [G] WINDOWS COMMON pattern
solo : [G] WINDOWS COMMON solo
twiddle : [G] WINDOWS COMMON twiddle
+mines : [G] WINDOWS COMMON MINES
# Mac OS X unified application containing all the puzzles.
Puzzles : [MX] osx osx.icns osx-info.plist COMMON ALL
--- a/list.c
+++ b/list.c
@@ -19,6 +19,7 @@
extern const game cube;
extern const game fifteen;
+extern const game mines;
extern const game net;
extern const game netslide;
extern const game pattern;
@@ -30,6 +31,7 @@
const game *gamelist[] = {&cube,
&fifteen,
+ &mines,
&net,
&netslide,
&pattern,
--- /dev/null
+++ b/mines.c
@@ -1,0 +1,2648 @@
+/*
+ * mines.c: Minesweeper clone with sophisticated grid generation.
+ *
+ * Still TODO:
+ *
+ * - possibly disable undo? Or alternatively mark game states as
+ * `cheated', although that's horrid.
+ * + OK. Rather than _disabling_ undo, we have a hook callable
+ * in the game backend which is called before we do an undo.
+ * That hook can talk to the game_ui and set the cheated flag,
+ * and then make_move can avoid setting the `won' flag after that.
+ *
+ * - delay game description generation until first click
+ * + do we actually _need_ to do this? Hmm.
+ * + it's a perfectly good puzzle game without
+ * + but it might be useful when we start timing, since it
+ * ensures the user is really paying attention.
+ *
+ * - timer
+ *
+ * - question marks (arrgh, preferences?)
+ *
+ * - sensible parameter constraints
+ * + 30x16: 191 mines just about works if rather slowly, 192 is
+ * just about doom (the latter corresponding to a density of
+ * exactly 1 in 2.5)
+ * + 9x9: 45 mines works - over 1 in 2! 50 seems a bit slow.
+ * + it might not be feasible to work out the exact limit
+ */
+
+#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_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,
+ NCOLOURS
+};
+
+#define TILE_SIZE 20
+#define BORDER (TILE_SIZE * 3 / 2)
+#define HIGHLIGHT_WIDTH 2
+#define OUTER_HIGHLIGHT_WIDTH 3
+#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 game_state {+ int w, h, n, dead, won;
+ char *mines; /* real mine positions */
+ 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 int game_fetch_preset(int i, char **name, game_params **params)
+{+ game_params *ret;
+ char str[80];
+ static const struct { int w, h, n; } values[] = {+ {9, 9, 10},+ {16, 16, 40},+ {30, 16, 99},+ };
+
+ if (i < 0 || i >= lenof(values))
+ return FALSE;
+
+ ret = snew(game_params);
+ ret->w = values[i].w;
+ ret->h = values[i].h;
+ ret->n = values[i].n;
+ ret->unique = TRUE;
+
+ 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(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(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(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(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);
+ ret->unique = cfg[3].ival;
+
+ return ret;
+}
+
+static char *validate_params(game_params *params)
+{+ if (params->w <= 0 && params->h <= 0)
+ return "Width and height must both be greater than zero";
+ if (params->w <= 0)
+ return "Width must be greater than zero";
+ if (params->h <= 0)
+ return "Height must be greater than zero";
+
+ /*
+ * 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 word)
+{+ 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 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;
+}
+
+static void known_squares(int w, int h, struct squaretodo *std, char *grid,
+ int (*open)(void *ctx, int x, int y), 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.
+ */
+static int minesolve(int w, int h, int n, char *grid,
+ int (*open)(void *ctx, int x, int y),
+ struct perturbations *(*perturb)(void *ctx, char *grid,
+ int x, int y, int mask),
+ 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)
+ break;
+ 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.
+ */
+ 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
+
+ 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", 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
+
+ /*
+ * 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;
+ 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;
+}
+
+static struct perturbations *mineperturb(void *vctx, 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[9], *toempty[9], **todo;
+ int ntofill, ntoempty, ntodo, dtodo, dset;
+ struct perturbations *ret;
+
+ /*
+ * 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 (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;
+ 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++;
+ }
+
+ /*
+ * 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;
+ 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 this didn't work at all, I think we just give up.
+ */
+ if (ntofill != nfull && ntoempty != nempty) {+ sfree(sqlist);
+ return 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;
+ } else {+ todo = toempty;
+ ntodo = ntoempty;
+ dtodo = -1;
+ dset = +1;
+ }
+ 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 */
+ 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++;
+ }
+ }
+ assert(i == ret->n);
+
+ sfree(sqlist);
+
+ /*
+ * 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;
+
+ do {+ success = FALSE;
+
+ 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) {+ char *solvegrid = snewn(w*h, 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;
+
+ 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;
+}
+
+/*
+ * The Mines game descriptions contain the location of every mine,
+ * and can therefore be used to cheat.
+ *
+ * It would be pointless to attempt to _prevent_ this form of
+ * cheating by encrypting the description, since Mines is
+ * open-source so anyone can find out the encryption key. However,
+ * I think it is worth doing a bit of gentle obfuscation to prevent
+ * _accidental_ spoilers: if you happened to note that the game ID
+ * starts with an F, for example, you might be unable to put the
+ * knowledge of those mines out of your mind while playing. So,
+ * just as discussions of film endings are rot13ed to avoid
+ * spoiling it for people who don't want to be told, we apply a
+ * keyless, reversible, but visually completely obfuscatory masking
+ * function to the mine bitmap.
+ */
+static void obfuscate_bitmap(unsigned char *bmp, int bits, int decode)
+{+ int bytes, firsthalf, secondhalf;
+ struct step {+ unsigned char *seedstart;
+ int seedlen;
+ unsigned char *targetstart;
+ int targetlen;
+ } steps[2];
+ int i, j;
+
+ /*
+ * My obfuscation algorithm is similar in concept to the OAEP
+ * encoding used in some forms of RSA. Here's a specification
+ * of it:
+ *
+ * + We have a `masking function' which constructs a stream of
+ * pseudorandom bytes from a seed of some number of input
+ * bytes.
+ *
+ * + We pad out our input bit stream to a whole number of
+ * bytes by adding up to 7 zero bits on the end. (In fact
+ * the bitmap passed as input to this function will already
+ * have had this done in practice.)
+ *
+ * + We divide the _byte_ stream exactly in half, rounding the
+ * half-way position _down_. So an 81-bit input string, for
+ * example, rounds up to 88 bits or 11 bytes, and then
+ * dividing by two gives 5 bytes in the first half and 6 in
+ * the second half.
+ *
+ * + We generate a mask from the second half of the bytes, and
+ * XOR it over the first half.
+ *
+ * + We generate a mask from the (encoded) first half of the
+ * bytes, and XOR it over the second half. Any null bits at
+ * the end which were added as padding are cleared back to
+ * zero even if this operation would have made them nonzero.
+ *
+ * To de-obfuscate, the steps are precisely the same except
+ * that the final two are reversed.
+ *
+ * Finally, our masking function. Given an input seed string of
+ * bytes, the output mask consists of concatenating the SHA-1
+ * hashes of the seed string and successive decimal integers,
+ * starting from 0.
+ */
+
+ bytes = (bits + 7) / 8;
+ firsthalf = bytes / 2;
+ secondhalf = bytes - firsthalf;
+
+ steps[decode ? 1 : 0].seedstart = bmp + firsthalf;
+ steps[decode ? 1 : 0].seedlen = secondhalf;
+ steps[decode ? 1 : 0].targetstart = bmp;
+ steps[decode ? 1 : 0].targetlen = firsthalf;
+
+ steps[decode ? 0 : 1].seedstart = bmp;
+ steps[decode ? 0 : 1].seedlen = firsthalf;
+ steps[decode ? 0 : 1].targetstart = bmp + firsthalf;
+ steps[decode ? 0 : 1].targetlen = secondhalf;
+
+ for (i = 0; i < 2; i++) {+ SHA_State base, final;
+ unsigned char digest[20];
+ char numberbuf[80];
+ int digestpos = 20, counter = 0;
+
+ SHA_Init(&base);
+ SHA_Bytes(&base, steps[i].seedstart, steps[i].seedlen);
+
+ for (j = 0; j < steps[i].targetlen; j++) {+ if (digestpos >= 20) {+ sprintf(numberbuf, "%d", counter++);
+ final = base;
+ SHA_Bytes(&final, numberbuf, strlen(numberbuf));
+ SHA_Final(&final, digest);
+ digestpos = 0;
+ }
+ steps[i].targetstart[j] ^= digest[digestpos]++;
+ }
+
+ /*
+ * Mask off the pad bits in the final byte after both steps.
+ */
+ if (bits % 8)
+ bmp[bits / 8] &= 0xFF & (0xFF00 >> (bits % 8));
+ }
+}
+
+static char *new_game_desc(game_params *params, random_state *rs,
+ game_aux_info **aux)
+{+ char *grid, *ret, *p;
+ unsigned char *bmp;
+ int x, y, i, area;
+
+ /*
+ * FIXME: allow user to specify initial open square.
+ */
+ x = random_upto(rs, params->w);
+ y = random_upto(rs, params->h);
+
+ grid = minegen(params->w, params->h, params->n, x, y, params->unique, rs);
+
+ /*
+ * Set up the mine bitmap and obfuscate it.
+ */
+ area = params->w * params->h;
+ 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);
+ }
+ 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,m", x, y); /* '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 void game_free_aux_info(game_aux_info *aux)
+{+ assert(!"Shouldn't happen");
+}
+
+static char *validate_desc(game_params *params, char *desc)
+{+ int wh = params->w * params->h;
+ int x, y;
+
+ if (!*desc || !isdigit((unsigned char)*desc))
+ return "No initial x-coordinate in game description";
+ 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', meaning `masked', if present */
+ if (*desc == 'm')
+ 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->mines[y*w+x]) {+ /*
+ * The player has landed on a mine. Bad luck. Expose all
+ * the mines.
+ */
+ state->dead = TRUE;
+ for (yy = 0; yy < h; yy++)
+ for (xx = 0; xx < w; xx++) {+ if (state->mines[yy*w+xx] &&
+ (state->grid[yy*w+xx] == -2 ||
+ state->grid[yy*w+xx] == -3)) {+ state->grid[yy*w+xx] = 64;
+ }
+ if (!state->mines[yy*w+xx] &&
+ state->grid[yy*w+xx] == -1) {+ state->grid[yy*w+xx] = 66;
+ }
+ }
+ 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->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->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->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(game_params *params, char *desc)
+{+ game_state *state = snew(game_state);
+ int i, wh, x, y, ret, masked;
+ unsigned char *bmp;
+
+ state->w = params->w;
+ state->h = params->h;
+ state->n = params->n;
+ state->dead = state->won = FALSE;
+
+ wh = state->w * state->h;
+ state->mines = snewn(wh, char);
+
+ 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 */
+
+ if (*desc == 'm') {+ masked = TRUE;
+ desc++;
+ } else {+ /*
+ * 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->mines, 0, wh);
+ for (i = 0; i < wh; i++) {+ if (bmp[i / 8] & (0x80 >> (i % 8)))
+ state->mines[i] = 1;
+ }
+
+ state->grid = snewn(wh, char);
+ memset(state->grid, -2, wh);
+
+ ret = open_square(state, x, y);
+ /*
+ * FIXME: This shouldn't be an assert. Perhaps we actually
+ * ought to check it in validate_params! Alternatively, we can
+ * remove the assert completely and actually permit a game
+ * description to start you off dead.
+ */
+ assert(ret != -1);
+
+ return state;
+}
+
+static game_state *dup_game(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->mines = snewn(ret->w * ret->h, char);
+ memcpy(ret->mines, state->mines, ret->w * ret->h);
+ ret->grid = snewn(ret->w * ret->h, char);
+ memcpy(ret->grid, state->grid, ret->w * ret->h);
+
+ return ret;
+}
+
+static void free_game(game_state *state)
+{+ sfree(state->mines);
+ sfree(state->grid);
+ sfree(state);
+}
+
+static game_state *solve_game(game_state *state, game_aux_info *aux,
+ char **error)
+{+ return NULL;
+}
+
+static char *game_text_format(game_state *state)
+{+ return NULL;
+}
+
+struct game_ui {+ int hx, hy, hradius; /* for mouse-down highlights */
+ int flash_is_death;
+};
+
+static game_ui *new_ui(game_state *state)
+{+ game_ui *ui = snew(game_ui);
+ ui->hx = ui->hy = -1;
+ ui->hradius = 0;
+ ui->flash_is_death = FALSE; /* *shrug* */
+ return ui;
+}
+
+static void free_ui(game_ui *ui)
+{+ sfree(ui);
+}
+
+static game_state *make_move(game_state *from, game_ui *ui, int x, int y,
+ int button)
+{+ game_state *ret;
+ int cx, cy;
+
+ if (from->dead || from->won)
+ return NULL; /* no further moves permitted */
+
+ if (!IS_MOUSE_DOWN(button) && !IS_MOUSE_DRAG(button) &&
+ !IS_MOUSE_RELEASE(button))
+ return NULL;
+
+ cx = FROMCOORD(x);
+ cy = FROMCOORD(y);
+ if (cx < 0 || cx >= from->w || cy < 0 || cy > from->h)
+ return NULL;
+
+ if (button == LEFT_BUTTON || button == LEFT_DRAG) {+ /*
+ * 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);
+ return from;
+ }
+
+ if (button == RIGHT_BUTTON) {+ /*
+ * 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;
+
+ ret = dup_game(from);
+ ret->grid[cy * from->w + cx] ^= (-2 ^ -1);
+
+ return ret;
+ }
+
+ if (button == LEFT_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 `from'.
+ */
+
+ /*
+ * 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 (from->grid[cy * from->w + cx] == -2 ||
+ from->grid[cy * from->w + cx] == -3) {+ ret = dup_game(from);
+ open_square(ret, cx, cy);
+ return ret;
+ }
+
+ /*
+ * Left-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) {+ 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]) {+ ret = dup_game(from);
+ 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);
+ return ret;
+ }
+ }
+
+ return from;
+ }
+
+ return NULL;
+}
+
+/* ----------------------------------------------------------------------
+ * Drawing routines.
+ */
+
+struct game_drawstate {+ int w, h, started;
+ 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.
+ */
+};
+
+static void game_size(game_params *params, int *x, int *y)
+{+ *x = BORDER * 2 + TILE_SIZE * params->w;
+ *y = BORDER * 2 + TILE_SIZE * params->h;
+}
+
+static float *game_colours(frontend *fe, game_state *state, int *ncolours)
+{+ float *ret = snewn(3 * NCOLOURS, float);
+
+ frontend_default_colour(fe, &ret[COL_BACKGROUND * 3]);
+
+ 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.0 / 3.0;
+ ret[COL_LOWLIGHT * 3 + 1] = ret[COL_BACKGROUND * 3 + 1] * 2.0 / 3.0;
+ ret[COL_LOWLIGHT * 3 + 2] = ret[COL_BACKGROUND * 3 + 2] * 2.0 / 3.0;
+
+ *ncolours = NCOLOURS;
+ return ret;
+}
+
+static game_drawstate *game_new_drawstate(game_state *state)
+{+ struct game_drawstate *ds = snew(struct game_drawstate);
+
+ ds->w = state->w;
+ ds->h = state->h;
+ ds->started = FALSE;
+ ds->grid = snewn(ds->w * ds->h, char);
+
+ memset(ds->grid, -99, ds->w * ds->h);
+
+ return ds;
+}
+
+static void game_free_drawstate(game_drawstate *ds)
+{+ sfree(ds->grid);
+ sfree(ds);
+}
+
+static void draw_tile(frontend *fe, 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(fe, x, y, TILE_SIZE, TILE_SIZE, bg);
+ draw_line(fe, x, y, x + TILE_SIZE - 1, y, COL_LOWLIGHT);
+ draw_line(fe, 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(fe, coords, 3, TRUE, COL_LOWLIGHT ^ hl);
+ draw_polygon(fe, coords, 3, FALSE, COL_LOWLIGHT ^ hl);
+
+ coords[0] = x;
+ coords[1] = y;
+ draw_polygon(fe, coords, 3, TRUE, COL_HIGHLIGHT ^ hl);
+ draw_polygon(fe, coords, 3, FALSE, COL_HIGHLIGHT ^ hl);
+
+ draw_rect(fe, 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 + TILE_SIZE * (dx); \
+ coords[(n)*2+1] = y + TILE_SIZE * (dy); \
+} while (0)
+ SETCOORD(0, 0.6, 0.35);
+ SETCOORD(1, 0.6, 0.7);
+ SETCOORD(2, 0.8, 0.8);
+ SETCOORD(3, 0.25, 0.8);
+ SETCOORD(4, 0.55, 0.7);
+ SETCOORD(5, 0.55, 0.35);
+ draw_polygon(fe, coords, 6, TRUE, COL_FLAGBASE);
+ draw_polygon(fe, coords, 6, FALSE, COL_FLAGBASE);
+
+ SETCOORD(0, 0.6, 0.2);
+ SETCOORD(1, 0.6, 0.5);
+ SETCOORD(2, 0.2, 0.35);
+ draw_polygon(fe, coords, 3, TRUE, COL_FLAG);
+ draw_polygon(fe, coords, 3, FALSE, COL_FLAG);
+#undef SETCOORD
+
+ } else if (v == -3) {+ /*
+ * Draw a question mark.
+ */
+ draw_text(fe, 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.
+ */
+ draw_rect(fe, x, y, TILE_SIZE, TILE_SIZE,
+ (v == 65 ? COL_BANG : bg));
+ draw_line(fe, x, y, x + TILE_SIZE - 1, y, COL_LOWLIGHT);
+ draw_line(fe, 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(fe, 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.
+ *
+ * FIXME: this could be done better!
+ */
+#if 0
+ draw_text(fe, x + TILE_SIZE / 2, y + TILE_SIZE / 2,
+ FONT_VARIABLE, TILE_SIZE * 7 / 8,
+ ALIGN_VCENTRE | ALIGN_HCENTRE,
+ COL_MINE, "*");
+#else
+ {+ int cx = x + TILE_SIZE / 2;
+ int cy = y + TILE_SIZE / 2;
+ int r = TILE_SIZE / 2 - 3;
+ int coords[4*5*2];
+ int xdx = 1, xdy = 0, ydx = 0, ydy = 1;
+ int tdx, tdy, i;
+
+ for (i = 0; i < 4*5*2; i += 5*2) {+ coords[i+2*0+0] = cx - r/6*xdx + r*4/5*ydx;
+ coords[i+2*0+1] = cy - r/6*xdy + r*4/5*ydy;
+ coords[i+2*1+0] = cx - r/6*xdx + r*ydx;
+ coords[i+2*1+1] = cy - r/6*xdy + r*ydy;
+ coords[i+2*2+0] = cx + r/6*xdx + r*ydx;
+ coords[i+2*2+1] = cy + r/6*xdy + r*ydy;
+ coords[i+2*3+0] = cx + r/6*xdx + r*4/5*ydx;
+ coords[i+2*3+1] = cy + r/6*xdy + r*4/5*ydy;
+ coords[i+2*4+0] = cx + r*3/5*xdx + r*3/5*ydx;
+ coords[i+2*4+1] = cy + r*3/5*xdy + r*3/5*ydy;
+
+ tdx = ydx;
+ tdy = ydy;
+ ydx = xdx;
+ ydy = xdy;
+ xdx = -tdx;
+ xdy = -tdy;
+ }
+
+ draw_polygon(fe, coords, 5*4, TRUE, COL_MINE);
+ draw_polygon(fe, coords, 5*4, FALSE, COL_MINE);
+
+ draw_rect(fe, cx-r/3, cy-r/3, r/3, r/4, COL_HIGHLIGHT);
+ }
+#endif
+
+ if (v == 66) {+ /*
+ * Cross through the mine.
+ */
+ int dx;
+ for (dx = -1; dx <= +1; dx++) {+ draw_line(fe, x + 3 + dx, y + 2,
+ x + TILE_SIZE - 3 + dx,
+ y + TILE_SIZE - 2, COL_CROSS);
+ draw_line(fe, x + TILE_SIZE - 3 + dx, y + 2,
+ x + 3 + dx, y + TILE_SIZE - 2,
+ COL_CROSS);
+ }
+ }
+ }
+ }
+
+ draw_update(fe, x, y, TILE_SIZE, TILE_SIZE);
+}
+
+static void game_redraw(frontend *fe, game_drawstate *ds, game_state *oldstate,
+ game_state *state, int dir, game_ui *ui,
+ float animtime, float flashtime)
+{+ int x, y;
+ int mines, markers, bg;
+
+ if (flashtime) {+ int frame = (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[6];
+
+ draw_rect(fe, 0, 0,
+ TILE_SIZE * state->w + 2 * BORDER,
+ TILE_SIZE * state->h + 2 * BORDER, COL_BACKGROUND);
+ draw_update(fe, 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] = COORD(0) - OUTER_HIGHLIGHT_WIDTH;
+ coords[5] = COORD(state->h) + OUTER_HIGHLIGHT_WIDTH - 1;
+ draw_polygon(fe, coords, 3, TRUE, COL_HIGHLIGHT);
+ draw_polygon(fe, coords, 3, FALSE, COL_HIGHLIGHT);
+
+ coords[1] = COORD(0) - OUTER_HIGHLIGHT_WIDTH;
+ coords[0] = COORD(0) - OUTER_HIGHLIGHT_WIDTH;
+ draw_polygon(fe, coords, 3, TRUE, COL_LOWLIGHT);
+ draw_polygon(fe, coords, 3, FALSE, COL_LOWLIGHT);
+
+ ds->started = TRUE;
+ }
+
+ /*
+ * 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];
+
+ if (v == -1)
+ markers++;
+ if (state->mines[y*ds->w+x])
+ mines++;
+
+ if ((v == -2 || v == -3) &&
+ (abs(x-ui->hx) <= ui->hradius && abs(y-ui->hy) <= ui->hradius))
+ v -= 20;
+
+ if (ds->grid[y*ds->w+x] != v || bg != COL_BACKGROUND) {+ draw_tile(fe, COORD(x), COORD(y), v, bg);
+ ds->grid[y*ds->w+x] = (bg == COL_BACKGROUND ? v : -10);
+ }
+ }
+
+ /*
+ * Update the status bar.
+ */
+ {+ char statusbar[512];
+ if (state->dead) {+ sprintf(statusbar, "GAME OVER!");
+ } else if (state->won) {+ sprintf(statusbar, "COMPLETED!");
+ } else {+ sprintf(statusbar, "Mines marked: %d / %d", markers, mines);
+ }
+ status_bar(fe, statusbar);
+ }
+}
+
+static float game_anim_length(game_state *oldstate, game_state *newstate,
+ int dir, game_ui *ui)
+{+ return 0.0F;
+}
+
+static float game_flash_length(game_state *oldstate, game_state *newstate,
+ int dir, game_ui *ui)
+{+ 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_wants_statusbar(void)
+{+ return TRUE;
+}
+
+#ifdef COMBINED
+#define thegame mines
+#endif
+
+const struct game thegame = {+ "Mines", "games.mines",
+ default_params,
+ game_fetch_preset,
+ decode_params,
+ encode_params,
+ free_params,
+ dup_params,
+ TRUE, game_configure, custom_params,
+ validate_params,
+ new_game_desc,
+ game_free_aux_info,
+ validate_desc,
+ new_game,
+ dup_game,
+ free_game,
+ FALSE, solve_game,
+ FALSE, game_text_format,
+ new_ui,
+ free_ui,
+ make_move,
+ game_size,
+ game_colours,
+ game_new_drawstate,
+ game_free_drawstate,
+ game_redraw,
+ game_anim_length,
+ game_flash_length,
+ game_wants_statusbar,
+};
--- a/puzzles.but
+++ b/puzzles.but
@@ -829,6 +829,78 @@
a large puzzle size.
+\C{mines} \i{Mines}+
+\cfg{winhelp-topic}{games.mines}+
+You have a grid of covered squares, some of which contain mines, but
+you don't know which. Your job is to uncover every square which does
+\e{not} contain a mine. If you uncover a square containing a mine,+you lose. If you uncover a square which does not contain a mine, you
+are told how many mines are contained within the eight surrounding
+squares.
+
+This game needs no introduction; popularised by Windows, it is
+perhaps the single best known desktop puzzle game in existence.
+
+This version of it has an unusual property. By default, it will
+generate its mine positions in such a way as to ensure that you
+never need to \e{guess} where a mine is: you will always be able to+deduce it somehow. So you will never, as can happen in other
+versions, get to the last four squares and discover that there are
+two mines left but you have no way of knowing for sure where they
+are.
+
+\H{mines-controls} \I{controls, for Mines}Mines controls+
+This game is played with the mouse.
+
+If you left-click in a covered square, it will be uncovered.
+
+If you right-click in a covered square, it will place a flag which
+indicates that the square is believed to be a mine. Left-clicking in
+a marked square will not uncover it, for safety. You can right-click
+again to remove a mark placed in error.
+
+If you left-click in an \e{uncovered} square, it will \q{clear+around} the square. This means: if the square has exactly as many
+flags surrounding it as it should have mines, then all the covered
+squares next to it which are \e{not} flagged will be uncovered. So+once you think you know the location of all the mines around a
+square, you can use this function as a shortcut to avoid having to
+click on each of the remaining squares one by one.
+
+If you uncover a square which has \e{no} mines in the surrounding+eight squares, then it is obviously safe to uncover those squares in
+turn, and so on if any of them also has no surrounding mines. This
+will be done for you automatically; so sometimes when you uncover a
+square, a whole new area will open up to be explored.
+
+(All the actions described in \k{common-actions} are also available.+Even Undo is available, although you might consider it cheating to
+use it!)
+
+\H{mines-parameters} \I{parameters, for Mines}Mines parameters+
+The options available from the \q{Custom...} option on the \q{Type}+menu are:
+
+\dt \e{Width}, \e{Height}+
+\dd Size of grid in squares.
+
+\dt \e{Mines}+
+\dd Number of mines in the grid.
+
+\dt \e{Ensure solubility}+
+\dd When this option is enabled (as it is by default), Mines will
+ensure that the entire grid can be fully deduced starting from the
+initial open space. If you prefer the riskier grids generated by
+other implementations, you can switch off this option.
+
+
\A{licence} \I{MIT licence}\ii{Licence} This software is \i{copyright} 2004-2005 Simon Tatham.--- a/puzzles.h
+++ b/puzzles.h
@@ -176,6 +176,18 @@
unsigned long random_bits(random_state *state, int bits);
unsigned long random_upto(random_state *state, unsigned long limit);
void random_free(random_state *state);
+/* random.c also exports SHA, which occasionally comes in useful. */
+typedef unsigned long uint32;
+typedef struct {+ uint32 h[5];
+ unsigned char block[64];
+ int blkused;
+ uint32 lenhi, lenlo;
+} SHA_State;
+void SHA_Init(SHA_State *s);
+void SHA_Bytes(SHA_State *s, void *p, int len);
+void SHA_Final(SHA_State *s, unsigned char *output);
+void SHA_Simple(void *p, int len, unsigned char *output);
/*
* Data structure containing the function calls and data specific
--- a/random.c
+++ b/random.c
@@ -15,15 +15,6 @@
#include "puzzles.h"
-typedef unsigned long uint32;
-
-typedef struct {- uint32 h[5];
- unsigned char block[64];
- int blkused;
- uint32 lenhi, lenlo;
-} SHA_State;
-
/* ----------------------------------------------------------------------
* Core SHA algorithm: processes 16-word blocks into a message digest.
*/
@@ -108,7 +99,7 @@
* the end, and pass those blocks to the core SHA algorithm.
*/
-static void SHA_Init(SHA_State * s)
+void SHA_Init(SHA_State * s)
{SHA_Core_Init(s->h);
s->blkused = 0;
@@ -115,7 +106,7 @@
s->lenhi = s->lenlo = 0;
}
-static void SHA_Bytes(SHA_State * s, void *p, int len)
+void SHA_Bytes(SHA_State * s, void *p, int len)
{unsigned char *q = (unsigned char *) p;
uint32 wordblock[16];
@@ -158,7 +149,7 @@
}
}
-static void SHA_Final(SHA_State * s, unsigned char *output)
+void SHA_Final(SHA_State * s, unsigned char *output)
{int i;
int pad;
@@ -196,7 +187,7 @@
}
}
-static void SHA_Simple(void *p, int len, unsigned char *output)
+void SHA_Simple(void *p, int len, unsigned char *output)
{SHA_State s;