solo.c

   1 /*
   2  * solo.c: the number-placing puzzle most popularly known as `Sudoku'.
   3  *
   4  * TODO:
   5  *
   6  *  - finalise game name
   7  *
   8  *  - can we do anything about nasty centring of text in GTK? It
   9  *    seems to be taking ascenders/descenders into account when
  10  *    centring. Ick.
  11  *
  12  *  - implement stronger modes of reasoning in nsolve, thus
  13  *    enabling harder puzzles
  14  *
  15  *  - configurable difficulty levels
  16  *
  17  *  - vary the symmetry (rotational or none)?
  18  *
  19  *  - try for cleverer ways of reducing the solved grid; they seem
  20  *    to be coming out a bit full for the most part, and in
  21  *    particular it's inexcusable to leave a grid with an entire
  22  *    block (or presumably row or column) filled! I _hope_ we can
  23  *    do this simply by better prioritising (somehow) the possible
  24  *    removals.
  25  *     + one simple option might be to work the other way: start
  26  *       with an empty grid and gradually _add_ numbers until it
  27  *       becomes solvable? Perhaps there might be some heuristic
  28  *       which enables us to pinpoint the most critical clues and
  29  *       thus add as few as possible.
  30  *
  31  *  - alternative interface modes
  32  *     + sudoku.com's Windows program has a palette of possible
  33  *       entries; you select a palette entry first and then click
  34  *       on the square you want it to go in, thus enabling
  35  *       mouse-only play. Useful for PDAs! I don't think it's
  36  *       actually incompatible with the current highlight-then-type
  37  *       approach: you _either_ highlight a palette entry and then
  38  *       click, _or_ you highlight a square and then type. At most
  39  *       one thing is ever highlighted at a time, so there's no way
  40  *       to confuse the two.
  41  *     + `pencil marks' might be useful for more subtle forms of
  42  *       deduction, once we implement creation of puzzles that
  43  *       require it.
  44  */
  45
  46 /*
  47  * Solo puzzles need to be square overall (since each row and each
  48  * column must contain one of every digit), but they need not be
  49  * subdivided the same way internally. I am going to adopt a
  50  * convention whereby I _always_ refer to `r' as the number of rows
  51  * of _big_ divisions, and `c' as the number of columns of _big_
  52  * divisions. Thus, a 2c by 3r puzzle looks something like this:
  53  *
  54  *   4 5 1 | 2 6 3
  55  *   6 3 2 | 5 4 1
  56  *   ------+------     (Of course, you can't subdivide it the other way
  57  *   1 4 5 | 6 3 2     or you'll get clashes; observe that the 4 in the
  58  *   3 2 6 | 4 1 5     top left would conflict with the 4 in the second
  59  *   ------+------     box down on the left-hand side.)
  60  *   5 1 4 | 3 2 6
  61  *   2 6 3 | 1 5 4
  62  *
  63  * The need for a strong naming convention should now be clear:
  64  * each small box is two rows of digits by three columns, while the
  65  * overall puzzle has three rows of small boxes by two columns. So
  66  * I will (hopefully) consistently use `r' to denote the number of
  67  * rows _of small boxes_ (here 3), which is also the number of
  68  * columns of digits in each small box; and `c' vice versa (here
  69  * 2).
  70  *
  71  * I'm also going to choose arbitrarily to list c first wherever
  72  * possible: the above is a 2x3 puzzle, not a 3x2 one.
  73  */
  74
  75 #include <stdio.h>
  76 #include <stdlib.h>
  77 #include <string.h>
  78 #include <assert.h>
  79 #include <ctype.h>
  80 #include <math.h>
  81
  82 #include "puzzles.h"
  83
  84 /*
  85  * To save space, I store digits internally as unsigned char. This
  86  * imposes a hard limit of 255 on the order of the puzzle. Since
  87  * even a 5x5 takes unacceptably long to generate, I don't see this
  88  * as a serious limitation unless something _really_ impressive
  89  * happens in computing technology; but here's a typedef anyway for
  90  * general good practice.
  91  */
  92 typedef unsigned char digit;
  93 #define ORDER_MAX 255
  94
  95 #define TILE_SIZE 32
  96 #define BORDER 18
  97
  98 #define FLASH_TIME 0.4F
  99
 100 enum {
 101     COL_BACKGROUND,
 102         COL_GRID,
 103         COL_CLUE,
 104         COL_USER,
 105         COL_HIGHLIGHT,
 106         NCOLOURS
 107 };
 108
 109 struct game_params {
 110     int c, r;
 111 };
 112
 113 struct game_state {
 114     int c, r;
 115     digit *grid;
 116     unsigned char *immutable;          /* marks which digits are clues */
 117     int completed;
 118 };
 119
 120 static game_params *default_params(void)
 121 {
 122     game_params *ret = snew(game_params);
 123
 124     ret->c = ret->r = 3;
 125
 126     return ret;
 127 }
 128
 129 static int game_fetch_preset(int i, char **name, game_params **params)
 130 {
 131     game_params *ret;
 132     int c, r;
 133     char buf[80];
 134
 135     switch (i) {
 136       case 0: c = 2, r = 2; break;
 137       case 1: c = 2, r = 3; break;
 138       case 2: c = 3, r = 3; break;
 139       case 3: c = 3, r = 4; break;
 140       case 4: c = 4, r = 4; break;
 141       default: return FALSE;
 142     }
 143
 144     sprintf(buf, "%dx%d", c, r);
 145     *name = dupstr(buf);
 146     *params = ret = snew(game_params);
 147     ret->c = c;
 148     ret->r = r;
 149     /* FIXME: difficulty presets? */
 150     return TRUE;
 151 }
 152
 153 static void free_params(game_params *params)
 154 {
 155     sfree(params);
 156 }
 157
 158 static game_params *dup_params(game_params *params)
 159 {
 160     game_params *ret = snew(game_params);
 161     *ret = *params;                    /* structure copy */
 162     return ret;
 163 }
 164
 165 static game_params *decode_params(char const *string)
 166 {
 167     game_params *ret = default_params();
 168
 169     ret->c = ret->r = atoi(string);
 170     while (*string && isdigit((unsigned char)*string)) string++;
 171     if (*string == 'x') {
 172         string++;
 173         ret->r = atoi(string);
 174         while (*string && isdigit((unsigned char)*string)) string++;
 175     }
 176     /* FIXME: difficulty levels */
 177
 178     return ret;
 179 }
 180
 181 static char *encode_params(game_params *params)
 182 {
 183     char str[80];
 184
 185     sprintf(str, "%dx%d", params->c, params->r);
 186     return dupstr(str);
 187 }
 188
 189 static config_item *game_configure(game_params *params)
 190 {
 191     config_item *ret;
 192     char buf[80];
 193
 194     ret = snewn(5, config_item);
 195
 196     ret[0].name = "Columns of sub-blocks";
 197     ret[0].type = C_STRING;
 198     sprintf(buf, "%d", params->c);
 199     ret[0].sval = dupstr(buf);
 200     ret[0].ival = 0;
 201
 202     ret[1].name = "Rows of sub-blocks";
 203     ret[1].type = C_STRING;
 204     sprintf(buf, "%d", params->r);
 205     ret[1].sval = dupstr(buf);
 206     ret[1].ival = 0;
 207
 208     /*
 209      * FIXME: difficulty level.
 210      */
 211
 212     ret[2].name = NULL;
 213     ret[2].type = C_END;
 214     ret[2].sval = NULL;
 215     ret[2].ival = 0;
 216
 217     return ret;
 218 }
 219
 220 static game_params *custom_params(config_item *cfg)
 221 {
 222     game_params *ret = snew(game_params);
 223
 224     ret->c = atof(cfg[0].sval);
 225     ret->r = atof(cfg[1].sval);
 226
 227     return ret;
 228 }
 229
 230 static char *validate_params(game_params *params)
 231 {
 232     if (params->c < 2 || params->r < 2)
 233         return "Both dimensions must be at least 2";
 234     if (params->c > ORDER_MAX || params->r > ORDER_MAX)
 235         return "Dimensions greater than "STR(ORDER_MAX)" are not supported";
 236     return NULL;
 237 }
 238
 239 /* ----------------------------------------------------------------------
 240  * Full recursive Solo solver.
 241  *
 242  * The algorithm for this solver is shamelessly copied from a
 243  * Python solver written by Andrew Wilkinson (which is GPLed, but
 244  * I've reused only ideas and no code). It mostly just does the
 245  * obvious recursive thing: pick an empty square, put one of the
 246  * possible digits in it, recurse until all squares are filled,
 247  * backtrack and change some choices if necessary.
 248  *
 249  * The clever bit is that every time it chooses which square to
 250  * fill in next, it does so by counting the number of _possible_
 251  * numbers that can go in each square, and it prioritises so that
 252  * it picks a square with the _lowest_ number of possibilities. The
 253  * idea is that filling in lots of the obvious bits (particularly
 254  * any squares with only one possibility) will cut down on the list
 255  * of possibilities for other squares and hence reduce the enormous
 256  * search space as much as possible as early as possible.
 257  *
 258  * In practice the algorithm appeared to work very well; run on
 259  * sample problems from the Times it completed in well under a
 260  * second on my G5 even when written in Python, and given an empty
 261  * grid (so that in principle it would enumerate _all_ solved
 262  * grids!) it found the first valid solution just as quickly. So
 263  * with a bit more randomisation I see no reason not to use this as
 264  * my grid generator.
 265  */
 266
 267 /*
 268  * Internal data structure used in solver to keep track of
 269  * progress.
 270  */
 271 struct rsolve_coord { int x, y, r; };
 272 struct rsolve_usage {
 273     int c, r, cr;                      /* cr == c*r */
 274     /* grid is a copy of the input grid, modified as we go along */
 275     digit *grid;
 276     /* row[y*cr+n-1] TRUE if digit n has been placed in row y */
 277     unsigned char *row;
 278     /* col[x*cr+n-1] TRUE if digit n has been placed in row x */
 279     unsigned char *col;
 280     /* blk[(y*c+x)*cr+n-1] TRUE if digit n has been placed in block (x,y) */
 281     unsigned char *blk;
 282     /* This lists all the empty spaces remaining in the grid. */
 283     struct rsolve_coord *spaces;
 284     int nspaces;
 285     /* If we need randomisation in the solve, this is our random state. */
 286     random_state *rs;
 287     /* Number of solutions so far found, and maximum number we care about. */
 288     int solns, maxsolns;
 289 };
 290
 291 /*
 292  * The real recursive step in the solving function.
 293  */
 294 static void rsolve_real(struct rsolve_usage *usage, digit *grid)
 295 {
 296     int c = usage->c, r = usage->r, cr = usage->cr;
 297     int i, j, n, sx, sy, bestm, bestr;
 298     int *digits;
 299
 300     /*
 301      * Firstly, check for completion! If there are no spaces left
 302      * in the grid, we have a solution.
 303      */
 304     if (usage->nspaces == 0) {
 305         if (!usage->solns) {
 306             /*
 307              * This is our first solution, so fill in the output grid.
 308              */
 309             memcpy(grid, usage->grid, cr * cr);
 310         }
 311         usage->solns++;
 312         return;
 313     }
 314
 315     /*
 316      * Otherwise, there must be at least one space. Find the most
 317      * constrained space, using the `r' field as a tie-breaker.
 318      */
 319     bestm = cr+1;                      /* so that any space will beat it */
 320     bestr = 0;
 321     i = sx = sy = -1;
 322     for (j = 0; j < usage->nspaces; j++) {
 323         int x = usage->spaces[j].x, y = usage->spaces[j].y;
 324         int m;
 325
 326         /*
 327          * Find the number of digits that could go in this space.
 328          */
 329         m = 0;
 330         for (n = 0; n < cr; n++)
 331             if (!usage->row[y*cr+n] && !usage->col[x*cr+n] &&
 332                 !usage->blk[((y/c)*c+(x/r))*cr+n])
 333                 m++;
 334
 335         if (m < bestm || (m == bestm && usage->spaces[j].r < bestr)) {
 336             bestm = m;
 337             bestr = usage->spaces[j].r;
 338             sx = x;
 339             sy = y;
 340             i = j;
 341         }
 342     }
 343
 344     /*
 345      * Swap that square into the final place in the spaces array,
 346      * so that decrementing nspaces will remove it from the list.
 347      */
 348     if (i != usage->nspaces-1) {
 349         struct rsolve_coord t;
 350         t = usage->spaces[usage->nspaces-1];
 351         usage->spaces[usage->nspaces-1] = usage->spaces[i];
 352         usage->spaces[i] = t;
 353     }
 354
 355     /*
 356      * Now we've decided which square to start our recursion at,
 357      * simply go through all possible values, shuffling them
 358      * randomly first if necessary.
 359      */
 360     digits = snewn(bestm, int);
 361     j = 0;
 362     for (n = 0; n < cr; n++)
 363         if (!usage->row[sy*cr+n] && !usage->col[sx*cr+n] &&
 364             !usage->blk[((sy/c)*c+(sx/r))*cr+n]) {
 365             digits[j++] = n+1;
 366         }
 367
 368     if (usage->rs) {
 369         /* shuffle */
 370         for (i = j; i > 1; i--) {
 371             int p = random_upto(usage->rs, i);
 372             if (p != i-1) {
 373                 int t = digits[p];
 374                 digits[p] = digits[i-1];
 375                 digits[i-1] = t;
 376             }
 377         }
 378     }
 379
 380     /* And finally, go through the digit list and actually recurse. */
 381     for (i = 0; i < j; i++) {
 382         n = digits[i];
 383
 384         /* Update the usage structure to reflect the placing of this digit. */
 385         usage->row[sy*cr+n-1] = usage->col[sx*cr+n-1] =
 386             usage->blk[((sy/c)*c+(sx/r))*cr+n-1] = TRUE;
 387         usage->grid[sy*cr+sx] = n;
 388         usage->nspaces--;
 389
 390         /* Call the solver recursively. */
 391         rsolve_real(usage, grid);
 392
 393         /*
 394          * If we have seen as many solutions as we need, terminate
 395          * all processing immediately.
 396          */
 397         if (usage->solns >= usage->maxsolns)
 398             break;
 399
 400         /* Revert the usage structure. */
 401         usage->row[sy*cr+n-1] = usage->col[sx*cr+n-1] =
 402             usage->blk[((sy/c)*c+(sx/r))*cr+n-1] = FALSE;
 403         usage->grid[sy*cr+sx] = 0;
 404         usage->nspaces++;
 405     }
 406
 407     sfree(digits);
 408 }
 409
 410 /*
 411  * Entry point to solver. You give it dimensions and a starting
 412  * grid, which is simply an array of N^4 digits. In that array, 0
 413  * means an empty square, and 1..N mean a clue square.
 414  *
 415  * Return value is the number of solutions found; searching will
 416  * stop after the provided `max'. (Thus, you can pass max==1 to
 417  * indicate that you only care about finding _one_ solution, or
 418  * max==2 to indicate that you want to know the difference between
 419  * a unique and non-unique solution.) The input parameter `grid' is
 420  * also filled in with the _first_ (or only) solution found by the
 421  * solver.
 422  */
 423 static int rsolve(int c, int r, digit *grid, random_state *rs, int max)
 424 {
 425     struct rsolve_usage *usage;
 426     int x, y, cr = c*r;
 427     int ret;
 428
 429     /*
 430      * Create an rsolve_usage structure.
 431      */
 432     usage = snew(struct rsolve_usage);
 433
 434     usage->c = c;
 435     usage->r = r;
 436     usage->cr = cr;
 437
 438     usage->grid = snewn(cr * cr, digit);
 439     memcpy(usage->grid, grid, cr * cr);
 440
 441     usage->row = snewn(cr * cr, unsigned char);
 442     usage->col = snewn(cr * cr, unsigned char);
 443     usage->blk = snewn(cr * cr, unsigned char);
 444     memset(usage->row, FALSE, cr * cr);
 445     memset(usage->col, FALSE, cr * cr);
 446     memset(usage->blk, FALSE, cr * cr);
 447
 448     usage->spaces = snewn(cr * cr, struct rsolve_coord);
 449     usage->nspaces = 0;
 450
 451     usage->solns = 0;
 452     usage->maxsolns = max;
 453
 454     usage->rs = rs;
 455
 456     /*
 457      * Now fill it in with data from the input grid.
 458      */
 459     for (y = 0; y < cr; y++) {
 460         for (x = 0; x < cr; x++) {
 461             int v = grid[y*cr+x];
 462             if (v == 0) {
 463                 usage->spaces[usage->nspaces].x = x;
 464                 usage->spaces[usage->nspaces].y = y;
 465                 if (rs)
 466                     usage->spaces[usage->nspaces].r = random_bits(rs, 31);
 467                 else
 468                     usage->spaces[usage->nspaces].r = usage->nspaces;
 469                 usage->nspaces++;
 470             } else {
 471                 usage->row[y*cr+v-1] = TRUE;
 472                 usage->col[x*cr+v-1] = TRUE;
 473                 usage->blk[((y/c)*c+(x/r))*cr+v-1] = TRUE;
 474             }
 475         }
 476     }
 477
 478     /*
 479      * Run the real recursive solving function.
 480      */
 481     rsolve_real(usage, grid);
 482     ret = usage->solns;
 483
 484     /*
 485      * Clean up the usage structure now we have our answer.
 486      */
 487     sfree(usage->spaces);
 488     sfree(usage->blk);
 489     sfree(usage->col);
 490     sfree(usage->row);
 491     sfree(usage->grid);
 492     sfree(usage);
 493
 494     /*
 495      * And return.
 496      */
 497     return ret;
 498 }
 499
 500 /* ----------------------------------------------------------------------
 501  * End of recursive solver code.
 502  */
 503
 504 /* ----------------------------------------------------------------------
 505  * Less capable non-recursive solver. This one is used to check
 506  * solubility of a grid as we gradually remove numbers from it: by
 507  * verifying a grid using this solver we can ensure it isn't _too_
 508  * hard (e.g. does not actually require guessing and backtracking).
 509  *
 510  * It supports a variety of specific modes of reasoning. By
 511  * enabling or disabling subsets of these modes we can arrange a
 512  * range of difficulty levels.
 513  */
 514
 515 /*
 516  * Modes of reasoning currently supported:
 517  *
 518  *  - Positional elimination: a number must go in a particular
 519  *    square because all the other empty squares in a given
 520  *    row/col/blk are ruled out.
 521  *
 522  *  - Numeric elimination: a square must have a particular number
 523  *    in because all the other numbers that could go in it are
 524  *    ruled out.
 525  *
 526  * More advanced modes of reasoning I'd like to support in future:
 527  *
 528  *  - Intersectional elimination: given two domains which overlap
 529  *    (hence one must be a block, and the other can be a row or
 530  *    col), if the possible locations for a particular number in
 531  *    one of the domains can be narrowed down to the overlap, then
 532  *    that number can be ruled out everywhere but the overlap in
 533  *    the other domain too.
 534  *
 535  *  - Setwise numeric elimination: if there is a subset of the
 536  *    empty squares within a domain such that the union of the
 537  *    possible numbers in that subset has the same size as the
 538  *    subset itself, then those numbers can be ruled out everywhere
 539  *    else in the domain. (For example, if there are five empty
 540  *    squares and the possible numbers in each are 12, 23, 13, 134
 541  *    and 1345, then the first three empty squares form such a
 542  *    subset: the numbers 1, 2 and 3 _must_ be in those three
 543  *    squares in some permutation, and hence we can deduce none of
 544  *    them can be in the fourth or fifth squares.)
 545  */
 546
 547 struct nsolve_usage {
 548     int c, r, cr;
 549     /*
 550      * We set up a cubic array, indexed by x, y and digit; each
 551      * element of this array is TRUE or FALSE according to whether
 552      * or not that digit _could_ in principle go in that position.
 553      *
 554      * The way to index this array is cube[(x*cr+y)*cr+n-1].
 555      */
 556     unsigned char *cube;
 557     /*
 558      * This is the grid in which we write down our final
 559      * deductions.
 560      */
 561     digit *grid;
 562     /*
 563      * Now we keep track, at a slightly higher level, of what we
 564      * have yet to work out, to prevent doing the same deduction
 565      * many times.
 566      */
 567     /* row[y*cr+n-1] TRUE if digit n has been placed in row y */
 568     unsigned char *row;
 569     /* col[x*cr+n-1] TRUE if digit n has been placed in row x */
 570     unsigned char *col;
 571     /* blk[(y*c+x)*cr+n-1] TRUE if digit n has been placed in block (x,y) */
 572     unsigned char *blk;
 573 };
 574 #define cube(x,y,n) (usage->cube[((x)*usage->cr+(y))*usage->cr+(n)-1])
 575
 576 /*
 577  * Function called when we are certain that a particular square has
 578  * a particular number in it.
 579  */
 580 static void nsolve_place(struct nsolve_usage *usage, int x, int y, int n)
 581 {
 582     int c = usage->c, r = usage->r, cr = usage->cr;
 583     int i, j, bx, by;
 584
 585     assert(cube(x,y,n));
 586
 587     /*
 588      * Rule out all other numbers in this square.
 589      */
 590     for (i = 1; i <= cr; i++)
 591         if (i != n)
 592             cube(x,y,i) = FALSE;
 593
 594     /*
 595      * Rule out this number in all other positions in the row.
 596      */
 597     for (i = 0; i < cr; i++)
 598         if (i != y)
 599             cube(x,i,n) = FALSE;
 600
 601     /*
 602      * Rule out this number in all other positions in the column.
 603      */
 604     for (i = 0; i < cr; i++)
 605         if (i != x)
 606             cube(i,y,n) = FALSE;
 607
 608     /*
 609      * Rule out this number in all other positions in the block.
 610      */
 611     bx = (x/r)*r;
 612     by = (y/c)*c;
 613     for (i = 0; i < r; i++)
 614         for (j = 0; j < c; j++)
 615             if (bx+i != x || by+j != y)
 616                 cube(bx+i,by+j,n) = FALSE;
 617
 618     /*
 619      * Enter the number in the result grid.
 620      */
 621     usage->grid[y*cr+x] = n;
 622
 623     /*
 624      * Cross out this number from the list of numbers left to place
 625      * in its row, its column and its block.
 626      */
 627     usage->row[y*cr+n-1] = usage->col[x*cr+n-1] =
 628         usage->blk[((y/c)*c+(x/r))*cr+n-1] = TRUE;
 629 }
 630
 631 static int nsolve_blk_pos_elim(struct nsolve_usage *usage,
 632                                int x, int y, int n)
 633 {
 634     int c = usage->c, r = usage->r;
 635     int i, j, fx, fy, m;
 636
 637     x *= r;
 638     y *= c;
 639
 640     /*
 641      * Count the possible positions within this block where this
 642      * number could appear.
 643      */
 644     m = 0;
 645     fx = fy = -1;
 646     for (i = 0; i < r; i++)
 647         for (j = 0; j < c; j++)
 648             if (cube(x+i,y+j,n)) {
 649                 fx = x+i;
 650                 fy = y+j;
 651                 m++;
 652             }
 653
 654     if (m == 1) {
 655         assert(fx >= 0 && fy >= 0);
 656         nsolve_place(usage, fx, fy, n);
 657         return TRUE;
 658     }
 659
 660     return FALSE;
 661 }
 662
 663 static int nsolve_row_pos_elim(struct nsolve_usage *usage,
 664                                int y, int n)
 665 {
 666     int cr = usage->cr;
 667     int x, fx, m;
 668
 669     /*
 670      * Count the possible positions within this row where this
 671      * number could appear.
 672      */
 673     m = 0;
 674     fx = -1;
 675     for (x = 0; x < cr; x++)
 676         if (cube(x,y,n)) {
 677             fx = x;
 678             m++;
 679         }
 680
 681     if (m == 1) {
 682         assert(fx >= 0);
 683         nsolve_place(usage, fx, y, n);
 684         return TRUE;
 685     }
 686
 687     return FALSE;
 688 }
 689
 690 static int nsolve_col_pos_elim(struct nsolve_usage *usage,
 691                                int x, int n)
 692 {
 693     int cr = usage->cr;
 694     int y, fy, m;
 695
 696     /*
 697      * Count the possible positions within this column where this
 698      * number could appear.
 699      */
 700     m = 0;
 701     fy = -1;
 702     for (y = 0; y < cr; y++)
 703         if (cube(x,y,n)) {
 704             fy = y;
 705             m++;
 706         }
 707
 708     if (m == 1) {
 709         assert(fy >= 0);
 710         nsolve_place(usage, x, fy, n);
 711         return TRUE;
 712     }
 713
 714     return FALSE;
 715 }
 716
 717 static int nsolve_num_elim(struct nsolve_usage *usage,
 718                            int x, int y)
 719 {
 720     int cr = usage->cr;
 721     int n, fn, m;
 722
 723     /*
 724      * Count the possible numbers that could appear in this square.
 725      */
 726     m = 0;
 727     fn = -1;
 728     for (n = 1; n <= cr; n++)
 729         if (cube(x,y,n)) {
 730             fn = n;
 731             m++;
 732         }
 733
 734     if (m == 1) {
 735         assert(fn > 0);
 736         nsolve_place(usage, x, y, fn);
 737         return TRUE;
 738     }
 739
 740     return FALSE;
 741 }
 742
 743 static int nsolve(int c, int r, digit *grid)
 744 {
 745     struct nsolve_usage *usage;
 746     int cr = c*r;
 747     int x, y, n;
 748
 749     /*
 750      * Set up a usage structure as a clean slate (everything
 751      * possible).
 752      */
 753     usage = snew(struct nsolve_usage);
 754     usage->c = c;
 755     usage->r = r;
 756     usage->cr = cr;
 757     usage->cube = snewn(cr*cr*cr, unsigned char);
 758     usage->grid = grid;                /* write straight back to the input */
 759     memset(usage->cube, TRUE, cr*cr*cr);
 760
 761     usage->row = snewn(cr * cr, unsigned char);
 762     usage->col = snewn(cr * cr, unsigned char);
 763     usage->blk = snewn(cr * cr, unsigned char);
 764     memset(usage->row, FALSE, cr * cr);
 765     memset(usage->col, FALSE, cr * cr);
 766     memset(usage->blk, FALSE, cr * cr);
 767
 768     /*
 769      * Place all the clue numbers we are given.
 770      */
 771     for (x = 0; x < cr; x++)
 772         for (y = 0; y < cr; y++)
 773             if (grid[y*cr+x])
 774                 nsolve_place(usage, x, y, grid[y*cr+x]);
 775
 776     /*
 777      * Now loop over the grid repeatedly trying all permitted modes
 778      * of reasoning. The loop terminates if we complete an
 779      * iteration without making any progress; we then return
 780      * failure or success depending on whether the grid is full or
 781      * not.
 782      */
 783     while (1) {
 784         /*
 785          * Blockwise positional elimination.
 786          */
 787         for (x = 0; x < c; x++)
 788             for (y = 0; y < r; y++)
 789                 for (n = 1; n <= cr; n++)
 790                     if (!usage->blk[((y/c)*c+(x/r))*cr+n-1] &&
 791                         nsolve_blk_pos_elim(usage, x, y, n))
 792                         continue;
 793
 794         /*
 795          * Row-wise positional elimination.
 796          */
 797         for (y = 0; y < cr; y++)
 798             for (n = 1; n <= cr; n++)
 799                 if (!usage->row[y*cr+n-1] &&
 800                     nsolve_row_pos_elim(usage, y, n))
 801                     continue;
 802         /*
 803          * Column-wise positional elimination.
 804          */
 805         for (x = 0; x < cr; x++)
 806             for (n = 1; n <= cr; n++)
 807                 if (!usage->col[x*cr+n-1] &&
 808                     nsolve_col_pos_elim(usage, x, n))
 809                     continue;
 810
 811         /*
 812          * Numeric elimination.
 813          */
 814         for (x = 0; x < cr; x++)
 815             for (y = 0; y < cr; y++)
 816                 if (!usage->grid[y*cr+x] &&
 817                     nsolve_num_elim(usage, x, y))
 818                     continue;
 819
 820         /*
 821          * If we reach here, we have made no deductions in this
 822          * iteration, so the algorithm terminates.
 823          */
 824         break;
 825     }
 826
 827     sfree(usage->cube);
 828     sfree(usage->row);
 829     sfree(usage->col);
 830     sfree(usage->blk);
 831     sfree(usage);
 832
 833     for (x = 0; x < cr; x++)
 834         for (y = 0; y < cr; y++)
 835             if (!grid[y*cr+x])
 836                 return FALSE;
 837     return TRUE;
 838 }
 839
 840 /* ----------------------------------------------------------------------
 841  * End of non-recursive solver code.
 842  */
 843
 844 /*
 845  * Check whether a grid contains a valid complete puzzle.
 846  */
 847 static int check_valid(int c, int r, digit *grid)
 848 {
 849     int cr = c*r;
 850     unsigned char *used;
 851     int x, y, n;
 852
 853     used = snewn(cr, unsigned char);
 854
 855     /*
 856      * Check that each row contains precisely one of everything.
 857      */
 858     for (y = 0; y < cr; y++) {
 859         memset(used, FALSE, cr);
 860         for (x = 0; x < cr; x++)
 861             if (grid[y*cr+x] > 0 && grid[y*cr+x] <= cr)
 862                 used[grid[y*cr+x]-1] = TRUE;
 863         for (n = 0; n < cr; n++)
 864             if (!used[n]) {
 865                 sfree(used);
 866                 return FALSE;
 867             }
 868     }
 869
 870     /*
 871      * Check that each column contains precisely one of everything.
 872      */
 873     for (x = 0; x < cr; x++) {
 874         memset(used, FALSE, cr);
 875         for (y = 0; y < cr; y++)
 876             if (grid[y*cr+x] > 0 && grid[y*cr+x] <= cr)
 877                 used[grid[y*cr+x]-1] = TRUE;
 878         for (n = 0; n < cr; n++)
 879             if (!used[n]) {
 880                 sfree(used);
 881                 return FALSE;
 882             }
 883     }
 884
 885     /*
 886      * Check that each block contains precisely one of everything.
 887      */
 888     for (x = 0; x < cr; x += r) {
 889         for (y = 0; y < cr; y += c) {
 890             int xx, yy;
 891             memset(used, FALSE, cr);
 892             for (xx = x; xx < x+r; xx++)
 893                 for (yy = 0; yy < y+c; yy++)
 894                     if (grid[yy*cr+xx] > 0 && grid[yy*cr+xx] <= cr)
 895                         used[grid[yy*cr+xx]-1] = TRUE;
 896             for (n = 0; n < cr; n++)
 897                 if (!used[n]) {
 898                     sfree(used);
 899                     return FALSE;
 900                 }
 901         }
 902     }
 903
 904     sfree(used);
 905     return TRUE;
 906 }
 907
 908 static char *new_game_seed(game_params *params, random_state *rs)
 909 {
 910     int c = params->c, r = params->r, cr = c*r;
 911     int area = cr*cr;
 912     digit *grid, *grid2;
 913     struct xy { int x, y; } *locs;
 914     int nlocs;
 915     int ret;
 916     char *seed;
 917
 918     /*
 919      * Start the recursive solver with an empty grid to generate a
 920      * random solved state.
 921      */
 922     grid = snewn(area, digit);
 923     memset(grid, 0, area);
 924     ret = rsolve(c, r, grid, rs, 1);
 925     assert(ret == 1);
 926     assert(check_valid(c, r, grid));
 927
 928 #ifdef DEBUG
 929     memcpy(grid,
 930            "\x0\x1\x0\x0\x6\x0\x0\x0\x0"
 931            "\x5\x0\x0\x7\x0\x4\x0\x2\x0"
 932            "\x0\x0\x6\x1\x0\x0\x0\x0\x0"
 933            "\x8\x9\x7\x0\x0\x0\x0\x0\x0"
 934            "\x0\x0\x3\x0\x4\x0\x9\x0\x0"
 935            "\x0\x0\x0\x0\x0\x0\x8\x7\x6"
 936            "\x0\x0\x0\x0\x0\x9\x1\x0\x0"
 937            "\x0\x3\x0\x6\x0\x5\x0\x0\x7"
 938            "\x0\x0\x0\x0\x8\x0\x0\x5\x0"
 939            , area);
 940
 941     {
 942         int y, x;
 943         for (y = 0; y < cr; y++) {
 944             for (x = 0; x < cr; x++) {
 945                 printf("%2.0d", grid[y*cr+x]);
 946             }
 947             printf("\n");
 948         }
 949         printf("\n");
 950     }
 951
 952     nsolve(c, r, grid);
 953
 954     {
 955         int y, x;
 956         for (y = 0; y < cr; y++) {
 957             for (x = 0; x < cr; x++) {
 958                 printf("%2.0d", grid[y*cr+x]);
 959             }
 960             printf("\n");
 961         }
 962         printf("\n");
 963     }
 964 #endif
 965
 966     /*
 967      * Now we have a solved grid, start removing things from it
 968      * while preserving solubility.
 969      */
 970     locs = snewn((cr+1)/2 * (cr+1)/2, struct xy);
 971     grid2 = snewn(area, digit);
 972     while (1) {
 973         int x, y, i;
 974
 975         /*
 976          * Iterate over the top left corner of the grid and
 977          * enumerate all the filled squares we could empty.
 978          */
 979         nlocs = 0;
 980
 981         for (x = 0; 2*x < cr; x++)
 982             for (y = 0; 2*y < cr; y++)
 983                 if (grid[y*cr+x]) {
 984                     locs[nlocs].x = x;
 985                     locs[nlocs].y = y;
 986                     nlocs++;
 987                 }
 988
 989         /*
 990          * Now shuffle that list.
 991          */
 992         for (i = nlocs; i > 1; i--) {
 993             int p = random_upto(rs, i);
 994             if (p != i-1) {
 995                 struct xy t = locs[p];
 996                 locs[p] = locs[i-1];
 997                 locs[i-1] = t;
 998             }
 999         }
1000
1001         /*
1002          * Now loop over the shuffled list and, for each element,
1003          * see whether removing that element (and its reflections)
1004          * from the grid will still leave the grid soluble by
1005          * nsolve.
1006          */
1007         for (i = 0; i < nlocs; i++) {
1008             x = locs[i].x;
1009             y = locs[i].y;
1010
1011             memcpy(grid2, grid, area);
1012             grid2[y*cr+x] = 0;
1013             grid2[y*cr+cr-1-x] = 0;
1014             grid2[(cr-1-y)*cr+x] = 0;
1015             grid2[(cr-1-y)*cr+cr-1-x] = 0;
1016
1017             if (nsolve(c, r, grid2)) {
1018                 grid[y*cr+x] = 0;
1019                 grid[y*cr+cr-1-x] = 0;
1020                 grid[(cr-1-y)*cr+x] = 0;
1021                 grid[(cr-1-y)*cr+cr-1-x] = 0;
1022                 break;
1023             }
1024         }
1025
1026         if (i == nlocs) {
1027             /*
1028              * There was nothing we could remove without destroying
1029              * solvability.
1030              */
1031             break;
1032         }
1033     }
1034     sfree(grid2);
1035     sfree(locs);
1036
1037 #ifdef DEBUG
1038     {
1039         int y, x;
1040         for (y = 0; y < cr; y++) {
1041             for (x = 0; x < cr; x++) {
1042                 printf("%2.0d", grid[y*cr+x]);
1043             }
1044             printf("\n");
1045         }
1046         printf("\n");
1047     }
1048 #endif
1049
1050     /*
1051      * Now we have the grid as it will be presented to the user.
1052      * Encode it in a game seed.
1053      */
1054     {
1055         char *p;
1056         int run, i;
1057
1058         seed = snewn(5 * area, char);
1059         p = seed;
1060         run = 0;
1061         for (i = 0; i <= area; i++) {
1062             int n = (i < area ? grid[i] : -1);
1063
1064             if (!n)
1065                 run++;
1066             else {
1067                 if (run) {
1068                     while (run > 0) {
1069                         int c = 'a' - 1 + run;
1070                         if (run > 26)
1071                             c = 'z';
1072                         *p++ = c;
1073                         run -= c - ('a' - 1);
1074                     }
1075                 } else {
1076                     /*
1077                      * If there's a number in the very top left or
1078                      * bottom right, there's no point putting an
1079                      * unnecessary _ before or after it.
1080                      */
1081                     if (p > seed && n > 0)
1082                         *p++ = '_';
1083                 }
1084                 if (n > 0)
1085                     p += sprintf(p, "%d", n);
1086                 run = 0;
1087             }
1088         }
1089         assert(p - seed < 5 * area);
1090         *p++ = '\0';
1091         seed = sresize(seed, p - seed, char);
1092     }
1093
1094     sfree(grid);
1095
1096     return seed;
1097 }
1098
1099 static char *validate_seed(game_params *params, char *seed)
1100 {
1101     int area = params->r * params->r * params->c * params->c;
1102     int squares = 0;
1103
1104     while (*seed) {
1105         int n = *seed++;
1106         if (n >= 'a' && n <= 'z') {
1107             squares += n - 'a' + 1;
1108         } else if (n == '_') {
1109             /* do nothing */;
1110         } else if (n > '0' && n <= '9') {
1111             squares++;
1112             while (*seed >= '0' && *seed <= '9')
1113                 seed++;
1114         } else
1115             return "Invalid character in game specification";
1116     }
1117
1118     if (squares < area)
1119         return "Not enough data to fill grid";
1120
1121     if (squares > area)
1122         return "Too much data to fit in grid";
1123
1124     return NULL;
1125 }
1126
1127 static game_state *new_game(game_params *params, char *seed)
1128 {
1129     game_state *state = snew(game_state);
1130     int c = params->c, r = params->r, cr = c*r, area = cr * cr;
1131     int i;
1132
1133     state->c = params->c;
1134     state->r = params->r;
1135
1136     state->grid = snewn(area, digit);
1137     state->immutable = snewn(area, unsigned char);
1138     memset(state->immutable, FALSE, area);
1139
1140     state->completed = FALSE;
1141
1142     i = 0;
1143     while (*seed) {
1144         int n = *seed++;
1145         if (n >= 'a' && n <= 'z') {
1146             int run = n - 'a' + 1;
1147             assert(i + run <= area);
1148             while (run-- > 0)
1149                 state->grid[i++] = 0;
1150         } else if (n == '_') {
1151             /* do nothing */;
1152         } else if (n > '0' && n <= '9') {
1153             assert(i < area);
1154             state->immutable[i] = TRUE;
1155             state->grid[i++] = atoi(seed-1);
1156             while (*seed >= '0' && *seed <= '9')
1157                 seed++;
1158         } else {
1159             assert(!"We can't get here");
1160         }
1161     }
1162     assert(i == area);
1163
1164     return state;
1165 }
1166
1167 static game_state *dup_game(game_state *state)
1168 {
1169     game_state *ret = snew(game_state);
1170     int c = state->c, r = state->r, cr = c*r, area = cr * cr;
1171
1172     ret->c = state->c;
1173     ret->r = state->r;
1174
1175     ret->grid = snewn(area, digit);
1176     memcpy(ret->grid, state->grid, area);
1177
1178     ret->immutable = snewn(area, unsigned char);
1179     memcpy(ret->immutable, state->immutable, area);
1180
1181     ret->completed = state->completed;
1182
1183     return ret;
1184 }
1185
1186 static void free_game(game_state *state)
1187 {
1188     sfree(state->immutable);
1189     sfree(state->grid);
1190     sfree(state);
1191 }
1192
1193 struct game_ui {
1194     /*
1195      * These are the coordinates of the currently highlighted
1196      * square on the grid, or -1,-1 if there isn't one. When there
1197      * is, pressing a valid number or letter key or Space will
1198      * enter that number or letter in the grid.
1199      */
1200     int hx, hy;
1201 };
1202
1203 static game_ui *new_ui(game_state *state)
1204 {
1205     game_ui *ui = snew(game_ui);
1206
1207     ui->hx = ui->hy = -1;
1208
1209     return ui;
1210 }
1211
1212 static void free_ui(game_ui *ui)
1213 {
1214     sfree(ui);
1215 }
1216
1217 static game_state *make_move(game_state *from, game_ui *ui, int x, int y,
1218                              int button)
1219 {
1220     int c = from->c, r = from->r, cr = c*r;
1221     int tx, ty;
1222     game_state *ret;
1223
1224     tx = (x - BORDER) / TILE_SIZE;
1225     ty = (y - BORDER) / TILE_SIZE;
1226
1227     if (tx >= 0 && tx < cr && ty >= 0 && ty < cr && button == LEFT_BUTTON) {
1228         if (tx == ui->hx && ty == ui->hy) {
1229             ui->hx = ui->hy = -1;
1230         } else {
1231             ui->hx = tx;
1232             ui->hy = ty;
1233         }
1234         return from;                   /* UI activity occurred */
1235     }
1236
1237     if (ui->hx != -1 && ui->hy != -1 &&
1238         ((button >= '1' && button <= '9' && button - '0' <= cr) ||
1239          (button >= 'a' && button <= 'z' && button - 'a' + 10 <= cr) ||
1240          (button >= 'A' && button <= 'Z' && button - 'A' + 10 <= cr) ||
1241          button == ' ')) {
1242         int n = button - '0';
1243         if (button >= 'A' && button <= 'Z')
1244             n = button - 'A' + 10;
1245         if (button >= 'a' && button <= 'z')
1246             n = button - 'a' + 10;
1247         if (button == ' ')
1248             n = 0;
1249
1250         if (from->immutable[ui->hy*cr+ui->hx])
1251             return NULL;               /* can't overwrite this square */
1252
1253         ret = dup_game(from);
1254         ret->grid[ui->hy*cr+ui->hx] = n;
1255         ui->hx = ui->hy = -1;
1256
1257         /*
1258          * We've made a real change to the grid. Check to see
1259          * if the game has been completed.
1260          */
1261         if (!ret->completed && check_valid(c, r, ret->grid)) {
1262             ret->completed = TRUE;
1263         }
1264
1265         return ret;                    /* made a valid move */
1266     }
1267
1268     return NULL;
1269 }
1270
1271 /* ----------------------------------------------------------------------
1272  * Drawing routines.
1273  */
1274
1275 struct game_drawstate {
1276     int started;
1277     int c, r, cr;
1278     digit *grid;
1279     unsigned char *hl;
1280 };
1281
1282 #define XSIZE(cr) ((cr) * TILE_SIZE + 2*BORDER + 1)
1283 #define YSIZE(cr) ((cr) * TILE_SIZE + 2*BORDER + 1)
1284
1285 static void game_size(game_params *params, int *x, int *y)
1286 {
1287     int c = params->c, r = params->r, cr = c*r;
1288
1289     *x = XSIZE(cr);
1290     *y = YSIZE(cr);
1291 }
1292
1293 static float *game_colours(frontend *fe, game_state *state, int *ncolours)
1294 {
1295     float *ret = snewn(3 * NCOLOURS, float);
1296
1297     frontend_default_colour(fe, &ret[COL_BACKGROUND * 3]);
1298
1299     ret[COL_GRID * 3 + 0] = 0.0F;
1300     ret[COL_GRID * 3 + 1] = 0.0F;
1301     ret[COL_GRID * 3 + 2] = 0.0F;
1302
1303     ret[COL_CLUE * 3 + 0] = 0.0F;
1304     ret[COL_CLUE * 3 + 1] = 0.0F;
1305     ret[COL_CLUE * 3 + 2] = 0.0F;
1306
1307     ret[COL_USER * 3 + 0] = 0.0F;
1308     ret[COL_USER * 3 + 1] = 0.6F * ret[COL_BACKGROUND * 3 + 1];
1309     ret[COL_USER * 3 + 2] = 0.0F;
1310
1311     ret[COL_HIGHLIGHT * 3 + 0] = 0.85F * ret[COL_BACKGROUND * 3 + 0];
1312     ret[COL_HIGHLIGHT * 3 + 1] = 0.85F * ret[COL_BACKGROUND * 3 + 1];
1313     ret[COL_HIGHLIGHT * 3 + 2] = 0.85F * ret[COL_BACKGROUND * 3 + 2];
1314
1315     *ncolours = NCOLOURS;
1316     return ret;
1317 }
1318
1319 static game_drawstate *game_new_drawstate(game_state *state)
1320 {
1321     struct game_drawstate *ds = snew(struct game_drawstate);
1322     int c = state->c, r = state->r, cr = c*r;
1323
1324     ds->started = FALSE;
1325     ds->c = c;
1326     ds->r = r;
1327     ds->cr = cr;
1328     ds->grid = snewn(cr*cr, digit);
1329     memset(ds->grid, 0, cr*cr);
1330     ds->hl = snewn(cr*cr, unsigned char);
1331     memset(ds->hl, 0, cr*cr);
1332
1333     return ds;
1334 }
1335
1336 static void game_free_drawstate(game_drawstate *ds)
1337 {
1338     sfree(ds->hl);
1339     sfree(ds->grid);
1340     sfree(ds);
1341 }
1342
1343 static void draw_number(frontend *fe, game_drawstate *ds, game_state *state,
1344                         int x, int y, int hl)
1345 {
1346     int c = state->c, r = state->r, cr = c*r;
1347     int tx, ty;
1348     int cx, cy, cw, ch;
1349     char str[2];
1350
1351     if (ds->grid[y*cr+x] == state->grid[y*cr+x] && ds->hl[y*cr+x] == hl)
1352         return;                        /* no change required */
1353
1354     tx = BORDER + x * TILE_SIZE + 2;
1355     ty = BORDER + y * TILE_SIZE + 2;
1356
1357     cx = tx;
1358     cy = ty;
1359     cw = TILE_SIZE-3;
1360     ch = TILE_SIZE-3;
1361
1362     if (x % r)
1363         cx--, cw++;
1364     if ((x+1) % r)
1365         cw++;
1366     if (y % c)
1367         cy--, ch++;
1368     if ((y+1) % c)
1369         ch++;
1370
1371     clip(fe, cx, cy, cw, ch);
1372
1373     /* background needs erasing? */
1374     if (ds->grid[y*cr+x] || ds->hl[y*cr+x] != hl)
1375         draw_rect(fe, cx, cy, cw, ch, hl ? COL_HIGHLIGHT : COL_BACKGROUND);
1376
1377     /* new number needs drawing? */
1378     if (state->grid[y*cr+x]) {
1379         str[1] = '\0';
1380         str[0] = state->grid[y*cr+x] + '0';
1381         if (str[0] > '9')
1382             str[0] += 'a' - ('9'+1);
1383         draw_text(fe, tx + TILE_SIZE/2, ty + TILE_SIZE/2,
1384                   FONT_VARIABLE, TILE_SIZE/2, ALIGN_VCENTRE | ALIGN_HCENTRE,
1385                   state->immutable[y*cr+x] ? COL_CLUE : COL_USER, str);
1386     }
1387
1388     unclip(fe);
1389
1390     draw_update(fe, cx, cy, cw, ch);
1391
1392     ds->grid[y*cr+x] = state->grid[y*cr+x];
1393     ds->hl[y*cr+x] = hl;
1394 }
1395
1396 static void game_redraw(frontend *fe, game_drawstate *ds, game_state *oldstate,
1397                         game_state *state, int dir, game_ui *ui,
1398                         float animtime, float flashtime)
1399 {
1400     int c = state->c, r = state->r, cr = c*r;
1401     int x, y;
1402
1403     if (!ds->started) {
1404         /*
1405          * The initial contents of the window are not guaranteed
1406          * and can vary with front ends. To be on the safe side,
1407          * all games should start by drawing a big
1408          * background-colour rectangle covering the whole window.
1409          */
1410         draw_rect(fe, 0, 0, XSIZE(cr), YSIZE(cr), COL_BACKGROUND);
1411
1412         /*
1413          * Draw the grid.
1414          */
1415         for (x = 0; x <= cr; x++) {
1416             int thick = (x % r ? 0 : 1);
1417             draw_rect(fe, BORDER + x*TILE_SIZE - thick, BORDER-1,
1418                       1+2*thick, cr*TILE_SIZE+3, COL_GRID);
1419         }
1420         for (y = 0; y <= cr; y++) {
1421             int thick = (y % c ? 0 : 1);
1422             draw_rect(fe, BORDER-1, BORDER + y*TILE_SIZE - thick,
1423                       cr*TILE_SIZE+3, 1+2*thick, COL_GRID);
1424         }
1425     }
1426
1427     /*
1428      * Draw any numbers which need redrawing.
1429      */
1430     for (x = 0; x < cr; x++) {
1431         for (y = 0; y < cr; y++) {
1432             draw_number(fe, ds, state, x, y,
1433                         (x == ui->hx && y == ui->hy) ||
1434                         (flashtime > 0 &&
1435                          (flashtime <= FLASH_TIME/3 ||
1436                           flashtime >= FLASH_TIME*2/3)));
1437         }
1438     }
1439
1440     /*
1441      * Update the _entire_ grid if necessary.
1442      */
1443     if (!ds->started) {
1444         draw_update(fe, 0, 0, XSIZE(cr), YSIZE(cr));
1445         ds->started = TRUE;
1446     }
1447 }
1448
1449 static float game_anim_length(game_state *oldstate, game_state *newstate,
1450                               int dir)
1451 {
1452     return 0.0F;
1453 }
1454
1455 static float game_flash_length(game_state *oldstate, game_state *newstate,
1456                                int dir)
1457 {
1458     if (!oldstate->completed && newstate->completed)
1459         return FLASH_TIME;
1460     return 0.0F;
1461 }
1462
1463 static int game_wants_statusbar(void)
1464 {
1465     return FALSE;
1466 }
1467
1468 #ifdef COMBINED
1469 #define thegame solo
1470 #endif
1471
1472 const struct game thegame = {
1473     "Solo", "games.solo", TRUE,
1474     default_params,
1475     game_fetch_preset,
1476     decode_params,
1477     encode_params,
1478     free_params,
1479     dup_params,
1480     game_configure,
1481     custom_params,
1482     validate_params,
1483     new_game_seed,
1484     validate_seed,
1485     new_game,
1486     dup_game,
1487     free_game,
1488     new_ui,
1489     free_ui,
1490     make_move,
1491     game_size,
1492     game_colours,
1493     game_new_drawstate,
1494     game_free_drawstate,
1495     game_redraw,
1496     game_anim_length,
1497     game_flash_length,
1498     game_wants_statusbar,
1499 };