solo.c

   1 /*
   2  * solo.c: the number-placing puzzle most popularly known as `Sudoku'.
   3  *
   4  * TODO:
   5  *
   6  *  - reports from users are that `Trivial'-mode puzzles are still
   7  *    rather hard compared to newspapers' easy ones, so some better
   8  *    low-end difficulty grading would be nice
   9  *     + it's possible that really easy puzzles always have
  10  *       _several_ things you can do, so don't make you hunt too
  11  *       hard for the one deduction you can currently make
  12  *     + it's also possible that easy puzzles require fewer
  13  *       cross-eliminations: perhaps there's a higher incidence of
  14  *       things you can deduce by looking only at (say) rows,
  15  *       rather than things you have to check both rows and columns
  16  *       for
  17  *     + but really, what I need to do is find some really easy
  18  *       puzzles and _play_ them, to see what's actually easy about
  19  *       them
  20  *     + while I'm revamping this area, filling in the _last_
  21  *       number in a nearly-full row or column should certainly be
  22  *       permitted even at the lowest difficulty level.
  23  *     + also Owen noticed that `Basic' grids requiring numeric
  24  *       elimination are actually very hard, so I wonder if a
  25  *       difficulty gradation between that and positional-
  26  *       elimination-only might be in order
  27  *     + but it's not good to have _too_ many difficulty levels, or
  28  *       it'll take too long to randomly generate a given level.
  29  *
  30  *  - it might still be nice to do some prioritisation on the
  31  *    removal of numbers from the grid
  32  *     + one possibility is to try to minimise the maximum number
  33  *       of filled squares in any block, which in particular ought
  34  *       to enforce never leaving a completely filled block in the
  35  *       puzzle as presented.
  36  *
  37  *  - alternative interface modes
  38  *     + sudoku.com's Windows program has a palette of possible
  39  *       entries; you select a palette entry first and then click
  40  *       on the square you want it to go in, thus enabling
  41  *       mouse-only play. Useful for PDAs! I don't think it's
  42  *       actually incompatible with the current highlight-then-type
  43  *       approach: you _either_ highlight a palette entry and then
  44  *       click, _or_ you highlight a square and then type. At most
  45  *       one thing is ever highlighted at a time, so there's no way
  46  *       to confuse the two.
  47  *     + then again, I don't actually like sudoku.com's interface;
  48  *       it's too much like a paint package whereas I prefer to
  49  *       think of Solo as a text editor.
  50  *     + another PDA-friendly possibility is a drag interface:
  51  *       _drag_ numbers from the palette into the grid squares.
  52  *       Thought experiments suggest I'd prefer that to the
  53  *       sudoku.com approach, but I haven't actually tried it.
  54  */
  55
  56 /*
  57  * Solo puzzles need to be square overall (since each row and each
  58  * column must contain one of every digit), but they need not be
  59  * subdivided the same way internally. I am going to adopt a
  60  * convention whereby I _always_ refer to `r' as the number of rows
  61  * of _big_ divisions, and `c' as the number of columns of _big_
  62  * divisions. Thus, a 2c by 3r puzzle looks something like this:
  63  *
  64  *   4 5 1 | 2 6 3
  65  *   6 3 2 | 5 4 1
  66  *   ------+------     (Of course, you can't subdivide it the other way
  67  *   1 4 5 | 6 3 2     or you'll get clashes; observe that the 4 in the
  68  *   3 2 6 | 4 1 5     top left would conflict with the 4 in the second
  69  *   ------+------     box down on the left-hand side.)
  70  *   5 1 4 | 3 2 6
  71  *   2 6 3 | 1 5 4
  72  *
  73  * The need for a strong naming convention should now be clear:
  74  * each small box is two rows of digits by three columns, while the
  75  * overall puzzle has three rows of small boxes by two columns. So
  76  * I will (hopefully) consistently use `r' to denote the number of
  77  * rows _of small boxes_ (here 3), which is also the number of
  78  * columns of digits in each small box; and `c' vice versa (here
  79  * 2).
  80  *
  81  * I'm also going to choose arbitrarily to list c first wherever
  82  * possible: the above is a 2x3 puzzle, not a 3x2 one.
  83  */
  84
  85 #include <stdio.h>
  86 #include <stdlib.h>
  87 #include <string.h>
  88 #include <assert.h>
  89 #include <ctype.h>
  90 #include <math.h>
  91
  92 #ifdef STANDALONE_SOLVER
  93 #include <stdarg.h>
  94 int solver_show_working;
  95 #endif
  96
  97 #include "puzzles.h"
  98
  99 #define max(x,y) ((x)>(y)?(x):(y))
 100
 101 /*
 102  * To save space, I store digits internally as unsigned char. This
 103  * imposes a hard limit of 255 on the order of the puzzle. Since
 104  * even a 5x5 takes unacceptably long to generate, I don't see this
 105  * as a serious limitation unless something _really_ impressive
 106  * happens in computing technology; but here's a typedef anyway for
 107  * general good practice.
 108  */
 109 typedef unsigned char digit;
 110 #define ORDER_MAX 255
 111
 112 #define TILE_SIZE 32
 113 #define BORDER 18
 114
 115 #define FLASH_TIME 0.4F
 116
 117 enum { SYMM_NONE, SYMM_ROT2, SYMM_ROT4, SYMM_REF4 };
 118
 119 enum { DIFF_BLOCK, DIFF_SIMPLE, DIFF_INTERSECT,
 120        DIFF_SET, DIFF_RECURSIVE, DIFF_AMBIGUOUS, DIFF_IMPOSSIBLE };
 121
 122 enum {
 123     COL_BACKGROUND,
 124     COL_GRID,
 125     COL_CLUE,
 126     COL_USER,
 127     COL_HIGHLIGHT,
 128     COL_PENCIL,
 129     NCOLOURS
 130 };
 131
 132 struct game_params {
 133     int c, r, symm, diff;
 134 };
 135
 136 struct game_state {
 137     int c, r;
 138     digit *grid;
 139     unsigned char *pencil;             /* c*r*c*r elements */
 140     unsigned char *immutable;          /* marks which digits are clues */
 141     int completed, cheated;
 142 };
 143
 144 static game_params *default_params(void)
 145 {
 146     game_params *ret = snew(game_params);
 147
 148     ret->c = ret->r = 3;
 149     ret->symm = SYMM_ROT2;             /* a plausible default */
 150     ret->diff = DIFF_BLOCK;            /* so is this */
 151
 152     return ret;
 153 }
 154
 155 static void free_params(game_params *params)
 156 {
 157     sfree(params);
 158 }
 159
 160 static game_params *dup_params(game_params *params)
 161 {
 162     game_params *ret = snew(game_params);
 163     *ret = *params;                    /* structure copy */
 164     return ret;
 165 }
 166
 167 static int game_fetch_preset(int i, char **name, game_params **params)
 168 {
 169     static struct {
 170         char *title;
 171         game_params params;
 172     } presets[] = {
 173         { "2x2 Trivial", { 2, 2, SYMM_ROT2, DIFF_BLOCK } },
 174         { "2x3 Basic", { 2, 3, SYMM_ROT2, DIFF_SIMPLE } },
 175         { "3x3 Trivial", { 3, 3, SYMM_ROT2, DIFF_BLOCK } },
 176         { "3x3 Basic", { 3, 3, SYMM_ROT2, DIFF_SIMPLE } },
 177         { "3x3 Intermediate", { 3, 3, SYMM_ROT2, DIFF_INTERSECT } },
 178         { "3x3 Advanced", { 3, 3, SYMM_ROT2, DIFF_SET } },
 179         { "3x3 Unreasonable", { 3, 3, SYMM_ROT2, DIFF_RECURSIVE } },
 180         { "3x4 Basic", { 3, 4, SYMM_ROT2, DIFF_SIMPLE } },
 181         { "4x4 Basic", { 4, 4, SYMM_ROT2, DIFF_SIMPLE } },
 182     };
 183
 184     if (i < 0 || i >= lenof(presets))
 185         return FALSE;
 186
 187     *name = dupstr(presets[i].title);
 188     *params = dup_params(&presets[i].params);
 189
 190     return TRUE;
 191 }
 192
 193 static void decode_params(game_params *ret, char const *string)
 194 {
 195     ret->c = ret->r = atoi(string);
 196     while (*string && isdigit((unsigned char)*string)) string++;
 197     if (*string == 'x') {
 198         string++;
 199         ret->r = atoi(string);
 200         while (*string && isdigit((unsigned char)*string)) string++;
 201     }
 202     while (*string) {
 203         if (*string == 'r' || *string == 'm' || *string == 'a') {
 204             int sn, sc;
 205             sc = *string++;
 206             sn = atoi(string);
 207             while (*string && isdigit((unsigned char)*string)) string++;
 208             if (sc == 'm' && sn == 4)
 209                 ret->symm = SYMM_REF4;
 210             if (sc == 'r' && sn == 4)
 211                 ret->symm = SYMM_ROT4;
 212             if (sc == 'r' && sn == 2)
 213                 ret->symm = SYMM_ROT2;
 214             if (sc == 'a')
 215                 ret->symm = SYMM_NONE;
 216         } else if (*string == 'd') {
 217             string++;
 218             if (*string == 't')        /* trivial */
 219                 string++, ret->diff = DIFF_BLOCK;
 220             else if (*string == 'b')   /* basic */
 221                 string++, ret->diff = DIFF_SIMPLE;
 222             else if (*string == 'i')   /* intermediate */
 223                 string++, ret->diff = DIFF_INTERSECT;
 224             else if (*string == 'a')   /* advanced */
 225                 string++, ret->diff = DIFF_SET;
 226             else if (*string == 'u')   /* unreasonable */
 227                 string++, ret->diff = DIFF_RECURSIVE;
 228         } else
 229             string++;                  /* eat unknown character */
 230     }
 231 }
 232
 233 static char *encode_params(game_params *params, int full)
 234 {
 235     char str[80];
 236
 237     sprintf(str, "%dx%d", params->c, params->r);
 238     if (full) {
 239         switch (params->symm) {
 240           case SYMM_REF4: strcat(str, "m4"); break;
 241           case SYMM_ROT4: strcat(str, "r4"); break;
 242           /* case SYMM_ROT2: strcat(str, "r2"); break; [default] */
 243           case SYMM_NONE: strcat(str, "a"); break;
 244         }
 245         switch (params->diff) {
 246           /* case DIFF_BLOCK: strcat(str, "dt"); break; [default] */
 247           case DIFF_SIMPLE: strcat(str, "db"); break;
 248           case DIFF_INTERSECT: strcat(str, "di"); break;
 249           case DIFF_SET: strcat(str, "da"); break;
 250           case DIFF_RECURSIVE: strcat(str, "du"); break;
 251         }
 252     }
 253     return dupstr(str);
 254 }
 255
 256 static config_item *game_configure(game_params *params)
 257 {
 258     config_item *ret;
 259     char buf[80];
 260
 261     ret = snewn(5, config_item);
 262
 263     ret[0].name = "Columns of sub-blocks";
 264     ret[0].type = C_STRING;
 265     sprintf(buf, "%d", params->c);
 266     ret[0].sval = dupstr(buf);
 267     ret[0].ival = 0;
 268
 269     ret[1].name = "Rows of sub-blocks";
 270     ret[1].type = C_STRING;
 271     sprintf(buf, "%d", params->r);
 272     ret[1].sval = dupstr(buf);
 273     ret[1].ival = 0;
 274
 275     ret[2].name = "Symmetry";
 276     ret[2].type = C_CHOICES;
 277     ret[2].sval = ":None:2-way rotation:4-way rotation:4-way mirror";
 278     ret[2].ival = params->symm;
 279
 280     ret[3].name = "Difficulty";
 281     ret[3].type = C_CHOICES;
 282     ret[3].sval = ":Trivial:Basic:Intermediate:Advanced:Unreasonable";
 283     ret[3].ival = params->diff;
 284
 285     ret[4].name = NULL;
 286     ret[4].type = C_END;
 287     ret[4].sval = NULL;
 288     ret[4].ival = 0;
 289
 290     return ret;
 291 }
 292
 293 static game_params *custom_params(config_item *cfg)
 294 {
 295     game_params *ret = snew(game_params);
 296
 297     ret->c = atoi(cfg[0].sval);
 298     ret->r = atoi(cfg[1].sval);
 299     ret->symm = cfg[2].ival;
 300     ret->diff = cfg[3].ival;
 301
 302     return ret;
 303 }
 304
 305 static char *validate_params(game_params *params)
 306 {
 307     if (params->c < 2 || params->r < 2)
 308         return "Both dimensions must be at least 2";
 309     if (params->c > ORDER_MAX || params->r > ORDER_MAX)
 310         return "Dimensions greater than "STR(ORDER_MAX)" are not supported";
 311     return NULL;
 312 }
 313
 314 /* ----------------------------------------------------------------------
 315  * Full recursive Solo solver.
 316  *
 317  * The algorithm for this solver is shamelessly copied from a
 318  * Python solver written by Andrew Wilkinson (which is GPLed, but
 319  * I've reused only ideas and no code). It mostly just does the
 320  * obvious recursive thing: pick an empty square, put one of the
 321  * possible digits in it, recurse until all squares are filled,
 322  * backtrack and change some choices if necessary.
 323  *
 324  * The clever bit is that every time it chooses which square to
 325  * fill in next, it does so by counting the number of _possible_
 326  * numbers that can go in each square, and it prioritises so that
 327  * it picks a square with the _lowest_ number of possibilities. The
 328  * idea is that filling in lots of the obvious bits (particularly
 329  * any squares with only one possibility) will cut down on the list
 330  * of possibilities for other squares and hence reduce the enormous
 331  * search space as much as possible as early as possible.
 332  *
 333  * In practice the algorithm appeared to work very well; run on
 334  * sample problems from the Times it completed in well under a
 335  * second on my G5 even when written in Python, and given an empty
 336  * grid (so that in principle it would enumerate _all_ solved
 337  * grids!) it found the first valid solution just as quickly. So
 338  * with a bit more randomisation I see no reason not to use this as
 339  * my grid generator.
 340  */
 341
 342 /*
 343  * Internal data structure used in solver to keep track of
 344  * progress.
 345  */
 346 struct rsolve_coord { int x, y, r; };
 347 struct rsolve_usage {
 348     int c, r, cr;                      /* cr == c*r */
 349     /* grid is a copy of the input grid, modified as we go along */
 350     digit *grid;
 351     /* row[y*cr+n-1] TRUE if digit n has been placed in row y */
 352     unsigned char *row;
 353     /* col[x*cr+n-1] TRUE if digit n has been placed in row x */
 354     unsigned char *col;
 355     /* blk[(y*c+x)*cr+n-1] TRUE if digit n has been placed in block (x,y) */
 356     unsigned char *blk;
 357     /* This lists all the empty spaces remaining in the grid. */
 358     struct rsolve_coord *spaces;
 359     int nspaces;
 360     /* If we need randomisation in the solve, this is our random state. */
 361     random_state *rs;
 362     /* Number of solutions so far found, and maximum number we care about. */
 363     int solns, maxsolns;
 364 };
 365
 366 /*
 367  * The real recursive step in the solving function.
 368  */
 369 static void rsolve_real(struct rsolve_usage *usage, digit *grid)
 370 {
 371     int c = usage->c, r = usage->r, cr = usage->cr;
 372     int i, j, n, sx, sy, bestm, bestr;
 373     int *digits;
 374
 375     /*
 376      * Firstly, check for completion! If there are no spaces left
 377      * in the grid, we have a solution.
 378      */
 379     if (usage->nspaces == 0) {
 380         if (!usage->solns) {
 381             /*
 382              * This is our first solution, so fill in the output grid.
 383              */
 384             memcpy(grid, usage->grid, cr * cr);
 385         }
 386         usage->solns++;
 387         return;
 388     }
 389
 390     /*
 391      * Otherwise, there must be at least one space. Find the most
 392      * constrained space, using the `r' field as a tie-breaker.
 393      */
 394     bestm = cr+1;                      /* so that any space will beat it */
 395     bestr = 0;
 396     i = sx = sy = -1;
 397     for (j = 0; j < usage->nspaces; j++) {
 398         int x = usage->spaces[j].x, y = usage->spaces[j].y;
 399         int m;
 400
 401         /*
 402          * Find the number of digits that could go in this space.
 403          */
 404         m = 0;
 405         for (n = 0; n < cr; n++)
 406             if (!usage->row[y*cr+n] && !usage->col[x*cr+n] &&
 407                 !usage->blk[((y/c)*c+(x/r))*cr+n])
 408                 m++;
 409
 410         if (m < bestm || (m == bestm && usage->spaces[j].r < bestr)) {
 411             bestm = m;
 412             bestr = usage->spaces[j].r;
 413             sx = x;
 414             sy = y;
 415             i = j;
 416         }
 417     }
 418
 419     /*
 420      * Swap that square into the final place in the spaces array,
 421      * so that decrementing nspaces will remove it from the list.
 422      */
 423     if (i != usage->nspaces-1) {
 424         struct rsolve_coord t;
 425         t = usage->spaces[usage->nspaces-1];
 426         usage->spaces[usage->nspaces-1] = usage->spaces[i];
 427         usage->spaces[i] = t;
 428     }
 429
 430     /*
 431      * Now we've decided which square to start our recursion at,
 432      * simply go through all possible values, shuffling them
 433      * randomly first if necessary.
 434      */
 435     digits = snewn(bestm, int);
 436     j = 0;
 437     for (n = 0; n < cr; n++)
 438         if (!usage->row[sy*cr+n] && !usage->col[sx*cr+n] &&
 439             !usage->blk[((sy/c)*c+(sx/r))*cr+n]) {
 440             digits[j++] = n+1;
 441         }
 442
 443     if (usage->rs) {
 444         /* shuffle */
 445         for (i = j; i > 1; i--) {
 446             int p = random_upto(usage->rs, i);
 447             if (p != i-1) {
 448                 int t = digits[p];
 449                 digits[p] = digits[i-1];
 450                 digits[i-1] = t;
 451             }
 452         }
 453     }
 454
 455     /* And finally, go through the digit list and actually recurse. */
 456     for (i = 0; i < j; i++) {
 457         n = digits[i];
 458
 459         /* Update the usage structure to reflect the placing of this digit. */
 460         usage->row[sy*cr+n-1] = usage->col[sx*cr+n-1] =
 461             usage->blk[((sy/c)*c+(sx/r))*cr+n-1] = TRUE;
 462         usage->grid[sy*cr+sx] = n;
 463         usage->nspaces--;
 464
 465         /* Call the solver recursively. */
 466         rsolve_real(usage, grid);
 467
 468         /*
 469          * If we have seen as many solutions as we need, terminate
 470          * all processing immediately.
 471          */
 472         if (usage->solns >= usage->maxsolns)
 473             break;
 474
 475         /* Revert the usage structure. */
 476         usage->row[sy*cr+n-1] = usage->col[sx*cr+n-1] =
 477             usage->blk[((sy/c)*c+(sx/r))*cr+n-1] = FALSE;
 478         usage->grid[sy*cr+sx] = 0;
 479         usage->nspaces++;
 480     }
 481
 482     sfree(digits);
 483 }
 484
 485 /*
 486  * Entry point to solver. You give it dimensions and a starting
 487  * grid, which is simply an array of N^4 digits. In that array, 0
 488  * means an empty square, and 1..N mean a clue square.
 489  *
 490  * Return value is the number of solutions found; searching will
 491  * stop after the provided `max'. (Thus, you can pass max==1 to
 492  * indicate that you only care about finding _one_ solution, or
 493  * max==2 to indicate that you want to know the difference between
 494  * a unique and non-unique solution.) The input parameter `grid' is
 495  * also filled in with the _first_ (or only) solution found by the
 496  * solver.
 497  */
 498 static int rsolve(int c, int r, digit *grid, random_state *rs, int max)
 499 {
 500     struct rsolve_usage *usage;
 501     int x, y, cr = c*r;
 502     int ret;
 503
 504     /*
 505      * Create an rsolve_usage structure.
 506      */
 507     usage = snew(struct rsolve_usage);
 508
 509     usage->c = c;
 510     usage->r = r;
 511     usage->cr = cr;
 512
 513     usage->grid = snewn(cr * cr, digit);
 514     memcpy(usage->grid, grid, cr * cr);
 515
 516     usage->row = snewn(cr * cr, unsigned char);
 517     usage->col = snewn(cr * cr, unsigned char);
 518     usage->blk = snewn(cr * cr, unsigned char);
 519     memset(usage->row, FALSE, cr * cr);
 520     memset(usage->col, FALSE, cr * cr);
 521     memset(usage->blk, FALSE, cr * cr);
 522
 523     usage->spaces = snewn(cr * cr, struct rsolve_coord);
 524     usage->nspaces = 0;
 525
 526     usage->solns = 0;
 527     usage->maxsolns = max;
 528
 529     usage->rs = rs;
 530
 531     /*
 532      * Now fill it in with data from the input grid.
 533      */
 534     for (y = 0; y < cr; y++) {
 535         for (x = 0; x < cr; x++) {
 536             int v = grid[y*cr+x];
 537             if (v == 0) {
 538                 usage->spaces[usage->nspaces].x = x;
 539                 usage->spaces[usage->nspaces].y = y;
 540                 if (rs)
 541                     usage->spaces[usage->nspaces].r = random_bits(rs, 31);
 542                 else
 543                     usage->spaces[usage->nspaces].r = usage->nspaces;
 544                 usage->nspaces++;
 545             } else {
 546                 usage->row[y*cr+v-1] = TRUE;
 547                 usage->col[x*cr+v-1] = TRUE;
 548                 usage->blk[((y/c)*c+(x/r))*cr+v-1] = TRUE;
 549             }
 550         }
 551     }
 552
 553     /*
 554      * Run the real recursive solving function.
 555      */
 556     rsolve_real(usage, grid);
 557     ret = usage->solns;
 558
 559     /*
 560      * Clean up the usage structure now we have our answer.
 561      */
 562     sfree(usage->spaces);
 563     sfree(usage->blk);
 564     sfree(usage->col);
 565     sfree(usage->row);
 566     sfree(usage->grid);
 567     sfree(usage);
 568
 569     /*
 570      * And return.
 571      */
 572     return ret;
 573 }
 574
 575 /* ----------------------------------------------------------------------
 576  * End of recursive solver code.
 577  */
 578
 579 /* ----------------------------------------------------------------------
 580  * Less capable non-recursive solver. This one is used to check
 581  * solubility of a grid as we gradually remove numbers from it: by
 582  * verifying a grid using this solver we can ensure it isn't _too_
 583  * hard (e.g. does not actually require guessing and backtracking).
 584  *
 585  * It supports a variety of specific modes of reasoning. By
 586  * enabling or disabling subsets of these modes we can arrange a
 587  * range of difficulty levels.
 588  */
 589
 590 /*
 591  * Modes of reasoning currently supported:
 592  *
 593  *  - Positional elimination: a number must go in a particular
 594  *    square because all the other empty squares in a given
 595  *    row/col/blk are ruled out.
 596  *
 597  *  - Numeric elimination: a square must have a particular number
 598  *    in because all the other numbers that could go in it are
 599  *    ruled out.
 600  *
 601  *  - Intersectional analysis: given two domains which overlap
 602  *    (hence one must be a block, and the other can be a row or
 603  *    col), if the possible locations for a particular number in
 604  *    one of the domains can be narrowed down to the overlap, then
 605  *    that number can be ruled out everywhere but the overlap in
 606  *    the other domain too.
 607  *
 608  *  - Set elimination: if there is a subset of the empty squares
 609  *    within a domain such that the union of the possible numbers
 610  *    in that subset has the same size as the subset itself, then
 611  *    those numbers can be ruled out everywhere else in the domain.
 612  *    (For example, if there are five empty squares and the
 613  *    possible numbers in each are 12, 23, 13, 134 and 1345, then
 614  *    the first three empty squares form such a subset: the numbers
 615  *    1, 2 and 3 _must_ be in those three squares in some
 616  *    permutation, and hence we can deduce none of them can be in
 617  *    the fourth or fifth squares.)
 618  *     + You can also see this the other way round, concentrating
 619  *       on numbers rather than squares: if there is a subset of
 620  *       the unplaced numbers within a domain such that the union
 621  *       of all their possible positions has the same size as the
 622  *       subset itself, then all other numbers can be ruled out for
 623  *       those positions. However, it turns out that this is
 624  *       exactly equivalent to the first formulation at all times:
 625  *       there is a 1-1 correspondence between suitable subsets of
 626  *       the unplaced numbers and suitable subsets of the unfilled
 627  *       places, found by taking the _complement_ of the union of
 628  *       the numbers' possible positions (or the spaces' possible
 629  *       contents).
 630  */
 631
 632 /*
 633  * Within this solver, I'm going to transform all y-coordinates by
 634  * inverting the significance of the block number and the position
 635  * within the block. That is, we will start with the top row of
 636  * each block in order, then the second row of each block in order,
 637  * etc.
 638  *
 639  * This transformation has the enormous advantage that it means
 640  * every row, column _and_ block is described by an arithmetic
 641  * progression of coordinates within the cubic array, so that I can
 642  * use the same very simple function to do blockwise, row-wise and
 643  * column-wise elimination.
 644  */
 645 #define YTRANS(y) (((y)%c)*r+(y)/c)
 646 #define YUNTRANS(y) (((y)%r)*c+(y)/r)
 647
 648 struct nsolve_usage {
 649     int c, r, cr;
 650     /*
 651      * We set up a cubic array, indexed by x, y and digit; each
 652      * element of this array is TRUE or FALSE according to whether
 653      * or not that digit _could_ in principle go in that position.
 654      *
 655      * The way to index this array is cube[(x*cr+y)*cr+n-1].
 656      * y-coordinates in here are transformed.
 657      */
 658     unsigned char *cube;
 659     /*
 660      * This is the grid in which we write down our final
 661      * deductions. y-coordinates in here are _not_ transformed.
 662      */
 663     digit *grid;
 664     /*
 665      * Now we keep track, at a slightly higher level, of what we
 666      * have yet to work out, to prevent doing the same deduction
 667      * many times.
 668      */
 669     /* row[y*cr+n-1] TRUE if digit n has been placed in row y */
 670     unsigned char *row;
 671     /* col[x*cr+n-1] TRUE if digit n has been placed in row x */
 672     unsigned char *col;
 673     /* blk[(y*c+x)*cr+n-1] TRUE if digit n has been placed in block (x,y) */
 674     unsigned char *blk;
 675 };
 676 #define cubepos(x,y,n) (((x)*usage->cr+(y))*usage->cr+(n)-1)
 677 #define cube(x,y,n) (usage->cube[cubepos(x,y,n)])
 678
 679 /*
 680  * Function called when we are certain that a particular square has
 681  * a particular number in it. The y-coordinate passed in here is
 682  * transformed.
 683  */
 684 static void nsolve_place(struct nsolve_usage *usage, int x, int y, int n)
 685 {
 686     int c = usage->c, r = usage->r, cr = usage->cr;
 687     int i, j, bx, by;
 688
 689     assert(cube(x,y,n));
 690
 691     /*
 692      * Rule out all other numbers in this square.
 693      */
 694     for (i = 1; i <= cr; i++)
 695         if (i != n)
 696             cube(x,y,i) = FALSE;
 697
 698     /*
 699      * Rule out this number in all other positions in the row.
 700      */
 701     for (i = 0; i < cr; i++)
 702         if (i != y)
 703             cube(x,i,n) = FALSE;
 704
 705     /*
 706      * Rule out this number in all other positions in the column.
 707      */
 708     for (i = 0; i < cr; i++)
 709         if (i != x)
 710             cube(i,y,n) = FALSE;
 711
 712     /*
 713      * Rule out this number in all other positions in the block.
 714      */
 715     bx = (x/r)*r;
 716     by = y % r;
 717     for (i = 0; i < r; i++)
 718         for (j = 0; j < c; j++)
 719             if (bx+i != x || by+j*r != y)
 720                 cube(bx+i,by+j*r,n) = FALSE;
 721
 722     /*
 723      * Enter the number in the result grid.
 724      */
 725     usage->grid[YUNTRANS(y)*cr+x] = n;
 726
 727     /*
 728      * Cross out this number from the list of numbers left to place
 729      * in its row, its column and its block.
 730      */
 731     usage->row[y*cr+n-1] = usage->col[x*cr+n-1] =
 732         usage->blk[((y%r)*c+(x/r))*cr+n-1] = TRUE;
 733 }
 734
 735 static int nsolve_elim(struct nsolve_usage *usage, int start, int step
 736 #ifdef STANDALONE_SOLVER
 737                        , char *fmt, ...
 738 #endif
 739                        )
 740 {
 741     int c = usage->c, r = usage->r, cr = c*r;
 742     int fpos, m, i;
 743
 744     /*
 745      * Count the number of set bits within this section of the
 746      * cube.
 747      */
 748     m = 0;
 749     fpos = -1;
 750     for (i = 0; i < cr; i++)
 751         if (usage->cube[start+i*step]) {
 752             fpos = start+i*step;
 753             m++;
 754         }
 755
 756     if (m == 1) {
 757         int x, y, n;
 758         assert(fpos >= 0);
 759
 760         n = 1 + fpos % cr;
 761         y = fpos / cr;
 762         x = y / cr;
 763         y %= cr;
 764
 765         if (!usage->grid[YUNTRANS(y)*cr+x]) {
 766 #ifdef STANDALONE_SOLVER
 767             if (solver_show_working) {
 768                 va_list ap;
 769                 va_start(ap, fmt);
 770                 vprintf(fmt, ap);
 771                 va_end(ap);
 772                 printf(":\n  placing %d at (%d,%d)\n",
 773                        n, 1+x, 1+YUNTRANS(y));
 774             }
 775 #endif
 776             nsolve_place(usage, x, y, n);
 777             return TRUE;
 778         }
 779     }
 780
 781     return FALSE;
 782 }
 783
 784 static int nsolve_intersect(struct nsolve_usage *usage,
 785                             int start1, int step1, int start2, int step2
 786 #ifdef STANDALONE_SOLVER
 787                             , char *fmt, ...
 788 #endif
 789                             )
 790 {
 791     int c = usage->c, r = usage->r, cr = c*r;
 792     int ret, i;
 793
 794     /*
 795      * Loop over the first domain and see if there's any set bit
 796      * not also in the second.
 797      */
 798     for (i = 0; i < cr; i++) {
 799         int p = start1+i*step1;
 800         if (usage->cube[p] &&
 801             !(p >= start2 && p < start2+cr*step2 &&
 802               (p - start2) % step2 == 0))
 803             return FALSE;              /* there is, so we can't deduce */
 804     }
 805
 806     /*
 807      * We have determined that all set bits in the first domain are
 808      * within its overlap with the second. So loop over the second
 809      * domain and remove all set bits that aren't also in that
 810      * overlap; return TRUE iff we actually _did_ anything.
 811      */
 812     ret = FALSE;
 813     for (i = 0; i < cr; i++) {
 814         int p = start2+i*step2;
 815         if (usage->cube[p] &&
 816             !(p >= start1 && p < start1+cr*step1 && (p - start1) % step1 == 0))
 817         {
 818 #ifdef STANDALONE_SOLVER
 819             if (solver_show_working) {
 820                 int px, py, pn;
 821
 822                 if (!ret) {
 823                     va_list ap;
 824                     va_start(ap, fmt);
 825                     vprintf(fmt, ap);
 826                     va_end(ap);
 827                     printf(":\n");
 828                 }
 829
 830                 pn = 1 + p % cr;
 831                 py = p / cr;
 832                 px = py / cr;
 833                 py %= cr;
 834
 835                 printf("  ruling out %d at (%d,%d)\n",
 836                        pn, 1+px, 1+YUNTRANS(py));
 837             }
 838 #endif
 839             ret = TRUE;                /* we did something */
 840             usage->cube[p] = 0;
 841         }
 842     }
 843
 844     return ret;
 845 }
 846
 847 static int nsolve_set(struct nsolve_usage *usage,
 848                       int start, int step1, int step2
 849 #ifdef STANDALONE_SOLVER
 850                       , char *fmt, ...
 851 #endif
 852                       )
 853 {
 854     int c = usage->c, r = usage->r, cr = c*r;
 855     int i, j, n, count;
 856     unsigned char *grid = snewn(cr*cr, unsigned char);
 857     unsigned char *rowidx = snewn(cr, unsigned char);
 858     unsigned char *colidx = snewn(cr, unsigned char);
 859     unsigned char *set = snewn(cr, unsigned char);
 860
 861     /*
 862      * We are passed a cr-by-cr matrix of booleans. Our first job
 863      * is to winnow it by finding any definite placements - i.e.
 864      * any row with a solitary 1 - and discarding that row and the
 865      * column containing the 1.
 866      */
 867     memset(rowidx, TRUE, cr);
 868     memset(colidx, TRUE, cr);
 869     for (i = 0; i < cr; i++) {
 870         int count = 0, first = -1;
 871         for (j = 0; j < cr; j++)
 872             if (usage->cube[start+i*step1+j*step2])
 873                 first = j, count++;
 874         if (count == 0) {
 875             /*
 876              * This condition actually marks a completely insoluble
 877              * (i.e. internally inconsistent) puzzle. We return and
 878              * report no progress made.
 879              */
 880             return FALSE;
 881         }
 882         if (count == 1)
 883             rowidx[i] = colidx[first] = FALSE;
 884     }
 885
 886     /*
 887      * Convert each of rowidx/colidx from a list of 0s and 1s to a
 888      * list of the indices of the 1s.
 889      */
 890     for (i = j = 0; i < cr; i++)
 891         if (rowidx[i])
 892             rowidx[j++] = i;
 893     n = j;
 894     for (i = j = 0; i < cr; i++)
 895         if (colidx[i])
 896             colidx[j++] = i;
 897     assert(n == j);
 898
 899     /*
 900      * And create the smaller matrix.
 901      */
 902     for (i = 0; i < n; i++)
 903         for (j = 0; j < n; j++)
 904             grid[i*cr+j] = usage->cube[start+rowidx[i]*step1+colidx[j]*step2];
 905
 906     /*
 907      * Having done that, we now have a matrix in which every row
 908      * has at least two 1s in. Now we search to see if we can find
 909      * a rectangle of zeroes (in the set-theoretic sense of
 910      * `rectangle', i.e. a subset of rows crossed with a subset of
 911      * columns) whose width and height add up to n.
 912      */
 913
 914     memset(set, 0, n);
 915     count = 0;
 916     while (1) {
 917         /*
 918          * We have a candidate set. If its size is <=1 or >=n-1
 919          * then we move on immediately.
 920          */
 921         if (count > 1 && count < n-1) {
 922             /*
 923              * The number of rows we need is n-count. See if we can
 924              * find that many rows which each have a zero in all
 925              * the positions listed in `set'.
 926              */
 927             int rows = 0;
 928             for (i = 0; i < n; i++) {
 929                 int ok = TRUE;
 930                 for (j = 0; j < n; j++)
 931                     if (set[j] && grid[i*cr+j]) {
 932                         ok = FALSE;
 933                         break;
 934                     }
 935                 if (ok)
 936                     rows++;
 937             }
 938
 939             /*
 940              * We expect never to be able to get _more_ than
 941              * n-count suitable rows: this would imply that (for
 942              * example) there are four numbers which between them
 943              * have at most three possible positions, and hence it
 944              * indicates a faulty deduction before this point or
 945              * even a bogus clue.
 946              */
 947             assert(rows <= n - count);
 948             if (rows >= n - count) {
 949                 int progress = FALSE;
 950
 951                 /*
 952                  * We've got one! Now, for each row which _doesn't_
 953                  * satisfy the criterion, eliminate all its set
 954                  * bits in the positions _not_ listed in `set'.
 955                  * Return TRUE (meaning progress has been made) if
 956                  * we successfully eliminated anything at all.
 957                  *
 958                  * This involves referring back through
 959                  * rowidx/colidx in order to work out which actual
 960                  * positions in the cube to meddle with.
 961                  */
 962                 for (i = 0; i < n; i++) {
 963                     int ok = TRUE;
 964                     for (j = 0; j < n; j++)
 965                         if (set[j] && grid[i*cr+j]) {
 966                             ok = FALSE;
 967                             break;
 968                         }
 969                     if (!ok) {
 970                         for (j = 0; j < n; j++)
 971                             if (!set[j] && grid[i*cr+j]) {
 972                                 int fpos = (start+rowidx[i]*step1+
 973                                             colidx[j]*step2);
 974 #ifdef STANDALONE_SOLVER
 975                                 if (solver_show_working) {
 976                                     int px, py, pn;
 977
 978                                     if (!progress) {
 979                                         va_list ap;
 980                                         va_start(ap, fmt);
 981                                         vprintf(fmt, ap);
 982                                         va_end(ap);
 983                                         printf(":\n");
 984                                     }
 985
 986                                     pn = 1 + fpos % cr;
 987                                     py = fpos / cr;
 988                                     px = py / cr;
 989                                     py %= cr;
 990
 991                                     printf("  ruling out %d at (%d,%d)\n",
 992                                            pn, 1+px, 1+YUNTRANS(py));
 993                                 }
 994 #endif
 995                                 progress = TRUE;
 996                                 usage->cube[fpos] = FALSE;
 997                             }
 998                     }
 999                 }
1000
1001                 if (progress) {
1002                     sfree(set);
1003                     sfree(colidx);
1004                     sfree(rowidx);
1005                     sfree(grid);
1006                     return TRUE;
1007                 }
1008             }
1009         }
1010
1011         /*
1012          * Binary increment: change the rightmost 0 to a 1, and
1013          * change all 1s to the right of it to 0s.
1014          */
1015         i = n;
1016         while (i > 0 && set[i-1])
1017             set[--i] = 0, count--;
1018         if (i > 0)
1019             set[--i] = 1, count++;
1020         else
1021             break;                     /* done */
1022     }
1023
1024     sfree(set);
1025     sfree(colidx);
1026     sfree(rowidx);
1027     sfree(grid);
1028
1029     return FALSE;
1030 }
1031
1032 static int nsolve(int c, int r, digit *grid)
1033 {
1034     struct nsolve_usage *usage;
1035     int cr = c*r;
1036     int x, y, n;
1037     int diff = DIFF_BLOCK;
1038
1039     /*
1040      * Set up a usage structure as a clean slate (everything
1041      * possible).
1042      */
1043     usage = snew(struct nsolve_usage);
1044     usage->c = c;
1045     usage->r = r;
1046     usage->cr = cr;
1047     usage->cube = snewn(cr*cr*cr, unsigned char);
1048     usage->grid = grid;                /* write straight back to the input */
1049     memset(usage->cube, TRUE, cr*cr*cr);
1050
1051     usage->row = snewn(cr * cr, unsigned char);
1052     usage->col = snewn(cr * cr, unsigned char);
1053     usage->blk = snewn(cr * cr, unsigned char);
1054     memset(usage->row, FALSE, cr * cr);
1055     memset(usage->col, FALSE, cr * cr);
1056     memset(usage->blk, FALSE, cr * cr);
1057
1058     /*
1059      * Place all the clue numbers we are given.
1060      */
1061     for (x = 0; x < cr; x++)
1062         for (y = 0; y < cr; y++)
1063             if (grid[y*cr+x])
1064                 nsolve_place(usage, x, YTRANS(y), grid[y*cr+x]);
1065
1066     /*
1067      * Now loop over the grid repeatedly trying all permitted modes
1068      * of reasoning. The loop terminates if we complete an
1069      * iteration without making any progress; we then return
1070      * failure or success depending on whether the grid is full or
1071      * not.
1072      */
1073     while (1) {
1074         /*
1075          * I'd like to write `continue;' inside each of the
1076          * following loops, so that the solver returns here after
1077          * making some progress. However, I can't specify that I
1078          * want to continue an outer loop rather than the innermost
1079          * one, so I'm apologetically resorting to a goto.
1080          */
1081         cont:
1082
1083         /*
1084          * Blockwise positional elimination.
1085          */
1086         for (x = 0; x < cr; x += r)
1087             for (y = 0; y < r; y++)
1088                 for (n = 1; n <= cr; n++)
1089                     if (!usage->blk[(y*c+(x/r))*cr+n-1] &&
1090                         nsolve_elim(usage, cubepos(x,y,n), r*cr
1091 #ifdef STANDALONE_SOLVER
1092                                     , "positional elimination,"
1093                                     " block (%d,%d)", 1+x/r, 1+y
1094 #endif
1095                                     )) {
1096                         diff = max(diff, DIFF_BLOCK);
1097                         goto cont;
1098                     }
1099
1100         /*
1101          * Row-wise positional elimination.
1102          */
1103         for (y = 0; y < cr; y++)
1104             for (n = 1; n <= cr; n++)
1105                 if (!usage->row[y*cr+n-1] &&
1106                     nsolve_elim(usage, cubepos(0,y,n), cr*cr
1107 #ifdef STANDALONE_SOLVER
1108                                 , "positional elimination,"
1109                                 " row %d", 1+YUNTRANS(y)
1110 #endif
1111                                 )) {
1112                     diff = max(diff, DIFF_SIMPLE);
1113                     goto cont;
1114                 }
1115         /*
1116          * Column-wise positional elimination.
1117          */
1118         for (x = 0; x < cr; x++)
1119             for (n = 1; n <= cr; n++)
1120                 if (!usage->col[x*cr+n-1] &&
1121                     nsolve_elim(usage, cubepos(x,0,n), cr
1122 #ifdef STANDALONE_SOLVER
1123                                 , "positional elimination," " column %d", 1+x
1124 #endif
1125                                 )) {
1126                     diff = max(diff, DIFF_SIMPLE);
1127                     goto cont;
1128                 }
1129
1130         /*
1131          * Numeric elimination.
1132          */
1133         for (x = 0; x < cr; x++)
1134             for (y = 0; y < cr; y++)
1135                 if (!usage->grid[YUNTRANS(y)*cr+x] &&
1136                     nsolve_elim(usage, cubepos(x,y,1), 1
1137 #ifdef STANDALONE_SOLVER
1138                                 , "numeric elimination at (%d,%d)", 1+x,
1139                                 1+YUNTRANS(y)
1140 #endif
1141                                 )) {
1142                     diff = max(diff, DIFF_SIMPLE);
1143                     goto cont;
1144                 }
1145
1146         /*
1147          * Intersectional analysis, rows vs blocks.
1148          */
1149         for (y = 0; y < cr; y++)
1150             for (x = 0; x < cr; x += r)
1151                 for (n = 1; n <= cr; n++)
1152                     if (!usage->row[y*cr+n-1] &&
1153                         !usage->blk[((y%r)*c+(x/r))*cr+n-1] &&
1154                         (nsolve_intersect(usage, cubepos(0,y,n), cr*cr,
1155                                           cubepos(x,y%r,n), r*cr
1156 #ifdef STANDALONE_SOLVER
1157                                           , "intersectional analysis,"
1158                                           " row %d vs block (%d,%d)",
1159                                           1+YUNTRANS(y), 1+x/r, 1+y%r
1160 #endif
1161                                           ) ||
1162                          nsolve_intersect(usage, cubepos(x,y%r,n), r*cr,
1163                                           cubepos(0,y,n), cr*cr
1164 #ifdef STANDALONE_SOLVER
1165                                           , "intersectional analysis,"
1166                                           " block (%d,%d) vs row %d",
1167                                           1+x/r, 1+y%r, 1+YUNTRANS(y)
1168 #endif
1169                                           ))) {
1170                         diff = max(diff, DIFF_INTERSECT);
1171                         goto cont;
1172                     }
1173
1174         /*
1175          * Intersectional analysis, columns vs blocks.
1176          */
1177         for (x = 0; x < cr; x++)
1178             for (y = 0; y < r; y++)
1179                 for (n = 1; n <= cr; n++)
1180                     if (!usage->col[x*cr+n-1] &&
1181                         !usage->blk[(y*c+(x/r))*cr+n-1] &&
1182                         (nsolve_intersect(usage, cubepos(x,0,n), cr,
1183                                           cubepos((x/r)*r,y,n), r*cr
1184 #ifdef STANDALONE_SOLVER
1185                                           , "intersectional analysis,"
1186                                           " column %d vs block (%d,%d)",
1187                                           1+x, 1+x/r, 1+y
1188 #endif
1189                                           ) ||
1190                          nsolve_intersect(usage, cubepos((x/r)*r,y,n), r*cr,
1191                                           cubepos(x,0,n), cr
1192 #ifdef STANDALONE_SOLVER
1193                                           , "intersectional analysis,"
1194                                           " block (%d,%d) vs column %d",
1195                                           1+x/r, 1+y, 1+x
1196 #endif
1197                                           ))) {
1198                         diff = max(diff, DIFF_INTERSECT);
1199                         goto cont;
1200                     }
1201
1202         /*
1203          * Blockwise set elimination.
1204          */
1205         for (x = 0; x < cr; x += r)
1206             for (y = 0; y < r; y++)
1207                 if (nsolve_set(usage, cubepos(x,y,1), r*cr, 1
1208 #ifdef STANDALONE_SOLVER
1209                                , "set elimination, block (%d,%d)", 1+x/r, 1+y
1210 #endif
1211                                )) {
1212                     diff = max(diff, DIFF_SET);
1213                     goto cont;
1214                 }
1215
1216         /*
1217          * Row-wise set elimination.
1218          */
1219         for (y = 0; y < cr; y++)
1220             if (nsolve_set(usage, cubepos(0,y,1), cr*cr, 1
1221 #ifdef STANDALONE_SOLVER
1222                            , "set elimination, row %d", 1+YUNTRANS(y)
1223 #endif
1224                            )) {
1225                 diff = max(diff, DIFF_SET);
1226                 goto cont;
1227             }
1228
1229         /*
1230          * Column-wise set elimination.
1231          */
1232         for (x = 0; x < cr; x++)
1233             if (nsolve_set(usage, cubepos(x,0,1), cr, 1
1234 #ifdef STANDALONE_SOLVER
1235                            , "set elimination, column %d", 1+x
1236 #endif
1237                            )) {
1238                 diff = max(diff, DIFF_SET);
1239                 goto cont;
1240             }
1241
1242         /*
1243          * If we reach here, we have made no deductions in this
1244          * iteration, so the algorithm terminates.
1245          */
1246         break;
1247     }
1248
1249     sfree(usage->cube);
1250     sfree(usage->row);
1251     sfree(usage->col);
1252     sfree(usage->blk);
1253     sfree(usage);
1254
1255     for (x = 0; x < cr; x++)
1256         for (y = 0; y < cr; y++)
1257             if (!grid[y*cr+x])
1258                 return DIFF_IMPOSSIBLE;
1259     return diff;
1260 }
1261
1262 /* ----------------------------------------------------------------------
1263  * End of non-recursive solver code.
1264  */
1265
1266 /*
1267  * Check whether a grid contains a valid complete puzzle.
1268  */
1269 static int check_valid(int c, int r, digit *grid)
1270 {
1271     int cr = c*r;
1272     unsigned char *used;
1273     int x, y, n;
1274
1275     used = snewn(cr, unsigned char);
1276
1277     /*
1278      * Check that each row contains precisely one of everything.
1279      */
1280     for (y = 0; y < cr; y++) {
1281         memset(used, FALSE, cr);
1282         for (x = 0; x < cr; x++)
1283             if (grid[y*cr+x] > 0 && grid[y*cr+x] <= cr)
1284                 used[grid[y*cr+x]-1] = TRUE;
1285         for (n = 0; n < cr; n++)
1286             if (!used[n]) {
1287                 sfree(used);
1288                 return FALSE;
1289             }
1290     }
1291
1292     /*
1293      * Check that each column contains precisely one of everything.
1294      */
1295     for (x = 0; x < cr; x++) {
1296         memset(used, FALSE, cr);
1297         for (y = 0; y < cr; y++)
1298             if (grid[y*cr+x] > 0 && grid[y*cr+x] <= cr)
1299                 used[grid[y*cr+x]-1] = TRUE;
1300         for (n = 0; n < cr; n++)
1301             if (!used[n]) {
1302                 sfree(used);
1303                 return FALSE;
1304             }
1305     }
1306
1307     /*
1308      * Check that each block contains precisely one of everything.
1309      */
1310     for (x = 0; x < cr; x += r) {
1311         for (y = 0; y < cr; y += c) {
1312             int xx, yy;
1313             memset(used, FALSE, cr);
1314             for (xx = x; xx < x+r; xx++)
1315                 for (yy = 0; yy < y+c; yy++)
1316                     if (grid[yy*cr+xx] > 0 && grid[yy*cr+xx] <= cr)
1317                         used[grid[yy*cr+xx]-1] = TRUE;
1318             for (n = 0; n < cr; n++)
1319                 if (!used[n]) {
1320                     sfree(used);
1321                     return FALSE;
1322                 }
1323         }
1324     }
1325
1326     sfree(used);
1327     return TRUE;
1328 }
1329
1330 static void symmetry_limit(game_params *params, int *xlim, int *ylim, int s)
1331 {
1332     int c = params->c, r = params->r, cr = c*r;
1333
1334     switch (s) {
1335       case SYMM_NONE:
1336         *xlim = *ylim = cr;
1337         break;
1338       case SYMM_ROT2:
1339         *xlim = (cr+1) / 2;
1340         *ylim = cr;
1341         break;
1342       case SYMM_REF4:
1343       case SYMM_ROT4:
1344         *xlim = *ylim = (cr+1) / 2;
1345         break;
1346     }
1347 }
1348
1349 static int symmetries(game_params *params, int x, int y, int *output, int s)
1350 {
1351     int c = params->c, r = params->r, cr = c*r;
1352     int i = 0;
1353
1354     *output++ = x;
1355     *output++ = y;
1356     i++;
1357
1358     switch (s) {
1359       case SYMM_NONE:
1360         break;                         /* just x,y is all we need */
1361       case SYMM_REF4:
1362       case SYMM_ROT4:
1363         switch (s) {
1364           case SYMM_REF4:
1365             *output++ = cr - 1 - x;
1366             *output++ = y;
1367             i++;
1368
1369             *output++ = x;
1370             *output++ = cr - 1 - y;
1371             i++;
1372             break;
1373           case SYMM_ROT4:
1374             *output++ = cr - 1 - y;
1375             *output++ = x;
1376             i++;
1377
1378             *output++ = y;
1379             *output++ = cr - 1 - x;
1380             i++;
1381             break;
1382         }
1383         /* fall through */
1384       case SYMM_ROT2:
1385         *output++ = cr - 1 - x;
1386         *output++ = cr - 1 - y;
1387         i++;
1388         break;
1389     }
1390
1391     return i;
1392 }
1393
1394 struct game_aux_info {
1395     int c, r;
1396     digit *grid;
1397 };
1398
1399 static char *new_game_desc(game_params *params, random_state *rs,
1400                            game_aux_info **aux, int interactive)
1401 {
1402     int c = params->c, r = params->r, cr = c*r;
1403     int area = cr*cr;
1404     digit *grid, *grid2;
1405     struct xy { int x, y; } *locs;
1406     int nlocs;
1407     int ret;
1408     char *desc;
1409     int coords[16], ncoords;
1410     int xlim, ylim;
1411     int maxdiff, recursing;
1412
1413     /*
1414      * Adjust the maximum difficulty level to be consistent with
1415      * the puzzle size: all 2x2 puzzles appear to be Trivial
1416      * (DIFF_BLOCK) so we cannot hold out for even a Basic
1417      * (DIFF_SIMPLE) one.
1418      */
1419     maxdiff = params->diff;
1420     if (c == 2 && r == 2)
1421         maxdiff = DIFF_BLOCK;
1422
1423     grid = snewn(area, digit);
1424     locs = snewn(area, struct xy);
1425     grid2 = snewn(area, digit);
1426
1427     /*
1428      * Loop until we get a grid of the required difficulty. This is
1429      * nasty, but it seems to be unpleasantly hard to generate
1430      * difficult grids otherwise.
1431      */
1432     do {
1433         /*
1434          * Start the recursive solver with an empty grid to generate a
1435          * random solved state.
1436          */
1437         memset(grid, 0, area);
1438         ret = rsolve(c, r, grid, rs, 1);
1439         assert(ret == 1);
1440         assert(check_valid(c, r, grid));
1441
1442         /*
1443          * Save the solved grid in the aux_info.
1444          */
1445         {
1446             game_aux_info *ai = snew(game_aux_info);
1447             ai->c = c;
1448             ai->r = r;
1449             ai->grid = snewn(cr * cr, digit);
1450             memcpy(ai->grid, grid, cr * cr * sizeof(digit));
1451             *aux = ai;
1452         }
1453
1454         /*
1455          * Now we have a solved grid, start removing things from it
1456          * while preserving solubility.
1457          */
1458         symmetry_limit(params, &xlim, &ylim, params->symm);
1459         recursing = FALSE;
1460         while (1) {
1461             int x, y, i, j;
1462
1463             /*
1464              * Iterate over the grid and enumerate all the filled
1465              * squares we could empty.
1466              */
1467             nlocs = 0;
1468
1469             for (x = 0; x < xlim; x++)
1470                 for (y = 0; y < ylim; y++)
1471                     if (grid[y*cr+x]) {
1472                         locs[nlocs].x = x;
1473                         locs[nlocs].y = y;
1474                         nlocs++;
1475                     }
1476
1477             /*
1478              * Now shuffle that list.
1479              */
1480             for (i = nlocs; i > 1; i--) {
1481                 int p = random_upto(rs, i);
1482                 if (p != i-1) {
1483                     struct xy t = locs[p];
1484                     locs[p] = locs[i-1];
1485                     locs[i-1] = t;
1486                 }
1487             }
1488
1489             /*
1490              * Now loop over the shuffled list and, for each element,
1491              * see whether removing that element (and its reflections)
1492              * from the grid will still leave the grid soluble by
1493              * nsolve.
1494              */
1495             for (i = 0; i < nlocs; i++) {
1496                 int ret;
1497
1498                 x = locs[i].x;
1499                 y = locs[i].y;
1500
1501                 memcpy(grid2, grid, area);
1502                 ncoords = symmetries(params, x, y, coords, params->symm);
1503                 for (j = 0; j < ncoords; j++)
1504                     grid2[coords[2*j+1]*cr+coords[2*j]] = 0;
1505
1506                 if (recursing)
1507                     ret = (rsolve(c, r, grid2, NULL, 2) == 1);
1508                 else
1509                     ret = (nsolve(c, r, grid2) <= maxdiff);
1510
1511                 if (ret) {
1512                     for (j = 0; j < ncoords; j++)
1513                         grid[coords[2*j+1]*cr+coords[2*j]] = 0;
1514                     break;
1515                 }
1516             }
1517
1518             if (i == nlocs) {
1519                 /*
1520                  * There was nothing we could remove without
1521                  * destroying solvability. If we're trying to
1522                  * generate a recursion-only grid and haven't
1523                  * switched over to rsolve yet, we now do;
1524                  * otherwise we give up.
1525                  */
1526                 if (maxdiff == DIFF_RECURSIVE && !recursing) {
1527                     recursing = TRUE;
1528                 } else {
1529                     break;
1530                 }
1531             }
1532         }
1533
1534         memcpy(grid2, grid, area);
1535     } while (nsolve(c, r, grid2) < maxdiff);
1536
1537     sfree(grid2);
1538     sfree(locs);
1539
1540     /*
1541      * Now we have the grid as it will be presented to the user.
1542      * Encode it in a game desc.
1543      */
1544     {
1545         char *p;
1546         int run, i;
1547
1548         desc = snewn(5 * area, char);
1549         p = desc;
1550         run = 0;
1551         for (i = 0; i <= area; i++) {
1552             int n = (i < area ? grid[i] : -1);
1553
1554             if (!n)
1555                 run++;
1556             else {
1557                 if (run) {
1558                     while (run > 0) {
1559                         int c = 'a' - 1 + run;
1560                         if (run > 26)
1561                             c = 'z';
1562                         *p++ = c;
1563                         run -= c - ('a' - 1);
1564                     }
1565                 } else {
1566                     /*
1567                      * If there's a number in the very top left or
1568                      * bottom right, there's no point putting an
1569                      * unnecessary _ before or after it.
1570                      */
1571                     if (p > desc && n > 0)
1572                         *p++ = '_';
1573                 }
1574                 if (n > 0)
1575                     p += sprintf(p, "%d", n);
1576                 run = 0;
1577             }
1578         }
1579         assert(p - desc < 5 * area);
1580         *p++ = '\0';
1581         desc = sresize(desc, p - desc, char);
1582     }
1583
1584     sfree(grid);
1585
1586     return desc;
1587 }
1588
1589 static void game_free_aux_info(game_aux_info *aux)
1590 {
1591     sfree(aux->grid);
1592     sfree(aux);
1593 }
1594
1595 static char *validate_desc(game_params *params, char *desc)
1596 {
1597     int area = params->r * params->r * params->c * params->c;
1598     int squares = 0;
1599
1600     while (*desc) {
1601         int n = *desc++;
1602         if (n >= 'a' && n <= 'z') {
1603             squares += n - 'a' + 1;
1604         } else if (n == '_') {
1605             /* do nothing */;
1606         } else if (n > '0' && n <= '9') {
1607             squares++;
1608             while (*desc >= '0' && *desc <= '9')
1609                 desc++;
1610         } else
1611             return "Invalid character in game description";
1612     }
1613
1614     if (squares < area)
1615         return "Not enough data to fill grid";
1616
1617     if (squares > area)
1618         return "Too much data to fit in grid";
1619
1620     return NULL;
1621 }
1622
1623 static game_state *new_game(midend_data *me, game_params *params, char *desc)
1624 {
1625     game_state *state = snew(game_state);
1626     int c = params->c, r = params->r, cr = c*r, area = cr * cr;
1627     int i;
1628
1629     state->c = params->c;
1630     state->r = params->r;
1631
1632     state->grid = snewn(area, digit);
1633     state->pencil = snewn(area * cr, unsigned char);
1634     memset(state->pencil, 0, area * cr);
1635     state->immutable = snewn(area, unsigned char);
1636     memset(state->immutable, FALSE, area);
1637
1638     state->completed = state->cheated = FALSE;
1639
1640     i = 0;
1641     while (*desc) {
1642         int n = *desc++;
1643         if (n >= 'a' && n <= 'z') {
1644             int run = n - 'a' + 1;
1645             assert(i + run <= area);
1646             while (run-- > 0)
1647                 state->grid[i++] = 0;
1648         } else if (n == '_') {
1649             /* do nothing */;
1650         } else if (n > '0' && n <= '9') {
1651             assert(i < area);
1652             state->immutable[i] = TRUE;
1653             state->grid[i++] = atoi(desc-1);
1654             while (*desc >= '0' && *desc <= '9')
1655                 desc++;
1656         } else {
1657             assert(!"We can't get here");
1658         }
1659     }
1660     assert(i == area);
1661
1662     return state;
1663 }
1664
1665 static game_state *dup_game(game_state *state)
1666 {
1667     game_state *ret = snew(game_state);
1668     int c = state->c, r = state->r, cr = c*r, area = cr * cr;
1669
1670     ret->c = state->c;
1671     ret->r = state->r;
1672
1673     ret->grid = snewn(area, digit);
1674     memcpy(ret->grid, state->grid, area);
1675
1676     ret->pencil = snewn(area * cr, unsigned char);
1677     memcpy(ret->pencil, state->pencil, area * cr);
1678
1679     ret->immutable = snewn(area, unsigned char);
1680     memcpy(ret->immutable, state->immutable, area);
1681
1682     ret->completed = state->completed;
1683     ret->cheated = state->cheated;
1684
1685     return ret;
1686 }
1687
1688 static void free_game(game_state *state)
1689 {
1690     sfree(state->immutable);
1691     sfree(state->pencil);
1692     sfree(state->grid);
1693     sfree(state);
1694 }
1695
1696 static game_state *solve_game(game_state *state, game_aux_info *ai,
1697                               char **error)
1698 {
1699     game_state *ret;
1700     int c = state->c, r = state->r, cr = c*r;
1701     int rsolve_ret;
1702
1703     ret = dup_game(state);
1704     ret->completed = ret->cheated = TRUE;
1705
1706     /*
1707      * If we already have the solution in the aux_info, save
1708      * ourselves some time.
1709      */
1710     if (ai) {
1711
1712         assert(c == ai->c);
1713         assert(r == ai->r);
1714         memcpy(ret->grid, ai->grid, cr * cr * sizeof(digit));
1715
1716     } else {
1717         rsolve_ret = rsolve(c, r, ret->grid, NULL, 2);
1718
1719         if (rsolve_ret != 1) {
1720             free_game(ret);
1721             if (rsolve_ret == 0)
1722                 *error = "No solution exists for this puzzle";
1723             else
1724                 *error = "Multiple solutions exist for this puzzle";
1725             return NULL;
1726         }
1727     }
1728
1729     return ret;
1730 }
1731
1732 static char *grid_text_format(int c, int r, digit *grid)
1733 {
1734     int cr = c*r;
1735     int x, y;
1736     int maxlen;
1737     char *ret, *p;
1738
1739     /*
1740      * There are cr lines of digits, plus r-1 lines of block
1741      * separators. Each line contains cr digits, cr-1 separating
1742      * spaces, and c-1 two-character block separators. Thus, the
1743      * total length of a line is 2*cr+2*c-3 (not counting the
1744      * newline), and there are cr+r-1 of them.
1745      */
1746     maxlen = (cr+r-1) * (2*cr+2*c-2);
1747     ret = snewn(maxlen+1, char);
1748     p = ret;
1749
1750     for (y = 0; y < cr; y++) {
1751         for (x = 0; x < cr; x++) {
1752             int ch = grid[y * cr + x];
1753             if (ch == 0)
1754                 ch = ' ';
1755             else if (ch <= 9)
1756                 ch = '0' + ch;
1757             else
1758                 ch = 'a' + ch-10;
1759             *p++ = ch;
1760             if (x+1 < cr) {
1761                 *p++ = ' ';
1762                 if ((x+1) % r == 0) {
1763                     *p++ = '|';
1764                     *p++ = ' ';
1765                 }
1766             }
1767         }
1768         *p++ = '\n';
1769         if (y+1 < cr && (y+1) % c == 0) {
1770             for (x = 0; x < cr; x++) {
1771                 *p++ = '-';
1772                 if (x+1 < cr) {
1773                     *p++ = '-';
1774                     if ((x+1) % r == 0) {
1775                         *p++ = '+';
1776                         *p++ = '-';
1777                     }
1778                 }
1779             }
1780             *p++ = '\n';
1781         }
1782     }
1783
1784     assert(p - ret == maxlen);
1785     *p = '\0';
1786     return ret;
1787 }
1788
1789 static char *game_text_format(game_state *state)
1790 {
1791     return grid_text_format(state->c, state->r, state->grid);
1792 }
1793
1794 struct game_ui {
1795     /*
1796      * These are the coordinates of the currently highlighted
1797      * square on the grid, or -1,-1 if there isn't one. When there
1798      * is, pressing a valid number or letter key or Space will
1799      * enter that number or letter in the grid.
1800      */
1801     int hx, hy;
1802     /*
1803      * This indicates whether the current highlight is a
1804      * pencil-mark one or a real one.
1805      */
1806     int hpencil;
1807 };
1808
1809 static game_ui *new_ui(game_state *state)
1810 {
1811     game_ui *ui = snew(game_ui);
1812
1813     ui->hx = ui->hy = -1;
1814     ui->hpencil = 0;
1815
1816     return ui;
1817 }
1818
1819 static void free_ui(game_ui *ui)
1820 {
1821     sfree(ui);
1822 }
1823
1824 static game_state *make_move(game_state *from, game_ui *ui, game_drawstate *ds,
1825                              int x, int y, int button)
1826 {
1827     int c = from->c, r = from->r, cr = c*r;
1828     int tx, ty;
1829     game_state *ret;
1830
1831     button &= ~MOD_MASK;
1832
1833     tx = (x + TILE_SIZE - BORDER) / TILE_SIZE - 1;
1834     ty = (y + TILE_SIZE - BORDER) / TILE_SIZE - 1;
1835
1836     if (tx >= 0 && tx < cr && ty >= 0 && ty < cr) {
1837         if (button == LEFT_BUTTON) {
1838             if (from->immutable[ty*cr+tx]) {
1839                 ui->hx = ui->hy = -1;
1840             } else if (tx == ui->hx && ty == ui->hy && ui->hpencil == 0) {
1841                 ui->hx = ui->hy = -1;
1842             } else {
1843                 ui->hx = tx;
1844                 ui->hy = ty;
1845                 ui->hpencil = 0;
1846             }
1847             return from;                       /* UI activity occurred */
1848         }
1849         if (button == RIGHT_BUTTON) {
1850             /*
1851              * Pencil-mode highlighting for non filled squares.
1852              */
1853             if (from->grid[ty*cr+tx] == 0) {
1854                 if (tx == ui->hx && ty == ui->hy && ui->hpencil) {
1855                     ui->hx = ui->hy = -1;
1856                 } else {
1857                     ui->hpencil = 1;
1858                     ui->hx = tx;
1859                     ui->hy = ty;
1860                 }
1861             } else {
1862                 ui->hx = ui->hy = -1;
1863             }
1864             return from;                       /* UI activity occurred */
1865         }
1866     }
1867
1868     if (ui->hx != -1 && ui->hy != -1 &&
1869         ((button >= '1' && button <= '9' && button - '0' <= cr) ||
1870          (button >= 'a' && button <= 'z' && button - 'a' + 10 <= cr) ||
1871          (button >= 'A' && button <= 'Z' && button - 'A' + 10 <= cr) ||
1872          button == ' ')) {
1873         int n = button - '0';
1874         if (button >= 'A' && button <= 'Z')
1875             n = button - 'A' + 10;
1876         if (button >= 'a' && button <= 'z')
1877             n = button - 'a' + 10;
1878         if (button == ' ')
1879             n = 0;
1880
1881         /*
1882          * Can't overwrite this square. In principle this shouldn't
1883          * happen anyway because we should never have even been
1884          * able to highlight the square, but it never hurts to be
1885          * careful.
1886          */
1887         if (from->immutable[ui->hy*cr+ui->hx])
1888             return NULL;
1889
1890         /*
1891          * Can't make pencil marks in a filled square. In principle
1892          * this shouldn't happen anyway because we should never
1893          * have even been able to pencil-highlight the square, but
1894          * it never hurts to be careful.
1895          */
1896         if (ui->hpencil && from->grid[ui->hy*cr+ui->hx])
1897             return NULL;
1898
1899         ret = dup_game(from);
1900         if (ui->hpencil && n > 0) {
1901             int index = (ui->hy*cr+ui->hx) * cr + (n-1);
1902             ret->pencil[index] = !ret->pencil[index];
1903         } else {
1904             ret->grid[ui->hy*cr+ui->hx] = n;
1905             memset(ret->pencil + (ui->hy*cr+ui->hx)*cr, 0, cr);
1906
1907             /*
1908              * We've made a real change to the grid. Check to see
1909              * if the game has been completed.
1910              */
1911             if (!ret->completed && check_valid(c, r, ret->grid)) {
1912                 ret->completed = TRUE;
1913             }
1914         }
1915         ui->hx = ui->hy = -1;
1916
1917         return ret;                    /* made a valid move */
1918     }
1919
1920     return NULL;
1921 }
1922
1923 /* ----------------------------------------------------------------------
1924  * Drawing routines.
1925  */
1926
1927 struct game_drawstate {
1928     int started;
1929     int c, r, cr;
1930     digit *grid;
1931     unsigned char *pencil;
1932     unsigned char *hl;
1933 };
1934
1935 #define XSIZE(cr) ((cr) * TILE_SIZE + 2*BORDER + 1)
1936 #define YSIZE(cr) ((cr) * TILE_SIZE + 2*BORDER + 1)
1937
1938 static void game_size(game_params *params, int *x, int *y)
1939 {
1940     int c = params->c, r = params->r, cr = c*r;
1941
1942     *x = XSIZE(cr);
1943     *y = YSIZE(cr);
1944 }
1945
1946 static float *game_colours(frontend *fe, game_state *state, int *ncolours)
1947 {
1948     float *ret = snewn(3 * NCOLOURS, float);
1949
1950     frontend_default_colour(fe, &ret[COL_BACKGROUND * 3]);
1951
1952     ret[COL_GRID * 3 + 0] = 0.0F;
1953     ret[COL_GRID * 3 + 1] = 0.0F;
1954     ret[COL_GRID * 3 + 2] = 0.0F;
1955
1956     ret[COL_CLUE * 3 + 0] = 0.0F;
1957     ret[COL_CLUE * 3 + 1] = 0.0F;
1958     ret[COL_CLUE * 3 + 2] = 0.0F;
1959
1960     ret[COL_USER * 3 + 0] = 0.0F;
1961     ret[COL_USER * 3 + 1] = 0.6F * ret[COL_BACKGROUND * 3 + 1];
1962     ret[COL_USER * 3 + 2] = 0.0F;
1963
1964     ret[COL_HIGHLIGHT * 3 + 0] = 0.85F * ret[COL_BACKGROUND * 3 + 0];
1965     ret[COL_HIGHLIGHT * 3 + 1] = 0.85F * ret[COL_BACKGROUND * 3 + 1];
1966     ret[COL_HIGHLIGHT * 3 + 2] = 0.85F * ret[COL_BACKGROUND * 3 + 2];
1967
1968     ret[COL_PENCIL * 3 + 0] = 0.5F * ret[COL_BACKGROUND * 3 + 0];
1969     ret[COL_PENCIL * 3 + 1] = 0.5F * ret[COL_BACKGROUND * 3 + 1];
1970     ret[COL_PENCIL * 3 + 2] = ret[COL_BACKGROUND * 3 + 2];
1971
1972     *ncolours = NCOLOURS;
1973     return ret;
1974 }
1975
1976 static game_drawstate *game_new_drawstate(game_state *state)
1977 {
1978     struct game_drawstate *ds = snew(struct game_drawstate);
1979     int c = state->c, r = state->r, cr = c*r;
1980
1981     ds->started = FALSE;
1982     ds->c = c;
1983     ds->r = r;
1984     ds->cr = cr;
1985     ds->grid = snewn(cr*cr, digit);
1986     memset(ds->grid, 0, cr*cr);
1987     ds->pencil = snewn(cr*cr*cr, digit);
1988     memset(ds->pencil, 0, cr*cr*cr);
1989     ds->hl = snewn(cr*cr, unsigned char);
1990     memset(ds->hl, 0, cr*cr);
1991
1992     return ds;
1993 }
1994
1995 static void game_free_drawstate(game_drawstate *ds)
1996 {
1997     sfree(ds->hl);
1998     sfree(ds->pencil);
1999     sfree(ds->grid);
2000     sfree(ds);
2001 }
2002
2003 static void draw_number(frontend *fe, game_drawstate *ds, game_state *state,
2004                         int x, int y, int hl)
2005 {
2006     int c = state->c, r = state->r, cr = c*r;
2007     int tx, ty;
2008     int cx, cy, cw, ch;
2009     char str[2];
2010
2011     if (ds->grid[y*cr+x] == state->grid[y*cr+x] &&
2012         ds->hl[y*cr+x] == hl &&
2013         !memcmp(ds->pencil+(y*cr+x)*cr, state->pencil+(y*cr+x)*cr, cr))
2014         return;                        /* no change required */
2015
2016     tx = BORDER + x * TILE_SIZE + 2;
2017     ty = BORDER + y * TILE_SIZE + 2;
2018
2019     cx = tx;
2020     cy = ty;
2021     cw = TILE_SIZE-3;
2022     ch = TILE_SIZE-3;
2023
2024     if (x % r)
2025         cx--, cw++;
2026     if ((x+1) % r)
2027         cw++;
2028     if (y % c)
2029         cy--, ch++;
2030     if ((y+1) % c)
2031         ch++;
2032
2033     clip(fe, cx, cy, cw, ch);
2034
2035     /* background needs erasing */
2036     draw_rect(fe, cx, cy, cw, ch, hl == 1 ? COL_HIGHLIGHT : COL_BACKGROUND);
2037
2038     /* pencil-mode highlight */
2039     if (hl == 2) {
2040         int coords[6];
2041         coords[0] = cx;
2042         coords[1] = cy;
2043         coords[2] = cx+cw/2;
2044         coords[3] = cy;
2045         coords[4] = cx;
2046         coords[5] = cy+ch/2;
2047         draw_polygon(fe, coords, 3, TRUE, COL_HIGHLIGHT);
2048     }
2049
2050     /* new number needs drawing? */
2051     if (state->grid[y*cr+x]) {
2052         str[1] = '\0';
2053         str[0] = state->grid[y*cr+x] + '0';
2054         if (str[0] > '9')
2055             str[0] += 'a' - ('9'+1);
2056         draw_text(fe, tx + TILE_SIZE/2, ty + TILE_SIZE/2,
2057                   FONT_VARIABLE, TILE_SIZE/2, ALIGN_VCENTRE | ALIGN_HCENTRE,
2058                   state->immutable[y*cr+x] ? COL_CLUE : COL_USER, str);
2059     } else {
2060         /* pencil marks required? */
2061         int i, j;
2062
2063         for (i = j = 0; i < cr; i++)
2064             if (state->pencil[(y*cr+x)*cr+i]) {
2065                 int dx = j % r, dy = j / r, crm = max(c, r);
2066                 str[1] = '\0';
2067                 str[0] = i + '1';
2068                 if (str[0] > '9')
2069                     str[0] += 'a' - ('9'+1);
2070                 draw_text(fe, tx + (4*dx+3) * TILE_SIZE / (4*r+2),
2071                           ty + (4*dy+3) * TILE_SIZE / (4*c+2),
2072                           FONT_VARIABLE, TILE_SIZE/(crm*5/4),
2073                           ALIGN_VCENTRE | ALIGN_HCENTRE, COL_PENCIL, str);
2074                 j++;
2075             }
2076     }
2077
2078     unclip(fe);
2079
2080     draw_update(fe, cx, cy, cw, ch);
2081
2082     ds->grid[y*cr+x] = state->grid[y*cr+x];
2083     memcpy(ds->pencil+(y*cr+x)*cr, state->pencil+(y*cr+x)*cr, cr);
2084     ds->hl[y*cr+x] = hl;
2085 }
2086
2087 static void game_redraw(frontend *fe, game_drawstate *ds, game_state *oldstate,
2088                         game_state *state, int dir, game_ui *ui,
2089                         float animtime, float flashtime)
2090 {
2091     int c = state->c, r = state->r, cr = c*r;
2092     int x, y;
2093
2094     if (!ds->started) {
2095         /*
2096          * The initial contents of the window are not guaranteed
2097          * and can vary with front ends. To be on the safe side,
2098          * all games should start by drawing a big
2099          * background-colour rectangle covering the whole window.
2100          */
2101         draw_rect(fe, 0, 0, XSIZE(cr), YSIZE(cr), COL_BACKGROUND);
2102
2103         /*
2104          * Draw the grid.
2105          */
2106         for (x = 0; x <= cr; x++) {
2107             int thick = (x % r ? 0 : 1);
2108             draw_rect(fe, BORDER + x*TILE_SIZE - thick, BORDER-1,
2109                       1+2*thick, cr*TILE_SIZE+3, COL_GRID);
2110         }
2111         for (y = 0; y <= cr; y++) {
2112             int thick = (y % c ? 0 : 1);
2113             draw_rect(fe, BORDER-1, BORDER + y*TILE_SIZE - thick,
2114                       cr*TILE_SIZE+3, 1+2*thick, COL_GRID);
2115         }
2116     }
2117
2118     /*
2119      * Draw any numbers which need redrawing.
2120      */
2121     for (x = 0; x < cr; x++) {
2122         for (y = 0; y < cr; y++) {
2123             int highlight = 0;
2124             if (flashtime > 0 &&
2125                 (flashtime <= FLASH_TIME/3 ||
2126                  flashtime >= FLASH_TIME*2/3))
2127                 highlight = 1;
2128             if (x == ui->hx && y == ui->hy)
2129                 highlight = ui->hpencil ? 2 : 1;
2130             draw_number(fe, ds, state, x, y, highlight);
2131         }
2132     }
2133
2134     /*
2135      * Update the _entire_ grid if necessary.
2136      */
2137     if (!ds->started) {
2138         draw_update(fe, 0, 0, XSIZE(cr), YSIZE(cr));
2139         ds->started = TRUE;
2140     }
2141 }
2142
2143 static float game_anim_length(game_state *oldstate, game_state *newstate,
2144                               int dir, game_ui *ui)
2145 {
2146     return 0.0F;
2147 }
2148
2149 static float game_flash_length(game_state *oldstate, game_state *newstate,
2150                                int dir, game_ui *ui)
2151 {
2152     if (!oldstate->completed && newstate->completed &&
2153         !oldstate->cheated && !newstate->cheated)
2154         return FLASH_TIME;
2155     return 0.0F;
2156 }
2157
2158 static int game_wants_statusbar(void)
2159 {
2160     return FALSE;
2161 }
2162
2163 static int game_timing_state(game_state *state)
2164 {
2165     return TRUE;
2166 }
2167
2168 #ifdef COMBINED
2169 #define thegame solo
2170 #endif
2171
2172 const struct game thegame = {
2173     "Solo", "games.solo",
2174     default_params,
2175     game_fetch_preset,
2176     decode_params,
2177     encode_params,
2178     free_params,
2179     dup_params,
2180     TRUE, game_configure, custom_params,
2181     validate_params,
2182     new_game_desc,
2183     game_free_aux_info,
2184     validate_desc,
2185     new_game,
2186     dup_game,
2187     free_game,
2188     TRUE, solve_game,
2189     TRUE, game_text_format,
2190     new_ui,
2191     free_ui,
2192     make_move,
2193     game_size,
2194     game_colours,
2195     game_new_drawstate,
2196     game_free_drawstate,
2197     game_redraw,
2198     game_anim_length,
2199     game_flash_length,
2200     game_wants_statusbar,
2201     FALSE, game_timing_state,
2202     0,                                 /* mouse_priorities */
2203 };
2204
2205 #ifdef STANDALONE_SOLVER
2206
2207 /*
2208  * gcc -DSTANDALONE_SOLVER -o solosolver solo.c malloc.c
2209  */
2210
2211 void frontend_default_colour(frontend *fe, float *output) {}
2212 void draw_text(frontend *fe, int x, int y, int fonttype, int fontsize,
2213                int align, int colour, char *text) {}
2214 void draw_rect(frontend *fe, int x, int y, int w, int h, int colour) {}
2215 void draw_line(frontend *fe, int x1, int y1, int x2, int y2, int colour) {}
2216 void draw_polygon(frontend *fe, int *coords, int npoints,
2217                   int fill, int colour) {}
2218 void clip(frontend *fe, int x, int y, int w, int h) {}
2219 void unclip(frontend *fe) {}
2220 void start_draw(frontend *fe) {}
2221 void draw_update(frontend *fe, int x, int y, int w, int h) {}
2222 void end_draw(frontend *fe) {}
2223 unsigned long random_bits(random_state *state, int bits)
2224 { assert(!"Shouldn't get randomness"); return 0; }
2225 unsigned long random_upto(random_state *state, unsigned long limit)
2226 { assert(!"Shouldn't get randomness"); return 0; }
2227
2228 void fatal(char *fmt, ...)
2229 {
2230     va_list ap;
2231
2232     fprintf(stderr, "fatal error: ");
2233
2234     va_start(ap, fmt);
2235     vfprintf(stderr, fmt, ap);
2236     va_end(ap);
2237
2238     fprintf(stderr, "\n");
2239     exit(1);
2240 }
2241
2242 int main(int argc, char **argv)
2243 {
2244     game_params *p;
2245     game_state *s;
2246     int recurse = TRUE;
2247     char *id = NULL, *desc, *err;
2248     int y, x;
2249     int grade = FALSE;
2250
2251     while (--argc > 0) {
2252         char *p = *++argv;
2253         if (!strcmp(p, "-r")) {
2254             recurse = TRUE;
2255         } else if (!strcmp(p, "-n")) {
2256             recurse = FALSE;
2257         } else if (!strcmp(p, "-v")) {
2258             solver_show_working = TRUE;
2259             recurse = FALSE;
2260         } else if (!strcmp(p, "-g")) {
2261             grade = TRUE;
2262             recurse = FALSE;
2263         } else if (*p == '-') {
2264             fprintf(stderr, "%s: unrecognised option `%s'\n", argv[0]);
2265             return 1;
2266         } else {
2267             id = p;
2268         }
2269     }
2270
2271     if (!id) {
2272         fprintf(stderr, "usage: %s [-n | -r | -g | -v] <game_id>\n", argv[0]);
2273         return 1;
2274     }
2275
2276     desc = strchr(id, ':');
2277     if (!desc) {
2278         fprintf(stderr, "%s: game id expects a colon in it\n", argv[0]);
2279         return 1;
2280     }
2281     *desc++ = '\0';
2282
2283     p = default_params();
2284     decode_params(p, id);
2285     err = validate_desc(p, desc);
2286     if (err) {
2287         fprintf(stderr, "%s: %s\n", argv[0], err);
2288         return 1;
2289     }
2290     s = new_game(NULL, p, desc);
2291
2292     if (recurse) {
2293         int ret = rsolve(p->c, p->r, s->grid, NULL, 2);
2294         if (ret > 1) {
2295             fprintf(stderr, "%s: rsolve: multiple solutions detected\n",
2296                     argv[0]);
2297         }
2298     } else {
2299         int ret = nsolve(p->c, p->r, s->grid);
2300         if (grade) {
2301             if (ret == DIFF_IMPOSSIBLE) {
2302                 /*
2303                  * Now resort to rsolve to determine whether it's
2304                  * really soluble.
2305                  */
2306                 ret = rsolve(p->c, p->r, s->grid, NULL, 2);
2307                 if (ret == 0)
2308                     ret = DIFF_IMPOSSIBLE;
2309                 else if (ret == 1)
2310                     ret = DIFF_RECURSIVE;
2311                 else
2312                     ret = DIFF_AMBIGUOUS;
2313             }
2314             printf("Difficulty rating: %s\n",
2315                    ret==DIFF_BLOCK ? "Trivial (blockwise positional elimination only)":
2316                    ret==DIFF_SIMPLE ? "Basic (row/column/number elimination required)":
2317                    ret==DIFF_INTERSECT ? "Intermediate (intersectional analysis required)":
2318                    ret==DIFF_SET ? "Advanced (set elimination required)":
2319                    ret==DIFF_RECURSIVE ? "Unreasonable (guesswork and backtracking required)":
2320                    ret==DIFF_AMBIGUOUS ? "Ambiguous (multiple solutions exist)":
2321                    ret==DIFF_IMPOSSIBLE ? "Impossible (no solution exists)":
2322                    "INTERNAL ERROR: unrecognised difficulty code");
2323         }
2324     }
2325
2326     printf("%s\n", grid_text_format(p->c, p->r, s->grid));
2327
2328     return 0;
2329 }
2330
2331 #endif