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