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