In Windows/Gtk front-ends, consistently use the ellipsis convention for naming
[sgt/puzzles] / solo.c
diff --git a/solo.c b/solo.c
index f8d8d6b..a2f40eb 100644 (file)
--- a/solo.c
+++ b/solo.c
@@ -116,8 +116,8 @@ typedef unsigned char digit;
 enum { SYMM_NONE, SYMM_ROT2, SYMM_ROT4, SYMM_REF2, SYMM_REF2D, SYMM_REF4,
        SYMM_REF4D, SYMM_REF8 };
 
-enum { DIFF_BLOCK, DIFF_SIMPLE, DIFF_INTERSECT,
-       DIFF_SET, DIFF_RECURSIVE, DIFF_AMBIGUOUS, DIFF_IMPOSSIBLE };
+enum { DIFF_BLOCK, DIFF_SIMPLE, DIFF_INTERSECT, DIFF_SET, DIFF_EXTREME,
+       DIFF_RECURSIVE, DIFF_AMBIGUOUS, DIFF_IMPOSSIBLE };
 
 enum {
     COL_BACKGROUND,
@@ -177,6 +177,7 @@ static int game_fetch_preset(int i, char **name, game_params **params)
         { "3x3 Basic", { 3, 3, SYMM_ROT2, DIFF_SIMPLE } },
         { "3x3 Intermediate", { 3, 3, SYMM_ROT2, DIFF_INTERSECT } },
         { "3x3 Advanced", { 3, 3, SYMM_ROT2, DIFF_SET } },
+        { "3x3 Extreme", { 3, 3, SYMM_ROT2, DIFF_EXTREME } },
         { "3x3 Unreasonable", { 3, 3, SYMM_ROT2, DIFF_RECURSIVE } },
 #ifndef SLOW_SYSTEM
         { "3x4 Basic", { 3, 4, SYMM_ROT2, DIFF_SIMPLE } },
@@ -236,6 +237,8 @@ static void decode_params(game_params *ret, char const *string)
                 string++, ret->diff = DIFF_INTERSECT;
             else if (*string == 'a')   /* advanced */
                 string++, ret->diff = DIFF_SET;
+            else if (*string == 'e')   /* extreme */
+                string++, ret->diff = DIFF_EXTREME;
             else if (*string == 'u')   /* unreasonable */
                 string++, ret->diff = DIFF_RECURSIVE;
         } else
@@ -264,6 +267,7 @@ static char *encode_params(game_params *params, int full)
           case DIFF_SIMPLE: strcat(str, "db"); break;
           case DIFF_INTERSECT: strcat(str, "di"); break;
           case DIFF_SET: strcat(str, "da"); break;
+          case DIFF_EXTREME: strcat(str, "de"); break;
           case DIFF_RECURSIVE: strcat(str, "du"); break;
         }
     }
@@ -298,7 +302,7 @@ static config_item *game_configure(game_params *params)
 
     ret[3].name = "Difficulty";
     ret[3].type = C_CHOICES;
-    ret[3].sval = ":Trivial:Basic:Intermediate:Advanced:Unreasonable";
+    ret[3].sval = ":Trivial:Basic:Intermediate:Advanced:Extreme:Unreasonable";
     ret[3].ival = params->diff;
 
     ret[4].name = NULL;
@@ -335,9 +339,7 @@ static char *validate_params(game_params *params, int full)
 /* ----------------------------------------------------------------------
  * Solver.
  * 
- * This solver is used for several purposes:
- *  + to generate filled grids as the basis for new puzzles (by
- *    supplying no clue squares at all)
+ * This solver is used for two purposes:
  *  + to check solubility of a grid as we gradually remove numbers
  *    from it
  *  + to solve an externally generated puzzle when the user selects
@@ -389,6 +391,29 @@ static char *validate_params(game_params *params, int full)
  *       the numbers' possible positions (or the spaces' possible
  *       contents).
  * 
+ *  - Mutual neighbour elimination: find two squares A,B and a
+ *    number N in the possible set of A, such that putting N in A
+ *    would rule out enough possibilities from the mutual
+ *    neighbours of A and B that there would be no possibilities
+ *    left for B. Thereby rule out N in A.
+ *     + The simplest case of this is if B has two possibilities
+ *      (wlog {1,2}), and there are two mutual neighbours of A and
+ *      B which have possibilities {1,3} and {2,3}. Thus, if A
+ *      were to be 3, then those neighbours would contain 1 and 2,
+ *      and hence there would be nothing left which could go in B.
+ *     + There can be more complex cases of it too: if A and B are
+ *      in the same column of large blocks, then they can have
+ *      more than two mutual neighbours, some of which can also be
+ *      neighbours of one another. Suppose, for example, that B
+ *      has possibilities {1,2,3}; there's one square P in the
+ *      same column as B and the same block as A, with
+ *      possibilities {1,4}; and there are _two_ squares Q,R in
+ *      the same column as A and the same block as B with
+ *      possibilities {2,3,4}. Then if A contained 4, P would
+ *      contain 1, and Q and R would have to contain 2 and 3 in
+ *      _some_ order; therefore, once again, B would have no
+ *      remaining possibilities.
+ * 
  *  - Recursion. If all else fails, we pick one of the currently
  *    most constrained empty squares and take a random guess at its
  *    contents, then continue solving on that basis and see if we
@@ -627,6 +652,10 @@ static int solver_intersect(struct solver_usage *usage,
 
 struct solver_scratch {
     unsigned char *grid, *rowidx, *colidx, *set;
+    int *neighbours, *bfsqueue;
+#ifdef STANDALONE_SOLVER
+    int *bfsprev;
+#endif
 };
 
 static int solver_set(struct solver_usage *usage,
@@ -825,6 +854,353 @@ static int solver_set(struct solver_usage *usage,
     return 0;
 }
 
+/*
+ * Try to find a number in the possible set of (x1,y1) which can be
+ * ruled out because it would leave no possibilities for (x2,y2).
+ */
+static int solver_mne(struct solver_usage *usage,
+                     struct solver_scratch *scratch,
+                     int x1, int y1, int x2, int y2)
+{
+    int c = usage->c, r = usage->r, cr = c*r;
+    int *nb[2];
+    unsigned char *set = scratch->set;
+    unsigned char *numbers = scratch->rowidx;
+    unsigned char *numbersleft = scratch->colidx;
+    int nnb, count;
+    int i, j, n, nbi;
+
+    nb[0] = scratch->neighbours;
+    nb[1] = scratch->neighbours + cr;
+
+    /*
+     * First, work out the mutual neighbour squares of the two. We
+     * can assert that they're not actually in the same block,
+     * which leaves two possibilities: they're in different block
+     * rows _and_ different block columns (thus their mutual
+     * neighbours are precisely the other two corners of the
+     * rectangle), or they're in the same row (WLOG) and different
+     * columns, in which case their mutual neighbours are the
+     * column of each block aligned with the other square.
+     * 
+     * We divide the mutual neighbours into two separate subsets
+     * nb[0] and nb[1]; squares in the same subset are not only
+     * adjacent to both our key squares, but are also always
+     * adjacent to one another.
+     */
+    if (x1 / r != x2 / r && y1 % r != y2 % r) {
+       /* Corners of the rectangle. */
+       nnb = 1;
+       nb[0][0] = cubepos(x2, y1, 1);
+       nb[1][0] = cubepos(x1, y2, 1);
+    } else if (x1 / r != x2 / r) {
+       /* Same row of blocks; different blocks within that row. */
+       int x1b = x1 - (x1 % r);
+       int x2b = x2 - (x2 % r);
+
+       nnb = r;
+       for (i = 0; i < r; i++) {
+           nb[0][i] = cubepos(x2b+i, y1, 1);
+           nb[1][i] = cubepos(x1b+i, y2, 1);
+       }
+    } else {
+       /* Same column of blocks; different blocks within that column. */
+       int y1b = y1 % r;
+       int y2b = y2 % r;
+
+       assert(y1 % r != y2 % r);
+
+       nnb = c;
+       for (i = 0; i < c; i++) {
+           nb[0][i] = cubepos(x2, y1b+i*r, 1);
+           nb[1][i] = cubepos(x1, y2b+i*r, 1);
+       }
+    }
+
+    /*
+     * Right. Now loop over each possible number.
+     */
+    for (n = 1; n <= cr; n++) {
+       if (!cube(x1, y1, n))
+           continue;
+       for (j = 0; j < cr; j++)
+           numbersleft[j] = cube(x2, y2, j+1);
+
+       /*
+        * Go over every possible subset of each neighbour list,
+        * and see if its union of possible numbers minus n has the
+        * same size as the subset. If so, add the numbers in that
+        * subset to the set of things which would be ruled out
+        * from (x2,y2) if n were placed at (x1,y1).
+        */
+       memset(set, 0, nnb);
+       count = 0;
+       while (1) {
+           /*
+            * Binary increment: change the rightmost 0 to a 1, and
+            * change all 1s to the right of it to 0s.
+            */
+           i = nnb;
+           while (i > 0 && set[i-1])
+               set[--i] = 0, count--;
+           if (i > 0)
+               set[--i] = 1, count++;
+           else
+               break;                 /* done */
+
+           /*
+            * Examine this subset of each neighbour set.
+            */
+           for (nbi = 0; nbi < 2; nbi++) {
+               int *nbs = nb[nbi];
+               
+               memset(numbers, 0, cr);
+
+               for (i = 0; i < nnb; i++)
+                   if (set[i])
+                       for (j = 0; j < cr; j++)
+                           if (j != n-1 && usage->cube[nbs[i] + j])
+                               numbers[j] = 1;
+
+               for (i = j = 0; j < cr; j++)
+                   i += numbers[j];
+
+               if (i == count) {
+                   /*
+                    * Got one. This subset of nbs, in the absence
+                    * of n, would definitely contain all the
+                    * numbers listed in `numbers'. Rule them out
+                    * of `numbersleft'.
+                    */
+                   for (j = 0; j < cr; j++)
+                       if (numbers[j])
+                           numbersleft[j] = 0;
+               }
+           }
+       }
+
+       /*
+        * If we've got nothing left in `numbersleft', we have a
+        * successful mutual neighbour elimination.
+        */
+       for (j = 0; j < cr; j++)
+           if (numbersleft[j])
+               break;
+
+       if (j == cr) {
+#ifdef STANDALONE_SOLVER
+           if (solver_show_working) {
+               printf("%*smutual neighbour elimination, (%d,%d) vs (%d,%d):\n",
+                      solver_recurse_depth*4, "",
+                      1+x1, 1+YUNTRANS(y1), 1+x2, 1+YUNTRANS(y2));
+               printf("%*s  ruling out %d at (%d,%d)\n",
+                      solver_recurse_depth*4, "",
+                      n, 1+x1, 1+YUNTRANS(y1));
+           }
+#endif
+           cube(x1, y1, n) = FALSE;
+           return +1;
+       }
+    }
+
+    return 0;                         /* nothing found */
+}
+
+/*
+ * Look for forcing chains. A forcing chain is a path of
+ * pairwise-exclusive squares (i.e. each pair of adjacent squares
+ * in the path are in the same row, column or block) with the
+ * following properties:
+ *
+ *  (a) Each square on the path has precisely two possible numbers.
+ *
+ *  (b) Each pair of squares which are adjacent on the path share
+ *      at least one possible number in common.
+ *
+ *  (c) Each square in the middle of the path shares _both_ of its
+ *      numbers with at least one of its neighbours (not the same
+ *      one with both neighbours).
+ *
+ * These together imply that at least one of the possible number
+ * choices at one end of the path forces _all_ the rest of the
+ * numbers along the path. In order to make real use of this, we
+ * need further properties:
+ *
+ *  (c) Ruling out some number N from the square at one end
+ *      of the path forces the square at the other end to
+ *      take number N.
+ *
+ *  (d) The two end squares are both in line with some third
+ *      square.
+ *
+ *  (e) That third square currently has N as a possibility.
+ *
+ * If we can find all of that lot, we can deduce that at least one
+ * of the two ends of the forcing chain has number N, and that
+ * therefore the mutually adjacent third square does not.
+ *
+ * To find forcing chains, we're going to start a bfs at each
+ * suitable square, once for each of its two possible numbers.
+ */
+static int solver_forcing(struct solver_usage *usage,
+                          struct solver_scratch *scratch)
+{
+    int c = usage->c, r = usage->r, cr = c*r;
+    int *bfsqueue = scratch->bfsqueue;
+#ifdef STANDALONE_SOLVER
+    int *bfsprev = scratch->bfsprev;
+#endif
+    unsigned char *number = scratch->grid;
+    int *neighbours = scratch->neighbours;
+    int x, y;
+
+    for (y = 0; y < cr; y++)
+        for (x = 0; x < cr; x++) {
+            int count, t, n;
+
+            /*
+             * If this square doesn't have exactly two candidate
+             * numbers, don't try it.
+             * 
+             * In this loop we also sum the candidate numbers,
+             * which is a nasty hack to allow us to quickly find
+             * `the other one' (since we will shortly know there
+             * are exactly two).
+             */
+            for (count = t = 0, n = 1; n <= cr; n++)
+                if (cube(x, y, n))
+                    count++, t += n;
+            if (count != 2)
+                continue;
+
+            /*
+             * Now attempt a bfs for each candidate.
+             */
+            for (n = 1; n <= cr; n++)
+                if (cube(x, y, n)) {
+                    int orign, currn, head, tail;
+
+                    /*
+                     * Begin a bfs.
+                     */
+                    orign = n;
+
+                    memset(number, cr+1, cr*cr);
+                    head = tail = 0;
+                    bfsqueue[tail++] = y*cr+x;
+#ifdef STANDALONE_SOLVER
+                    bfsprev[y*cr+x] = -1;
+#endif
+                    number[y*cr+x] = t - n;
+
+                    while (head < tail) {
+                        int xx, yy, nneighbours, xt, yt, xblk, i;
+
+                        xx = bfsqueue[head++];
+                        yy = xx / cr;
+                        xx %= cr;
+
+                        currn = number[yy*cr+xx];
+
+                        /*
+                         * Find neighbours of yy,xx.
+                         */
+                        nneighbours = 0;
+                        for (yt = 0; yt < cr; yt++)
+                            neighbours[nneighbours++] = yt*cr+xx;
+                        for (xt = 0; xt < cr; xt++)
+                            neighbours[nneighbours++] = yy*cr+xt;
+                        xblk = xx - (xx % r);
+                        for (yt = yy % r; yt < cr; yt += r)
+                            for (xt = xblk; xt < xblk+r; xt++)
+                                neighbours[nneighbours++] = yt*cr+xt;
+
+                        /*
+                         * Try visiting each of those neighbours.
+                         */
+                        for (i = 0; i < nneighbours; i++) {
+                            int cc, tt, nn;
+
+                            xt = neighbours[i] % cr;
+                            yt = neighbours[i] / cr;
+
+                            /*
+                             * We need this square to not be
+                             * already visited, and to include
+                             * currn as a possible number.
+                             */
+                            if (number[yt*cr+xt] <= cr)
+                                continue;
+                            if (!cube(xt, yt, currn))
+                                continue;
+
+                            /*
+                             * Don't visit _this_ square a second
+                             * time!
+                             */
+                            if (xt == xx && yt == yy)
+                                continue;
+
+                            /*
+                             * To continue with the bfs, we need
+                             * this square to have exactly two
+                             * possible numbers.
+                             */
+                            for (cc = tt = 0, nn = 1; nn <= cr; nn++)
+                                if (cube(xt, yt, nn))
+                                    cc++, tt += nn;
+                            if (cc == 2) {
+                                bfsqueue[tail++] = yt*cr+xt;
+#ifdef STANDALONE_SOLVER
+                                bfsprev[yt*cr+xt] = yy*cr+xx;
+#endif
+                                number[yt*cr+xt] = tt - currn;
+                            }
+
+                            /*
+                             * One other possibility is that this
+                             * might be the square in which we can
+                             * make a real deduction: if it's
+                             * adjacent to x,y, and currn is equal
+                             * to the original number we ruled out.
+                             */
+                            if (currn == orign &&
+                                (xt == x || yt == y ||
+                                 (xt / r == x / r && yt % r == y % r))) {
+#ifdef STANDALONE_SOLVER
+                                if (solver_show_working) {
+                                    char *sep = "";
+                                    int xl, yl;
+                                    printf("%*sforcing chain, %d at ends of ",
+                                           solver_recurse_depth*4, "", orign);
+                                    xl = xx;
+                                    yl = yy;
+                                    while (1) {
+                                        printf("%s(%d,%d)", sep, 1+xl,
+                                               1+YUNTRANS(yl));
+                                        xl = bfsprev[yl*cr+xl];
+                                        if (xl < 0)
+                                            break;
+                                        yl = xl / cr;
+                                        xl %= cr;
+                                        sep = "-";
+                                    }
+                                    printf("\n%*s  ruling out %d at (%d,%d)\n",
+                                           solver_recurse_depth*4, "",
+                                           orign, 1+xt, 1+YUNTRANS(yt));
+                                }
+#endif
+                                cube(xt, yt, orign) = FALSE;
+                                return 1;
+                            }
+                        }
+                    }
+                }
+        }
+
+    return 0;
+}
+
 static struct solver_scratch *solver_new_scratch(struct solver_usage *usage)
 {
     struct solver_scratch *scratch = snew(struct solver_scratch);
@@ -833,11 +1209,21 @@ static struct solver_scratch *solver_new_scratch(struct solver_usage *usage)
     scratch->rowidx = snewn(cr, unsigned char);
     scratch->colidx = snewn(cr, unsigned char);
     scratch->set = snewn(cr, unsigned char);
+    scratch->neighbours = snewn(3*cr, int);
+    scratch->bfsqueue = snewn(cr*cr, int);
+#ifdef STANDALONE_SOLVER
+    scratch->bfsprev = snewn(cr*cr, int);
+#endif
     return scratch;
 }
 
 static void solver_free_scratch(struct solver_scratch *scratch)
 {
+#ifdef STANDALONE_SOLVER
+    sfree(scratch->bfsprev);
+#endif
+    sfree(scratch->bfsqueue);
+    sfree(scratch->neighbours);
     sfree(scratch->set);
     sfree(scratch->colidx);
     sfree(scratch->rowidx);
@@ -850,7 +1236,7 @@ static int solver(int c, int r, digit *grid, int maxdiff)
     struct solver_usage *usage;
     struct solver_scratch *scratch;
     int cr = c*r;
-    int x, y, n, ret;
+    int x, y, x2, y2, n, ret;
     int diff = DIFF_BLOCK;
 
     /*
@@ -1107,6 +1493,71 @@ static int solver(int c, int r, digit *grid, int maxdiff)
        }
 
        /*
+        * Row-vs-column set elimination on a single number.
+        */
+       for (n = 1; n <= cr; n++) {
+            ret = solver_set(usage, scratch, cubepos(0,0,n), cr*cr, cr
+#ifdef STANDALONE_SOLVER
+                            , "positional set elimination, number %d", n
+#endif
+                            );
+           if (ret < 0) {
+               diff = DIFF_IMPOSSIBLE;
+               goto got_result;
+           } else if (ret > 0) {
+               diff = max(diff, DIFF_EXTREME);
+               goto cont;
+           }
+       }
+
+       /*
+        * Mutual neighbour elimination.
+        */
+       for (y = 0; y+1 < cr; y++) {
+           for (x = 0; x+1 < cr; x++) {
+               for (y2 = y+1; y2 < cr; y2++) {
+                   for (x2 = x+1; x2 < cr; x2++) {
+                       /*
+                        * Can't do mutual neighbour elimination
+                        * between elements of the same actual
+                        * block.
+                        */
+                       if (x/r == x2/r && y%r == y2%r)
+                           continue;
+
+                       /*
+                        * Otherwise, try (x,y) vs (x2,y2) in both
+                        * directions, and likewise (x2,y) vs
+                        * (x,y2).
+                        */
+                       if (!usage->grid[YUNTRANS(y)*cr+x] &&
+                           !usage->grid[YUNTRANS(y2)*cr+x2] &&
+                           (solver_mne(usage, scratch, x, y, x2, y2) ||
+                            solver_mne(usage, scratch, x2, y2, x, y))) {
+                           diff = max(diff, DIFF_EXTREME);
+                           goto cont;
+                       }
+                       if (!usage->grid[YUNTRANS(y)*cr+x2] &&
+                           !usage->grid[YUNTRANS(y2)*cr+x] &&
+                           (solver_mne(usage, scratch, x2, y, x, y2) ||
+                            solver_mne(usage, scratch, x, y2, x2, y))) {
+                           diff = max(diff, DIFF_EXTREME);
+                           goto cont;
+                       }
+                   }
+               }
+           }
+       }
+
+        /*
+         * Forcing chains.
+         */
+        if (solver_forcing(usage, scratch)) {
+            diff = max(diff, DIFF_EXTREME);
+            goto cont;
+        }
+
+       /*
         * If we reach here, we have made no deductions in this
         * iteration, so the algorithm terminates.
         */
@@ -1674,8 +2125,8 @@ static char *new_game_desc(game_params *params, random_state *rs,
     int nlocs;
     char *desc;
     int coords[16], ncoords;
-    int *symmclasses, nsymmclasses;
-    int maxdiff, recursing;
+    int maxdiff;
+    int x, y, i, j;
 
     /*
      * Adjust the maximum difficulty level to be consistent with
@@ -1692,31 +2143,6 @@ static char *new_game_desc(game_params *params, random_state *rs,
     grid2 = snewn(area, digit);
 
     /*
-     * Find the set of equivalence classes of squares permitted
-     * by the selected symmetry. We do this by enumerating all
-     * the grid squares which have no symmetric companion
-     * sorting lower than themselves.
-     */
-    nsymmclasses = 0;
-    symmclasses = snewn(cr * cr, int);
-    {
-        int x, y;
-
-        for (y = 0; y < cr; y++)
-            for (x = 0; x < cr; x++) {
-                int i = y*cr+x;
-                int j;
-
-                ncoords = symmetries(params, x, y, coords, params->symm);
-                for (j = 0; j < ncoords; j++)
-                    if (coords[2*j+1]*cr+coords[2*j] < i)
-                        break;
-                if (j == ncoords)
-                    symmclasses[nsymmclasses++] = i;
-            }
-    }
-
-    /*
      * Loop until we get a grid of the required difficulty. This is
      * nasty, but it seems to be unpleasantly hard to generate
      * difficult grids otherwise.
@@ -1748,62 +2174,55 @@ static char *new_game_desc(game_params *params, random_state *rs,
          * Now we have a solved grid, start removing things from it
          * while preserving solubility.
          */
-       recursing = FALSE;
-        while (1) {
-            int x, y, i, j;
 
-            /*
-             * Iterate over the grid and enumerate all the filled
-             * squares we could empty.
-             */
-            nlocs = 0;
+        /*
+         * Find the set of equivalence classes of squares permitted
+         * by the selected symmetry. We do this by enumerating all
+         * the grid squares which have no symmetric companion
+         * sorting lower than themselves.
+         */
+        nlocs = 0;
+        for (y = 0; y < cr; y++)
+            for (x = 0; x < cr; x++) {
+                int i = y*cr+x;
+                int j;
 
-            for (i = 0; i < nsymmclasses; i++) {
-                x = symmclasses[i] % cr;
-                y = symmclasses[i] / cr;
-                if (grid[y*cr+x]) {
+                ncoords = symmetries(params, x, y, coords, params->symm);
+                for (j = 0; j < ncoords; j++)
+                    if (coords[2*j+1]*cr+coords[2*j] < i)
+                        break;
+                if (j == ncoords) {
                     locs[nlocs].x = x;
                     locs[nlocs].y = y;
                     nlocs++;
                 }
             }
 
-            /*
-             * Now shuffle that list.
-             */
-           shuffle(locs, nlocs, sizeof(*locs), rs);
-
-            /*
-             * Now loop over the shuffled list and, for each element,
-             * see whether removing that element (and its reflections)
-             * from the grid will still leave the grid soluble by
-             * solver.
-             */
-            for (i = 0; i < nlocs; i++) {
-               int ret;
+        /*
+         * Now shuffle that list.
+         */
+        shuffle(locs, nlocs, sizeof(*locs), rs);
 
-                x = locs[i].x;
-                y = locs[i].y;
+        /*
+         * Now loop over the shuffled list and, for each element,
+         * see whether removing that element (and its reflections)
+         * from the grid will still leave the grid soluble.
+         */
+        for (i = 0; i < nlocs; i++) {
+            int ret;
 
-                memcpy(grid2, grid, area);
-                ncoords = symmetries(params, x, y, coords, params->symm);
-                for (j = 0; j < ncoords; j++)
-                    grid2[coords[2*j+1]*cr+coords[2*j]] = 0;
+            x = locs[i].x;
+            y = locs[i].y;
 
-               ret = solver(c, r, grid2, maxdiff);
-                if (ret != DIFF_IMPOSSIBLE && ret != DIFF_AMBIGUOUS) {
-                    for (j = 0; j < ncoords; j++)
-                        grid[coords[2*j+1]*cr+coords[2*j]] = 0;
-                    break;
-                }
-            }
+            memcpy(grid2, grid, area);
+            ncoords = symmetries(params, x, y, coords, params->symm);
+            for (j = 0; j < ncoords; j++)
+                grid2[coords[2*j+1]*cr+coords[2*j]] = 0;
 
-            if (i == nlocs) {
-                /*
-                 * There was nothing we could remove without
-                 * destroying solvability. Give up.
-                 */
-                break;
+            ret = solver(c, r, grid2, maxdiff);
+            if (ret <= maxdiff) {
+                for (j = 0; j < ncoords; j++)
+                    grid[coords[2*j+1]*cr+coords[2*j]] = 0;
             }
         }
 
@@ -1813,8 +2232,6 @@ static char *new_game_desc(game_params *params, random_state *rs,
     sfree(grid2);
     sfree(locs);
 
-    sfree(symmclasses);
-
     /*
      * Now we have the grid as it will be presented to the user.
      * Encode it in a game desc.
@@ -1876,6 +2293,9 @@ static char *validate_desc(game_params *params, char *desc)
         } else if (n == '_') {
             /* do nothing */;
         } else if (n > '0' && n <= '9') {
+            int val = atoi(desc-1);
+            if (val < 1 || val > params->c * params->r)
+                return "Out-of-range number in game description";
             squares++;
             while (*desc >= '0' && *desc <= '9')
                 desc++;
@@ -1892,7 +2312,7 @@ static char *validate_desc(game_params *params, char *desc)
     return NULL;
 }
 
-static game_state *new_game(midend_data *me, game_params *params, char *desc)
+static game_state *new_game(midend *me, game_params *params, char *desc)
 {
     game_state *state = snew(game_state);
     int c = params->c, r = params->r, cr = c*r, area = cr * cr;
@@ -2025,7 +2445,7 @@ static char *grid_text_format(int c, int r, digit *grid)
         for (x = 0; x < cr; x++) {
             int ch = grid[y * cr + x];
             if (ch == 0)
-                ch = ' ';
+                ch = '.';
             else if (ch <= 9)
                 ch = '0' + ch;
             else
@@ -2179,13 +2599,13 @@ static char *interpret_move(game_state *state, game_ui *ui, game_drawstate *ds,
        ((button >= '1' && button <= '9' && button - '0' <= cr) ||
         (button >= 'a' && button <= 'z' && button - 'a' + 10 <= cr) ||
         (button >= 'A' && button <= 'Z' && button - 'A' + 10 <= cr) ||
-        button == ' ')) {
+        button == ' ' || button == '\010' || button == '\177')) {
        int n = button - '0';
        if (button >= 'A' && button <= 'Z')
            n = button - 'A' + 10;
        if (button >= 'a' && button <= 'z')
            n = button - 'a' + 10;
-       if (button == ' ')
+       if (button == ' ' || button == '\010' || button == '\177')
            n = 0;
 
         /*
@@ -2286,13 +2706,13 @@ static void game_compute_size(game_params *params, int tilesize,
     *y = SIZE(params->c * params->r);
 }
 
-static void game_set_size(game_drawstate *ds, game_params *params,
-                         int tilesize)
+static void game_set_size(drawing *dr, game_drawstate *ds,
+                         game_params *params, int tilesize)
 {
     ds->tilesize = tilesize;
 }
 
-static float *game_colours(frontend *fe, game_state *state, int *ncolours)
+static float *game_colours(frontend *fe, int *ncolours)
 {
     float *ret = snewn(3 * NCOLOURS, float);
 
@@ -2326,7 +2746,7 @@ static float *game_colours(frontend *fe, game_state *state, int *ncolours)
     return ret;
 }
 
-static game_drawstate *game_new_drawstate(game_state *state)
+static game_drawstate *game_new_drawstate(drawing *dr, game_state *state)
 {
     struct game_drawstate *ds = snew(struct game_drawstate);
     int c = state->c, r = state->r, cr = c*r;
@@ -2346,7 +2766,7 @@ static game_drawstate *game_new_drawstate(game_state *state)
     return ds;
 }
 
-static void game_free_drawstate(game_drawstate *ds)
+static void game_free_drawstate(drawing *dr, game_drawstate *ds)
 {
     sfree(ds->hl);
     sfree(ds->pencil);
@@ -2355,7 +2775,7 @@ static void game_free_drawstate(game_drawstate *ds)
     sfree(ds);
 }
 
-static void draw_number(frontend *fe, game_drawstate *ds, game_state *state,
+static void draw_number(drawing *dr, game_drawstate *ds, game_state *state,
                        int x, int y, int hl)
 {
     int c = state->c, r = state->r, cr = c*r;
@@ -2385,10 +2805,10 @@ static void draw_number(frontend *fe, game_drawstate *ds, game_state *state,
     if ((y+1) % c)
        ch++;
 
-    clip(fe, cx, cy, cw, ch);
+    clip(dr, cx, cy, cw, ch);
 
     /* background needs erasing */
-    draw_rect(fe, cx, cy, cw, ch, (hl & 15) == 1 ? COL_HIGHLIGHT : COL_BACKGROUND);
+    draw_rect(dr, cx, cy, cw, ch, (hl & 15) == 1 ? COL_HIGHLIGHT : COL_BACKGROUND);
 
     /* pencil-mode highlight */
     if ((hl & 15) == 2) {
@@ -2399,7 +2819,7 @@ static void draw_number(frontend *fe, game_drawstate *ds, game_state *state,
         coords[3] = cy;
         coords[4] = cx;
         coords[5] = cy+ch/2;
-        draw_polygon(fe, coords, 3, COL_HIGHLIGHT, COL_HIGHLIGHT);
+        draw_polygon(dr, coords, 3, COL_HIGHLIGHT, COL_HIGHLIGHT);
     }
 
     /* new number needs drawing? */
@@ -2408,7 +2828,7 @@ static void draw_number(frontend *fe, game_drawstate *ds, game_state *state,
        str[0] = state->grid[y*cr+x] + '0';
        if (str[0] > '9')
            str[0] += 'a' - ('9'+1);
-       draw_text(fe, tx + TILE_SIZE/2, ty + TILE_SIZE/2,
+       draw_text(dr, tx + TILE_SIZE/2, ty + TILE_SIZE/2,
                  FONT_VARIABLE, TILE_SIZE/2, ALIGN_VCENTRE | ALIGN_HCENTRE,
                  state->immutable[y*cr+x] ? COL_CLUE : (hl & 16) ? COL_ERROR : COL_USER, str);
     } else {
@@ -2443,7 +2863,7 @@ static void draw_number(frontend *fe, game_drawstate *ds, game_state *state,
                 str[0] = i + '1';
                 if (str[0] > '9')
                     str[0] += 'a' - ('9'+1);
-                draw_text(fe, tx + (4*dx+3) * TILE_SIZE / (4*pw+2),
+                draw_text(dr, tx + (4*dx+3) * TILE_SIZE / (4*pw+2),
                           ty + (4*dy+3) * TILE_SIZE / (4*ph+2),
                           FONT_VARIABLE, fontsize,
                           ALIGN_VCENTRE | ALIGN_HCENTRE, COL_PENCIL, str);
@@ -2451,16 +2871,16 @@ static void draw_number(frontend *fe, game_drawstate *ds, game_state *state,
             }
     }
 
-    unclip(fe);
+    unclip(dr);
 
-    draw_update(fe, cx, cy, cw, ch);
+    draw_update(dr, cx, cy, cw, ch);
 
     ds->grid[y*cr+x] = state->grid[y*cr+x];
     memcpy(ds->pencil+(y*cr+x)*cr, state->pencil+(y*cr+x)*cr, cr);
     ds->hl[y*cr+x] = hl;
 }
 
-static void game_redraw(frontend *fe, game_drawstate *ds, game_state *oldstate,
+static void game_redraw(drawing *dr, game_drawstate *ds, game_state *oldstate,
                        game_state *state, int dir, game_ui *ui,
                        float animtime, float flashtime)
 {
@@ -2474,19 +2894,19 @@ static void game_redraw(frontend *fe, game_drawstate *ds, game_state *oldstate,
         * all games should start by drawing a big
         * background-colour rectangle covering the whole window.
         */
-       draw_rect(fe, 0, 0, SIZE(cr), SIZE(cr), COL_BACKGROUND);
+       draw_rect(dr, 0, 0, SIZE(cr), SIZE(cr), COL_BACKGROUND);
 
        /*
         * Draw the grid.
         */
        for (x = 0; x <= cr; x++) {
            int thick = (x % r ? 0 : 1);
-           draw_rect(fe, BORDER + x*TILE_SIZE - thick, BORDER-1,
+           draw_rect(dr, BORDER + x*TILE_SIZE - thick, BORDER-1,
                      1+2*thick, cr*TILE_SIZE+3, COL_GRID);
        }
        for (y = 0; y <= cr; y++) {
            int thick = (y % c ? 0 : 1);
-           draw_rect(fe, BORDER-1, BORDER + y*TILE_SIZE - thick,
+           draw_rect(dr, BORDER-1, BORDER + y*TILE_SIZE - thick,
                      cr*TILE_SIZE+3, 1+2*thick, COL_GRID);
        }
     }
@@ -2532,7 +2952,7 @@ static void game_redraw(frontend *fe, game_drawstate *ds, game_state *oldstate,
                      (ds->entered_items[((x/r)+(y/c)*c)*cr+d-1] & 32)))
                highlight |= 16;
 
-           draw_number(fe, ds, state, x, y, highlight);
+           draw_number(dr, ds, state, x, y, highlight);
        }
     }
 
@@ -2540,7 +2960,7 @@ static void game_redraw(frontend *fe, game_drawstate *ds, game_state *oldstate,
      * Update the _entire_ grid if necessary.
      */
     if (!ds->started) {
-       draw_update(fe, 0, 0, SIZE(cr), SIZE(cr));
+       draw_update(dr, 0, 0, SIZE(cr), SIZE(cr));
        ds->started = TRUE;
     }
 }
@@ -2560,14 +2980,71 @@ static float game_flash_length(game_state *oldstate, game_state *newstate,
     return 0.0F;
 }
 
-static int game_wants_statusbar(void)
+static int game_timing_state(game_state *state, game_ui *ui)
 {
-    return FALSE;
+    return TRUE;
 }
 
-static int game_timing_state(game_state *state, game_ui *ui)
+static void game_print_size(game_params *params, float *x, float *y)
 {
-    return TRUE;
+    int pw, ph;
+
+    /*
+     * I'll use 9mm squares by default. They should be quite big
+     * for this game, because players will want to jot down no end
+     * of pencil marks in the squares.
+     */
+    game_compute_size(params, 900, &pw, &ph);
+    *x = pw / 100.0;
+    *y = ph / 100.0;
+}
+
+static void game_print(drawing *dr, game_state *state, int tilesize)
+{
+    int c = state->c, r = state->r, cr = c*r;
+    int ink = print_mono_colour(dr, 0);
+    int x, y;
+
+    /* Ick: fake up `ds->tilesize' for macro expansion purposes */
+    game_drawstate ads, *ds = &ads;
+    game_set_size(dr, ds, NULL, tilesize);
+
+    /*
+     * Border.
+     */
+    print_line_width(dr, 3 * TILE_SIZE / 40);
+    draw_rect_outline(dr, BORDER, BORDER, cr*TILE_SIZE, cr*TILE_SIZE, ink);
+
+    /*
+     * Grid.
+     */
+    for (x = 1; x < cr; x++) {
+       print_line_width(dr, (x % r ? 1 : 3) * TILE_SIZE / 40);
+       draw_line(dr, BORDER+x*TILE_SIZE, BORDER,
+                 BORDER+x*TILE_SIZE, BORDER+cr*TILE_SIZE, ink);
+    }
+    for (y = 1; y < cr; y++) {
+       print_line_width(dr, (y % c ? 1 : 3) * TILE_SIZE / 40);
+       draw_line(dr, BORDER, BORDER+y*TILE_SIZE,
+                 BORDER+cr*TILE_SIZE, BORDER+y*TILE_SIZE, ink);
+    }
+
+    /*
+     * Numbers.
+     */
+    for (y = 0; y < cr; y++)
+       for (x = 0; x < cr; x++)
+           if (state->grid[y*cr+x]) {
+               char str[2];
+               str[1] = '\0';
+               str[0] = state->grid[y*cr+x] + '0';
+               if (str[0] > '9')
+                   str[0] += 'a' - ('9'+1);
+               draw_text(dr, BORDER + x*TILE_SIZE + TILE_SIZE/2,
+                         BORDER + y*TILE_SIZE + TILE_SIZE/2,
+                         FONT_VARIABLE, TILE_SIZE/2,
+                         ALIGN_VCENTRE | ALIGN_HCENTRE, ink, str);
+           }
 }
 
 #ifdef COMBINED
@@ -2575,7 +3052,7 @@ static int game_timing_state(game_state *state, game_ui *ui)
 #endif
 
 const struct game thegame = {
-    "Solo", "games.solo",
+    "Solo", "games.solo", "solo",
     default_params,
     game_fetch_preset,
     decode_params,
@@ -2605,50 +3082,14 @@ const struct game thegame = {
     game_redraw,
     game_anim_length,
     game_flash_length,
-    game_wants_statusbar,
+    TRUE, FALSE, game_print_size, game_print,
+    FALSE,                            /* wants_statusbar */
     FALSE, game_timing_state,
-    0,                                /* mouse_priorities */
+    0,                                /* flags */
 };
 
 #ifdef STANDALONE_SOLVER
 
-/*
- * gcc -DSTANDALONE_SOLVER -o solosolver solo.c malloc.c
- */
-
-void frontend_default_colour(frontend *fe, float *output) {}
-void draw_text(frontend *fe, int x, int y, int fonttype, int fontsize,
-               int align, int colour, char *text) {}
-void draw_rect(frontend *fe, int x, int y, int w, int h, int colour) {}
-void draw_line(frontend *fe, int x1, int y1, int x2, int y2, int colour) {}
-void draw_polygon(frontend *fe, int *coords, int npoints,
-                  int fillcolour, int outlinecolour) {}
-void clip(frontend *fe, int x, int y, int w, int h) {}
-void unclip(frontend *fe) {}
-void start_draw(frontend *fe) {}
-void draw_update(frontend *fe, int x, int y, int w, int h) {}
-void end_draw(frontend *fe) {}
-unsigned long random_bits(random_state *state, int bits)
-{ assert(!"Shouldn't get randomness"); return 0; }
-unsigned long random_upto(random_state *state, unsigned long limit)
-{ assert(!"Shouldn't get randomness"); return 0; }
-void shuffle(void *array, int nelts, int eltsize, random_state *rs)
-{ assert(!"Shouldn't get randomness"); }
-
-void fatal(char *fmt, ...)
-{
-    va_list ap;
-
-    fprintf(stderr, "fatal error: ");
-
-    va_start(ap, fmt);
-    vfprintf(stderr, fmt, ap);
-    va_end(ap);
-
-    fprintf(stderr, "\n");
-    exit(1);
-}
-
 int main(int argc, char **argv)
 {
     game_params *p;
@@ -2699,6 +3140,7 @@ int main(int argc, char **argv)
               ret==DIFF_SIMPLE ? "Basic (row/column/number elimination required)":
               ret==DIFF_INTERSECT ? "Intermediate (intersectional analysis required)":
               ret==DIFF_SET ? "Advanced (set elimination required)":
+              ret==DIFF_EXTREME ? "Extreme (complex non-recursive techniques required)":
               ret==DIFF_RECURSIVE ? "Unreasonable (guesswork and backtracking required)":
               ret==DIFF_AMBIGUOUS ? "Ambiguous (multiple solutions exist)":
               ret==DIFF_IMPOSSIBLE ? "Impossible (no solution exists)":