mines.c

   1 /*
   2  * mines.c: Minesweeper clone with sophisticated grid generation.
   3  *
   4  * Still TODO:
   5  *
   6  *  - possibly disable undo? Or alternatively mark game states as
   7  *    `cheated', although that's horrid.
   8  *     + OK. Rather than _disabling_ undo, we have a hook callable
   9  *       in the game backend which is called before we do an undo.
  10  *       That hook can talk to the game_ui and set the cheated flag,
  11  *       and then make_move can avoid setting the `won' flag after that.
  12  *
  13  *  - question marks (arrgh, preferences?)
  14  *
  15  *  - sensible parameter constraints
  16  *     + 30x16: 191 mines just about works if rather slowly, 192 is
  17  *       just about doom (the latter corresponding to a density of
  18  *       exactly 1 in 2.5)
  19  *     + 9x9: 45 mines works - over 1 in 2! 50 seems a bit slow.
  20  *     + it might not be feasible to work out the exact limit
  21  */
  22
  23 #include <stdio.h>
  24 #include <stdlib.h>
  25 #include <string.h>
  26 #include <assert.h>
  27 #include <ctype.h>
  28 #include <math.h>
  29
  30 #include "tree234.h"
  31 #include "puzzles.h"
  32
  33 enum {
  34     COL_BACKGROUND,
  35     COL_1, COL_2, COL_3, COL_4, COL_5, COL_6, COL_7, COL_8,
  36     COL_MINE, COL_BANG, COL_CROSS, COL_FLAG, COL_FLAGBASE, COL_QUERY,
  37     COL_HIGHLIGHT, COL_LOWLIGHT,
  38     NCOLOURS
  39 };
  40
  41 #define TILE_SIZE 20
  42 #define BORDER (TILE_SIZE * 3 / 2)
  43 #define HIGHLIGHT_WIDTH 2
  44 #define OUTER_HIGHLIGHT_WIDTH 3
  45 #define COORD(x)  ( (x) * TILE_SIZE + BORDER )
  46 #define FROMCOORD(x)  ( ((x) - BORDER + TILE_SIZE) / TILE_SIZE - 1 )
  47
  48 #define FLASH_FRAME 0.13F
  49
  50 struct game_params {
  51     int w, h, n;
  52     int unique;
  53 };
  54
  55 struct mine_layout {
  56     /*
  57      * This structure is shared between all the game_states for a
  58      * given instance of the puzzle, so we reference-count it.
  59      */
  60     int refcount;
  61     char *mines;
  62     /*
  63      * If we haven't yet actually generated the mine layout, here's
  64      * all the data we will need to do so.
  65      */
  66     int n, unique;
  67     random_state *rs;
  68     midend_data *me;                   /* to give back the new game desc */
  69 };
  70
  71 struct game_state {
  72     int w, h, n, dead, won;
  73     struct mine_layout *layout;        /* real mine positions */
  74     char *grid;                        /* player knowledge */
  75     /*
  76      * Each item in the `grid' array is one of the following values:
  77      *
  78      *  - 0 to 8 mean the square is open and has a surrounding mine
  79      *    count.
  80      *
  81      *  - -1 means the square is marked as a mine.
  82      *
  83      *  - -2 means the square is unknown.
  84      *
  85      *  - -3 means the square is marked with a question mark
  86      *    (FIXME: do we even want to bother with this?).
  87      *
  88      *  - 64 means the square has had a mine revealed when the game
  89      *    was lost.
  90      *
  91      *  - 65 means the square had a mine revealed and this was the
  92      *    one the player hits.
  93      *
  94      *  - 66 means the square has a crossed-out mine because the
  95      *    player had incorrectly marked it.
  96      */
  97 };
  98
  99 static game_params *default_params(void)
 100 {
 101     game_params *ret = snew(game_params);
 102
 103     ret->w = ret->h = 9;
 104     ret->n = 10;
 105     ret->unique = TRUE;
 106
 107     return ret;
 108 }
 109
 110 static int game_fetch_preset(int i, char **name, game_params **params)
 111 {
 112     game_params *ret;
 113     char str[80];
 114     static const struct { int w, h, n; } values[] = {
 115         {9, 9, 10},
 116         {16, 16, 40},
 117         {30, 16, 99},
 118     };
 119
 120     if (i < 0 || i >= lenof(values))
 121         return FALSE;
 122
 123     ret = snew(game_params);
 124     ret->w = values[i].w;
 125     ret->h = values[i].h;
 126     ret->n = values[i].n;
 127     ret->unique = TRUE;
 128
 129     sprintf(str, "%dx%d, %d mines", ret->w, ret->h, ret->n);
 130
 131     *name = dupstr(str);
 132     *params = ret;
 133     return TRUE;
 134 }
 135
 136 static void free_params(game_params *params)
 137 {
 138     sfree(params);
 139 }
 140
 141 static game_params *dup_params(game_params *params)
 142 {
 143     game_params *ret = snew(game_params);
 144     *ret = *params;                    /* structure copy */
 145     return ret;
 146 }
 147
 148 static void decode_params(game_params *params, char const *string)
 149 {
 150     char const *p = string;
 151
 152     params->w = atoi(p);
 153     while (*p && isdigit((unsigned char)*p)) p++;
 154     if (*p == 'x') {
 155         p++;
 156         params->h = atoi(p);
 157         while (*p && isdigit((unsigned char)*p)) p++;
 158     } else {
 159         params->h = params->w;
 160     }
 161     if (*p == 'n') {
 162         p++;
 163         params->n = atoi(p);
 164         while (*p && (*p == '.' || isdigit((unsigned char)*p))) p++;
 165     } else {
 166         params->n = params->w * params->h / 10;
 167     }
 168
 169     while (*p) {
 170         if (*p == 'a') {
 171             p++;
 172             params->unique = FALSE;
 173         } else
 174             p++;                       /* skip any other gunk */
 175     }
 176 }
 177
 178 static char *encode_params(game_params *params, int full)
 179 {
 180     char ret[400];
 181     int len;
 182
 183     len = sprintf(ret, "%dx%d", params->w, params->h);
 184     /*
 185      * Mine count is a generation-time parameter, since it can be
 186      * deduced from the mine bitmap!
 187      */
 188     if (full)
 189         len += sprintf(ret+len, "n%d", params->n);
 190     if (full && !params->unique)
 191         ret[len++] = 'a';
 192     assert(len < lenof(ret));
 193     ret[len] = '\0';
 194
 195     return dupstr(ret);
 196 }
 197
 198 static config_item *game_configure(game_params *params)
 199 {
 200     config_item *ret;
 201     char buf[80];
 202
 203     ret = snewn(5, config_item);
 204
 205     ret[0].name = "Width";
 206     ret[0].type = C_STRING;
 207     sprintf(buf, "%d", params->w);
 208     ret[0].sval = dupstr(buf);
 209     ret[0].ival = 0;
 210
 211     ret[1].name = "Height";
 212     ret[1].type = C_STRING;
 213     sprintf(buf, "%d", params->h);
 214     ret[1].sval = dupstr(buf);
 215     ret[1].ival = 0;
 216
 217     ret[2].name = "Mines";
 218     ret[2].type = C_STRING;
 219     sprintf(buf, "%d", params->n);
 220     ret[2].sval = dupstr(buf);
 221     ret[2].ival = 0;
 222
 223     ret[3].name = "Ensure solubility";
 224     ret[3].type = C_BOOLEAN;
 225     ret[3].sval = NULL;
 226     ret[3].ival = params->unique;
 227
 228     ret[4].name = NULL;
 229     ret[4].type = C_END;
 230     ret[4].sval = NULL;
 231     ret[4].ival = 0;
 232
 233     return ret;
 234 }
 235
 236 static game_params *custom_params(config_item *cfg)
 237 {
 238     game_params *ret = snew(game_params);
 239
 240     ret->w = atoi(cfg[0].sval);
 241     ret->h = atoi(cfg[1].sval);
 242     ret->n = atoi(cfg[2].sval);
 243     if (strchr(cfg[2].sval, '%'))
 244         ret->n = ret->n * (ret->w * ret->h) / 100;
 245     ret->unique = cfg[3].ival;
 246
 247     return ret;
 248 }
 249
 250 static char *validate_params(game_params *params)
 251 {
 252     if (params->w <= 0 && params->h <= 0)
 253         return "Width and height must both be greater than zero";
 254     if (params->w <= 0)
 255         return "Width must be greater than zero";
 256     if (params->h <= 0)
 257         return "Height must be greater than zero";
 258
 259     /*
 260      * FIXME: Need more constraints here. Not sure what the
 261      * sensible limits for Minesweeper actually are. The limits
 262      * probably ought to change, however, depending on uniqueness.
 263      */
 264
 265     return NULL;
 266 }
 267
 268 /* ----------------------------------------------------------------------
 269  * Minesweeper solver, used to ensure the generated grids are
 270  * solvable without having to take risks.
 271  */
 272
 273 /*
 274  * Count the bits in a word. Only needs to cope with 16 bits.
 275  */
 276 static int bitcount16(int word)
 277 {
 278     word = ((word & 0xAAAA) >> 1) + (word & 0x5555);
 279     word = ((word & 0xCCCC) >> 2) + (word & 0x3333);
 280     word = ((word & 0xF0F0) >> 4) + (word & 0x0F0F);
 281     word = ((word & 0xFF00) >> 8) + (word & 0x00FF);
 282
 283     return word;
 284 }
 285
 286 /*
 287  * We use a tree234 to store a large number of small localised
 288  * sets, each with a mine count. We also keep some of those sets
 289  * linked together into a to-do list.
 290  */
 291 struct set {
 292     short x, y, mask, mines;
 293     int todo;
 294     struct set *prev, *next;
 295 };
 296
 297 static int setcmp(void *av, void *bv)
 298 {
 299     struct set *a = (struct set *)av;
 300     struct set *b = (struct set *)bv;
 301
 302     if (a->y < b->y)
 303         return -1;
 304     else if (a->y > b->y)
 305         return +1;
 306     else if (a->x < b->x)
 307         return -1;
 308     else if (a->x > b->x)
 309         return +1;
 310     else if (a->mask < b->mask)
 311         return -1;
 312     else if (a->mask > b->mask)
 313         return +1;
 314     else
 315         return 0;
 316 }
 317
 318 struct setstore {
 319     tree234 *sets;
 320     struct set *todo_head, *todo_tail;
 321 };
 322
 323 static struct setstore *ss_new(void)
 324 {
 325     struct setstore *ss = snew(struct setstore);
 326     ss->sets = newtree234(setcmp);
 327     ss->todo_head = ss->todo_tail = NULL;
 328     return ss;
 329 }
 330
 331 /*
 332  * Take two input sets, in the form (x,y,mask). Munge the first by
 333  * taking either its intersection with the second or its difference
 334  * with the second. Return the new mask part of the first set.
 335  */
 336 static int setmunge(int x1, int y1, int mask1, int x2, int y2, int mask2,
 337                     int diff)
 338 {
 339     /*
 340      * Adjust the second set so that it has the same x,y
 341      * coordinates as the first.
 342      */
 343     if (abs(x2-x1) >= 3 || abs(y2-y1) >= 3) {
 344         mask2 = 0;
 345     } else {
 346         while (x2 > x1) {
 347             mask2 &= ~(4|32|256);
 348             mask2 <<= 1;
 349             x2--;
 350         }
 351         while (x2 < x1) {
 352             mask2 &= ~(1|8|64);
 353             mask2 >>= 1;
 354             x2++;
 355         }
 356         while (y2 > y1) {
 357             mask2 &= ~(64|128|256);
 358             mask2 <<= 3;
 359             y2--;
 360         }
 361         while (y2 < y1) {
 362             mask2 &= ~(1|2|4);
 363             mask2 >>= 3;
 364             y2++;
 365         }
 366     }
 367
 368     /*
 369      * Invert the second set if `diff' is set (we're after A &~ B
 370      * rather than A & B).
 371      */
 372     if (diff)
 373         mask2 ^= 511;
 374
 375     /*
 376      * Now all that's left is a logical AND.
 377      */
 378     return mask1 & mask2;
 379 }
 380
 381 static void ss_add_todo(struct setstore *ss, struct set *s)
 382 {
 383     if (s->todo)
 384         return;                        /* already on it */
 385
 386 #ifdef SOLVER_DIAGNOSTICS
 387     printf("adding set on todo list: %d,%d %03x %d\n",
 388            s->x, s->y, s->mask, s->mines);
 389 #endif
 390
 391     s->prev = ss->todo_tail;
 392     if (s->prev)
 393         s->prev->next = s;
 394     else
 395         ss->todo_head = s;
 396     ss->todo_tail = s;
 397     s->next = NULL;
 398     s->todo = TRUE;
 399 }
 400
 401 static void ss_add(struct setstore *ss, int x, int y, int mask, int mines)
 402 {
 403     struct set *s;
 404
 405     assert(mask != 0);
 406
 407     /*
 408      * Normalise so that x and y are genuinely the bounding
 409      * rectangle.
 410      */
 411     while (!(mask & (1|8|64)))
 412         mask >>= 1, x++;
 413     while (!(mask & (1|2|4)))
 414         mask >>= 3, y++;
 415
 416     /*
 417      * Create a set structure and add it to the tree.
 418      */
 419     s = snew(struct set);
 420     s->x = x;
 421     s->y = y;
 422     s->mask = mask;
 423     s->mines = mines;
 424     s->todo = FALSE;
 425     if (add234(ss->sets, s) != s) {
 426         /*
 427          * This set already existed! Free it and return.
 428          */
 429         sfree(s);
 430         return;
 431     }
 432
 433     /*
 434      * We've added a new set to the tree, so put it on the todo
 435      * list.
 436      */
 437     ss_add_todo(ss, s);
 438 }
 439
 440 static void ss_remove(struct setstore *ss, struct set *s)
 441 {
 442     struct set *next = s->next, *prev = s->prev;
 443
 444 #ifdef SOLVER_DIAGNOSTICS
 445     printf("removing set %d,%d %03x\n", s->x, s->y, s->mask);
 446 #endif
 447     /*
 448      * Remove s from the todo list.
 449      */
 450     if (prev)
 451         prev->next = next;
 452     else if (s == ss->todo_head)
 453         ss->todo_head = next;
 454
 455     if (next)
 456         next->prev = prev;
 457     else if (s == ss->todo_tail)
 458         ss->todo_tail = prev;
 459
 460     s->todo = FALSE;
 461
 462     /*
 463      * Remove s from the tree.
 464      */
 465     del234(ss->sets, s);
 466
 467     /*
 468      * Destroy the actual set structure.
 469      */
 470     sfree(s);
 471 }
 472
 473 /*
 474  * Return a dynamically allocated list of all the sets which
 475  * overlap a provided input set.
 476  */
 477 static struct set **ss_overlap(struct setstore *ss, int x, int y, int mask)
 478 {
 479     struct set **ret = NULL;
 480     int nret = 0, retsize = 0;
 481     int xx, yy;
 482
 483     for (xx = x-3; xx < x+3; xx++)
 484         for (yy = y-3; yy < y+3; yy++) {
 485             struct set stmp, *s;
 486             int pos;
 487
 488             /*
 489              * Find the first set with these top left coordinates.
 490              */
 491             stmp.x = xx;
 492             stmp.y = yy;
 493             stmp.mask = 0;
 494
 495             if (findrelpos234(ss->sets, &stmp, NULL, REL234_GE, &pos)) {
 496                 while ((s = index234(ss->sets, pos)) != NULL &&
 497                        s->x == xx && s->y == yy) {
 498                     /*
 499                      * This set potentially overlaps the input one.
 500                      * Compute the intersection to see if they
 501                      * really overlap, and add it to the list if
 502                      * so.
 503                      */
 504                     if (setmunge(x, y, mask, s->x, s->y, s->mask, FALSE)) {
 505                         /*
 506                          * There's an overlap.
 507                          */
 508                         if (nret >= retsize) {
 509                             retsize = nret + 32;
 510                             ret = sresize(ret, retsize, struct set *);
 511                         }
 512                         ret[nret++] = s;
 513                     }
 514
 515                     pos++;
 516                 }
 517             }
 518         }
 519
 520     ret = sresize(ret, nret+1, struct set *);
 521     ret[nret] = NULL;
 522
 523     return ret;
 524 }
 525
 526 /*
 527  * Get an element from the head of the set todo list.
 528  */
 529 static struct set *ss_todo(struct setstore *ss)
 530 {
 531     if (ss->todo_head) {
 532         struct set *ret = ss->todo_head;
 533         ss->todo_head = ret->next;
 534         if (ss->todo_head)
 535             ss->todo_head->prev = NULL;
 536         else
 537             ss->todo_tail = NULL;
 538         ret->next = ret->prev = NULL;
 539         ret->todo = FALSE;
 540         return ret;
 541     } else {
 542         return NULL;
 543     }
 544 }
 545
 546 struct squaretodo {
 547     int *next;
 548     int head, tail;
 549 };
 550
 551 static void std_add(struct squaretodo *std, int i)
 552 {
 553     if (std->tail >= 0)
 554         std->next[std->tail] = i;
 555     else
 556         std->head = i;
 557     std->tail = i;
 558     std->next[i] = -1;
 559 }
 560
 561 static void known_squares(int w, int h, struct squaretodo *std, char *grid,
 562                           int (*open)(void *ctx, int x, int y), void *openctx,
 563                           int x, int y, int mask, int mine)
 564 {
 565     int xx, yy, bit;
 566
 567     bit = 1;
 568
 569     for (yy = 0; yy < 3; yy++)
 570         for (xx = 0; xx < 3; xx++) {
 571             if (mask & bit) {
 572                 int i = (y + yy) * w + (x + xx);
 573
 574                 /*
 575                  * It's possible that this square is _already_
 576                  * known, in which case we don't try to add it to
 577                  * the list twice.
 578                  */
 579                 if (grid[i] == -2) {
 580
 581                     if (mine) {
 582                         grid[i] = -1;   /* and don't open it! */
 583                     } else {
 584                         grid[i] = open(openctx, x + xx, y + yy);
 585                         assert(grid[i] != -1);   /* *bang* */
 586                     }
 587                     std_add(std, i);
 588
 589                 }
 590             }
 591             bit <<= 1;
 592         }
 593 }
 594
 595 /*
 596  * This is data returned from the `perturb' function. It details
 597  * which squares have become mines and which have become clear. The
 598  * solver is (of course) expected to honourably not use that
 599  * knowledge directly, but to efficently adjust its internal data
 600  * structures and proceed based on only the information it
 601  * legitimately has.
 602  */
 603 struct perturbation {
 604     int x, y;
 605     int delta;                         /* +1 == become a mine; -1 == cleared */
 606 };
 607 struct perturbations {
 608     int n;
 609     struct perturbation *changes;
 610 };
 611
 612 /*
 613  * Main solver entry point. You give it a grid of existing
 614  * knowledge (-1 for a square known to be a mine, 0-8 for empty
 615  * squares with a given number of neighbours, -2 for completely
 616  * unknown), plus a function which you can call to open new squares
 617  * once you're confident of them. It fills in as much more of the
 618  * grid as it can.
 619  *
 620  * Return value is:
 621  *
 622  *  - -1 means deduction stalled and nothing could be done
 623  *  - 0 means deduction succeeded fully
 624  *  - >0 means deduction succeeded but some number of perturbation
 625  *    steps were required; the exact return value is the number of
 626  *    perturb calls.
 627  */
 628 static int minesolve(int w, int h, int n, char *grid,
 629                      int (*open)(void *ctx, int x, int y),
 630                      struct perturbations *(*perturb)(void *ctx, char *grid,
 631                                                       int x, int y, int mask),
 632                      void *ctx, random_state *rs)
 633 {
 634     struct setstore *ss = ss_new();
 635     struct set **list;
 636     struct squaretodo astd, *std = &astd;
 637     int x, y, i, j;
 638     int nperturbs = 0;
 639
 640     /*
 641      * Set up a linked list of squares with known contents, so that
 642      * we can process them one by one.
 643      */
 644     std->next = snewn(w*h, int);
 645     std->head = std->tail = -1;
 646
 647     /*
 648      * Initialise that list with all known squares in the input
 649      * grid.
 650      */
 651     for (y = 0; y < h; y++) {
 652         for (x = 0; x < w; x++) {
 653             i = y*w+x;
 654             if (grid[i] != -2)
 655                 std_add(std, i);
 656         }
 657     }
 658
 659     /*
 660      * Main deductive loop.
 661      */
 662     while (1) {
 663         int done_something = FALSE;
 664         struct set *s;
 665
 666         /*
 667          * If there are any known squares on the todo list, process
 668          * them and construct a set for each.
 669          */
 670         while (std->head != -1) {
 671             i = std->head;
 672 #ifdef SOLVER_DIAGNOSTICS
 673             printf("known square at %d,%d [%d]\n", i%w, i/w, grid[i]);
 674 #endif
 675             std->head = std->next[i];
 676             if (std->head == -1)
 677                 std->tail = -1;
 678
 679             x = i % w;
 680             y = i / w;
 681
 682             if (grid[i] >= 0) {
 683                 int dx, dy, mines, bit, val;
 684 #ifdef SOLVER_DIAGNOSTICS
 685                 printf("creating set around this square\n");
 686 #endif
 687                 /*
 688                  * Empty square. Construct the set of non-known squares
 689                  * around this one, and determine its mine count.
 690                  */
 691                 mines = grid[i];
 692                 bit = 1;
 693                 val = 0;
 694                 for (dy = -1; dy <= +1; dy++) {
 695                     for (dx = -1; dx <= +1; dx++) {
 696 #ifdef SOLVER_DIAGNOSTICS
 697                         printf("grid %d,%d = %d\n", x+dx, y+dy, grid[i+dy*w+dx]);
 698 #endif
 699                         if (x+dx < 0 || x+dx >= w || y+dy < 0 || y+dy >= h)
 700                             /* ignore this one */;
 701                         else if (grid[i+dy*w+dx] == -1)
 702                             mines--;
 703                         else if (grid[i+dy*w+dx] == -2)
 704                             val |= bit;
 705                         bit <<= 1;
 706                     }
 707                 }
 708                 if (val)
 709                     ss_add(ss, x-1, y-1, val, mines);
 710             }
 711
 712             /*
 713              * Now, whether the square is empty or full, we must
 714              * find any set which contains it and replace it with
 715              * one which does not.
 716              */
 717             {
 718 #ifdef SOLVER_DIAGNOSTICS
 719                 printf("finding sets containing known square %d,%d\n", x, y);
 720 #endif
 721                 list = ss_overlap(ss, x, y, 1);
 722
 723                 for (j = 0; list[j]; j++) {
 724                     int newmask, newmines;
 725
 726                     s = list[j];
 727
 728                     /*
 729                      * Compute the mask for this set minus the
 730                      * newly known square.
 731                      */
 732                     newmask = setmunge(s->x, s->y, s->mask, x, y, 1, TRUE);
 733
 734                     /*
 735                      * Compute the new mine count.
 736                      */
 737                     newmines = s->mines - (grid[i] == -1);
 738
 739                     /*
 740                      * Insert the new set into the collection,
 741                      * unless it's been whittled right down to
 742                      * nothing.
 743                      */
 744                     if (newmask)
 745                         ss_add(ss, s->x, s->y, newmask, newmines);
 746
 747                     /*
 748                      * Destroy the old one; it is actually obsolete.
 749                      */
 750                     ss_remove(ss, s);
 751                 }
 752
 753                 sfree(list);
 754             }
 755
 756             /*
 757              * Marking a fresh square as known certainly counts as
 758              * doing something.
 759              */
 760             done_something = TRUE;
 761         }
 762
 763         /*
 764          * Now pick a set off the to-do list and attempt deductions
 765          * based on it.
 766          */
 767         if ((s = ss_todo(ss)) != NULL) {
 768
 769 #ifdef SOLVER_DIAGNOSTICS
 770             printf("set to do: %d,%d %03x %d\n", s->x, s->y, s->mask, s->mines);
 771 #endif
 772             /*
 773              * Firstly, see if this set has a mine count of zero or
 774              * of its own cardinality.
 775              */
 776             if (s->mines == 0 || s->mines == bitcount16(s->mask)) {
 777                 /*
 778                  * If so, we can immediately mark all the squares
 779                  * in the set as known.
 780                  */
 781 #ifdef SOLVER_DIAGNOSTICS
 782                 printf("easy\n");
 783 #endif
 784                 known_squares(w, h, std, grid, open, ctx,
 785                               s->x, s->y, s->mask, (s->mines != 0));
 786
 787                 /*
 788                  * Having done that, we need do nothing further
 789                  * with this set; marking all the squares in it as
 790                  * known will eventually eliminate it, and will
 791                  * also permit further deductions about anything
 792                  * that overlaps it.
 793                  */
 794                 continue;
 795             }
 796
 797             /*
 798              * Failing that, we now search through all the sets
 799              * which overlap this one.
 800              */
 801             list = ss_overlap(ss, s->x, s->y, s->mask);
 802
 803             for (j = 0; list[j]; j++) {
 804                 struct set *s2 = list[j];
 805                 int swing, s2wing, swc, s2wc;
 806
 807                 /*
 808                  * Find the non-overlapping parts s2-s and s-s2,
 809                  * and their cardinalities.
 810                  *
 811                  * I'm going to refer to these parts as `wings'
 812                  * surrounding the central part common to both
 813                  * sets. The `s wing' is s-s2; the `s2 wing' is
 814                  * s2-s.
 815                  */
 816                 swing = setmunge(s->x, s->y, s->mask, s2->x, s2->y, s2->mask,
 817                                  TRUE);
 818                 s2wing = setmunge(s2->x, s2->y, s2->mask, s->x, s->y, s->mask,
 819                                  TRUE);
 820                 swc = bitcount16(swing);
 821                 s2wc = bitcount16(s2wing);
 822
 823                 /*
 824                  * If one set has more mines than the other, and
 825                  * the number of extra mines is equal to the
 826                  * cardinality of that set's wing, then we can mark
 827                  * every square in the wing as a known mine, and
 828                  * every square in the other wing as known clear.
 829                  */
 830                 if (swc == s->mines - s2->mines ||
 831                     s2wc == s2->mines - s->mines) {
 832                     known_squares(w, h, std, grid, open, ctx,
 833                                   s->x, s->y, swing,
 834                                   (swc == s->mines - s2->mines));
 835                     known_squares(w, h, std, grid, open, ctx,
 836                                   s2->x, s2->y, s2wing,
 837                                   (s2wc == s2->mines - s->mines));
 838                     continue;
 839                 }
 840
 841                 /*
 842                  * Failing that, see if one set is a subset of the
 843                  * other. If so, we can divide up the mine count of
 844                  * the larger set between the smaller set and its
 845                  * complement, even if neither smaller set ends up
 846                  * being immediately clearable.
 847                  */
 848                 if (swc == 0 && s2wc != 0) {
 849                     /* s is a subset of s2. */
 850                     assert(s2->mines > s->mines);
 851                     ss_add(ss, s2->x, s2->y, s2wing, s2->mines - s->mines);
 852                 } else if (s2wc == 0 && swc != 0) {
 853                     /* s2 is a subset of s. */
 854                     assert(s->mines > s2->mines);
 855                     ss_add(ss, s->x, s->y, swing, s->mines - s2->mines);
 856                 }
 857             }
 858
 859             sfree(list);
 860
 861             /*
 862              * In this situation we have definitely done
 863              * _something_, even if it's only reducing the size of
 864              * our to-do list.
 865              */
 866             done_something = TRUE;
 867         } else if (n >= 0) {
 868             /*
 869              * We have nothing left on our todo list, which means
 870              * all localised deductions have failed. Our next step
 871              * is to resort to global deduction based on the total
 872              * mine count. This is computationally expensive
 873              * compared to any of the above deductions, which is
 874              * why we only ever do it when all else fails, so that
 875              * hopefully it won't have to happen too often.
 876              *
 877              * If you pass n<0 into this solver, that informs it
 878              * that you do not know the total mine count, so it
 879              * won't even attempt these deductions.
 880              */
 881
 882             int minesleft, squaresleft;
 883             int nsets, setused[10], cursor;
 884
 885             /*
 886              * Start by scanning the current grid state to work out
 887              * how many unknown squares we still have, and how many
 888              * mines are to be placed in them.
 889              */
 890             squaresleft = 0;
 891             minesleft = n;
 892             for (i = 0; i < w*h; i++) {
 893                 if (grid[i] == -1)
 894                     minesleft--;
 895                 else if (grid[i] == -2)
 896                     squaresleft++;
 897             }
 898
 899 #ifdef SOLVER_DIAGNOSTICS
 900             printf("global deduction time: squaresleft=%d minesleft=%d\n",
 901                    squaresleft, minesleft);
 902             for (y = 0; y < h; y++) {
 903                 for (x = 0; x < w; x++) {
 904                     int v = grid[y*w+x];
 905                     if (v == -1)
 906                         putchar('*');
 907                     else if (v == -2)
 908                         putchar('?');
 909                     else if (v == 0)
 910                         putchar('-');
 911                     else
 912                         putchar('0' + v);
 913                 }
 914                 putchar('\n');
 915             }
 916 #endif
 917
 918             /*
 919              * If there _are_ no unknown squares, we have actually
 920              * finished.
 921              */
 922             if (squaresleft == 0) {
 923                 assert(minesleft == 0);
 924                 break;
 925             }
 926
 927             /*
 928              * First really simple case: if there are no more mines
 929              * left, or if there are exactly as many mines left as
 930              * squares to play them in, then it's all easy.
 931              */
 932             if (minesleft == 0 || minesleft == squaresleft) {
 933                 for (i = 0; i < w*h; i++)
 934                     if (grid[i] == -2)
 935                         known_squares(w, h, std, grid, open, ctx,
 936                                       i % w, i / w, 1, minesleft != 0);
 937                 continue;              /* now go back to main deductive loop */
 938             }
 939
 940             /*
 941              * Failing that, we have to do some _real_ work.
 942              * Ideally what we do here is to try every single
 943              * combination of the currently available sets, in an
 944              * attempt to find a disjoint union (i.e. a set of
 945              * squares with a known mine count between them) such
 946              * that the remaining unknown squares _not_ contained
 947              * in that union either contain no mines or are all
 948              * mines.
 949              *
 950              * Actually enumerating all 2^n possibilities will get
 951              * a bit slow for large n, so I artificially cap this
 952              * recursion at n=10 to avoid too much pain.
 953              */
 954             nsets = count234(ss->sets);
 955             if (nsets <= lenof(setused)) {
 956                 /*
 957                  * Doing this with actual recursive function calls
 958                  * would get fiddly because a load of local
 959                  * variables from this function would have to be
 960                  * passed down through the recursion. So instead
 961                  * I'm going to use a virtual recursion within this
 962                  * function. The way this works is:
 963                  *
 964                  *  - we have an array `setused', such that
 965                  *    setused[n] is 0 or 1 depending on whether set
 966                  *    n is currently in the union we are
 967                  *    considering.
 968                  *
 969                  *  - we have a value `cursor' which indicates how
 970                  *    much of `setused' we have so far filled in.
 971                  *    It's conceptually the recursion depth.
 972                  *
 973                  * We begin by setting `cursor' to zero. Then:
 974                  *
 975                  *  - if cursor can advance, we advance it by one.
 976                  *    We set the value in `setused' that it went
 977                  *    past to 1 if that set is disjoint from
 978                  *    anything else currently in `setused', or to 0
 979                  *    otherwise.
 980                  *
 981                  *  - If cursor cannot advance because it has
 982                  *    reached the end of the setused list, then we
 983                  *    have a maximal disjoint union. Check to see
 984                  *    whether its mine count has any useful
 985                  *    properties. If so, mark all the squares not
 986                  *    in the union as known and terminate.
 987                  *
 988                  *  - If cursor has reached the end of setused and
 989                  *    the algorithm _hasn't_ terminated, back
 990                  *    cursor up to the nearest 1, turn it into a 0
 991                  *    and advance cursor just past it.
 992                  *
 993                  *  - If we attempt to back up to the nearest 1 and
 994                  *    there isn't one at all, then we have gone
 995                  *    through all disjoint unions of sets in the
 996                  *    list and none of them has been helpful, so we
 997                  *    give up.
 998                  */
 999                 struct set *sets[lenof(setused)];
1000                 for (i = 0; i < nsets; i++)
1001                     sets[i] = index234(ss->sets, i);
1002
1003                 cursor = 0;
1004                 while (1) {
1005
1006                     if (cursor < nsets) {
1007                         int ok = TRUE;
1008
1009                         /* See if any existing set overlaps this one. */
1010                         for (i = 0; i < cursor; i++)
1011                             if (setused[i] &&
1012                                 setmunge(sets[cursor]->x,
1013                                          sets[cursor]->y,
1014                                          sets[cursor]->mask,
1015                                          sets[i]->x, sets[i]->y, sets[i]->mask,
1016                                          FALSE)) {
1017                                 ok = FALSE;
1018                                 break;
1019                             }
1020
1021                         if (ok) {
1022                             /*
1023                              * We're adding this set to our union,
1024                              * so adjust minesleft and squaresleft
1025                              * appropriately.
1026                              */
1027                             minesleft -= sets[cursor]->mines;
1028                             squaresleft -= bitcount16(sets[cursor]->mask);
1029                         }
1030
1031                         setused[cursor++] = ok;
1032                     } else {
1033 #ifdef SOLVER_DIAGNOSTICS
1034                         printf("trying a set combination with %d %d\n",
1035                                squaresleft, minesleft);
1036 #endif /* SOLVER_DIAGNOSTICS */
1037
1038                         /*
1039                          * We've reached the end. See if we've got
1040                          * anything interesting.
1041                          */
1042                         if (squaresleft > 0 &&
1043                             (minesleft == 0 || minesleft == squaresleft)) {
1044                             /*
1045                              * We have! There is at least one
1046                              * square not contained within the set
1047                              * union we've just found, and we can
1048                              * deduce that either all such squares
1049                              * are mines or all are not (depending
1050                              * on whether minesleft==0). So now all
1051                              * we have to do is actually go through
1052                              * the grid, find those squares, and
1053                              * mark them.
1054                              */
1055                             for (i = 0; i < w*h; i++)
1056                                 if (grid[i] == -2) {
1057                                     int outside = TRUE;
1058                                     y = i / w;
1059                                     x = i % w;
1060                                     for (j = 0; j < nsets; j++)
1061                                         if (setused[j] &&
1062                                             setmunge(sets[j]->x, sets[j]->y,
1063                                                      sets[j]->mask, x, y, 1,
1064                                                      FALSE)) {
1065                                             outside = FALSE;
1066                                             break;
1067                                         }
1068                                     if (outside)
1069                                         known_squares(w, h, std, grid,
1070                                                       open, ctx,
1071                                                       x, y, 1, minesleft != 0);
1072                                 }
1073
1074                             done_something = TRUE;
1075                             break;     /* return to main deductive loop */
1076                         }
1077
1078                         /*
1079                          * If we reach here, then this union hasn't
1080                          * done us any good, so move on to the
1081                          * next. Backtrack cursor to the nearest 1,
1082                          * change it to a 0 and continue.
1083                          */
1084                         while (cursor-- >= 0 && !setused[cursor]);
1085                         if (cursor >= 0) {
1086                             assert(setused[cursor]);
1087
1088                             /*
1089                              * We're removing this set from our
1090                              * union, so re-increment minesleft and
1091                              * squaresleft.
1092                              */
1093                             minesleft += sets[cursor]->mines;
1094                             squaresleft += bitcount16(sets[cursor]->mask);
1095
1096                             setused[cursor++] = 0;
1097                         } else {
1098                             /*
1099                              * We've backtracked all the way to the
1100                              * start without finding a single 1,
1101                              * which means that our virtual
1102                              * recursion is complete and nothing
1103                              * helped.
1104                              */
1105                             break;
1106                         }
1107                     }
1108
1109                 }
1110
1111             }
1112         }
1113
1114         if (done_something)
1115             continue;
1116
1117 #ifdef SOLVER_DIAGNOSTICS
1118         /*
1119          * Dump the current known state of the grid.
1120          */
1121         printf("solver ran out of steam, ret=%d, grid:\n", nperturbs);
1122         for (y = 0; y < h; y++) {
1123             for (x = 0; x < w; x++) {
1124                 int v = grid[y*w+x];
1125                 if (v == -1)
1126                     putchar('*');
1127                 else if (v == -2)
1128                     putchar('?');
1129                 else if (v == 0)
1130                     putchar('-');
1131                 else
1132                     putchar('0' + v);
1133             }
1134             putchar('\n');
1135         }
1136
1137         {
1138             struct set *s;
1139
1140             for (i = 0; (s = index234(ss->sets, i)) != NULL; i++)
1141                 printf("remaining set: %d,%d %03x %d\n", s->x, s->y, s->mask, s->mines);
1142         }
1143 #endif
1144
1145         /*
1146          * Now we really are at our wits' end as far as solving
1147          * this grid goes. Our only remaining option is to call
1148          * a perturb function and ask it to modify the grid to
1149          * make it easier.
1150          */
1151         if (perturb) {
1152             struct perturbations *ret;
1153             struct set *s;
1154
1155             nperturbs++;
1156
1157             /*
1158              * Choose a set at random from the current selection,
1159              * and ask the perturb function to either fill or empty
1160              * it.
1161              *
1162              * If we have no sets at all, we must give up.
1163              */
1164             if (count234(ss->sets) == 0)
1165                 break;
1166             s = index234(ss->sets, random_upto(rs, count234(ss->sets)));
1167 #ifdef SOLVER_DIAGNOSTICS
1168             printf("perturbing on set %d,%d %03x\n", s->x, s->y, s->mask);
1169 #endif
1170             ret = perturb(ctx, grid, s->x, s->y, s->mask);
1171
1172             if (ret) {
1173                 assert(ret->n > 0);    /* otherwise should have been NULL */
1174
1175                 /*
1176                  * A number of squares have been fiddled with, and
1177                  * the returned structure tells us which. Adjust
1178                  * the mine count in any set which overlaps one of
1179                  * those squares, and put them back on the to-do
1180                  * list.
1181                  */
1182                 for (i = 0; i < ret->n; i++) {
1183 #ifdef SOLVER_DIAGNOSTICS
1184                     printf("perturbation %s mine at %d,%d\n",
1185                            ret->changes[i].delta > 0 ? "added" : "removed",
1186                            ret->changes[i].x, ret->changes[i].y);
1187 #endif
1188
1189                     list = ss_overlap(ss,
1190                                       ret->changes[i].x, ret->changes[i].y, 1);
1191
1192                     for (j = 0; list[j]; j++) {
1193                         list[j]->mines += ret->changes[i].delta;
1194                         ss_add_todo(ss, list[j]);
1195                     }
1196
1197                     sfree(list);
1198                 }
1199
1200                 /*
1201                  * Now free the returned data.
1202                  */
1203                 sfree(ret->changes);
1204                 sfree(ret);
1205
1206 #ifdef SOLVER_DIAGNOSTICS
1207                 /*
1208                  * Dump the current known state of the grid.
1209                  */
1210                 printf("state after perturbation:\n", nperturbs);
1211                 for (y = 0; y < h; y++) {
1212                     for (x = 0; x < w; x++) {
1213                         int v = grid[y*w+x];
1214                         if (v == -1)
1215                             putchar('*');
1216                         else if (v == -2)
1217                             putchar('?');
1218                         else if (v == 0)
1219                             putchar('-');
1220                         else
1221                             putchar('0' + v);
1222                     }
1223                     putchar('\n');
1224                 }
1225
1226                 {
1227                     struct set *s;
1228
1229                     for (i = 0; (s = index234(ss->sets, i)) != NULL; i++)
1230                         printf("remaining set: %d,%d %03x %d\n", s->x, s->y, s->mask, s->mines);
1231                 }
1232 #endif
1233
1234                 /*
1235                  * And now we can go back round the deductive loop.
1236                  */
1237                 continue;
1238             }
1239         }
1240
1241         /*
1242          * If we get here, even that didn't work (either we didn't
1243          * have a perturb function or it returned failure), so we
1244          * give up entirely.
1245          */
1246         break;
1247     }
1248
1249     /*
1250      * See if we've got any unknown squares left.
1251      */
1252     for (y = 0; y < h; y++)
1253         for (x = 0; x < w; x++)
1254             if (grid[y*w+x] == -2) {
1255                 nperturbs = -1;        /* failed to complete */
1256                 break;
1257             }
1258
1259     /*
1260      * Free the set list and square-todo list.
1261      */
1262     {
1263         struct set *s;
1264         while ((s = delpos234(ss->sets, 0)) != NULL)
1265             sfree(s);
1266         freetree234(ss->sets);
1267         sfree(ss);
1268         sfree(std->next);
1269     }
1270
1271     return nperturbs;
1272 }
1273
1274 /* ----------------------------------------------------------------------
1275  * Grid generator which uses the above solver.
1276  */
1277
1278 struct minectx {
1279     char *grid;
1280     int w, h;
1281     int sx, sy;
1282     random_state *rs;
1283 };
1284
1285 static int mineopen(void *vctx, int x, int y)
1286 {
1287     struct minectx *ctx = (struct minectx *)vctx;
1288     int i, j, n;
1289
1290     assert(x >= 0 && x < ctx->w && y >= 0 && y < ctx->h);
1291     if (ctx->grid[y * ctx->w + x])
1292         return -1;                     /* *bang* */
1293
1294     n = 0;
1295     for (i = -1; i <= +1; i++) {
1296         if (x + i < 0 || x + i >= ctx->w)
1297             continue;
1298         for (j = -1; j <= +1; j++) {
1299             if (y + j < 0 || y + j >= ctx->h)
1300                 continue;
1301             if (i == 0 && j == 0)
1302                 continue;
1303             if (ctx->grid[(y+j) * ctx->w + (x+i)])
1304                 n++;
1305         }
1306     }
1307
1308     return n;
1309 }
1310
1311 /* Structure used internally to mineperturb(). */
1312 struct square {
1313     int x, y, type, random;
1314 };
1315 static int squarecmp(const void *av, const void *bv)
1316 {
1317     const struct square *a = (const struct square *)av;
1318     const struct square *b = (const struct square *)bv;
1319     if (a->type < b->type)
1320         return -1;
1321     else if (a->type > b->type)
1322         return +1;
1323     else if (a->random < b->random)
1324         return -1;
1325     else if (a->random > b->random)
1326         return +1;
1327     else if (a->y < b->y)
1328         return -1;
1329     else if (a->y > b->y)
1330         return +1;
1331     else if (a->x < b->x)
1332         return -1;
1333     else if (a->x > b->x)
1334         return +1;
1335     return 0;
1336 }
1337
1338 static struct perturbations *mineperturb(void *vctx, char *grid,
1339                                          int setx, int sety, int mask)
1340 {
1341     struct minectx *ctx = (struct minectx *)vctx;
1342     struct square *sqlist;
1343     int x, y, dx, dy, i, n, nfull, nempty;
1344     struct square *tofill[9], *toempty[9], **todo;
1345     int ntofill, ntoempty, ntodo, dtodo, dset;
1346     struct perturbations *ret;
1347
1348     /*
1349      * Make a list of all the squares in the grid which we can
1350      * possibly use. This list should be in preference order, which
1351      * means
1352      *
1353      *  - first, unknown squares on the boundary of known space
1354      *  - next, unknown squares beyond that boundary
1355      *  - as a very last resort, known squares, but not within one
1356      *    square of the starting position.
1357      *
1358      * Each of these sections needs to be shuffled independently.
1359      * We do this by preparing list of all squares and then sorting
1360      * it with a random secondary key.
1361      */
1362     sqlist = snewn(ctx->w * ctx->h, struct square);
1363     n = 0;
1364     for (y = 0; y < ctx->h; y++)
1365         for (x = 0; x < ctx->w; x++) {
1366             /*
1367              * If this square is too near the starting position,
1368              * don't put it on the list at all.
1369              */
1370             if (abs(y - ctx->sy) <= 1 && abs(x - ctx->sx) <= 1)
1371                 continue;
1372
1373             /*
1374              * If this square is in the input set, also don't put
1375              * it on the list!
1376              */
1377             if (x >= setx && x < setx + 3 &&
1378                 y >= sety && y < sety + 3 &&
1379                 mask & (1 << ((y-sety)*3+(x-setx))))
1380                 continue;
1381
1382             sqlist[n].x = x;
1383             sqlist[n].y = y;
1384
1385             if (grid[y*ctx->w+x] != -2) {
1386                 sqlist[n].type = 3;    /* known square */
1387             } else {
1388                 /*
1389                  * Unknown square. Examine everything around it and
1390                  * see if it borders on any known squares. If it
1391                  * does, it's class 1, otherwise it's 2.
1392                  */
1393
1394                 sqlist[n].type = 2;
1395
1396                 for (dy = -1; dy <= +1; dy++)
1397                     for (dx = -1; dx <= +1; dx++)
1398                         if (x+dx >= 0 && x+dx < ctx->w &&
1399                             y+dy >= 0 && y+dy < ctx->h &&
1400                             grid[(y+dy)*ctx->w+(x+dx)] != -2) {
1401                             sqlist[n].type = 1;
1402                             break;
1403                         }
1404             }
1405
1406             /*
1407              * Finally, a random number to cause qsort to
1408              * shuffle within each group.
1409              */
1410             sqlist[n].random = random_bits(ctx->rs, 31);
1411
1412             n++;
1413         }
1414
1415     qsort(sqlist, n, sizeof(struct square), squarecmp);
1416
1417     /*
1418      * Now count up the number of full and empty squares in the set
1419      * we've been provided.
1420      */
1421     nfull = nempty = 0;
1422     for (dy = 0; dy < 3; dy++)
1423         for (dx = 0; dx < 3; dx++)
1424             if (mask & (1 << (dy*3+dx))) {
1425                 assert(setx+dx <= ctx->w);
1426                 assert(sety+dy <= ctx->h);
1427                 if (ctx->grid[(sety+dy)*ctx->w+(setx+dx)])
1428                     nfull++;
1429                 else
1430                     nempty++;
1431             }
1432
1433     /*
1434      * Now go through our sorted list until we find either `nfull'
1435      * empty squares, or `nempty' full squares; these will be
1436      * swapped with the appropriate squares in the set to either
1437      * fill or empty the set while keeping the same number of mines
1438      * overall.
1439      */
1440     ntofill = ntoempty = 0;
1441     for (i = 0; i < n; i++) {
1442         struct square *sq = &sqlist[i];
1443         if (ctx->grid[sq->y * ctx->w + sq->x])
1444             toempty[ntoempty++] = sq;
1445         else
1446             tofill[ntofill++] = sq;
1447         if (ntofill == nfull || ntoempty == nempty)
1448             break;
1449     }
1450
1451     /*
1452      * If this didn't work at all, I think we just give up.
1453      */
1454     if (ntofill != nfull && ntoempty != nempty) {
1455         sfree(sqlist);
1456         return NULL;
1457     }
1458
1459     /*
1460      * Now we're pretty much there. We need to either
1461      *  (a) put a mine in each of the empty squares in the set, and
1462      *      take one out of each square in `toempty'
1463      *  (b) take a mine out of each of the full squares in the set,
1464      *      and put one in each square in `tofill'
1465      * depending on which one we've found enough squares to do.
1466      *
1467      * So we start by constructing our list of changes to return to
1468      * the solver, so that it can update its data structures
1469      * efficiently rather than having to rescan the whole grid.
1470      */
1471     ret = snew(struct perturbations);
1472     if (ntofill == nfull) {
1473         todo = tofill;
1474         ntodo = ntofill;
1475         dtodo = +1;
1476         dset = -1;
1477     } else {
1478         todo = toempty;
1479         ntodo = ntoempty;
1480         dtodo = -1;
1481         dset = +1;
1482     }
1483     ret->n = 2 * ntodo;
1484     ret->changes = snewn(ret->n, struct perturbation);
1485     for (i = 0; i < ntodo; i++) {
1486         ret->changes[i].x = todo[i]->x;
1487         ret->changes[i].y = todo[i]->y;
1488         ret->changes[i].delta = dtodo;
1489     }
1490     /* now i == ntodo */
1491     for (dy = 0; dy < 3; dy++)
1492         for (dx = 0; dx < 3; dx++)
1493             if (mask & (1 << (dy*3+dx))) {
1494                 int currval = (ctx->grid[(sety+dy)*ctx->w+(setx+dx)] ? +1 : -1);
1495                 if (dset == -currval) {
1496                     ret->changes[i].x = setx + dx;
1497                     ret->changes[i].y = sety + dy;
1498                     ret->changes[i].delta = dset;
1499                     i++;
1500                 }
1501             }
1502     assert(i == ret->n);
1503
1504     sfree(sqlist);
1505
1506     /*
1507      * Having set up the precise list of changes we're going to
1508      * make, we now simply make them and return.
1509      */
1510     for (i = 0; i < ret->n; i++) {
1511         int delta;
1512
1513         x = ret->changes[i].x;
1514         y = ret->changes[i].y;
1515         delta = ret->changes[i].delta;
1516
1517         /*
1518          * Check we're not trying to add an existing mine or remove
1519          * an absent one.
1520          */
1521         assert((delta < 0) ^ (ctx->grid[y*ctx->w+x] == 0));
1522
1523         /*
1524          * Actually make the change.
1525          */
1526         ctx->grid[y*ctx->w+x] = (delta > 0);
1527
1528         /*
1529          * Update any numbers already present in the grid.
1530          */
1531         for (dy = -1; dy <= +1; dy++)
1532             for (dx = -1; dx <= +1; dx++)
1533                 if (x+dx >= 0 && x+dx < ctx->w &&
1534                     y+dy >= 0 && y+dy < ctx->h &&
1535                     grid[(y+dy)*ctx->w+(x+dx)] != -2) {
1536                     if (dx == 0 && dy == 0) {
1537                         /*
1538                          * The square itself is marked as known in
1539                          * the grid. Mark it as a mine if it's a
1540                          * mine, or else work out its number.
1541                          */
1542                         if (delta > 0) {
1543                             grid[y*ctx->w+x] = -1;
1544                         } else {
1545                             int dx2, dy2, minecount = 0;
1546                             for (dy2 = -1; dy2 <= +1; dy2++)
1547                                 for (dx2 = -1; dx2 <= +1; dx2++)
1548                                     if (x+dx2 >= 0 && x+dx2 < ctx->w &&
1549                                         y+dy2 >= 0 && y+dy2 < ctx->h &&
1550                                         ctx->grid[(y+dy2)*ctx->w+(x+dx2)])
1551                                         minecount++;
1552                             grid[y*ctx->w+x] = minecount;
1553                         }
1554                     } else {
1555                         if (grid[(y+dy)*ctx->w+(x+dx)] >= 0)
1556                             grid[(y+dy)*ctx->w+(x+dx)] += delta;
1557                     }
1558                 }
1559     }
1560
1561 #ifdef GENERATION_DIAGNOSTICS
1562     {
1563         int yy, xx;
1564         printf("grid after perturbing:\n");
1565         for (yy = 0; yy < ctx->h; yy++) {
1566             for (xx = 0; xx < ctx->w; xx++) {
1567                 int v = ctx->grid[yy*ctx->w+xx];
1568                 if (yy == ctx->sy && xx == ctx->sx) {
1569                     assert(!v);
1570                     putchar('S');
1571                 } else if (v) {
1572                     putchar('*');
1573                 } else {
1574                     putchar('-');
1575                 }
1576             }
1577             putchar('\n');
1578         }
1579         printf("\n");
1580     }
1581 #endif
1582
1583     return ret;
1584 }
1585
1586 static char *minegen(int w, int h, int n, int x, int y, int unique,
1587                      random_state *rs)
1588 {
1589     char *ret = snewn(w*h, char);
1590     int success;
1591
1592     do {
1593         success = FALSE;
1594
1595         memset(ret, 0, w*h);
1596
1597         /*
1598          * Start by placing n mines, none of which is at x,y or within
1599          * one square of it.
1600          */
1601         {
1602             int *tmp = snewn(w*h, int);
1603             int i, j, k, nn;
1604
1605             /*
1606              * Write down the list of possible mine locations.
1607              */
1608             k = 0;
1609             for (i = 0; i < h; i++)
1610                 for (j = 0; j < w; j++)
1611                     if (abs(i - y) > 1 || abs(j - x) > 1)
1612                         tmp[k++] = i*w+j;
1613
1614             /*
1615              * Now pick n off the list at random.
1616              */
1617             nn = n;
1618             while (nn-- > 0) {
1619                 i = random_upto(rs, k);
1620                 ret[tmp[i]] = 1;
1621                 tmp[i] = tmp[--k];
1622             }
1623
1624             sfree(tmp);
1625         }
1626
1627 #ifdef GENERATION_DIAGNOSTICS
1628         {
1629             int yy, xx;
1630             printf("grid after initial generation:\n");
1631             for (yy = 0; yy < h; yy++) {
1632                 for (xx = 0; xx < w; xx++) {
1633                     int v = ret[yy*w+xx];
1634                     if (yy == y && xx == x) {
1635                         assert(!v);
1636                         putchar('S');
1637                     } else if (v) {
1638                         putchar('*');
1639                     } else {
1640                         putchar('-');
1641                     }
1642                 }
1643                 putchar('\n');
1644             }
1645             printf("\n");
1646         }
1647 #endif
1648
1649         /*
1650          * Now set up a results grid to run the solver in, and a
1651          * context for the solver to open squares. Then run the solver
1652          * repeatedly; if the number of perturb steps ever goes up or
1653          * it ever returns -1, give up completely.
1654          *
1655          * We bypass this bit if we're not after a unique grid.
1656          */
1657         if (unique) {
1658             char *solvegrid = snewn(w*h, char);
1659             struct minectx actx, *ctx = &actx;
1660             int solveret, prevret = -2;
1661
1662             ctx->grid = ret;
1663             ctx->w = w;
1664             ctx->h = h;
1665             ctx->sx = x;
1666             ctx->sy = y;
1667             ctx->rs = rs;
1668
1669             while (1) {
1670                 memset(solvegrid, -2, w*h);
1671                 solvegrid[y*w+x] = mineopen(ctx, x, y);
1672                 assert(solvegrid[y*w+x] == 0); /* by deliberate arrangement */
1673
1674                 solveret =
1675                     minesolve(w, h, n, solvegrid, mineopen, mineperturb, ctx, rs);
1676                 if (solveret < 0 || (prevret >= 0 && solveret >= prevret)) {
1677                     success = FALSE;
1678                     break;
1679                 } else if (solveret == 0) {
1680                     success = TRUE;
1681                     break;
1682                 }
1683             }
1684
1685             sfree(solvegrid);
1686         } else {
1687             success = TRUE;
1688         }
1689
1690     } while (!success);
1691
1692     return ret;
1693 }
1694
1695 /*
1696  * The Mines game descriptions contain the location of every mine,
1697  * and can therefore be used to cheat.
1698  *
1699  * It would be pointless to attempt to _prevent_ this form of
1700  * cheating by encrypting the description, since Mines is
1701  * open-source so anyone can find out the encryption key. However,
1702  * I think it is worth doing a bit of gentle obfuscation to prevent
1703  * _accidental_ spoilers: if you happened to note that the game ID
1704  * starts with an F, for example, you might be unable to put the
1705  * knowledge of those mines out of your mind while playing. So,
1706  * just as discussions of film endings are rot13ed to avoid
1707  * spoiling it for people who don't want to be told, we apply a
1708  * keyless, reversible, but visually completely obfuscatory masking
1709  * function to the mine bitmap.
1710  */
1711 static void obfuscate_bitmap(unsigned char *bmp, int bits, int decode)
1712 {
1713     int bytes, firsthalf, secondhalf;
1714     struct step {
1715         unsigned char *seedstart;
1716         int seedlen;
1717         unsigned char *targetstart;
1718         int targetlen;
1719     } steps[2];
1720     int i, j;
1721
1722     /*
1723      * My obfuscation algorithm is similar in concept to the OAEP
1724      * encoding used in some forms of RSA. Here's a specification
1725      * of it:
1726      *
1727      *  + We have a `masking function' which constructs a stream of
1728      *    pseudorandom bytes from a seed of some number of input
1729      *    bytes.
1730      *
1731      *  + We pad out our input bit stream to a whole number of
1732      *    bytes by adding up to 7 zero bits on the end. (In fact
1733      *    the bitmap passed as input to this function will already
1734      *    have had this done in practice.)
1735      *
1736      *  + We divide the _byte_ stream exactly in half, rounding the
1737      *    half-way position _down_. So an 81-bit input string, for
1738      *    example, rounds up to 88 bits or 11 bytes, and then
1739      *    dividing by two gives 5 bytes in the first half and 6 in
1740      *    the second half.
1741      *
1742      *  + We generate a mask from the second half of the bytes, and
1743      *    XOR it over the first half.
1744      *
1745      *  + We generate a mask from the (encoded) first half of the
1746      *    bytes, and XOR it over the second half. Any null bits at
1747      *    the end which were added as padding are cleared back to
1748      *    zero even if this operation would have made them nonzero.
1749      *
1750      * To de-obfuscate, the steps are precisely the same except
1751      * that the final two are reversed.
1752      *
1753      * Finally, our masking function. Given an input seed string of
1754      * bytes, the output mask consists of concatenating the SHA-1
1755      * hashes of the seed string and successive decimal integers,
1756      * starting from 0.
1757      */
1758
1759     bytes = (bits + 7) / 8;
1760     firsthalf = bytes / 2;
1761     secondhalf = bytes - firsthalf;
1762
1763     steps[decode ? 1 : 0].seedstart = bmp + firsthalf;
1764     steps[decode ? 1 : 0].seedlen = secondhalf;
1765     steps[decode ? 1 : 0].targetstart = bmp;
1766     steps[decode ? 1 : 0].targetlen = firsthalf;
1767
1768     steps[decode ? 0 : 1].seedstart = bmp;
1769     steps[decode ? 0 : 1].seedlen = firsthalf;
1770     steps[decode ? 0 : 1].targetstart = bmp + firsthalf;
1771     steps[decode ? 0 : 1].targetlen = secondhalf;
1772
1773     for (i = 0; i < 2; i++) {
1774         SHA_State base, final;
1775         unsigned char digest[20];
1776         char numberbuf[80];
1777         int digestpos = 20, counter = 0;
1778
1779         SHA_Init(&base);
1780         SHA_Bytes(&base, steps[i].seedstart, steps[i].seedlen);
1781
1782         for (j = 0; j < steps[i].targetlen; j++) {
1783             if (digestpos >= 20) {
1784                 sprintf(numberbuf, "%d", counter++);
1785                 final = base;
1786                 SHA_Bytes(&final, numberbuf, strlen(numberbuf));
1787                 SHA_Final(&final, digest);
1788                 digestpos = 0;
1789             }
1790             steps[i].targetstart[j] ^= digest[digestpos]++;
1791         }
1792
1793         /*
1794          * Mask off the pad bits in the final byte after both steps.
1795          */
1796         if (bits % 8)
1797             bmp[bits / 8] &= 0xFF & (0xFF00 >> (bits % 8));
1798     }
1799 }
1800
1801 static char *new_mine_layout(int w, int h, int n, int x, int y, int unique,
1802                              random_state *rs, char **game_desc)
1803 {
1804     char *grid, *ret, *p;
1805     unsigned char *bmp;
1806     int i, area;
1807
1808     grid = minegen(w, h, n, x, y, unique, rs);
1809
1810     if (game_desc) {
1811         /*
1812          * Set up the mine bitmap and obfuscate it.
1813          */
1814         area = w * h;
1815         bmp = snewn((area + 7) / 8, unsigned char);
1816         memset(bmp, 0, (area + 7) / 8);
1817         for (i = 0; i < area; i++) {
1818             if (grid[i])
1819                 bmp[i / 8] |= 0x80 >> (i % 8);
1820         }
1821         obfuscate_bitmap(bmp, area, FALSE);
1822
1823         /*
1824          * Now encode the resulting bitmap in hex. We can work to
1825          * nibble rather than byte granularity, since the obfuscation
1826          * function guarantees to return a bit string of the same
1827          * length as its input.
1828          */
1829         ret = snewn((area+3)/4 + 100, char);
1830         p = ret + sprintf(ret, "%d,%d,m", x, y);   /* 'm' == masked */
1831         for (i = 0; i < (area+3)/4; i++) {
1832             int v = bmp[i/2];
1833             if (i % 2 == 0)
1834                 v >>= 4;
1835             *p++ = "0123456789abcdef"[v & 0xF];
1836         }
1837         *p = '\0';
1838
1839         sfree(bmp);
1840
1841         *game_desc = ret;
1842     }
1843
1844     return grid;
1845 }
1846
1847 static char *new_game_desc(game_params *params, random_state *rs,
1848                            game_aux_info **aux)
1849 {
1850 #ifdef PREOPENED
1851     int x = random_upto(rs, params->w);
1852     int y = random_upto(rs, params->h);
1853     char *grid, *desc;
1854
1855     grid = new_mine_layout(params->w, params->h, params->n,
1856                            x, y, params->unique, rs);
1857 #else
1858     char *rsdesc, *desc;
1859
1860     rsdesc = random_state_encode(rs);
1861     desc = snewn(strlen(rsdesc) + 100, char);
1862     sprintf(desc, "r%d,%c,%s", params->n, params->unique ? 'u' : 'a', rsdesc);
1863     sfree(rsdesc);
1864     return desc;
1865 #endif
1866 }
1867
1868 static void game_free_aux_info(game_aux_info *aux)
1869 {
1870     assert(!"Shouldn't happen");
1871 }
1872
1873 static char *validate_desc(game_params *params, char *desc)
1874 {
1875     int wh = params->w * params->h;
1876     int x, y;
1877
1878     if (*desc == 'r') {
1879         if (!*desc || !isdigit((unsigned char)*desc))
1880             return "No initial mine count in game description";
1881         while (*desc && isdigit((unsigned char)*desc))
1882             desc++;                    /* skip over mine count */
1883         if (*desc != ',')
1884             return "No ',' after initial x-coordinate in game description";
1885         desc++;
1886         if (*desc != 'u' && *desc != 'a')
1887             return "No uniqueness specifier in game description";
1888         desc++;
1889         if (*desc != ',')
1890             return "No ',' after uniqueness specifier in game description";
1891         /* now ignore the rest */
1892     } else {
1893         if (!*desc || !isdigit((unsigned char)*desc))
1894             return "No initial x-coordinate in game description";
1895         x = atoi(desc);
1896         if (x < 0 || x >= params->w)
1897             return "Initial x-coordinate was out of range";
1898         while (*desc && isdigit((unsigned char)*desc))
1899             desc++;                    /* skip over x coordinate */
1900         if (*desc != ',')
1901             return "No ',' after initial x-coordinate in game description";
1902         desc++;                        /* eat comma */
1903         if (!*desc || !isdigit((unsigned char)*desc))
1904             return "No initial y-coordinate in game description";
1905         y = atoi(desc);
1906         if (y < 0 || y >= params->h)
1907             return "Initial y-coordinate was out of range";
1908         while (*desc && isdigit((unsigned char)*desc))
1909             desc++;                    /* skip over y coordinate */
1910         if (*desc != ',')
1911             return "No ',' after initial y-coordinate in game description";
1912         desc++;                        /* eat comma */
1913         /* eat `m', meaning `masked', if present */
1914         if (*desc == 'm')
1915             desc++;
1916         /* now just check length of remainder */
1917         if (strlen(desc) != (wh+3)/4)
1918             return "Game description is wrong length";
1919     }
1920
1921     return NULL;
1922 }
1923
1924 static int open_square(game_state *state, int x, int y)
1925 {
1926     int w = state->w, h = state->h;
1927     int xx, yy, nmines, ncovered;
1928
1929     if (!state->layout->mines) {
1930         /*
1931          * We have a preliminary game in which the mine layout
1932          * hasn't been generated yet. Generate it based on the
1933          * initial click location.
1934          */
1935         char *desc;
1936         state->layout->mines = new_mine_layout(w, h, state->layout->n,
1937                                                x, y, state->layout->unique,
1938                                                state->layout->rs,
1939                                                &desc);
1940         midend_supersede_game_desc(state->layout->me, desc);
1941         sfree(desc);
1942         random_free(state->layout->rs);
1943         state->layout->rs = NULL;
1944     }
1945
1946     if (state->layout->mines[y*w+x]) {
1947         /*
1948          * The player has landed on a mine. Bad luck. Expose all
1949          * the mines.
1950          */
1951         state->dead = TRUE;
1952         for (yy = 0; yy < h; yy++)
1953             for (xx = 0; xx < w; xx++) {
1954                 if (state->layout->mines[yy*w+xx] &&
1955                     (state->grid[yy*w+xx] == -2 ||
1956                      state->grid[yy*w+xx] == -3)) {
1957                     state->grid[yy*w+xx] = 64;
1958                 }
1959                 if (!state->layout->mines[yy*w+xx] &&
1960                     state->grid[yy*w+xx] == -1) {
1961                     state->grid[yy*w+xx] = 66;
1962                 }
1963             }
1964         state->grid[y*w+x] = 65;
1965         return -1;
1966     }
1967
1968     /*
1969      * Otherwise, the player has opened a safe square. Mark it to-do.
1970      */
1971     state->grid[y*w+x] = -10;          /* `todo' value internal to this func */
1972
1973     /*
1974      * Now go through the grid finding all `todo' values and
1975      * opening them. Every time one of them turns out to have no
1976      * neighbouring mines, we add all its unopened neighbours to
1977      * the list as well.
1978      *
1979      * FIXME: We really ought to be able to do this better than
1980      * using repeated N^2 scans of the grid.
1981      */
1982     while (1) {
1983         int done_something = FALSE;
1984
1985         for (yy = 0; yy < h; yy++)
1986             for (xx = 0; xx < w; xx++)
1987                 if (state->grid[yy*w+xx] == -10) {
1988                     int dx, dy, v;
1989
1990                     assert(!state->layout->mines[yy*w+xx]);
1991
1992                     v = 0;
1993
1994                     for (dx = -1; dx <= +1; dx++)
1995                         for (dy = -1; dy <= +1; dy++)
1996                             if (xx+dx >= 0 && xx+dx < state->w &&
1997                                 yy+dy >= 0 && yy+dy < state->h &&
1998                                 state->layout->mines[(yy+dy)*w+(xx+dx)])
1999                                 v++;
2000
2001                     state->grid[yy*w+xx] = v;
2002
2003                     if (v == 0) {
2004                         for (dx = -1; dx <= +1; dx++)
2005                             for (dy = -1; dy <= +1; dy++)
2006                                 if (xx+dx >= 0 && xx+dx < state->w &&
2007                                     yy+dy >= 0 && yy+dy < state->h &&
2008                                     state->grid[(yy+dy)*w+(xx+dx)] == -2)
2009                                     state->grid[(yy+dy)*w+(xx+dx)] = -10;
2010                     }
2011
2012                     done_something = TRUE;
2013                 }
2014
2015         if (!done_something)
2016             break;
2017     }
2018
2019     /*
2020      * Finally, scan the grid and see if exactly as many squares
2021      * are still covered as there are mines. If so, set the `won'
2022      * flag and fill in mine markers on all covered squares.
2023      */
2024     nmines = ncovered = 0;
2025     for (yy = 0; yy < h; yy++)
2026         for (xx = 0; xx < w; xx++) {
2027             if (state->grid[yy*w+xx] < 0)
2028                 ncovered++;
2029             if (state->layout->mines[yy*w+xx])
2030                 nmines++;
2031         }
2032     assert(ncovered >= nmines);
2033     if (ncovered == nmines) {
2034         for (yy = 0; yy < h; yy++)
2035             for (xx = 0; xx < w; xx++) {
2036                 if (state->grid[yy*w+xx] < 0)
2037                     state->grid[yy*w+xx] = -1;
2038         }
2039         state->won = TRUE;
2040     }
2041
2042     return 0;
2043 }
2044
2045 static game_state *new_game(midend_data *me, game_params *params, char *desc)
2046 {
2047     game_state *state = snew(game_state);
2048     int i, wh, x, y, ret, masked;
2049     unsigned char *bmp;
2050
2051     state->w = params->w;
2052     state->h = params->h;
2053     state->n = params->n;
2054     state->dead = state->won = FALSE;
2055
2056     wh = state->w * state->h;
2057
2058     state->layout = snew(struct mine_layout);
2059     state->layout->refcount = 1;
2060
2061     state->grid = snewn(wh, char);
2062     memset(state->grid, -2, wh);
2063
2064     if (*desc == 'r') {
2065         desc++;
2066         state->layout->n = atoi(desc);
2067         while (*desc && isdigit((unsigned char)*desc))
2068             desc++;                    /* skip over mine count */
2069         if (*desc) desc++;             /* eat comma */
2070         if (*desc == 'a')
2071             state->layout->unique = FALSE;
2072         else
2073             state->layout->unique = TRUE;
2074         desc++;
2075         if (*desc) desc++;             /* eat comma */
2076
2077         state->layout->mines = NULL;
2078         state->layout->rs = random_state_decode(desc);
2079         state->layout->me = me;
2080
2081     } else {
2082
2083         state->layout->mines = snewn(wh, char);
2084         x = atoi(desc);
2085         while (*desc && isdigit((unsigned char)*desc))
2086             desc++;                    /* skip over x coordinate */
2087         if (*desc) desc++;             /* eat comma */
2088         y = atoi(desc);
2089         while (*desc && isdigit((unsigned char)*desc))
2090             desc++;                    /* skip over y coordinate */
2091         if (*desc) desc++;             /* eat comma */
2092
2093         if (*desc == 'm') {
2094             masked = TRUE;
2095             desc++;
2096         } else {
2097             /*
2098              * We permit game IDs to be entered by hand without the
2099              * masking transformation.
2100              */
2101             masked = FALSE;
2102         }
2103
2104         bmp = snewn((wh + 7) / 8, unsigned char);
2105         memset(bmp, 0, (wh + 7) / 8);
2106         for (i = 0; i < (wh+3)/4; i++) {
2107             int c = desc[i];
2108             int v;
2109
2110             assert(c != 0);            /* validate_desc should have caught */
2111             if (c >= '0' && c <= '9')
2112                 v = c - '0';
2113             else if (c >= 'a' && c <= 'f')
2114                 v = c - 'a' + 10;
2115             else if (c >= 'A' && c <= 'F')
2116                 v = c - 'A' + 10;
2117             else
2118                 v = 0;
2119
2120             bmp[i / 2] |= v << (4 * (1 - (i % 2)));
2121         }
2122
2123         if (masked)
2124             obfuscate_bitmap(bmp, wh, TRUE);
2125
2126         memset(state->layout->mines, 0, wh);
2127         for (i = 0; i < wh; i++) {
2128             if (bmp[i / 8] & (0x80 >> (i % 8)))
2129                 state->layout->mines[i] = 1;
2130         }
2131
2132         ret = open_square(state, x, y);
2133     }
2134
2135     return state;
2136 }
2137
2138 static game_state *dup_game(game_state *state)
2139 {
2140     game_state *ret = snew(game_state);
2141
2142     ret->w = state->w;
2143     ret->h = state->h;
2144     ret->n = state->n;
2145     ret->dead = state->dead;
2146     ret->won = state->won;
2147     ret->layout = state->layout;
2148     ret->layout->refcount++;
2149     ret->grid = snewn(ret->w * ret->h, char);
2150     memcpy(ret->grid, state->grid, ret->w * ret->h);
2151
2152     return ret;
2153 }
2154
2155 static void free_game(game_state *state)
2156 {
2157     if (--state->layout->refcount <= 0) {
2158         sfree(state->layout->mines);
2159         if (state->layout->rs)
2160             random_free(state->layout->rs);
2161         sfree(state->layout);
2162     }
2163     sfree(state->grid);
2164     sfree(state);
2165 }
2166
2167 static game_state *solve_game(game_state *state, game_aux_info *aux,
2168                               char **error)
2169 {
2170     return NULL;
2171 }
2172
2173 static char *game_text_format(game_state *state)
2174 {
2175     return NULL;
2176 }
2177
2178 struct game_ui {
2179     int hx, hy, hradius;               /* for mouse-down highlights */
2180     int flash_is_death;
2181 };
2182
2183 static game_ui *new_ui(game_state *state)
2184 {
2185     game_ui *ui = snew(game_ui);
2186     ui->hx = ui->hy = -1;
2187     ui->hradius = 0;
2188     ui->flash_is_death = FALSE;        /* *shrug* */
2189     return ui;
2190 }
2191
2192 static void free_ui(game_ui *ui)
2193 {
2194     sfree(ui);
2195 }
2196
2197 static game_state *make_move(game_state *from, game_ui *ui, int x, int y,
2198                              int button)
2199 {
2200     game_state *ret;
2201     int cx, cy;
2202
2203     if (from->dead || from->won)
2204         return NULL;                   /* no further moves permitted */
2205
2206     if (!IS_MOUSE_DOWN(button) && !IS_MOUSE_DRAG(button) &&
2207         !IS_MOUSE_RELEASE(button))
2208         return NULL;
2209
2210     cx = FROMCOORD(x);
2211     cy = FROMCOORD(y);
2212     if (cx < 0 || cx >= from->w || cy < 0 || cy > from->h)
2213         return NULL;
2214
2215     if (button == LEFT_BUTTON || button == LEFT_DRAG) {
2216         /*
2217          * Mouse-downs and mouse-drags just cause highlighting
2218          * updates.
2219          */
2220         ui->hx = cx;
2221         ui->hy = cy;
2222         ui->hradius = (from->grid[cy*from->w+cx] >= 0 ? 1 : 0);
2223         return from;
2224     }
2225
2226     if (button == RIGHT_BUTTON) {
2227         /*
2228          * Right-clicking only works on a covered square, and it
2229          * toggles between -1 (marked as mine) and -2 (not marked
2230          * as mine).
2231          *
2232          * FIXME: question marks.
2233          */
2234         if (from->grid[cy * from->w + cx] != -2 &&
2235             from->grid[cy * from->w + cx] != -1)
2236             return NULL;
2237
2238         ret = dup_game(from);
2239         ret->grid[cy * from->w + cx] ^= (-2 ^ -1);
2240
2241         return ret;
2242     }
2243
2244     if (button == LEFT_RELEASE) {
2245         ui->hx = ui->hy = -1;
2246         ui->hradius = 0;
2247
2248         /*
2249          * At this stage we must never return NULL: we have adjusted
2250          * the ui, so at worst we return `from'.
2251          */
2252
2253         /*
2254          * Left-clicking on a covered square opens a tile. Not
2255          * permitted if the tile is marked as a mine, for safety.
2256          * (Unmark it and _then_ open it.)
2257          */
2258         if (from->grid[cy * from->w + cx] == -2 ||
2259             from->grid[cy * from->w + cx] == -3) {
2260             ret = dup_game(from);
2261             open_square(ret, cx, cy);
2262             return ret;
2263         }
2264
2265         /*
2266          * Left-clicking on an uncovered tile: first we check to see if
2267          * the number of mine markers surrounding the tile is equal to
2268          * its mine count, and if so then we open all other surrounding
2269          * squares.
2270          */
2271         if (from->grid[cy * from->w + cx] > 0) {
2272             int dy, dx, n;
2273
2274             /* Count mine markers. */
2275             n = 0;
2276             for (dy = -1; dy <= +1; dy++)
2277                 for (dx = -1; dx <= +1; dx++)
2278                     if (cx+dx >= 0 && cx+dx < from->w &&
2279                         cy+dy >= 0 && cy+dy < from->h) {
2280                         if (from->grid[(cy+dy)*from->w+(cx+dx)] == -1)
2281                             n++;
2282                     }
2283
2284             if (n == from->grid[cy * from->w + cx]) {
2285                 ret = dup_game(from);
2286                 for (dy = -1; dy <= +1; dy++)
2287                     for (dx = -1; dx <= +1; dx++)
2288                         if (cx+dx >= 0 && cx+dx < ret->w &&
2289                             cy+dy >= 0 && cy+dy < ret->h &&
2290                             (ret->grid[(cy+dy)*ret->w+(cx+dx)] == -2 ||
2291                              ret->grid[(cy+dy)*ret->w+(cx+dx)] == -3))
2292                             open_square(ret, cx+dx, cy+dy);
2293                 return ret;
2294             }
2295         }
2296
2297         return from;
2298     }
2299
2300     return NULL;
2301 }
2302
2303 /* ----------------------------------------------------------------------
2304  * Drawing routines.
2305  */
2306
2307 struct game_drawstate {
2308     int w, h, started;
2309     char *grid;
2310     /*
2311      * Items in this `grid' array have all the same values as in
2312      * the game_state grid, and in addition:
2313      *
2314      *  - -10 means the tile was drawn `specially' as a result of a
2315      *    flash, so it will always need redrawing.
2316      *
2317      *  - -22 and -23 mean the tile is highlighted for a possible
2318      *    click.
2319      */
2320 };
2321
2322 static void game_size(game_params *params, int *x, int *y)
2323 {
2324     *x = BORDER * 2 + TILE_SIZE * params->w;
2325     *y = BORDER * 2 + TILE_SIZE * params->h;
2326 }
2327
2328 static float *game_colours(frontend *fe, game_state *state, int *ncolours)
2329 {
2330     float *ret = snewn(3 * NCOLOURS, float);
2331
2332     frontend_default_colour(fe, &ret[COL_BACKGROUND * 3]);
2333
2334     ret[COL_1 * 3 + 0] = 0.0F;
2335     ret[COL_1 * 3 + 1] = 0.0F;
2336     ret[COL_1 * 3 + 2] = 1.0F;
2337
2338     ret[COL_2 * 3 + 0] = 0.0F;
2339     ret[COL_2 * 3 + 1] = 0.5F;
2340     ret[COL_2 * 3 + 2] = 0.0F;
2341
2342     ret[COL_3 * 3 + 0] = 1.0F;
2343     ret[COL_3 * 3 + 1] = 0.0F;
2344     ret[COL_3 * 3 + 2] = 0.0F;
2345
2346     ret[COL_4 * 3 + 0] = 0.0F;
2347     ret[COL_4 * 3 + 1] = 0.0F;
2348     ret[COL_4 * 3 + 2] = 0.5F;
2349
2350     ret[COL_5 * 3 + 0] = 0.5F;
2351     ret[COL_5 * 3 + 1] = 0.0F;
2352     ret[COL_5 * 3 + 2] = 0.0F;
2353
2354     ret[COL_6 * 3 + 0] = 0.0F;
2355     ret[COL_6 * 3 + 1] = 0.5F;
2356     ret[COL_6 * 3 + 2] = 0.5F;
2357
2358     ret[COL_7 * 3 + 0] = 0.0F;
2359     ret[COL_7 * 3 + 1] = 0.0F;
2360     ret[COL_7 * 3 + 2] = 0.0F;
2361
2362     ret[COL_8 * 3 + 0] = 0.5F;
2363     ret[COL_8 * 3 + 1] = 0.5F;
2364     ret[COL_8 * 3 + 2] = 0.5F;
2365
2366     ret[COL_MINE * 3 + 0] = 0.0F;
2367     ret[COL_MINE * 3 + 1] = 0.0F;
2368     ret[COL_MINE * 3 + 2] = 0.0F;
2369
2370     ret[COL_BANG * 3 + 0] = 1.0F;
2371     ret[COL_BANG * 3 + 1] = 0.0F;
2372     ret[COL_BANG * 3 + 2] = 0.0F;
2373
2374     ret[COL_CROSS * 3 + 0] = 1.0F;
2375     ret[COL_CROSS * 3 + 1] = 0.0F;
2376     ret[COL_CROSS * 3 + 2] = 0.0F;
2377
2378     ret[COL_FLAG * 3 + 0] = 1.0F;
2379     ret[COL_FLAG * 3 + 1] = 0.0F;
2380     ret[COL_FLAG * 3 + 2] = 0.0F;
2381
2382     ret[COL_FLAGBASE * 3 + 0] = 0.0F;
2383     ret[COL_FLAGBASE * 3 + 1] = 0.0F;
2384     ret[COL_FLAGBASE * 3 + 2] = 0.0F;
2385
2386     ret[COL_QUERY * 3 + 0] = 0.0F;
2387     ret[COL_QUERY * 3 + 1] = 0.0F;
2388     ret[COL_QUERY * 3 + 2] = 0.0F;
2389
2390     ret[COL_HIGHLIGHT * 3 + 0] = 1.0F;
2391     ret[COL_HIGHLIGHT * 3 + 1] = 1.0F;
2392     ret[COL_HIGHLIGHT * 3 + 2] = 1.0F;
2393
2394     ret[COL_LOWLIGHT * 3 + 0] = ret[COL_BACKGROUND * 3 + 0] * 2.0 / 3.0;
2395     ret[COL_LOWLIGHT * 3 + 1] = ret[COL_BACKGROUND * 3 + 1] * 2.0 / 3.0;
2396     ret[COL_LOWLIGHT * 3 + 2] = ret[COL_BACKGROUND * 3 + 2] * 2.0 / 3.0;
2397
2398     *ncolours = NCOLOURS;
2399     return ret;
2400 }
2401
2402 static game_drawstate *game_new_drawstate(game_state *state)
2403 {
2404     struct game_drawstate *ds = snew(struct game_drawstate);
2405
2406     ds->w = state->w;
2407     ds->h = state->h;
2408     ds->started = FALSE;
2409     ds->grid = snewn(ds->w * ds->h, char);
2410
2411     memset(ds->grid, -99, ds->w * ds->h);
2412
2413     return ds;
2414 }
2415
2416 static void game_free_drawstate(game_drawstate *ds)
2417 {
2418     sfree(ds->grid);
2419     sfree(ds);
2420 }
2421
2422 static void draw_tile(frontend *fe, int x, int y, int v, int bg)
2423 {
2424     if (v < 0) {
2425         int coords[12];
2426         int hl = 0;
2427
2428         if (v == -22 || v == -23) {
2429             v += 20;
2430
2431             /*
2432              * Omit the highlights in this case.
2433              */
2434             draw_rect(fe, x, y, TILE_SIZE, TILE_SIZE, bg);
2435             draw_line(fe, x, y, x + TILE_SIZE - 1, y, COL_LOWLIGHT);
2436             draw_line(fe, x, y, x, y + TILE_SIZE - 1, COL_LOWLIGHT);
2437         } else {
2438             /*
2439              * Draw highlights to indicate the square is covered.
2440              */
2441             coords[0] = x + TILE_SIZE - 1;
2442             coords[1] = y + TILE_SIZE - 1;
2443             coords[2] = x + TILE_SIZE - 1;
2444             coords[3] = y;
2445             coords[4] = x;
2446             coords[5] = y + TILE_SIZE - 1;
2447             draw_polygon(fe, coords, 3, TRUE, COL_LOWLIGHT ^ hl);
2448             draw_polygon(fe, coords, 3, FALSE, COL_LOWLIGHT ^ hl);
2449
2450             coords[0] = x;
2451             coords[1] = y;
2452             draw_polygon(fe, coords, 3, TRUE, COL_HIGHLIGHT ^ hl);
2453             draw_polygon(fe, coords, 3, FALSE, COL_HIGHLIGHT ^ hl);
2454
2455             draw_rect(fe, x + HIGHLIGHT_WIDTH, y + HIGHLIGHT_WIDTH,
2456                       TILE_SIZE - 2*HIGHLIGHT_WIDTH, TILE_SIZE - 2*HIGHLIGHT_WIDTH,
2457                       bg);
2458         }
2459
2460         if (v == -1) {
2461             /*
2462              * Draw a flag.
2463              */
2464 #define SETCOORD(n, dx, dy) do { \
2465     coords[(n)*2+0] = x + TILE_SIZE * (dx); \
2466     coords[(n)*2+1] = y + TILE_SIZE * (dy); \
2467 } while (0)
2468             SETCOORD(0, 0.6, 0.35);
2469             SETCOORD(1, 0.6, 0.7);
2470             SETCOORD(2, 0.8, 0.8);
2471             SETCOORD(3, 0.25, 0.8);
2472             SETCOORD(4, 0.55, 0.7);
2473             SETCOORD(5, 0.55, 0.35);
2474             draw_polygon(fe, coords, 6, TRUE, COL_FLAGBASE);
2475             draw_polygon(fe, coords, 6, FALSE, COL_FLAGBASE);
2476
2477             SETCOORD(0, 0.6, 0.2);
2478             SETCOORD(1, 0.6, 0.5);
2479             SETCOORD(2, 0.2, 0.35);
2480             draw_polygon(fe, coords, 3, TRUE, COL_FLAG);
2481             draw_polygon(fe, coords, 3, FALSE, COL_FLAG);
2482 #undef SETCOORD
2483
2484         } else if (v == -3) {
2485             /*
2486              * Draw a question mark.
2487              */
2488             draw_text(fe, x + TILE_SIZE / 2, y + TILE_SIZE / 2,
2489                       FONT_VARIABLE, TILE_SIZE * 6 / 8,
2490                       ALIGN_VCENTRE | ALIGN_HCENTRE,
2491                       COL_QUERY, "?");
2492         }
2493     } else {
2494         /*
2495          * Clear the square to the background colour, and draw thin
2496          * grid lines along the top and left.
2497          *
2498          * Exception is that for value 65 (mine we've just trodden
2499          * on), we clear the square to COL_BANG.
2500          */
2501         draw_rect(fe, x, y, TILE_SIZE, TILE_SIZE,
2502                   (v == 65 ? COL_BANG : bg));
2503         draw_line(fe, x, y, x + TILE_SIZE - 1, y, COL_LOWLIGHT);
2504         draw_line(fe, x, y, x, y + TILE_SIZE - 1, COL_LOWLIGHT);
2505
2506         if (v > 0 && v <= 8) {
2507             /*
2508              * Mark a number.
2509              */
2510             char str[2];
2511             str[0] = v + '0';
2512             str[1] = '\0';
2513             draw_text(fe, x + TILE_SIZE / 2, y + TILE_SIZE / 2,
2514                       FONT_VARIABLE, TILE_SIZE * 7 / 8,
2515                       ALIGN_VCENTRE | ALIGN_HCENTRE,
2516                       (COL_1 - 1) + v, str);
2517
2518         } else if (v >= 64) {
2519             /*
2520              * Mark a mine.
2521              *
2522              * FIXME: this could be done better!
2523              */
2524 #if 0
2525             draw_text(fe, x + TILE_SIZE / 2, y + TILE_SIZE / 2,
2526                       FONT_VARIABLE, TILE_SIZE * 7 / 8,
2527                       ALIGN_VCENTRE | ALIGN_HCENTRE,
2528                       COL_MINE, "*");
2529 #else
2530             {
2531                 int cx = x + TILE_SIZE / 2;
2532                 int cy = y + TILE_SIZE / 2;
2533                 int r = TILE_SIZE / 2 - 3;
2534                 int coords[4*5*2];
2535                 int xdx = 1, xdy = 0, ydx = 0, ydy = 1;
2536                 int tdx, tdy, i;
2537
2538                 for (i = 0; i < 4*5*2; i += 5*2) {
2539                     coords[i+2*0+0] = cx - r/6*xdx + r*4/5*ydx;
2540                     coords[i+2*0+1] = cy - r/6*xdy + r*4/5*ydy;
2541                     coords[i+2*1+0] = cx - r/6*xdx + r*ydx;
2542                     coords[i+2*1+1] = cy - r/6*xdy + r*ydy;
2543                     coords[i+2*2+0] = cx + r/6*xdx + r*ydx;
2544                     coords[i+2*2+1] = cy + r/6*xdy + r*ydy;
2545                     coords[i+2*3+0] = cx + r/6*xdx + r*4/5*ydx;
2546                     coords[i+2*3+1] = cy + r/6*xdy + r*4/5*ydy;
2547                     coords[i+2*4+0] = cx + r*3/5*xdx + r*3/5*ydx;
2548                     coords[i+2*4+1] = cy + r*3/5*xdy + r*3/5*ydy;
2549
2550                     tdx = ydx;
2551                     tdy = ydy;
2552                     ydx = xdx;
2553                     ydy = xdy;
2554                     xdx = -tdx;
2555                     xdy = -tdy;
2556                 }
2557
2558                 draw_polygon(fe, coords, 5*4, TRUE, COL_MINE);
2559                 draw_polygon(fe, coords, 5*4, FALSE, COL_MINE);
2560
2561                 draw_rect(fe, cx-r/3, cy-r/3, r/3, r/4, COL_HIGHLIGHT);
2562             }
2563 #endif
2564
2565             if (v == 66) {
2566                 /*
2567                  * Cross through the mine.
2568                  */
2569                 int dx;
2570                 for (dx = -1; dx <= +1; dx++) {
2571                     draw_line(fe, x + 3 + dx, y + 2,
2572                               x + TILE_SIZE - 3 + dx,
2573                               y + TILE_SIZE - 2, COL_CROSS);
2574                     draw_line(fe, x + TILE_SIZE - 3 + dx, y + 2,
2575                               x + 3 + dx, y + TILE_SIZE - 2,
2576                               COL_CROSS);
2577                 }
2578             }
2579         }
2580     }
2581
2582     draw_update(fe, x, y, TILE_SIZE, TILE_SIZE);
2583 }
2584
2585 static void game_redraw(frontend *fe, game_drawstate *ds, game_state *oldstate,
2586                         game_state *state, int dir, game_ui *ui,
2587                         float animtime, float flashtime)
2588 {
2589     int x, y;
2590     int mines, markers, bg;
2591
2592     if (flashtime) {
2593         int frame = (flashtime / FLASH_FRAME);
2594         if (frame % 2)
2595             bg = (ui->flash_is_death ? COL_BACKGROUND : COL_LOWLIGHT);
2596         else
2597             bg = (ui->flash_is_death ? COL_BANG : COL_HIGHLIGHT);
2598     } else
2599         bg = COL_BACKGROUND;
2600
2601     if (!ds->started) {
2602         int coords[6];
2603
2604         draw_rect(fe, 0, 0,
2605                   TILE_SIZE * state->w + 2 * BORDER,
2606                   TILE_SIZE * state->h + 2 * BORDER, COL_BACKGROUND);
2607         draw_update(fe, 0, 0,
2608                     TILE_SIZE * state->w + 2 * BORDER,
2609                     TILE_SIZE * state->h + 2 * BORDER);
2610
2611         /*
2612          * Recessed area containing the whole puzzle.
2613          */
2614         coords[0] = COORD(state->w) + OUTER_HIGHLIGHT_WIDTH - 1;
2615         coords[1] = COORD(state->h) + OUTER_HIGHLIGHT_WIDTH - 1;
2616         coords[2] = COORD(state->w) + OUTER_HIGHLIGHT_WIDTH - 1;
2617         coords[3] = COORD(0) - OUTER_HIGHLIGHT_WIDTH;
2618         coords[4] = COORD(0) - OUTER_HIGHLIGHT_WIDTH;
2619         coords[5] = COORD(state->h) + OUTER_HIGHLIGHT_WIDTH - 1;
2620         draw_polygon(fe, coords, 3, TRUE, COL_HIGHLIGHT);
2621         draw_polygon(fe, coords, 3, FALSE, COL_HIGHLIGHT);
2622
2623         coords[1] = COORD(0) - OUTER_HIGHLIGHT_WIDTH;
2624         coords[0] = COORD(0) - OUTER_HIGHLIGHT_WIDTH;
2625         draw_polygon(fe, coords, 3, TRUE, COL_LOWLIGHT);
2626         draw_polygon(fe, coords, 3, FALSE, COL_LOWLIGHT);
2627
2628         ds->started = TRUE;
2629     }
2630
2631     /*
2632      * Now draw the tiles. Also in this loop, count up the number
2633      * of mines and mine markers.
2634      */
2635     mines = markers = 0;
2636     for (y = 0; y < ds->h; y++)
2637         for (x = 0; x < ds->w; x++) {
2638             int v = state->grid[y*ds->w+x];
2639
2640             if (v == -1)
2641                 markers++;
2642             if (state->layout->mines && state->layout->mines[y*ds->w+x])
2643                 mines++;
2644
2645             if ((v == -2 || v == -3) &&
2646                 (abs(x-ui->hx) <= ui->hradius && abs(y-ui->hy) <= ui->hradius))
2647                 v -= 20;
2648
2649             if (ds->grid[y*ds->w+x] != v || bg != COL_BACKGROUND) {
2650                 draw_tile(fe, COORD(x), COORD(y), v, bg);
2651                 ds->grid[y*ds->w+x] = (bg == COL_BACKGROUND ? v : -10);
2652             }
2653         }
2654
2655     if (!state->layout->mines)
2656         mines = state->layout->n;
2657
2658     /*
2659      * Update the status bar.
2660      */
2661     {
2662         char statusbar[512];
2663         if (state->dead) {
2664             sprintf(statusbar, "GAME OVER!");
2665         } else if (state->won) {
2666             sprintf(statusbar, "COMPLETED!");
2667         } else {
2668             sprintf(statusbar, "Mines marked: %d / %d", markers, mines);
2669         }
2670         status_bar(fe, statusbar);
2671     }
2672 }
2673
2674 static float game_anim_length(game_state *oldstate, game_state *newstate,
2675                               int dir, game_ui *ui)
2676 {
2677     return 0.0F;
2678 }
2679
2680 static float game_flash_length(game_state *oldstate, game_state *newstate,
2681                                int dir, game_ui *ui)
2682 {
2683     if (dir > 0 && !oldstate->dead && !oldstate->won) {
2684         if (newstate->dead) {
2685             ui->flash_is_death = TRUE;
2686             return 3 * FLASH_FRAME;
2687         }
2688         if (newstate->won) {
2689             ui->flash_is_death = FALSE;
2690             return 2 * FLASH_FRAME;
2691         }
2692     }
2693     return 0.0F;
2694 }
2695
2696 static int game_wants_statusbar(void)
2697 {
2698     return TRUE;
2699 }
2700
2701 static int game_timing_state(game_state *state)
2702 {
2703     if (state->dead || state->won || !state->layout->mines)
2704         return FALSE;
2705     return TRUE;
2706 }
2707
2708 #ifdef COMBINED
2709 #define thegame mines
2710 #endif
2711
2712 const struct game thegame = {
2713     "Mines", "games.mines",
2714     default_params,
2715     game_fetch_preset,
2716     decode_params,
2717     encode_params,
2718     free_params,
2719     dup_params,
2720     TRUE, game_configure, custom_params,
2721     validate_params,
2722     new_game_desc,
2723     game_free_aux_info,
2724     validate_desc,
2725     new_game,
2726     dup_game,
2727     free_game,
2728     FALSE, solve_game,
2729     FALSE, game_text_format,
2730     new_ui,
2731     free_ui,
2732     make_move,
2733     game_size,
2734     game_colours,
2735     game_new_drawstate,
2736     game_free_drawstate,
2737     game_redraw,
2738     game_anim_length,
2739     game_flash_length,
2740     game_wants_statusbar,
2741     TRUE, game_timing_state,
2742 };