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_PENCIL,
 127     NCOLOURS
 128 };
 129
 130 struct game_params {
 131     int c, r, symm, diff;
 132 };
 133
 134 struct game_state {
 135     int c, r;
 136     digit *grid;
 137     unsigned char *pencil;             /* c*r*c*r elements */
 138     unsigned char *immutable;          /* marks which digits are clues */
 139     int completed, cheated;
 140 };
 141
 142 static game_params *default_params(void)
 143 {
 144     game_params *ret = snew(game_params);
 145
 146     ret->c = ret->r = 3;
 147     ret->symm = SYMM_ROT2;             /* a plausible default */
 148     ret->diff = DIFF_BLOCK;            /* so is this */
 149
 150     return ret;
 151 }
 152
 153 static void free_params(game_params *params)
 154 {
 155     sfree(params);
 156 }
 157
 158 static game_params *dup_params(game_params *params)
 159 {
 160     game_params *ret = snew(game_params);
 161     *ret = *params;                    /* structure copy */
 162     return ret;
 163 }
 164
 165 static int game_fetch_preset(int i, char **name, game_params **params)
 166 {
 167     static struct {
 168         char *title;
 169         game_params params;
 170     } presets[] = {
 171         { "2x2 Trivial", { 2, 2, SYMM_ROT2, DIFF_BLOCK } },
 172         { "2x3 Basic", { 2, 3, SYMM_ROT2, DIFF_SIMPLE } },
 173         { "3x3 Trivial", { 3, 3, SYMM_ROT2, DIFF_BLOCK } },
 174         { "3x3 Basic", { 3, 3, SYMM_ROT2, DIFF_SIMPLE } },
 175         { "3x3 Intermediate", { 3, 3, SYMM_ROT2, DIFF_INTERSECT } },
 176         { "3x3 Advanced", { 3, 3, SYMM_ROT2, DIFF_SET } },
 177         { "3x3 Unreasonable", { 3, 3, SYMM_ROT2, DIFF_RECURSIVE } },
 178 #ifndef SLOW_SYSTEM
 179         { "3x4 Basic", { 3, 4, SYMM_ROT2, DIFF_SIMPLE } },
 180         { "4x4 Basic", { 4, 4, SYMM_ROT2, DIFF_SIMPLE } },
 181 #endif
 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 struct nsolve_scratch {
 848     unsigned char *grid, *rowidx, *colidx, *set;
 849 };
 850
 851 static int nsolve_set(struct nsolve_usage *usage,
 852                       struct nsolve_scratch *scratch,
 853                       int start, int step1, int step2
 854 #ifdef STANDALONE_SOLVER
 855                       , char *fmt, ...
 856 #endif
 857                       )
 858 {
 859     int c = usage->c, r = usage->r, cr = c*r;
 860     int i, j, n, count;
 861     unsigned char *grid = scratch->grid;
 862     unsigned char *rowidx = scratch->rowidx;
 863     unsigned char *colidx = scratch->colidx;
 864     unsigned char *set = scratch->set;
 865
 866     /*
 867      * We are passed a cr-by-cr matrix of booleans. Our first job
 868      * is to winnow it by finding any definite placements - i.e.
 869      * any row with a solitary 1 - and discarding that row and the
 870      * column containing the 1.
 871      */
 872     memset(rowidx, TRUE, cr);
 873     memset(colidx, TRUE, cr);
 874     for (i = 0; i < cr; i++) {
 875         int count = 0, first = -1;
 876         for (j = 0; j < cr; j++)
 877             if (usage->cube[start+i*step1+j*step2])
 878                 first = j, count++;
 879         if (count == 0) {
 880             /*
 881              * This condition actually marks a completely insoluble
 882              * (i.e. internally inconsistent) puzzle. We return and
 883              * report no progress made.
 884              */
 885             return FALSE;
 886         }
 887         if (count == 1)
 888             rowidx[i] = colidx[first] = FALSE;
 889     }
 890
 891     /*
 892      * Convert each of rowidx/colidx from a list of 0s and 1s to a
 893      * list of the indices of the 1s.
 894      */
 895     for (i = j = 0; i < cr; i++)
 896         if (rowidx[i])
 897             rowidx[j++] = i;
 898     n = j;
 899     for (i = j = 0; i < cr; i++)
 900         if (colidx[i])
 901             colidx[j++] = i;
 902     assert(n == j);
 903
 904     /*
 905      * And create the smaller matrix.
 906      */
 907     for (i = 0; i < n; i++)
 908         for (j = 0; j < n; j++)
 909             grid[i*cr+j] = usage->cube[start+rowidx[i]*step1+colidx[j]*step2];
 910
 911     /*
 912      * Having done that, we now have a matrix in which every row
 913      * has at least two 1s in. Now we search to see if we can find
 914      * a rectangle of zeroes (in the set-theoretic sense of
 915      * `rectangle', i.e. a subset of rows crossed with a subset of
 916      * columns) whose width and height add up to n.
 917      */
 918
 919     memset(set, 0, n);
 920     count = 0;
 921     while (1) {
 922         /*
 923          * We have a candidate set. If its size is <=1 or >=n-1
 924          * then we move on immediately.
 925          */
 926         if (count > 1 && count < n-1) {
 927             /*
 928              * The number of rows we need is n-count. See if we can
 929              * find that many rows which each have a zero in all
 930              * the positions listed in `set'.
 931              */
 932             int rows = 0;
 933             for (i = 0; i < n; i++) {
 934                 int ok = TRUE;
 935                 for (j = 0; j < n; j++)
 936                     if (set[j] && grid[i*cr+j]) {
 937                         ok = FALSE;
 938                         break;
 939                     }
 940                 if (ok)
 941                     rows++;
 942             }
 943
 944             /*
 945              * We expect never to be able to get _more_ than
 946              * n-count suitable rows: this would imply that (for
 947              * example) there are four numbers which between them
 948              * have at most three possible positions, and hence it
 949              * indicates a faulty deduction before this point or
 950              * even a bogus clue.
 951              */
 952             assert(rows <= n - count);
 953             if (rows >= n - count) {
 954                 int progress = FALSE;
 955
 956                 /*
 957                  * We've got one! Now, for each row which _doesn't_
 958                  * satisfy the criterion, eliminate all its set
 959                  * bits in the positions _not_ listed in `set'.
 960                  * Return TRUE (meaning progress has been made) if
 961                  * we successfully eliminated anything at all.
 962                  *
 963                  * This involves referring back through
 964                  * rowidx/colidx in order to work out which actual
 965                  * positions in the cube to meddle with.
 966                  */
 967                 for (i = 0; i < n; i++) {
 968                     int ok = TRUE;
 969                     for (j = 0; j < n; j++)
 970                         if (set[j] && grid[i*cr+j]) {
 971                             ok = FALSE;
 972                             break;
 973                         }
 974                     if (!ok) {
 975                         for (j = 0; j < n; j++)
 976                             if (!set[j] && grid[i*cr+j]) {
 977                                 int fpos = (start+rowidx[i]*step1+
 978                                             colidx[j]*step2);
 979 #ifdef STANDALONE_SOLVER
 980                                 if (solver_show_working) {
 981                                     int px, py, pn;
 982
 983                                     if (!progress) {
 984                                         va_list ap;
 985                                         va_start(ap, fmt);
 986                                         vprintf(fmt, ap);
 987                                         va_end(ap);
 988                                         printf(":\n");
 989                                     }
 990
 991                                     pn = 1 + fpos % cr;
 992                                     py = fpos / cr;
 993                                     px = py / cr;
 994                                     py %= cr;
 995
 996                                     printf("  ruling out %d at (%d,%d)\n",
 997                                            pn, 1+px, 1+YUNTRANS(py));
 998                                 }
 999 #endif
1000                                 progress = TRUE;
1001                                 usage->cube[fpos] = FALSE;
1002                             }
1003                     }
1004                 }
1005
1006                 if (progress) {
1007                     return TRUE;
1008                 }
1009             }
1010         }
1011
1012         /*
1013          * Binary increment: change the rightmost 0 to a 1, and
1014          * change all 1s to the right of it to 0s.
1015          */
1016         i = n;
1017         while (i > 0 && set[i-1])
1018             set[--i] = 0, count--;
1019         if (i > 0)
1020             set[--i] = 1, count++;
1021         else
1022             break;                     /* done */
1023     }
1024
1025     return FALSE;
1026 }
1027
1028 static struct nsolve_scratch *nsolve_new_scratch(struct nsolve_usage *usage)
1029 {
1030     struct nsolve_scratch *scratch = snew(struct nsolve_scratch);
1031     int cr = usage->cr;
1032     scratch->grid = snewn(cr*cr, unsigned char);
1033     scratch->rowidx = snewn(cr, unsigned char);
1034     scratch->colidx = snewn(cr, unsigned char);
1035     scratch->set = snewn(cr, unsigned char);
1036     return scratch;
1037 }
1038
1039 static void nsolve_free_scratch(struct nsolve_scratch *scratch)
1040 {
1041     sfree(scratch->set);
1042     sfree(scratch->colidx);
1043     sfree(scratch->rowidx);
1044     sfree(scratch->grid);
1045     sfree(scratch);
1046 }
1047
1048 static int nsolve(int c, int r, digit *grid)
1049 {
1050     struct nsolve_usage *usage;
1051     struct nsolve_scratch *scratch;
1052     int cr = c*r;
1053     int x, y, n;
1054     int diff = DIFF_BLOCK;
1055
1056     /*
1057      * Set up a usage structure as a clean slate (everything
1058      * possible).
1059      */
1060     usage = snew(struct nsolve_usage);
1061     usage->c = c;
1062     usage->r = r;
1063     usage->cr = cr;
1064     usage->cube = snewn(cr*cr*cr, unsigned char);
1065     usage->grid = grid;                /* write straight back to the input */
1066     memset(usage->cube, TRUE, cr*cr*cr);
1067
1068     usage->row = snewn(cr * cr, unsigned char);
1069     usage->col = snewn(cr * cr, unsigned char);
1070     usage->blk = snewn(cr * cr, unsigned char);
1071     memset(usage->row, FALSE, cr * cr);
1072     memset(usage->col, FALSE, cr * cr);
1073     memset(usage->blk, FALSE, cr * cr);
1074
1075     scratch = nsolve_new_scratch(usage);
1076
1077     /*
1078      * Place all the clue numbers we are given.
1079      */
1080     for (x = 0; x < cr; x++)
1081         for (y = 0; y < cr; y++)
1082             if (grid[y*cr+x])
1083                 nsolve_place(usage, x, YTRANS(y), grid[y*cr+x]);
1084
1085     /*
1086      * Now loop over the grid repeatedly trying all permitted modes
1087      * of reasoning. The loop terminates if we complete an
1088      * iteration without making any progress; we then return
1089      * failure or success depending on whether the grid is full or
1090      * not.
1091      */
1092     while (1) {
1093         /*
1094          * I'd like to write `continue;' inside each of the
1095          * following loops, so that the solver returns here after
1096          * making some progress. However, I can't specify that I
1097          * want to continue an outer loop rather than the innermost
1098          * one, so I'm apologetically resorting to a goto.
1099          */
1100         cont:
1101
1102         /*
1103          * Blockwise positional elimination.
1104          */
1105         for (x = 0; x < cr; x += r)
1106             for (y = 0; y < r; y++)
1107                 for (n = 1; n <= cr; n++)
1108                     if (!usage->blk[(y*c+(x/r))*cr+n-1] &&
1109                         nsolve_elim(usage, cubepos(x,y,n), r*cr
1110 #ifdef STANDALONE_SOLVER
1111                                     , "positional elimination,"
1112                                     " block (%d,%d)", 1+x/r, 1+y
1113 #endif
1114                                     )) {
1115                         diff = max(diff, DIFF_BLOCK);
1116                         goto cont;
1117                     }
1118
1119         /*
1120          * Row-wise positional elimination.
1121          */
1122         for (y = 0; y < cr; y++)
1123             for (n = 1; n <= cr; n++)
1124                 if (!usage->row[y*cr+n-1] &&
1125                     nsolve_elim(usage, cubepos(0,y,n), cr*cr
1126 #ifdef STANDALONE_SOLVER
1127                                 , "positional elimination,"
1128                                 " row %d", 1+YUNTRANS(y)
1129 #endif
1130                                 )) {
1131                     diff = max(diff, DIFF_SIMPLE);
1132                     goto cont;
1133                 }
1134         /*
1135          * Column-wise positional elimination.
1136          */
1137         for (x = 0; x < cr; x++)
1138             for (n = 1; n <= cr; n++)
1139                 if (!usage->col[x*cr+n-1] &&
1140                     nsolve_elim(usage, cubepos(x,0,n), cr
1141 #ifdef STANDALONE_SOLVER
1142                                 , "positional elimination," " column %d", 1+x
1143 #endif
1144                                 )) {
1145                     diff = max(diff, DIFF_SIMPLE);
1146                     goto cont;
1147                 }
1148
1149         /*
1150          * Numeric elimination.
1151          */
1152         for (x = 0; x < cr; x++)
1153             for (y = 0; y < cr; y++)
1154                 if (!usage->grid[YUNTRANS(y)*cr+x] &&
1155                     nsolve_elim(usage, cubepos(x,y,1), 1
1156 #ifdef STANDALONE_SOLVER
1157                                 , "numeric elimination at (%d,%d)", 1+x,
1158                                 1+YUNTRANS(y)
1159 #endif
1160                                 )) {
1161                     diff = max(diff, DIFF_SIMPLE);
1162                     goto cont;
1163                 }
1164
1165         /*
1166          * Intersectional analysis, rows vs blocks.
1167          */
1168         for (y = 0; y < cr; y++)
1169             for (x = 0; x < cr; x += r)
1170                 for (n = 1; n <= cr; n++)
1171                     if (!usage->row[y*cr+n-1] &&
1172                         !usage->blk[((y%r)*c+(x/r))*cr+n-1] &&
1173                         (nsolve_intersect(usage, cubepos(0,y,n), cr*cr,
1174                                           cubepos(x,y%r,n), r*cr
1175 #ifdef STANDALONE_SOLVER
1176                                           , "intersectional analysis,"
1177                                           " row %d vs block (%d,%d)",
1178                                           1+YUNTRANS(y), 1+x/r, 1+y%r
1179 #endif
1180                                           ) ||
1181                          nsolve_intersect(usage, cubepos(x,y%r,n), r*cr,
1182                                           cubepos(0,y,n), cr*cr
1183 #ifdef STANDALONE_SOLVER
1184                                           , "intersectional analysis,"
1185                                           " block (%d,%d) vs row %d",
1186                                           1+x/r, 1+y%r, 1+YUNTRANS(y)
1187 #endif
1188                                           ))) {
1189                         diff = max(diff, DIFF_INTERSECT);
1190                         goto cont;
1191                     }
1192
1193         /*
1194          * Intersectional analysis, columns vs blocks.
1195          */
1196         for (x = 0; x < cr; x++)
1197             for (y = 0; y < r; y++)
1198                 for (n = 1; n <= cr; n++)
1199                     if (!usage->col[x*cr+n-1] &&
1200                         !usage->blk[(y*c+(x/r))*cr+n-1] &&
1201                         (nsolve_intersect(usage, cubepos(x,0,n), cr,
1202                                           cubepos((x/r)*r,y,n), r*cr
1203 #ifdef STANDALONE_SOLVER
1204                                           , "intersectional analysis,"
1205                                           " column %d vs block (%d,%d)",
1206                                           1+x, 1+x/r, 1+y
1207 #endif
1208                                           ) ||
1209                          nsolve_intersect(usage, cubepos((x/r)*r,y,n), r*cr,
1210                                           cubepos(x,0,n), cr
1211 #ifdef STANDALONE_SOLVER
1212                                           , "intersectional analysis,"
1213                                           " block (%d,%d) vs column %d",
1214                                           1+x/r, 1+y, 1+x
1215 #endif
1216                                           ))) {
1217                         diff = max(diff, DIFF_INTERSECT);
1218                         goto cont;
1219                     }
1220
1221         /*
1222          * Blockwise set elimination.
1223          */
1224         for (x = 0; x < cr; x += r)
1225             for (y = 0; y < r; y++)
1226                 if (nsolve_set(usage, scratch, cubepos(x,y,1), r*cr, 1
1227 #ifdef STANDALONE_SOLVER
1228                                , "set elimination, block (%d,%d)", 1+x/r, 1+y
1229 #endif
1230                                )) {
1231                     diff = max(diff, DIFF_SET);
1232                     goto cont;
1233                 }
1234
1235         /*
1236          * Row-wise set elimination.
1237          */
1238         for (y = 0; y < cr; y++)
1239             if (nsolve_set(usage, scratch, cubepos(0,y,1), cr*cr, 1
1240 #ifdef STANDALONE_SOLVER
1241                            , "set elimination, row %d", 1+YUNTRANS(y)
1242 #endif
1243                            )) {
1244                 diff = max(diff, DIFF_SET);
1245                 goto cont;
1246             }
1247
1248         /*
1249          * Column-wise set elimination.
1250          */
1251         for (x = 0; x < cr; x++)
1252             if (nsolve_set(usage, scratch, cubepos(x,0,1), cr, 1
1253 #ifdef STANDALONE_SOLVER
1254                            , "set elimination, column %d", 1+x
1255 #endif
1256                            )) {
1257                 diff = max(diff, DIFF_SET);
1258                 goto cont;
1259             }
1260
1261         /*
1262          * If we reach here, we have made no deductions in this
1263          * iteration, so the algorithm terminates.
1264          */
1265         break;
1266     }
1267
1268     nsolve_free_scratch(scratch);
1269
1270     sfree(usage->cube);
1271     sfree(usage->row);
1272     sfree(usage->col);
1273     sfree(usage->blk);
1274     sfree(usage);
1275
1276     for (x = 0; x < cr; x++)
1277         for (y = 0; y < cr; y++)
1278             if (!grid[y*cr+x])
1279                 return DIFF_IMPOSSIBLE;
1280     return diff;
1281 }
1282
1283 /* ----------------------------------------------------------------------
1284  * End of non-recursive solver code.
1285  */
1286
1287 /*
1288  * Check whether a grid contains a valid complete puzzle.
1289  */
1290 static int check_valid(int c, int r, digit *grid)
1291 {
1292     int cr = c*r;
1293     unsigned char *used;
1294     int x, y, n;
1295
1296     used = snewn(cr, unsigned char);
1297
1298     /*
1299      * Check that each row contains precisely one of everything.
1300      */
1301     for (y = 0; y < cr; y++) {
1302         memset(used, FALSE, cr);
1303         for (x = 0; x < cr; x++)
1304             if (grid[y*cr+x] > 0 && grid[y*cr+x] <= cr)
1305                 used[grid[y*cr+x]-1] = TRUE;
1306         for (n = 0; n < cr; n++)
1307             if (!used[n]) {
1308                 sfree(used);
1309                 return FALSE;
1310             }
1311     }
1312
1313     /*
1314      * Check that each column contains precisely one of everything.
1315      */
1316     for (x = 0; x < cr; x++) {
1317         memset(used, FALSE, cr);
1318         for (y = 0; y < cr; y++)
1319             if (grid[y*cr+x] > 0 && grid[y*cr+x] <= cr)
1320                 used[grid[y*cr+x]-1] = TRUE;
1321         for (n = 0; n < cr; n++)
1322             if (!used[n]) {
1323                 sfree(used);
1324                 return FALSE;
1325             }
1326     }
1327
1328     /*
1329      * Check that each block contains precisely one of everything.
1330      */
1331     for (x = 0; x < cr; x += r) {
1332         for (y = 0; y < cr; y += c) {
1333             int xx, yy;
1334             memset(used, FALSE, cr);
1335             for (xx = x; xx < x+r; xx++)
1336                 for (yy = 0; yy < y+c; yy++)
1337                     if (grid[yy*cr+xx] > 0 && grid[yy*cr+xx] <= cr)
1338                         used[grid[yy*cr+xx]-1] = TRUE;
1339             for (n = 0; n < cr; n++)
1340                 if (!used[n]) {
1341                     sfree(used);
1342                     return FALSE;
1343                 }
1344         }
1345     }
1346
1347     sfree(used);
1348     return TRUE;
1349 }
1350
1351 static void symmetry_limit(game_params *params, int *xlim, int *ylim, int s)
1352 {
1353     int c = params->c, r = params->r, cr = c*r;
1354
1355     switch (s) {
1356       case SYMM_NONE:
1357         *xlim = *ylim = cr;
1358         break;
1359       case SYMM_ROT2:
1360         *xlim = (cr+1) / 2;
1361         *ylim = cr;
1362         break;
1363       case SYMM_REF4:
1364       case SYMM_ROT4:
1365         *xlim = *ylim = (cr+1) / 2;
1366         break;
1367     }
1368 }
1369
1370 static int symmetries(game_params *params, int x, int y, int *output, int s)
1371 {
1372     int c = params->c, r = params->r, cr = c*r;
1373     int i = 0;
1374
1375     *output++ = x;
1376     *output++ = y;
1377     i++;
1378
1379     switch (s) {
1380       case SYMM_NONE:
1381         break;                         /* just x,y is all we need */
1382       case SYMM_REF4:
1383       case SYMM_ROT4:
1384         switch (s) {
1385           case SYMM_REF4:
1386             *output++ = cr - 1 - x;
1387             *output++ = y;
1388             i++;
1389
1390             *output++ = x;
1391             *output++ = cr - 1 - y;
1392             i++;
1393             break;
1394           case SYMM_ROT4:
1395             *output++ = cr - 1 - y;
1396             *output++ = x;
1397             i++;
1398
1399             *output++ = y;
1400             *output++ = cr - 1 - x;
1401             i++;
1402             break;
1403         }
1404         /* fall through */
1405       case SYMM_ROT2:
1406         *output++ = cr - 1 - x;
1407         *output++ = cr - 1 - y;
1408         i++;
1409         break;
1410     }
1411
1412     return i;
1413 }
1414
1415 struct game_aux_info {
1416     int c, r;
1417     digit *grid;
1418 };
1419
1420 static char *new_game_desc(game_params *params, random_state *rs,
1421                            game_aux_info **aux, int interactive)
1422 {
1423     int c = params->c, r = params->r, cr = c*r;
1424     int area = cr*cr;
1425     digit *grid, *grid2;
1426     struct xy { int x, y; } *locs;
1427     int nlocs;
1428     int ret;
1429     char *desc;
1430     int coords[16], ncoords;
1431     int xlim, ylim;
1432     int maxdiff, recursing;
1433
1434     /*
1435      * Adjust the maximum difficulty level to be consistent with
1436      * the puzzle size: all 2x2 puzzles appear to be Trivial
1437      * (DIFF_BLOCK) so we cannot hold out for even a Basic
1438      * (DIFF_SIMPLE) one.
1439      */
1440     maxdiff = params->diff;
1441     if (c == 2 && r == 2)
1442         maxdiff = DIFF_BLOCK;
1443
1444     grid = snewn(area, digit);
1445     locs = snewn(area, struct xy);
1446     grid2 = snewn(area, digit);
1447
1448     /*
1449      * Loop until we get a grid of the required difficulty. This is
1450      * nasty, but it seems to be unpleasantly hard to generate
1451      * difficult grids otherwise.
1452      */
1453     do {
1454         /*
1455          * Start the recursive solver with an empty grid to generate a
1456          * random solved state.
1457          */
1458         memset(grid, 0, area);
1459         ret = rsolve(c, r, grid, rs, 1);
1460         assert(ret == 1);
1461         assert(check_valid(c, r, grid));
1462
1463         /*
1464          * Save the solved grid in the aux_info.
1465          */
1466         {
1467             game_aux_info *ai = snew(game_aux_info);
1468             ai->c = c;
1469             ai->r = r;
1470             ai->grid = snewn(cr * cr, digit);
1471             memcpy(ai->grid, grid, cr * cr * sizeof(digit));
1472             /*
1473              * We might already have written *aux the last time we
1474              * went round this loop, in which case we should free
1475              * the old aux_info before overwriting it with the new
1476              * one.
1477              */
1478             if (*aux) {
1479                 sfree((*aux)->grid);
1480                 sfree(*aux);
1481             }
1482             *aux = ai;
1483         }
1484
1485         /*
1486          * Now we have a solved grid, start removing things from it
1487          * while preserving solubility.
1488          */
1489         symmetry_limit(params, &xlim, &ylim, params->symm);
1490         recursing = FALSE;
1491         while (1) {
1492             int x, y, i, j;
1493
1494             /*
1495              * Iterate over the grid and enumerate all the filled
1496              * squares we could empty.
1497              */
1498             nlocs = 0;
1499
1500             for (x = 0; x < xlim; x++)
1501                 for (y = 0; y < ylim; y++)
1502                     if (grid[y*cr+x]) {
1503                         locs[nlocs].x = x;
1504                         locs[nlocs].y = y;
1505                         nlocs++;
1506                     }
1507
1508             /*
1509              * Now shuffle that list.
1510              */
1511             for (i = nlocs; i > 1; i--) {
1512                 int p = random_upto(rs, i);
1513                 if (p != i-1) {
1514                     struct xy t = locs[p];
1515                     locs[p] = locs[i-1];
1516                     locs[i-1] = t;
1517                 }
1518             }
1519
1520             /*
1521              * Now loop over the shuffled list and, for each element,
1522              * see whether removing that element (and its reflections)
1523              * from the grid will still leave the grid soluble by
1524              * nsolve.
1525              */
1526             for (i = 0; i < nlocs; i++) {
1527                 int ret;
1528
1529                 x = locs[i].x;
1530                 y = locs[i].y;
1531
1532                 memcpy(grid2, grid, area);
1533                 ncoords = symmetries(params, x, y, coords, params->symm);
1534                 for (j = 0; j < ncoords; j++)
1535                     grid2[coords[2*j+1]*cr+coords[2*j]] = 0;
1536
1537                 if (recursing)
1538                     ret = (rsolve(c, r, grid2, NULL, 2) == 1);
1539                 else
1540                     ret = (nsolve(c, r, grid2) <= maxdiff);
1541
1542                 if (ret) {
1543                     for (j = 0; j < ncoords; j++)
1544                         grid[coords[2*j+1]*cr+coords[2*j]] = 0;
1545                     break;
1546                 }
1547             }
1548
1549             if (i == nlocs) {
1550                 /*
1551                  * There was nothing we could remove without
1552                  * destroying solvability. If we're trying to
1553                  * generate a recursion-only grid and haven't
1554                  * switched over to rsolve yet, we now do;
1555                  * otherwise we give up.
1556                  */
1557                 if (maxdiff == DIFF_RECURSIVE && !recursing) {
1558                     recursing = TRUE;
1559                 } else {
1560                     break;
1561                 }
1562             }
1563         }
1564
1565         memcpy(grid2, grid, area);
1566     } while (nsolve(c, r, grid2) < maxdiff);
1567
1568     sfree(grid2);
1569     sfree(locs);
1570
1571     /*
1572      * Now we have the grid as it will be presented to the user.
1573      * Encode it in a game desc.
1574      */
1575     {
1576         char *p;
1577         int run, i;
1578
1579         desc = snewn(5 * area, char);
1580         p = desc;
1581         run = 0;
1582         for (i = 0; i <= area; i++) {
1583             int n = (i < area ? grid[i] : -1);
1584
1585             if (!n)
1586                 run++;
1587             else {
1588                 if (run) {
1589                     while (run > 0) {
1590                         int c = 'a' - 1 + run;
1591                         if (run > 26)
1592                             c = 'z';
1593                         *p++ = c;
1594                         run -= c - ('a' - 1);
1595                     }
1596                 } else {
1597                     /*
1598                      * If there's a number in the very top left or
1599                      * bottom right, there's no point putting an
1600                      * unnecessary _ before or after it.
1601                      */
1602                     if (p > desc && n > 0)
1603                         *p++ = '_';
1604                 }
1605                 if (n > 0)
1606                     p += sprintf(p, "%d", n);
1607                 run = 0;
1608             }
1609         }
1610         assert(p - desc < 5 * area);
1611         *p++ = '\0';
1612         desc = sresize(desc, p - desc, char);
1613     }
1614
1615     sfree(grid);
1616
1617     return desc;
1618 }
1619
1620 static void game_free_aux_info(game_aux_info *aux)
1621 {
1622     sfree(aux->grid);
1623     sfree(aux);
1624 }
1625
1626 static char *validate_desc(game_params *params, char *desc)
1627 {
1628     int area = params->r * params->r * params->c * params->c;
1629     int squares = 0;
1630
1631     while (*desc) {
1632         int n = *desc++;
1633         if (n >= 'a' && n <= 'z') {
1634             squares += n - 'a' + 1;
1635         } else if (n == '_') {
1636             /* do nothing */;
1637         } else if (n > '0' && n <= '9') {
1638             squares++;
1639             while (*desc >= '0' && *desc <= '9')
1640                 desc++;
1641         } else
1642             return "Invalid character in game description";
1643     }
1644
1645     if (squares < area)
1646         return "Not enough data to fill grid";
1647
1648     if (squares > area)
1649         return "Too much data to fit in grid";
1650
1651     return NULL;
1652 }
1653
1654 static game_state *new_game(midend_data *me, game_params *params, char *desc)
1655 {
1656     game_state *state = snew(game_state);
1657     int c = params->c, r = params->r, cr = c*r, area = cr * cr;
1658     int i;
1659
1660     state->c = params->c;
1661     state->r = params->r;
1662
1663     state->grid = snewn(area, digit);
1664     state->pencil = snewn(area * cr, unsigned char);
1665     memset(state->pencil, 0, area * cr);
1666     state->immutable = snewn(area, unsigned char);
1667     memset(state->immutable, FALSE, area);
1668
1669     state->completed = state->cheated = FALSE;
1670
1671     i = 0;
1672     while (*desc) {
1673         int n = *desc++;
1674         if (n >= 'a' && n <= 'z') {
1675             int run = n - 'a' + 1;
1676             assert(i + run <= area);
1677             while (run-- > 0)
1678                 state->grid[i++] = 0;
1679         } else if (n == '_') {
1680             /* do nothing */;
1681         } else if (n > '0' && n <= '9') {
1682             assert(i < area);
1683             state->immutable[i] = TRUE;
1684             state->grid[i++] = atoi(desc-1);
1685             while (*desc >= '0' && *desc <= '9')
1686                 desc++;
1687         } else {
1688             assert(!"We can't get here");
1689         }
1690     }
1691     assert(i == area);
1692
1693     return state;
1694 }
1695
1696 static game_state *dup_game(game_state *state)
1697 {
1698     game_state *ret = snew(game_state);
1699     int c = state->c, r = state->r, cr = c*r, area = cr * cr;
1700
1701     ret->c = state->c;
1702     ret->r = state->r;
1703
1704     ret->grid = snewn(area, digit);
1705     memcpy(ret->grid, state->grid, area);
1706
1707     ret->pencil = snewn(area * cr, unsigned char);
1708     memcpy(ret->pencil, state->pencil, area * cr);
1709
1710     ret->immutable = snewn(area, unsigned char);
1711     memcpy(ret->immutable, state->immutable, area);
1712
1713     ret->completed = state->completed;
1714     ret->cheated = state->cheated;
1715
1716     return ret;
1717 }
1718
1719 static void free_game(game_state *state)
1720 {
1721     sfree(state->immutable);
1722     sfree(state->pencil);
1723     sfree(state->grid);
1724     sfree(state);
1725 }
1726
1727 static game_state *solve_game(game_state *state, game_aux_info *ai,
1728                               char **error)
1729 {
1730     game_state *ret;
1731     int c = state->c, r = state->r, cr = c*r;
1732     int rsolve_ret;
1733
1734     ret = dup_game(state);
1735     ret->completed = ret->cheated = TRUE;
1736
1737     /*
1738      * If we already have the solution in the aux_info, save
1739      * ourselves some time.
1740      */
1741     if (ai) {
1742
1743         assert(c == ai->c);
1744         assert(r == ai->r);
1745         memcpy(ret->grid, ai->grid, cr * cr * sizeof(digit));
1746
1747     } else {
1748         rsolve_ret = rsolve(c, r, ret->grid, NULL, 2);
1749
1750         if (rsolve_ret != 1) {
1751             free_game(ret);
1752             if (rsolve_ret == 0)
1753                 *error = "No solution exists for this puzzle";
1754             else
1755                 *error = "Multiple solutions exist for this puzzle";
1756             return NULL;
1757         }
1758     }
1759
1760     return ret;
1761 }
1762
1763 static char *grid_text_format(int c, int r, digit *grid)
1764 {
1765     int cr = c*r;
1766     int x, y;
1767     int maxlen;
1768     char *ret, *p;
1769
1770     /*
1771      * There are cr lines of digits, plus r-1 lines of block
1772      * separators. Each line contains cr digits, cr-1 separating
1773      * spaces, and c-1 two-character block separators. Thus, the
1774      * total length of a line is 2*cr+2*c-3 (not counting the
1775      * newline), and there are cr+r-1 of them.
1776      */
1777     maxlen = (cr+r-1) * (2*cr+2*c-2);
1778     ret = snewn(maxlen+1, char);
1779     p = ret;
1780
1781     for (y = 0; y < cr; y++) {
1782         for (x = 0; x < cr; x++) {
1783             int ch = grid[y * cr + x];
1784             if (ch == 0)
1785                 ch = ' ';
1786             else if (ch <= 9)
1787                 ch = '0' + ch;
1788             else
1789                 ch = 'a' + ch-10;
1790             *p++ = ch;
1791             if (x+1 < cr) {
1792                 *p++ = ' ';
1793                 if ((x+1) % r == 0) {
1794                     *p++ = '|';
1795                     *p++ = ' ';
1796                 }
1797             }
1798         }
1799         *p++ = '\n';
1800         if (y+1 < cr && (y+1) % c == 0) {
1801             for (x = 0; x < cr; x++) {
1802                 *p++ = '-';
1803                 if (x+1 < cr) {
1804                     *p++ = '-';
1805                     if ((x+1) % r == 0) {
1806                         *p++ = '+';
1807                         *p++ = '-';
1808                     }
1809                 }
1810             }
1811             *p++ = '\n';
1812         }
1813     }
1814
1815     assert(p - ret == maxlen);
1816     *p = '\0';
1817     return ret;
1818 }
1819
1820 static char *game_text_format(game_state *state)
1821 {
1822     return grid_text_format(state->c, state->r, state->grid);
1823 }
1824
1825 struct game_ui {
1826     /*
1827      * These are the coordinates of the currently highlighted
1828      * square on the grid, or -1,-1 if there isn't one. When there
1829      * is, pressing a valid number or letter key or Space will
1830      * enter that number or letter in the grid.
1831      */
1832     int hx, hy;
1833     /*
1834      * This indicates whether the current highlight is a
1835      * pencil-mark one or a real one.
1836      */
1837     int hpencil;
1838 };
1839
1840 static game_ui *new_ui(game_state *state)
1841 {
1842     game_ui *ui = snew(game_ui);
1843
1844     ui->hx = ui->hy = -1;
1845     ui->hpencil = 0;
1846
1847     return ui;
1848 }
1849
1850 static void free_ui(game_ui *ui)
1851 {
1852     sfree(ui);
1853 }
1854
1855 static game_state *make_move(game_state *from, game_ui *ui, game_drawstate *ds,
1856                              int x, int y, int button)
1857 {
1858     int c = from->c, r = from->r, cr = c*r;
1859     int tx, ty;
1860     game_state *ret;
1861
1862     button &= ~MOD_MASK;
1863
1864     tx = (x + TILE_SIZE - BORDER) / TILE_SIZE - 1;
1865     ty = (y + TILE_SIZE - BORDER) / TILE_SIZE - 1;
1866
1867     if (tx >= 0 && tx < cr && ty >= 0 && ty < cr) {
1868         if (button == LEFT_BUTTON) {
1869             if (from->immutable[ty*cr+tx]) {
1870                 ui->hx = ui->hy = -1;
1871             } else if (tx == ui->hx && ty == ui->hy && ui->hpencil == 0) {
1872                 ui->hx = ui->hy = -1;
1873             } else {
1874                 ui->hx = tx;
1875                 ui->hy = ty;
1876                 ui->hpencil = 0;
1877             }
1878             return from;                       /* UI activity occurred */
1879         }
1880         if (button == RIGHT_BUTTON) {
1881             /*
1882              * Pencil-mode highlighting for non filled squares.
1883              */
1884             if (from->grid[ty*cr+tx] == 0) {
1885                 if (tx == ui->hx && ty == ui->hy && ui->hpencil) {
1886                     ui->hx = ui->hy = -1;
1887                 } else {
1888                     ui->hpencil = 1;
1889                     ui->hx = tx;
1890                     ui->hy = ty;
1891                 }
1892             } else {
1893                 ui->hx = ui->hy = -1;
1894             }
1895             return from;                       /* UI activity occurred */
1896         }
1897     }
1898
1899     if (ui->hx != -1 && ui->hy != -1 &&
1900         ((button >= '1' && button <= '9' && button - '0' <= cr) ||
1901          (button >= 'a' && button <= 'z' && button - 'a' + 10 <= cr) ||
1902          (button >= 'A' && button <= 'Z' && button - 'A' + 10 <= cr) ||
1903          button == ' ')) {
1904         int n = button - '0';
1905         if (button >= 'A' && button <= 'Z')
1906             n = button - 'A' + 10;
1907         if (button >= 'a' && button <= 'z')
1908             n = button - 'a' + 10;
1909         if (button == ' ')
1910             n = 0;
1911
1912         /*
1913          * Can't overwrite this square. In principle this shouldn't
1914          * happen anyway because we should never have even been
1915          * able to highlight the square, but it never hurts to be
1916          * careful.
1917          */
1918         if (from->immutable[ui->hy*cr+ui->hx])
1919             return NULL;
1920
1921         /*
1922          * Can't make pencil marks in a filled square. In principle
1923          * this shouldn't happen anyway because we should never
1924          * have even been able to pencil-highlight the square, but
1925          * it never hurts to be careful.
1926          */
1927         if (ui->hpencil && from->grid[ui->hy*cr+ui->hx])
1928             return NULL;
1929
1930         ret = dup_game(from);
1931         if (ui->hpencil && n > 0) {
1932             int index = (ui->hy*cr+ui->hx) * cr + (n-1);
1933             ret->pencil[index] = !ret->pencil[index];
1934         } else {
1935             ret->grid[ui->hy*cr+ui->hx] = n;
1936             memset(ret->pencil + (ui->hy*cr+ui->hx)*cr, 0, cr);
1937
1938             /*
1939              * We've made a real change to the grid. Check to see
1940              * if the game has been completed.
1941              */
1942             if (!ret->completed && check_valid(c, r, ret->grid)) {
1943                 ret->completed = TRUE;
1944             }
1945         }
1946         ui->hx = ui->hy = -1;
1947
1948         return ret;                    /* made a valid move */
1949     }
1950
1951     return NULL;
1952 }
1953
1954 /* ----------------------------------------------------------------------
1955  * Drawing routines.
1956  */
1957
1958 struct game_drawstate {
1959     int started;
1960     int c, r, cr;
1961     digit *grid;
1962     unsigned char *pencil;
1963     unsigned char *hl;
1964 };
1965
1966 #define XSIZE(cr) ((cr) * TILE_SIZE + 2*BORDER + 1)
1967 #define YSIZE(cr) ((cr) * TILE_SIZE + 2*BORDER + 1)
1968
1969 static void game_size(game_params *params, int *x, int *y)
1970 {
1971     int c = params->c, r = params->r, cr = c*r;
1972
1973     *x = XSIZE(cr);
1974     *y = YSIZE(cr);
1975 }
1976
1977 static float *game_colours(frontend *fe, game_state *state, int *ncolours)
1978 {
1979     float *ret = snewn(3 * NCOLOURS, float);
1980
1981     frontend_default_colour(fe, &ret[COL_BACKGROUND * 3]);
1982
1983     ret[COL_GRID * 3 + 0] = 0.0F;
1984     ret[COL_GRID * 3 + 1] = 0.0F;
1985     ret[COL_GRID * 3 + 2] = 0.0F;
1986
1987     ret[COL_CLUE * 3 + 0] = 0.0F;
1988     ret[COL_CLUE * 3 + 1] = 0.0F;
1989     ret[COL_CLUE * 3 + 2] = 0.0F;
1990
1991     ret[COL_USER * 3 + 0] = 0.0F;
1992     ret[COL_USER * 3 + 1] = 0.6F * ret[COL_BACKGROUND * 3 + 1];
1993     ret[COL_USER * 3 + 2] = 0.0F;
1994
1995     ret[COL_HIGHLIGHT * 3 + 0] = 0.85F * ret[COL_BACKGROUND * 3 + 0];
1996     ret[COL_HIGHLIGHT * 3 + 1] = 0.85F * ret[COL_BACKGROUND * 3 + 1];
1997     ret[COL_HIGHLIGHT * 3 + 2] = 0.85F * ret[COL_BACKGROUND * 3 + 2];
1998
1999     ret[COL_PENCIL * 3 + 0] = 0.5F * ret[COL_BACKGROUND * 3 + 0];
2000     ret[COL_PENCIL * 3 + 1] = 0.5F * ret[COL_BACKGROUND * 3 + 1];
2001     ret[COL_PENCIL * 3 + 2] = ret[COL_BACKGROUND * 3 + 2];
2002
2003     *ncolours = NCOLOURS;
2004     return ret;
2005 }
2006
2007 static game_drawstate *game_new_drawstate(game_state *state)
2008 {
2009     struct game_drawstate *ds = snew(struct game_drawstate);
2010     int c = state->c, r = state->r, cr = c*r;
2011
2012     ds->started = FALSE;
2013     ds->c = c;
2014     ds->r = r;
2015     ds->cr = cr;
2016     ds->grid = snewn(cr*cr, digit);
2017     memset(ds->grid, 0, cr*cr);
2018     ds->pencil = snewn(cr*cr*cr, digit);
2019     memset(ds->pencil, 0, cr*cr*cr);
2020     ds->hl = snewn(cr*cr, unsigned char);
2021     memset(ds->hl, 0, cr*cr);
2022
2023     return ds;
2024 }
2025
2026 static void game_free_drawstate(game_drawstate *ds)
2027 {
2028     sfree(ds->hl);
2029     sfree(ds->pencil);
2030     sfree(ds->grid);
2031     sfree(ds);
2032 }
2033
2034 static void draw_number(frontend *fe, game_drawstate *ds, game_state *state,
2035                         int x, int y, int hl)
2036 {
2037     int c = state->c, r = state->r, cr = c*r;
2038     int tx, ty;
2039     int cx, cy, cw, ch;
2040     char str[2];
2041
2042     if (ds->grid[y*cr+x] == state->grid[y*cr+x] &&
2043         ds->hl[y*cr+x] == hl &&
2044         !memcmp(ds->pencil+(y*cr+x)*cr, state->pencil+(y*cr+x)*cr, cr))
2045         return;                        /* no change required */
2046
2047     tx = BORDER + x * TILE_SIZE + 2;
2048     ty = BORDER + y * TILE_SIZE + 2;
2049
2050     cx = tx;
2051     cy = ty;
2052     cw = TILE_SIZE-3;
2053     ch = TILE_SIZE-3;
2054
2055     if (x % r)
2056         cx--, cw++;
2057     if ((x+1) % r)
2058         cw++;
2059     if (y % c)
2060         cy--, ch++;
2061     if ((y+1) % c)
2062         ch++;
2063
2064     clip(fe, cx, cy, cw, ch);
2065
2066     /* background needs erasing */
2067     draw_rect(fe, cx, cy, cw, ch, hl == 1 ? COL_HIGHLIGHT : COL_BACKGROUND);
2068
2069     /* pencil-mode highlight */
2070     if (hl == 2) {
2071         int coords[6];
2072         coords[0] = cx;
2073         coords[1] = cy;
2074         coords[2] = cx+cw/2;
2075         coords[3] = cy;
2076         coords[4] = cx;
2077         coords[5] = cy+ch/2;
2078         draw_polygon(fe, coords, 3, TRUE, COL_HIGHLIGHT);
2079     }
2080
2081     /* new number needs drawing? */
2082     if (state->grid[y*cr+x]) {
2083         str[1] = '\0';
2084         str[0] = state->grid[y*cr+x] + '0';
2085         if (str[0] > '9')
2086             str[0] += 'a' - ('9'+1);
2087         draw_text(fe, tx + TILE_SIZE/2, ty + TILE_SIZE/2,
2088                   FONT_VARIABLE, TILE_SIZE/2, ALIGN_VCENTRE | ALIGN_HCENTRE,
2089                   state->immutable[y*cr+x] ? COL_CLUE : COL_USER, str);
2090     } else {
2091         /* pencil marks required? */
2092         int i, j;
2093
2094         for (i = j = 0; i < cr; i++)
2095             if (state->pencil[(y*cr+x)*cr+i]) {
2096                 int dx = j % r, dy = j / r, crm = max(c, r);
2097                 str[1] = '\0';
2098                 str[0] = i + '1';
2099                 if (str[0] > '9')
2100                     str[0] += 'a' - ('9'+1);
2101                 draw_text(fe, tx + (4*dx+3) * TILE_SIZE / (4*r+2),
2102                           ty + (4*dy+3) * TILE_SIZE / (4*c+2),
2103                           FONT_VARIABLE, TILE_SIZE/(crm*5/4),
2104                           ALIGN_VCENTRE | ALIGN_HCENTRE, COL_PENCIL, str);
2105                 j++;
2106             }
2107     }
2108
2109     unclip(fe);
2110
2111     draw_update(fe, cx, cy, cw, ch);
2112
2113     ds->grid[y*cr+x] = state->grid[y*cr+x];
2114     memcpy(ds->pencil+(y*cr+x)*cr, state->pencil+(y*cr+x)*cr, cr);
2115     ds->hl[y*cr+x] = hl;
2116 }
2117
2118 static void game_redraw(frontend *fe, game_drawstate *ds, game_state *oldstate,
2119                         game_state *state, int dir, game_ui *ui,
2120                         float animtime, float flashtime)
2121 {
2122     int c = state->c, r = state->r, cr = c*r;
2123     int x, y;
2124
2125     if (!ds->started) {
2126         /*
2127          * The initial contents of the window are not guaranteed
2128          * and can vary with front ends. To be on the safe side,
2129          * all games should start by drawing a big
2130          * background-colour rectangle covering the whole window.
2131          */
2132         draw_rect(fe, 0, 0, XSIZE(cr), YSIZE(cr), COL_BACKGROUND);
2133
2134         /*
2135          * Draw the grid.
2136          */
2137         for (x = 0; x <= cr; x++) {
2138             int thick = (x % r ? 0 : 1);
2139             draw_rect(fe, BORDER + x*TILE_SIZE - thick, BORDER-1,
2140                       1+2*thick, cr*TILE_SIZE+3, COL_GRID);
2141         }
2142         for (y = 0; y <= cr; y++) {
2143             int thick = (y % c ? 0 : 1);
2144             draw_rect(fe, BORDER-1, BORDER + y*TILE_SIZE - thick,
2145                       cr*TILE_SIZE+3, 1+2*thick, COL_GRID);
2146         }
2147     }
2148
2149     /*
2150      * Draw any numbers which need redrawing.
2151      */
2152     for (x = 0; x < cr; x++) {
2153         for (y = 0; y < cr; y++) {
2154             int highlight = 0;
2155             if (flashtime > 0 &&
2156                 (flashtime <= FLASH_TIME/3 ||
2157                  flashtime >= FLASH_TIME*2/3))
2158                 highlight = 1;
2159             if (x == ui->hx && y == ui->hy)
2160                 highlight = ui->hpencil ? 2 : 1;
2161             draw_number(fe, ds, state, x, y, highlight);
2162         }
2163     }
2164
2165     /*
2166      * Update the _entire_ grid if necessary.
2167      */
2168     if (!ds->started) {
2169         draw_update(fe, 0, 0, XSIZE(cr), YSIZE(cr));
2170         ds->started = TRUE;
2171     }
2172 }
2173
2174 static float game_anim_length(game_state *oldstate, game_state *newstate,
2175                               int dir, game_ui *ui)
2176 {
2177     return 0.0F;
2178 }
2179
2180 static float game_flash_length(game_state *oldstate, game_state *newstate,
2181                                int dir, game_ui *ui)
2182 {
2183     if (!oldstate->completed && newstate->completed &&
2184         !oldstate->cheated && !newstate->cheated)
2185         return FLASH_TIME;
2186     return 0.0F;
2187 }
2188
2189 static int game_wants_statusbar(void)
2190 {
2191     return FALSE;
2192 }
2193
2194 static int game_timing_state(game_state *state)
2195 {
2196     return TRUE;
2197 }
2198
2199 #ifdef COMBINED
2200 #define thegame solo
2201 #endif
2202
2203 const struct game thegame = {
2204     "Solo", "games.solo",
2205     default_params,
2206     game_fetch_preset,
2207     decode_params,
2208     encode_params,
2209     free_params,
2210     dup_params,
2211     TRUE, game_configure, custom_params,
2212     validate_params,
2213     new_game_desc,
2214     game_free_aux_info,
2215     validate_desc,
2216     new_game,
2217     dup_game,
2218     free_game,
2219     TRUE, solve_game,
2220     TRUE, game_text_format,
2221     new_ui,
2222     free_ui,
2223     make_move,
2224     game_size,
2225     game_colours,
2226     game_new_drawstate,
2227     game_free_drawstate,
2228     game_redraw,
2229     game_anim_length,
2230     game_flash_length,
2231     game_wants_statusbar,
2232     FALSE, game_timing_state,
2233     0,                                 /* mouse_priorities */
2234 };
2235
2236 #ifdef STANDALONE_SOLVER
2237
2238 /*
2239  * gcc -DSTANDALONE_SOLVER -o solosolver solo.c malloc.c
2240  */
2241
2242 void frontend_default_colour(frontend *fe, float *output) {}
2243 void draw_text(frontend *fe, int x, int y, int fonttype, int fontsize,
2244                int align, int colour, char *text) {}
2245 void draw_rect(frontend *fe, int x, int y, int w, int h, int colour) {}
2246 void draw_line(frontend *fe, int x1, int y1, int x2, int y2, int colour) {}
2247 void draw_polygon(frontend *fe, int *coords, int npoints,
2248                   int fill, int colour) {}
2249 void clip(frontend *fe, int x, int y, int w, int h) {}
2250 void unclip(frontend *fe) {}
2251 void start_draw(frontend *fe) {}
2252 void draw_update(frontend *fe, int x, int y, int w, int h) {}
2253 void end_draw(frontend *fe) {}
2254 unsigned long random_bits(random_state *state, int bits)
2255 { assert(!"Shouldn't get randomness"); return 0; }
2256 unsigned long random_upto(random_state *state, unsigned long limit)
2257 { assert(!"Shouldn't get randomness"); return 0; }
2258
2259 void fatal(char *fmt, ...)
2260 {
2261     va_list ap;
2262
2263     fprintf(stderr, "fatal error: ");
2264
2265     va_start(ap, fmt);
2266     vfprintf(stderr, fmt, ap);
2267     va_end(ap);
2268
2269     fprintf(stderr, "\n");
2270     exit(1);
2271 }
2272
2273 int main(int argc, char **argv)
2274 {
2275     game_params *p;
2276     game_state *s;
2277     int recurse = TRUE;
2278     char *id = NULL, *desc, *err;
2279     int y, x;
2280     int grade = FALSE;
2281
2282     while (--argc > 0) {
2283         char *p = *++argv;
2284         if (!strcmp(p, "-r")) {
2285             recurse = TRUE;
2286         } else if (!strcmp(p, "-n")) {
2287             recurse = FALSE;
2288         } else if (!strcmp(p, "-v")) {
2289             solver_show_working = TRUE;
2290             recurse = FALSE;
2291         } else if (!strcmp(p, "-g")) {
2292             grade = TRUE;
2293             recurse = FALSE;
2294         } else if (*p == '-') {
2295             fprintf(stderr, "%s: unrecognised option `%s'\n", argv[0]);
2296             return 1;
2297         } else {
2298             id = p;
2299         }
2300     }
2301
2302     if (!id) {
2303         fprintf(stderr, "usage: %s [-n | -r | -g | -v] <game_id>\n", argv[0]);
2304         return 1;
2305     }
2306
2307     desc = strchr(id, ':');
2308     if (!desc) {
2309         fprintf(stderr, "%s: game id expects a colon in it\n", argv[0]);
2310         return 1;
2311     }
2312     *desc++ = '\0';
2313
2314     p = default_params();
2315     decode_params(p, id);
2316     err = validate_desc(p, desc);
2317     if (err) {
2318         fprintf(stderr, "%s: %s\n", argv[0], err);
2319         return 1;
2320     }
2321     s = new_game(NULL, p, desc);
2322
2323     if (recurse) {
2324         int ret = rsolve(p->c, p->r, s->grid, NULL, 2);
2325         if (ret > 1) {
2326             fprintf(stderr, "%s: rsolve: multiple solutions detected\n",
2327                     argv[0]);
2328         }
2329     } else {
2330         int ret = nsolve(p->c, p->r, s->grid);
2331         if (grade) {
2332             if (ret == DIFF_IMPOSSIBLE) {
2333                 /*
2334                  * Now resort to rsolve to determine whether it's
2335                  * really soluble.
2336                  */
2337                 ret = rsolve(p->c, p->r, s->grid, NULL, 2);
2338                 if (ret == 0)
2339                     ret = DIFF_IMPOSSIBLE;
2340                 else if (ret == 1)
2341                     ret = DIFF_RECURSIVE;
2342                 else
2343                     ret = DIFF_AMBIGUOUS;
2344             }
2345             printf("Difficulty rating: %s\n",
2346                    ret==DIFF_BLOCK ? "Trivial (blockwise positional elimination only)":
2347                    ret==DIFF_SIMPLE ? "Basic (row/column/number elimination required)":
2348                    ret==DIFF_INTERSECT ? "Intermediate (intersectional analysis required)":
2349                    ret==DIFF_SET ? "Advanced (set elimination required)":
2350                    ret==DIFF_RECURSIVE ? "Unreasonable (guesswork and backtracking required)":
2351                    ret==DIFF_AMBIGUOUS ? "Ambiguous (multiple solutions exist)":
2352                    ret==DIFF_IMPOSSIBLE ? "Impossible (no solution exists)":
2353                    "INTERNAL ERROR: unrecognised difficulty code");
2354         }
2355     }
2356
2357     printf("%s\n", grid_text_format(p->c, p->r, s->grid));
2358
2359     return 0;
2360 }
2361
2362 #endif