X-Git-Url: http://www.chiark.greenend.org.uk/ucgi/~ian/git?a=blobdiff_plain;f=lightup.c;h=bfc6980600c5bb6ad189cbfa3aed0ef4ddcda329;hb=3234912f921916a1b8da164fd61dc75579358577;hp=8549a751940fb32584f0b7d42e74f3a516a0a5df;hpb=c8c576f68949ecab29c8250222983c2b9d2931f7;p=sgt-puzzles.git

diff --git a/lightup.c b/lightup.c
index 8549a75..bfc6980 100644
--- a/lightup.c
+++ b/lightup.c
@@ -1,5 +1,45 @@
 /*
  * lightup.c: Implementation of the Nikoli game 'Light Up'.
+ *
+ * Possible future solver enhancements:
+ *
+ *  - In a situation where two clues are diagonally adjacent, you can
+ *    deduce bounds on the number of lights shared between them. For
+ *    instance, suppose a 3 clue is diagonally adjacent to a 1 clue:
+ *    of the two squares adjacent to both clues, at least one must be
+ *    a light (or the 3 would be unsatisfiable) and yet at most one
+ *    must be a light (or the 1 would be overcommitted), so in fact
+ *    _exactly_ one must be a light, and hence the other two squares
+ *    adjacent to the 3 must also be lights and the other two adjacent
+ *    to the 1 must not. Likewise if the 3 is replaced with a 2 but
+ *    one of its other two squares is known not to be a light, and so
+ *    on.
+ *
+ *  - In a situation where two clues are orthogonally separated (not
+ *    necessarily directly adjacent), you may be able to deduce
+ *    something about the squares that align with each other. For
+ *    instance, suppose two clues are vertically adjacent. Consider
+ *    the pair of squares A,B horizontally adjacent to the top clue,
+ *    and the pair C,D horizontally adjacent to the bottom clue.
+ *    Assuming no intervening obstacles, A and C align with each other
+ *    and hence at most one of them can be a light, and B and D
+ *    likewise, so we must have at most two lights between the four
+ *    squares. So if the clues indicate that there are at _least_ two
+ *    lights in those four squares because the top clue requires at
+ *    least one of AB to be a light and the bottom one requires at
+ *    least one of CD, then we can in fact deduce that there are
+ *    _exactly_ two lights between the four squares, and fill in the
+ *    other squares adjacent to each clue accordingly. For instance,
+ *    if both clues are 3s, then we instantly deduce that all four of
+ *    the squares _vertically_ adjacent to the two clues must be
+ *    lights. (For that to happen, of course, there'd also have to be
+ *    a black square in between the clues, so the two inner lights
+ *    don't light each other.)
+ *
+ *  - I haven't thought it through carefully, but there's always the
+ *    possibility that both of the above deductions are special cases
+ *    of some more general pattern which can be made computationally
+ *    feasible...
  */
 
 #include <stdio.h>
@@ -11,6 +51,20 @@
 
 #include "puzzles.h"
 
+/*
+ * In standalone solver mode, `verbose' is a variable which can be
+ * set by command-line option; in debugging mode it's simply always
+ * true.
+ */
+#if defined STANDALONE_SOLVER
+#define SOLVER_DIAGNOSTICS
+int verbose = 0;
+#undef debug
+#define debug(x) printf x
+#elif defined SOLVER_DIAGNOSTICS
+#define verbose 2
+#endif
+
 /* --- Constants, structure definitions, etc. --- */
 
 #define PREFERRED_TILE_SIZE 32
@@ -36,11 +90,13 @@ enum {
 
 enum { SYMM_NONE, SYMM_REF2, SYMM_ROT2, SYMM_REF4, SYMM_ROT4, SYMM_MAX };
 
+#define DIFFCOUNT 2
+
 struct game_params {
     int w, h;
     int blackpc;        /* %age of black squares */
     int symm;
-    int recurse;
+    int difficulty;     /* 0 to DIFFCOUNT */
 };
 
 #define F_BLACK         1
@@ -101,7 +157,8 @@ typedef struct {
 
 /* Fills in (doesn't allocate) a surrounds structure with the grid locations
  * around a given square, taking account of the edges. */
-static void get_surrounds(game_state *state, int ox, int oy, surrounds *s)
+static void get_surrounds(const game_state *state, int ox, int oy,
+                          surrounds *s)
 {
     assert(ox >= 0 && ox < state->w && oy >= 0 && oy < state->h);
     s->npoints = 0;
@@ -125,14 +182,17 @@ static void get_surrounds(game_state *state, int ox, int oy, surrounds *s)
 const struct game_params lightup_presets[] = {
     { 7, 7, 20, SYMM_ROT4, 0 },
     { 7, 7, 20, SYMM_ROT4, 1 },
+    { 7, 7, 20, SYMM_ROT4, 2 },
     { 10, 10, 20, SYMM_ROT2, 0 },
     { 10, 10, 20, SYMM_ROT2, 1 },
 #ifdef SLOW_SYSTEM
     { 12, 12, 20, SYMM_ROT2, 0 },
-    { 12, 12, 20, SYMM_ROT2, 1 }
+    { 12, 12, 20, SYMM_ROT2, 1 },
 #else
+    { 10, 10, 20, SYMM_ROT2, 2 },
     { 14, 14, 20, SYMM_ROT2, 0 },
-    { 14, 14, 20, SYMM_ROT2, 1 }
+    { 14, 14, 20, SYMM_ROT2, 1 },
+    { 14, 14, 20, SYMM_ROT2, 2 }
 #endif
 };
 
@@ -157,7 +217,9 @@ static int game_fetch_preset(int i, char **name, game_params **params)
     *params = ret;
 
     sprintf(buf, "%dx%d %s",
-            ret->w, ret->h, ret->recurse ? "hard" : "easy");
+            ret->w, ret->h,
+            ret->difficulty == 2 ? "hard" :
+            ret->difficulty == 1 ? "tricky" : "easy");
     *name = dupstr(buf);
 
     return TRUE;
@@ -168,7 +230,7 @@ static void free_params(game_params *params)
     sfree(params);
 }
 
-static game_params *dup_params(game_params *params)
+static game_params *dup_params(const game_params *params)
 {
     game_params *ret = snew(game_params);
     *ret = *params;		       /* structure copy */
@@ -194,30 +256,40 @@ static void decode_params(game_params *params, char const *string)
     if (*string == 's') {
         string++;
         EATNUM(params->symm);
+    } else {
+        /* cope with user input such as '18x10' by ensuring symmetry
+         * is not selected by default to be incompatible with dimensions */
+        if (params->symm == SYMM_ROT4 && params->w != params->h)
+            params->symm = SYMM_ROT2;
     }
-    params->recurse = 0;
+    params->difficulty = 0;
+    /* cope with old params */
     if (*string == 'r') {
-        params->recurse = 1;
+        params->difficulty = 2;
+        string++;
+    }
+    if (*string == 'd') {
         string++;
+        EATNUM(params->difficulty);
     }
 }
 
-static char *encode_params(game_params *params, int full)
+static char *encode_params(const game_params *params, int full)
 {
     char buf[80];
 
     if (full) {
-        sprintf(buf, "%dx%db%ds%d%s",
+        sprintf(buf, "%dx%db%ds%dd%d",
                 params->w, params->h, params->blackpc,
                 params->symm,
-                params->recurse ? "r" : "");
+                params->difficulty);
     } else {
         sprintf(buf, "%dx%d", params->w, params->h);
     }
     return dupstr(buf);
 }
 
-static config_item *game_configure(game_params *params)
+static config_item *game_configure(const game_params *params)
 {
     config_item *ret;
     char buf[80];
@@ -251,8 +323,8 @@ static config_item *game_configure(game_params *params)
 
     ret[4].name = "Difficulty";
     ret[4].type = C_CHOICES;
-    ret[4].sval = ":Easy:Hard";
-    ret[4].ival = params->recurse;
+    ret[4].sval = ":Easy:Tricky:Hard";
+    ret[4].ival = params->difficulty;
 
     ret[5].name = NULL;
     ret[5].type = C_END;
@@ -262,7 +334,7 @@ static config_item *game_configure(game_params *params)
     return ret;
 }
 
-static game_params *custom_params(config_item *cfg)
+static game_params *custom_params(const config_item *cfg)
 {
     game_params *ret = snew(game_params);
 
@@ -270,12 +342,12 @@ static game_params *custom_params(config_item *cfg)
     ret->h =       atoi(cfg[1].sval);
     ret->blackpc = atoi(cfg[2].sval);
     ret->symm =    cfg[3].ival;
-    ret->recurse = cfg[4].ival;
+    ret->difficulty = cfg[4].ival;
 
     return ret;
 }
 
-static char *validate_params(game_params *params, int full)
+static char *validate_params(const game_params *params, int full)
 {
     if (params->w < 2 || params->h < 2)
         return "Width and height must be at least 2";
@@ -287,14 +359,16 @@ static char *validate_params(game_params *params, int full)
                 return "4-fold symmetry is only available with square grids";
         }
         if (params->symm < 0 || params->symm >= SYMM_MAX)
-          return "Unknown symmetry type";
+            return "Unknown symmetry type";
+        if (params->difficulty < 0 || params->difficulty > DIFFCOUNT)
+            return "Unknown difficulty level";
     }
     return NULL;
 }
 
 /* --- Game state construction/freeing helper functions --- */
 
-static game_state *new_state(game_params *params)
+static game_state *new_state(const game_params *params)
 {
     game_state *ret = snew(game_state);
 
@@ -309,7 +383,7 @@ static game_state *new_state(game_params *params)
     return ret;
 }
 
-static game_state *dup_game(game_state *state)
+static game_state *dup_game(const game_state *state)
 {
     game_state *ret = snew(game_state);
 
@@ -336,7 +410,6 @@ static void free_game(game_state *state)
     sfree(state);
 }
 
-#ifdef DIAGNOSTICS
 static void debug_state(game_state *state)
 {
     int x, y;
@@ -356,9 +429,9 @@ static void debug_state(game_state *state)
                 else if (GRID(state, flags, x, y) & F_IMPOSSIBLE)
                     c = 'X';
             }
-            printf("%c", (int)c);
+            debug(("%c", (int)c));
         }
-        printf("     ");
+        debug(("     "));
         for (x = 0; x < state->w; x++) {
             if (GRID(state, flags, x, y) & F_BLACK)
                 c = '#';
@@ -366,13 +439,11 @@ static void debug_state(game_state *state)
                 c = (GRID(state, flags, x, y) & F_LIGHT) ? 'A' : 'a';
                 c += GRID(state, lights, x, y);
             }
-            printf("%c", (int)c);
+            debug(("%c", (int)c));
         }
-        printf("\n");
+        debug(("\n"));
     }
-    printf("\n");
 }
-#endif
 
 /* --- Game completion test routines. --- */
 
@@ -409,7 +480,7 @@ static int grid_overlap(game_state *state)
     return 0;
 }
 
-static int number_wrong(game_state *state, int x, int y)
+static int number_wrong(const game_state *state, int x, int y)
 {
     surrounds s;
     int i, n, empty, lights = GRID(state, lights, x, y);
@@ -498,7 +569,8 @@ static void clean_board(game_state *state, int leave_blacks)
     state->nlights = 0;
 }
 
-static void set_blacks(game_state *state, game_params *params, random_state *rs)
+static void set_blacks(game_state *state, const game_params *params,
+                       random_state *rs)
 {
     int x, y, degree = 0, rotate = 0, nblack;
     int rh, rw, i;
@@ -574,8 +646,8 @@ static void set_blacks(game_state *state, game_params *params, random_state *rs)
         GRID(state,flags,
              state->w/2 + wodd - 1, state->h/2 + hodd - 1) |= F_BLACK;
 
-#ifdef DIAGNOSTICS
-    debug_state(state);
+#ifdef SOLVER_DIAGNOSTICS
+    if (verbose) debug_state(state);
 #endif
 }
 
@@ -587,7 +659,6 @@ static void list_lights(game_state *state, int ox, int oy, int origin,
 {
     int x,y;
 
-    memset(lld, 0, sizeof(lld));
     lld->ox = lld->minx = lld->maxx = ox;
     lld->oy = lld->miny = lld->maxy = oy;
     lld->include_origin = origin;
@@ -679,7 +750,7 @@ static void place_lights(game_state *state, random_state *rs)
         /* If we're not lighting any lights ourself, don't remove anything. */
         n = 0;
         FOREACHLIT(&lld, if (GRID(state,flags,lx,ly) & F_LIGHT) { n += 1; } );
-        if (n == 0) continue;
+        if (n == 0) continue; /* [1] */
 
         /* Check whether removing lights we're lighting would cause anything
          * to go dark. */
@@ -697,8 +768,12 @@ static void place_lights(game_state *state, random_state *rs)
         }
         assert(grid_lit(state));
     }
-    /* if we got here, we've somehow removed all our lights and still have overlaps. */
-    assert(!"Shouldn't get here!");
+    /* could get here if the line at [1] continue'd out of the loop. */
+    if (grid_overlap(state)) {
+        debug_state(state);
+        assert(!"place_lights failed to resolve overlapping lights!");
+    }
+    sfree(numindices);
 }
 
 /* Fills in all black squares with numbers of adjacent lights. */
@@ -736,7 +811,7 @@ static int try_solve_light(game_state *state, int ox, int oy,
                            unsigned int flags, int lights)
 {
     ll_data lld;
-    int sx,sy,n = 0;
+    int sx = 0, sy = 0, n = 0;
 
     if (lights > 0) return 0;
     if (flags & F_BLACK) return 0;
@@ -749,9 +824,10 @@ static int try_solve_light(game_state *state, int ox, int oy,
     FOREACHLIT(&lld, { tsl_callback(state, lx, ly, &sx, &sy, &n); });
     if (n == 1) {
         set_light(state, sx, sy, 1);
-#ifdef SOLVE_DIAGNOSTICS
-        printf("(%d,%d) can only be lit from (%d,%d); setting to LIGHT\n",
-               ox,oy,sx,sy);
+#ifdef SOLVER_DIAGNOSTICS
+        debug(("(%d,%d) can only be lit from (%d,%d); setting to LIGHT\n",
+                ox,oy,sx,sy));
+        if (verbose) debug_state(state);
 #endif
         return 1;
     }
@@ -765,6 +841,13 @@ static int could_place_light(unsigned int flags, int lights)
     return (lights > 0) ? 0 : 1;
 }
 
+static int could_place_light_xy(game_state *state, int x, int y)
+{
+    int lights = GRID(state,lights,x,y);
+    unsigned int flags = GRID(state,flags,x,y);
+    return (could_place_light(flags, lights)) ? 1 : 0;
+}
+
 /* For a given number square, determine whether we have enough info
  * to unambiguously place its lights. */
 static int try_solve_number(game_state *state, int nx, int ny,
@@ -799,10 +882,6 @@ static int try_solve_number(game_state *state, int nx, int ny,
     if (nl == 0) {
         /* we have placed all lights we need to around here; all remaining
          * surrounds are therefore IMPOSSIBLE. */
-#ifdef SOLVE_DIAGNOSTICS
-        printf("Setting remaining surrounds to (%d,%d) IMPOSSIBLE.\n",
-               nx,ny);
-#endif
         GRID(state,flags,nx,ny) |= F_NUMBERUSED;
         for (i = 0; i < s.npoints; i++) {
             if (!(s.points[i].f & F_MARK)) {
@@ -810,12 +889,13 @@ static int try_solve_number(game_state *state, int nx, int ny,
                 ret = 1;
             }
         }
-    } else if (nl == ns) {
-        /* we have as many lights to place as spaces; fill them all. */
-#ifdef SOLVE_DIAGNOSTICS
-        printf("Setting all remaining surrounds to (%d,%d) LIGHT.\n",
+#ifdef SOLVER_DIAGNOSTICS
+        printf("Clue at (%d,%d) full; setting unlit to IMPOSSIBLE.\n",
                nx,ny);
+        if (verbose) debug_state(state);
 #endif
+    } else if (nl == ns) {
+        /* we have as many lights to place as spaces; fill them all. */
         GRID(state,flags,nx,ny) |= F_NUMBERUSED;
         for (i = 0; i < s.npoints; i++) {
             if (!(s.points[i].f & F_MARK)) {
@@ -823,24 +903,373 @@ static int try_solve_number(game_state *state, int nx, int ny,
                 ret = 1;
             }
         }
+#ifdef SOLVER_DIAGNOSTICS
+        printf("Clue at (%d,%d) trivial; setting unlit to LIGHT.\n",
+               nx,ny);
+        if (verbose) debug_state(state);
+#endif
     }
     return ret;
 }
 
+struct setscratch {
+    int x, y;
+    int n;
+};
+
+#define SCRATCHSZ (state->w+state->h)
+
+/* New solver algorithm: overlapping sets can add IMPOSSIBLE flags.
+ * Algorithm thanks to Simon:
+ *
+ * (a) Any square where you can place a light has a set of squares
+ *     which would become non-lights as a result. (This includes
+ *     squares lit by the first square, and can also include squares
+ *     adjacent to the same clue square if the new light is the last
+ *     one around that clue.) Call this MAKESDARK(x,y) with (x,y) being
+ *     the square you place a light.
+
+ * (b) Any unlit square has a set of squares on which you could place
+ *     a light to illuminate it. (Possibly including itself, of
+ *     course.) This set of squares has the property that _at least
+ *     one_ of them must contain a light. Sets of this type also arise
+ *     from clue squares. Call this MAKESLIGHT(x,y), again with (x,y)
+ *     the square you would place a light.
+
+ * (c) If there exists (dx,dy) and (lx,ly) such that MAKESDARK(dx,dy) is
+ *     a superset of MAKESLIGHT(lx,ly), this implies that placing a light at
+ *     (dx,dy) would either leave no remaining way to illuminate a certain
+ *     square, or would leave no remaining way to fulfill a certain clue
+ *     (at lx,ly). In either case, a light can be ruled out at that position.
+ *
+ * So, we construct all possible MAKESLIGHT sets, both from unlit squares
+ * and clue squares, and then we look for plausible MAKESDARK sets that include
+ * our (lx,ly) to see if we can find a (dx,dy) to rule out. By the time we have
+ * constructed the MAKESLIGHT set we don't care about (lx,ly), just the set
+ * members.
+ *
+ * Once we have such a set, Simon came up with a Cunning Plan to find
+ * the most sensible MAKESDARK candidate:
+ *
+ * (a) for each square S in your set X, find all the squares which _would_
+ *     rule it out. That means any square which would light S, plus
+ *     any square adjacent to the same clue square as S (provided
+ *     that clue square has only one remaining light to be placed).
+ *     It's not hard to make this list. Don't do anything with this
+ *     data at the moment except _count_ the squares.
+
+ * (b) Find the square S_min in the original set which has the
+ *     _smallest_ number of other squares which would rule it out.
+
+ * (c) Find all the squares that rule out S_min (it's probably
+ *     better to recompute this than to have stored it during step
+ *     (a), since the CPU requirement is modest but the storage
+ *     cost would get ugly.) For each of these squares, see if it
+ *     rules out everything else in the set X. Any which does can
+ *     be marked as not-a-light.
+ *
+ */
+
+typedef void (*trl_cb)(game_state *state, int dx, int dy,
+                       struct setscratch *scratch, int n, void *ctx);
+
+static void try_rule_out(game_state *state, int x, int y,
+                         struct setscratch *scratch, int n,
+                         trl_cb cb, void *ctx);
+
+static void trl_callback_search(game_state *state, int dx, int dy,
+                       struct setscratch *scratch, int n, void *ignored)
+{
+    int i;
+
+#ifdef SOLVER_DIAGNOSTICS
+    if (verbose) debug(("discount cb: light at (%d,%d)\n", dx, dy));
+#endif
+
+    for (i = 0; i < n; i++) {
+        if (dx == scratch[i].x && dy == scratch[i].y) {
+            scratch[i].n = 1;
+            return;
+        }
+    }
+}
+
+static void trl_callback_discount(game_state *state, int dx, int dy,
+                       struct setscratch *scratch, int n, void *ctx)
+{
+    int *didsth = (int *)ctx;
+    int i;
+
+    if (GRID(state,flags,dx,dy) & F_IMPOSSIBLE) {
+#ifdef SOLVER_DIAGNOSTICS
+        debug(("Square at (%d,%d) already impossible.\n", dx,dy));
+#endif
+        return;
+    }
+
+    /* Check whether a light at (dx,dy) rules out everything
+     * in scratch, and mark (dx,dy) as IMPOSSIBLE if it does.
+     * We can use try_rule_out for this as well, as the set of
+     * squares which would rule out (x,y) is the same as the
+     * set of squares which (x,y) would rule out. */
+
+#ifdef SOLVER_DIAGNOSTICS
+    if (verbose) debug(("Checking whether light at (%d,%d) rules out everything in scratch.\n", dx, dy));
+#endif
+
+    for (i = 0; i < n; i++)
+        scratch[i].n = 0;
+    try_rule_out(state, dx, dy, scratch, n, trl_callback_search, NULL);
+    for (i = 0; i < n; i++) {
+        if (scratch[i].n == 0) return;
+    }
+    /* The light ruled out everything in scratch. Yay. */
+    GRID(state,flags,dx,dy) |= F_IMPOSSIBLE;
+#ifdef SOLVER_DIAGNOSTICS
+    debug(("Set reduction discounted square at (%d,%d):\n", dx,dy));
+    if (verbose) debug_state(state);
+#endif
+
+    *didsth = 1;
+}
+
+static void trl_callback_incn(game_state *state, int dx, int dy,
+                       struct setscratch *scratch, int n, void *ctx)
+{
+    struct setscratch *s = (struct setscratch *)ctx;
+    s->n++;
+}
+
+static void try_rule_out(game_state *state, int x, int y,
+                         struct setscratch *scratch, int n,
+                         trl_cb cb, void *ctx)
+{
+    /* XXX Find all the squares which would rule out (x,y); anything
+     * that would light it as well as squares adjacent to same clues
+     * as X assuming that clue only has one remaining light.
+     * Call the callback with each square. */
+    ll_data lld;
+    surrounds s, ss;
+    int i, j, curr_lights, tot_lights;
+
+    /* Find all squares that would rule out a light at (x,y) and call trl_cb
+     * with them: anything that would light (x,y)... */
+
+    list_lights(state, x, y, 0, &lld);
+    FOREACHLIT(&lld, { if (could_place_light_xy(state, lx, ly)) { cb(state, lx, ly, scratch, n, ctx); } });
+
+    /* ... as well as any empty space (that isn't x,y) next to any clue square
+     * next to (x,y) that only has one light left to place. */
+
+    get_surrounds(state, x, y, &s);
+    for (i = 0; i < s.npoints; i++) {
+        if (!(GRID(state,flags,s.points[i].x,s.points[i].y) & F_NUMBERED))
+            continue;
+        /* we have an adjacent clue square; find /its/ surrounds
+         * and count the remaining lights it needs. */
+        get_surrounds(state,s.points[i].x,s.points[i].y,&ss);
+        curr_lights = 0;
+        for (j = 0; j < ss.npoints; j++) {
+            if (GRID(state,flags,ss.points[j].x,ss.points[j].y) & F_LIGHT)
+                curr_lights++;
+        }
+        tot_lights = GRID(state, lights, s.points[i].x, s.points[i].y);
+        /* We have a clue with tot_lights to fill, and curr_lights currently
+         * around it. If adding a light at (x,y) fills up the clue (i.e.
+         * curr_lights + 1 = tot_lights) then we need to discount all other
+         * unlit squares around the clue. */
+        if ((curr_lights + 1) == tot_lights) {
+            for (j = 0; j < ss.npoints; j++) {
+                int lx = ss.points[j].x, ly = ss.points[j].y;
+                if (lx == x && ly == y) continue;
+                if (could_place_light_xy(state, lx, ly))
+                    cb(state, lx, ly, scratch, n, ctx);
+            }
+        }
+    }
+}
+
+#ifdef SOLVER_DIAGNOSTICS
+static void debug_scratch(const char *msg, struct setscratch *scratch, int n)
+{
+    int i;
+    debug(("%s scratch (%d elements):\n", msg, n));
+    for (i = 0; i < n; i++) {
+        debug(("  (%d,%d) n%d\n", scratch[i].x, scratch[i].y, scratch[i].n));
+    }
+}
+#endif
+
+static int discount_set(game_state *state,
+                        struct setscratch *scratch, int n)
+{
+    int i, besti, bestn, didsth = 0;
+
+#ifdef SOLVER_DIAGNOSTICS
+    if (verbose > 1) debug_scratch("discount_set", scratch, n);
+#endif
+    if (n == 0) return 0;
+
+    for (i = 0; i < n; i++) {
+        try_rule_out(state, scratch[i].x, scratch[i].y, scratch, n,
+                     trl_callback_incn, (void*)&(scratch[i]));
+    }
+#ifdef SOLVER_DIAGNOSTICS
+    if (verbose > 1) debug_scratch("discount_set after count", scratch, n);
+#endif
+
+    besti = -1; bestn = SCRATCHSZ;
+    for (i = 0; i < n; i++) {
+        if (scratch[i].n < bestn) {
+            bestn = scratch[i].n;
+            besti = i;
+        }
+    }
+#ifdef SOLVER_DIAGNOSTICS
+    if (verbose > 1) debug(("best square (%d,%d) with n%d.\n",
+           scratch[besti].x, scratch[besti].y, scratch[besti].n));
+#endif
+    try_rule_out(state, scratch[besti].x, scratch[besti].y, scratch, n,
+                 trl_callback_discount, (void*)&didsth);
+#ifdef SOLVER_DIAGNOSTICS
+    if (didsth) debug((" [from square (%d,%d)]\n",
+                       scratch[besti].x, scratch[besti].y));
+#endif
+
+    return didsth;
+}
+
+static void discount_clear(game_state *state, struct setscratch *scratch, int *n)
+{
+    *n = 0;
+    memset(scratch, 0, SCRATCHSZ * sizeof(struct setscratch));
+}
+
+static void unlit_cb(game_state *state, int lx, int ly,
+                     struct setscratch *scratch, int *n)
+{
+    if (could_place_light_xy(state, lx, ly)) {
+        scratch[*n].x = lx; scratch[*n].y = ly; (*n)++;
+    }
+}
+
+/* Construct a MAKESLIGHT set from an unlit square. */
+static int discount_unlit(game_state *state, int x, int y,
+                          struct setscratch *scratch)
+{
+    ll_data lld;
+    int n, didsth;
+
+#ifdef SOLVER_DIAGNOSTICS
+    if (verbose) debug(("Trying to discount for unlit square at (%d,%d).\n", x, y));
+    if (verbose > 1) debug_state(state);
+#endif
+
+    discount_clear(state, scratch, &n);
+
+    list_lights(state, x, y, 1, &lld);
+    FOREACHLIT(&lld, { unlit_cb(state, lx, ly, scratch, &n); });
+    didsth = discount_set(state, scratch, n);
+#ifdef SOLVER_DIAGNOSTICS
+    if (didsth) debug(("  [from unlit square at (%d,%d)].\n", x, y));
+#endif
+    return didsth;
+
+}
+
+/* Construct a series of MAKESLIGHT sets from a clue square.
+ *  for a clue square with N remaining spaces that must contain M lights, every
+ *  subset of size N-M+1 of those N spaces forms such a set.
+ */
+
+static int discount_clue(game_state *state, int x, int y,
+                          struct setscratch *scratch)
+{
+    int slen, m = GRID(state, lights, x, y), n, i, didsth = 0, lights;
+    unsigned int flags;
+    surrounds s, sempty;
+    combi_ctx *combi;
+
+    if (m == 0) return 0;
+
+#ifdef SOLVER_DIAGNOSTICS
+    if (verbose) debug(("Trying to discount for sets at clue (%d,%d).\n", x, y));
+    if (verbose > 1) debug_state(state);
+#endif
+
+    /* m is no. of lights still to place; starts off at the clue value
+     * and decreases when we find a light already down.
+     * n is no. of spaces left; starts off at 0 and goes up when we find
+     * a plausible space. */
+
+    get_surrounds(state, x, y, &s);
+    memset(&sempty, 0, sizeof(surrounds));
+    for (i = 0; i < s.npoints; i++) {
+        int lx = s.points[i].x, ly = s.points[i].y;
+        flags = GRID(state,flags,lx,ly);
+        lights = GRID(state,lights,lx,ly);
+
+        if (flags & F_LIGHT) m--;
+
+        if (could_place_light(flags, lights)) {
+            sempty.points[sempty.npoints].x = lx;
+            sempty.points[sempty.npoints].y = ly;
+            sempty.npoints++;
+        }
+    }
+    n = sempty.npoints; /* sempty is now a surrounds of only blank squares. */
+    if (n == 0) return 0; /* clue is full already. */
+
+    if (m < 0 || m > n) return 0; /* become impossible. */
+
+    combi = new_combi(n - m + 1, n);
+    while (next_combi(combi)) {
+        discount_clear(state, scratch, &slen);
+        for (i = 0; i < combi->r; i++) {
+            scratch[slen].x = sempty.points[combi->a[i]].x;
+            scratch[slen].y = sempty.points[combi->a[i]].y;
+            slen++;
+        }
+        if (discount_set(state, scratch, slen)) didsth = 1;
+    }
+    free_combi(combi);
+#ifdef SOLVER_DIAGNOSTICS
+    if (didsth) debug(("  [from clue at (%d,%d)].\n", x, y));
+#endif
+    return didsth;
+}
+
+#define F_SOLVE_FORCEUNIQUE     1
+#define F_SOLVE_DISCOUNTSETS    2
+#define F_SOLVE_ALLOWRECURSE    4
+
+static unsigned int flags_from_difficulty(int difficulty)
+{
+    unsigned int sflags = F_SOLVE_FORCEUNIQUE;
+    assert(difficulty <= DIFFCOUNT);
+    if (difficulty >= 1) sflags |= F_SOLVE_DISCOUNTSETS;
+    if (difficulty >= 2) sflags |= F_SOLVE_ALLOWRECURSE;
+    return sflags;
+}
+
+#define MAXRECURSE 5
+
 static int solve_sub(game_state *state,
-                     int forceunique, int maxrecurse, int depth,
+                     unsigned int solve_flags, int depth,
                      int *maxdepth)
 {
     unsigned int flags;
     int x, y, didstuff, ncanplace, lights;
-    int bestx, besty, n, bestn, copy_soluble, self_soluble, ret;
+    int bestx, besty, n, bestn, copy_soluble, self_soluble, ret, maxrecurse = 0;
     game_state *scopy;
     ll_data lld;
+    struct setscratch *sscratch = NULL;
 
-#ifdef SOLVE_DIAGNOSTICS
+#ifdef SOLVER_DIAGNOSTICS
     printf("solve_sub: depth = %d\n", depth);
 #endif
     if (maxdepth && *maxdepth < depth) *maxdepth = depth;
+    if (solve_flags & F_SOLVE_ALLOWRECURSE) maxrecurse = MAXRECURSE;
 
     while (1) {
         if (grid_overlap(state)) {
@@ -848,10 +1277,10 @@ static int solve_sub(game_state *state,
              * (assuming a soluble grid). However, if we're trying to solve
              * from a half-completed *incorrect* grid this might occur; we
              * just return the 'no solutions' code in this case. */
-            return 0;
+            ret = 0; goto done;
         }
 
-        if (grid_correct(state)) return 1;
+        if (grid_correct(state)) { ret = 1; goto done; }
 
         ncanplace = 0;
         didstuff = 0;
@@ -868,12 +1297,42 @@ static int solve_sub(game_state *state,
             }
         }
         if (didstuff) continue;
-        if (!ncanplace) return 0; /* nowhere to put a light, puzzle in unsoluble. */
+        if (!ncanplace) {
+            /* nowhere to put a light, puzzle is unsoluble. */
+            ret = 0; goto done;
+        }
+
+        if (solve_flags & F_SOLVE_DISCOUNTSETS) {
+            if (!sscratch) sscratch = snewn(SCRATCHSZ, struct setscratch);
+            /* Try a more cunning (and more involved) way... more details above. */
+            for (x = 0; x < state->w; x++) {
+                for (y = 0; y < state->h; y++) {
+                    flags = GRID(state,flags,x,y);
+                    lights = GRID(state,lights,x,y);
+
+                    if (!(flags & F_BLACK) && lights == 0) {
+                        if (discount_unlit(state, x, y, sscratch)) {
+                            didstuff = 1;
+                            goto reduction_success;
+                        }
+                    } else if (flags & F_NUMBERED) {
+                        if (discount_clue(state, x, y, sscratch)) {
+                            didstuff = 1;
+                            goto reduction_success;
+                        }
+                    }
+                }
+            }
+        }
+reduction_success:
+        if (didstuff) continue;
 
         /* We now have to make a guess; we have places to put lights but
          * no definite idea about where they can go. */
-        if (depth >= maxrecurse) return -1; /* mustn't delve any deeper. */
-
+        if (depth >= maxrecurse) {
+            /* mustn't delve any deeper. */
+            ret = -1; goto done;
+        }
         /* Of all the squares that we could place a light, pick the one
          * that would light the most currently unlit squares. */
         /* This heuristic was just plucked from the air; there may well be
@@ -902,25 +1361,30 @@ static int solve_sub(game_state *state,
          * and once as 'impossible'; we need to make one copy to do this. */
 
         scopy = dup_game(state);
+#ifdef SOLVER_DIAGNOSTICS
+        debug(("Recursing #1: trying (%d,%d) as IMPOSSIBLE\n", bestx, besty));
+#endif
         GRID(state,flags,bestx,besty) |= F_IMPOSSIBLE;
-        self_soluble = solve_sub(state, forceunique, maxrecurse,
-                                 depth+1, maxdepth);
+        self_soluble = solve_sub(state, solve_flags,  depth+1, maxdepth);
 
-        if (!forceunique && self_soluble > 0) {
+        if (!(solve_flags & F_SOLVE_FORCEUNIQUE) && self_soluble > 0) {
             /* we didn't care about finding all solutions, and we just
              * found one; return with it immediately. */
             free_game(scopy);
-            return self_soluble;
+            ret = self_soluble;
+            goto done;
         }
 
+#ifdef SOLVER_DIAGNOSTICS
+        debug(("Recursing #2: trying (%d,%d) as LIGHT\n", bestx, besty));
+#endif
         set_light(scopy, bestx, besty, 1);
-        copy_soluble = solve_sub(scopy, forceunique, maxrecurse,
-                                 depth+1, maxdepth);
+        copy_soluble = solve_sub(scopy, solve_flags, depth+1, maxdepth);
 
         /* If we wanted a unique solution but we hit our recursion limit
          * (on either branch) then we have to assume we didn't find possible
          * extra solutions, and return 'not soluble'. */
-        if (forceunique &&
+        if ((solve_flags & F_SOLVE_FORCEUNIQUE) &&
             ((copy_soluble < 0) || (self_soluble < 0))) {
             ret = -1;
         /* Make sure that whether or not it was self or copy (or both) that
@@ -940,17 +1404,25 @@ static int solve_sub(game_state *state,
             ret = copy_soluble + self_soluble;
         }
         free_game(scopy);
-        return ret;
+        goto done;
     }
+done:
+    if (sscratch) sfree(sscratch);
+#ifdef SOLVER_DIAGNOSTICS
+    if (ret < 0)
+        debug(("solve_sub: depth = %d returning, ran out of recursion.\n",
+               depth));
+    else
+        debug(("solve_sub: depth = %d returning, %d solutions.\n",
+               depth, ret));
+#endif
+    return ret;
 }
 
-#define MAXRECURSE 5
-
 /* Fills in the (possibly partially-complete) game_state as far as it can,
  * returning the number of possible solutions. If it returns >0 then the
  * game_state will be in a solved state, but you won't know which one. */
-static int dosolve(game_state *state,
-                   int allowguess, int forceunique, int *maxdepth)
+static int dosolve(game_state *state, int solve_flags, int *maxdepth)
 {
     int x, y, nsol;
 
@@ -959,8 +1431,7 @@ static int dosolve(game_state *state,
             GRID(state,flags,x,y) &= ~F_NUMBERUSED;
         }
     }
-    nsol = solve_sub(state, forceunique,
-                     allowguess ? MAXRECURSE : 0, 0, maxdepth);
+    nsol = solve_sub(state, solve_flags, 0, maxdepth);
     return nsol;
 }
 
@@ -977,6 +1448,7 @@ static int strip_unused_nums(game_state *state)
             }
         }
     }
+    debug(("Stripped %d unused numbers.\n", n));
     return n;
 }
 
@@ -993,29 +1465,27 @@ static void unplace_lights(game_state *state)
     }
 }
 
-static int puzzle_is_good(game_state *state, game_params *params, int *mdepth)
+static int puzzle_is_good(game_state *state, int difficulty)
 {
-    int nsol;
+    int nsol, mdepth = 0;
+    unsigned int sflags = flags_from_difficulty(difficulty);
 
-    *mdepth = 0;
     unplace_lights(state);
 
-#ifdef DIAGNOSTICS
-    debug_state(state);
+#ifdef SOLVER_DIAGNOSTICS
+    debug(("Trying to solve with difficulty %d (0x%x):\n",
+           difficulty, sflags));
+    if (verbose) debug_state(state);
 #endif
 
-    nsol = dosolve(state, params->recurse, TRUE, mdepth);
+    nsol = dosolve(state, sflags, &mdepth);
     /* if we wanted an easy puzzle, make sure we didn't need recursion. */
-    if (!params->recurse && *mdepth > 0) {
-#ifdef DIAGNOSTICS
-        printf("Ignoring recursive puzzle.\n");
-#endif
+    if (!(sflags & F_SOLVE_ALLOWRECURSE) && mdepth > 0) {
+        debug(("Ignoring recursive puzzle.\n"));
         return 0;
     }
 
-#ifdef DIAGNOSTICS
-    printf("%d solutions found.\n", nsol);
-#endif
+    debug(("%d solutions found.\n", nsol));
     if (nsol <= 0) return 0;
     if (nsol > 1) return 0;
     return 1;
@@ -1048,11 +1518,13 @@ static int puzzle_is_good(game_state *state, game_params *params, int *mdepth)
 
 #define MAX_GRIDGEN_TRIES 20
 
-static char *new_game_desc(game_params *params, random_state *rs,
+static char *new_game_desc(const game_params *params_in, random_state *rs,
 			   char **aux, int interactive)
 {
+    game_params params_copy = *params_in; /* structure copy */
+    game_params *params = &params_copy;
     game_state *news = new_state(params), *copys;
-    int nsol, i, run, x, y, wh = params->w*params->h, num, mdepth;
+    int i, j, run, x, y, wh = params->w*params->h, num;
     char *ret, *p;
     int *numindices;
 
@@ -1060,7 +1532,7 @@ static char *new_game_desc(game_params *params, random_state *rs,
      * do this once, because if it gets used more than once it'll
      * be on a different grid layout. */
     numindices = snewn(wh, int);
-    for (i = 0; i < wh; i++) numindices[i] = i;
+    for (j = 0; j < wh; j++) numindices[j] = j;
     shuffle(numindices, wh, sizeof(*numindices), rs);
 
     while (1) {
@@ -1071,14 +1543,13 @@ static char *new_game_desc(game_params *params, random_state *rs,
             place_lights(news, rs);
             debug(("Generating initial grid.\n"));
             place_numbers(news);
-            if (!puzzle_is_good(news, params, &mdepth)) continue;
+            if (!puzzle_is_good(news, params->difficulty)) continue;
 
             /* Take a copy, remove numbers we didn't use and check there's
              * still a unique solution; if so, use the copy subsequently. */
             copys = dup_game(news);
-            nsol = strip_unused_nums(copys);
-            debug(("Stripped %d unused numbers.\n", nsol));
-            if (!puzzle_is_good(copys, params, &mdepth)) {
+            strip_unused_nums(copys);
+            if (!puzzle_is_good(copys, params->difficulty)) {
                 debug(("Stripped grid is not good, reverting.\n"));
                 free_game(copys);
             } else {
@@ -1088,25 +1559,26 @@ static char *new_game_desc(game_params *params, random_state *rs,
 
             /* Go through grid removing numbers at random one-by-one and
              * trying to solve again; if it ceases to be good put the number back. */
-            for (i = 0; i < wh; i++) {
-                y = numindices[i] / params->w;
-                x = numindices[i] % params->w;
+            for (j = 0; j < wh; j++) {
+                y = numindices[j] / params->w;
+                x = numindices[j] % params->w;
                 if (!(GRID(news, flags, x, y) & F_NUMBERED)) continue;
                 num = GRID(news, lights, x, y);
                 GRID(news, lights, x, y) = 0;
                 GRID(news, flags, x, y) &= ~F_NUMBERED;
-                if (!puzzle_is_good(news, params, &mdepth)) {
+                if (!puzzle_is_good(news, params->difficulty)) {
                     GRID(news, lights, x, y) = num;
                     GRID(news, flags, x, y) |= F_NUMBERED;
                 } else
                     debug(("Removed (%d,%d) still soluble.\n", x, y));
             }
-	    /* Get a good value of mdepth for the following test */
-	    i = puzzle_is_good(news, params, &mdepth);
-	    assert(i);
-            if (params->recurse && mdepth == 0) {
-                debug(("Maximum-difficulty puzzle still not recursive, skipping.\n"));
-                continue;
+            if (params->difficulty > 0) {
+                /* Was the maximally-difficult puzzle difficult enough?
+                 * Check we can't solve it with a more simplistic solver. */
+                if (puzzle_is_good(news, params->difficulty-1)) {
+                    debug(("Maximally-hard puzzle still not hard enough, skipping.\n"));
+                    continue;
+                }
             }
 
             goto goodpuzzle;
@@ -1115,9 +1587,7 @@ static char *new_game_desc(game_params *params, random_state *rs,
          * %age of black squares (if we didn't already have lots; in which case
          * why couldn't we generate a puzzle?) and try again. */
         if (params->blackpc < 90) params->blackpc += 5;
-#ifdef DIAGNOSTICS
-        printf("New black layout %d%%.\n", params->blackpc);
-#endif
+        debug(("New black layout %d%%.\n", params->blackpc));
     }
 goodpuzzle:
     /* Game is encoded as a long string one character per square;
@@ -1159,7 +1629,7 @@ goodpuzzle:
     return ret;
 }
 
-static char *validate_desc(game_params *params, char *desc)
+static char *validate_desc(const game_params *params, const char *desc)
 {
     int i;
     for (i = 0; i < params->w*params->h; i++) {
@@ -1181,7 +1651,8 @@ 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, const game_params *params,
+                            const char *desc)
 {
     game_state *ret = new_state(params);
     int x,y;
@@ -1228,27 +1699,29 @@ static game_state *new_game(midend_data *me, game_params *params, char *desc)
     return ret;
 }
 
-static char *solve_game(game_state *state, game_state *currstate,
-			char *aux, char **error)
+static char *solve_game(const game_state *state, const game_state *currstate,
+                        const char *aux, char **error)
 {
     game_state *solved;
     char *move = NULL, buf[80];
     int movelen, movesize, x, y, len;
-    unsigned int oldflags, solvedflags;
+    unsigned int oldflags, solvedflags, sflags;
 
     /* We don't care here about non-unique puzzles; if the
      * user entered one themself then I doubt they care. */
 
+    sflags = F_SOLVE_ALLOWRECURSE | F_SOLVE_DISCOUNTSETS;
+
     /* Try and solve from where we are now (for non-unique
      * puzzles this may produce a different answer). */
     solved = dup_game(currstate);
-    if (dosolve(solved, 1, 0, NULL) > 0) goto solved;
+    if (dosolve(solved, sflags, NULL) > 0) goto solved;
     free_game(solved);
 
     /* That didn't work; try solving from the clean puzzle. */
     solved = dup_game(state);
-    if (dosolve(solved, 1, 0, NULL) > 0) goto solved;
-    *error = "Puzzle is not self-consistent.";
+    if (dosolve(solved, sflags, NULL) > 0) goto solved;
+    *error = "Unable to find a solution to this puzzle.";
     goto done;
 
 solved:
@@ -1282,11 +1755,16 @@ done:
     return move;
 }
 
+static int game_can_format_as_text_now(const game_params *params)
+{
+    return TRUE;
+}
+
 /* 'borrowed' from slant.c, mainly. I could have printed it one
  * character per cell (like debug_state) but that comes out tiny.
  * 'L' is used for 'light here' because 'O' looks too much like '0'
  * (black square with no surrounding lights). */
-static char *game_text_format(game_state *state)
+static char *game_text_format(const game_state *state)
 {
     int w = state->w, h = state->h, W = w+1, H = h+1;
     int x, y, len, lights;
@@ -1341,7 +1819,7 @@ struct game_ui {
     int cur_x, cur_y, cur_visible;
 };
 
-static game_ui *new_ui(game_state *state)
+static game_ui *new_ui(const game_state *state)
 {
     game_ui *ui = snew(game_ui);
     ui->cur_x = ui->cur_y = ui->cur_visible = 0;
@@ -1353,19 +1831,19 @@ static void free_ui(game_ui *ui)
     sfree(ui);
 }
 
-static char *encode_ui(game_ui *ui)
+static char *encode_ui(const game_ui *ui)
 {
     /* nothing to encode. */
     return NULL;
 }
 
-static void decode_ui(game_ui *ui, char *encoding)
+static void decode_ui(game_ui *ui, const char *encoding)
 {
     /* nothing to decode. */
 }
 
-static void game_changed_state(game_ui *ui, game_state *oldstate,
-                               game_state *newstate)
+static void game_changed_state(game_ui *ui, const game_state *oldstate,
+                               const game_state *newstate)
 {
     if (newstate->completed)
         ui->cur_visible = 0;
@@ -1397,48 +1875,40 @@ struct game_drawstate {
             (pc)) -1 (nil)
         (nil))
  */
-static char *interpret_move(game_state *state, game_ui *ui, game_drawstate *ds,
-			    int x, int y, int button)
+static char *interpret_move(const game_state *state, game_ui *ui,
+                            const game_drawstate *ds,
+                            int x, int y, int button)
 {
     enum { NONE, FLIP_LIGHT, FLIP_IMPOSSIBLE } action = NONE;
-    int cx = -1, cy = -1, cv = ui->cur_visible;
+    int cx = -1, cy = -1;
     unsigned int flags;
-    char buf[80], *nullret, *empty = "", c;
+    char buf[80], *nullret = NULL, *empty = "", c;
 
     if (button == LEFT_BUTTON || button == RIGHT_BUTTON) {
+        if (ui->cur_visible)
+            nullret = empty;
         ui->cur_visible = 0;
         cx = FROMCOORD(x);
         cy = FROMCOORD(y);
         action = (button == LEFT_BUTTON) ? FLIP_LIGHT : FLIP_IMPOSSIBLE;
-    } else if (button == CURSOR_SELECT ||
+    } else if (IS_CURSOR_SELECT(button) ||
                button == 'i' || button == 'I' ||
                button == ' ' || button == '\r' || button == '\n') {
-        ui->cur_visible = 1;
-        cx = ui->cur_x;
-        cy = ui->cur_y;
-        action = (button == 'i' || button == 'I') ?
-            FLIP_IMPOSSIBLE : FLIP_LIGHT;
-    } else if (button == CURSOR_UP || button == CURSOR_DOWN ||
-               button == CURSOR_RIGHT || button == CURSOR_LEFT) {
-        int dx = 0, dy = 0;
-        switch (button) {
-        case CURSOR_UP:         dy = -1; break;
-        case CURSOR_DOWN:       dy = 1; break;
-        case CURSOR_RIGHT:      dx = 1; break;
-        case CURSOR_LEFT:       dx = -1; break;
-        default: assert(!"shouldn't get here");
+        if (ui->cur_visible) {
+            /* Only allow cursor-effect operations if the cursor is visible
+             * (otherwise you have no idea which square it might be affecting) */
+            cx = ui->cur_x;
+            cy = ui->cur_y;
+            action = (button == 'i' || button == 'I' || button == CURSOR_SELECT2) ?
+                FLIP_IMPOSSIBLE : FLIP_LIGHT;
         }
-        ui->cur_x += dx; ui->cur_y += dy;
-        ui->cur_x = min(max(ui->cur_x, 0), state->w - 1);
-        ui->cur_y = min(max(ui->cur_y, 0), state->h - 1);
         ui->cur_visible = 1;
-    }
-
-    /* Always redraw if the cursor is on, or if it's just been
-     * removed. */
-    if (ui->cur_visible) nullret = empty;
-    else if (cv) nullret = empty;
-    else nullret = NULL;
+    } else if (IS_CURSOR_MOVE(button)) {
+        move_cursor(button, &ui->cur_x, &ui->cur_y, state->w, state->h, 0);
+        ui->cur_visible = 1;
+        nullret = empty;
+    } else
+        return NULL;
 
     switch (action) {
     case FLIP_LIGHT:
@@ -1449,11 +1919,19 @@ static char *interpret_move(game_state *state, game_ui *ui, game_drawstate *ds,
         if (flags & F_BLACK)
             return nullret;
         if (action == FLIP_LIGHT) {
+#ifdef STYLUS_BASED
+            if (flags & F_IMPOSSIBLE || flags & F_LIGHT) c = 'I'; else c = 'L';
+#else
             if (flags & F_IMPOSSIBLE) return nullret;
             c = 'L';
+#endif
         } else {
+#ifdef STYLUS_BASED
+            if (flags & F_IMPOSSIBLE || flags & F_LIGHT) c = 'L'; else c = 'I';
+#else
             if (flags & F_LIGHT) return nullret;
             c = 'I';
+#endif
         }
         sprintf(buf, "%c%d,%d", (int)c, cx, cy);
         break;
@@ -1467,7 +1945,7 @@ static char *interpret_move(game_state *state, game_ui *ui, game_drawstate *ds,
     return dupstr(buf);
 }
 
-static game_state *execute_move(game_state *state, char *move)
+static game_state *execute_move(const game_state *state, const char *move)
 {
     game_state *ret = dup_game(state);
     int x, y, n, flags;
@@ -1517,8 +1995,8 @@ badmove:
  */
 
 /* XXX entirely cloned from fifteen.c; separate out? */
-static void game_compute_size(game_params *params, int tilesize,
-			      int *x, int *y)
+static void game_compute_size(const game_params *params, int tilesize,
+                              int *x, int *y)
 {
     /* Ick: fake up `ds->tilesize' for macro expansion purposes */
     struct { int tilesize; } ads, *ds = &ads;
@@ -1528,14 +2006,14 @@ static void game_compute_size(game_params *params, int tilesize,
     *y = TILE_SIZE * params->h + 2 * BORDER;
 }
 
-static void game_set_size(game_drawstate *ds, game_params *params,
-			  int tilesize)
+static void game_set_size(drawing *dr, game_drawstate *ds,
+                          const game_params *params, int tilesize)
 {
     ds->tilesize = tilesize;
     ds->crad = 3*(tilesize-1)/8;
 }
 
-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);
     int i;
@@ -1562,7 +2040,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, const game_state *state)
 {
     struct game_drawstate *ds = snew(struct game_drawstate);
     int i;
@@ -1579,7 +2057,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->flags);
     sfree(ds);
@@ -1592,15 +2070,15 @@ static void game_free_drawstate(game_drawstate *ds)
 #define HINT_OVERLAPS
 #define HINT_NUMBERS
 
-static unsigned int tile_flags(game_drawstate *ds, game_state *state, game_ui *ui,
-                               int x, int y, int flashing)
+static unsigned int tile_flags(game_drawstate *ds, const game_state *state,
+                               const game_ui *ui, int x, int y, int flashing)
 {
     unsigned int flags = GRID(state, flags, x, y);
     int lights = GRID(state, lights, x, y);
     unsigned int ret = 0;
 
     if (flashing) ret |= DF_FLASH;
-    if (ui->cur_visible && x == ui->cur_x && y == ui->cur_y)
+    if (ui && ui->cur_visible && x == ui->cur_x && y == ui->cur_y)
         ret |= DF_CURSOR;
 
     if (flags & F_BLACK) {
@@ -1627,54 +2105,64 @@ static unsigned int tile_flags(game_drawstate *ds, game_state *state, game_ui *u
     return ret;
 }
 
-static void tile_redraw(frontend *fe, game_drawstate *ds, game_state *state,
-                        int x, int y)
+static void tile_redraw(drawing *dr, game_drawstate *ds,
+                        const game_state *state, int x, int y)
 {
     unsigned int ds_flags = GRID(ds, flags, x, y);
     int dx = COORD(x), dy = COORD(y);
     int lit = (ds_flags & DF_FLASH) ? COL_GRID : COL_LIT;
 
     if (ds_flags & DF_BLACK) {
-        draw_rect(fe, dx, dy, TILE_SIZE, TILE_SIZE, COL_BLACK);
+        draw_rect(dr, dx, dy, TILE_SIZE, TILE_SIZE, COL_BLACK);
         if (ds_flags & DF_NUMBERED) {
             int ccol = (ds_flags & DF_NUMBERWRONG) ? COL_ERROR : COL_LIGHT;
-            char str[10];
+            char str[32];
 
             /* We know that this won't change over the course of the game
              * so it's OK to ignore this when calculating whether or not
              * to redraw the tile. */
             sprintf(str, "%d", GRID(state, lights, x, y));
-            draw_text(fe, dx + TILE_SIZE/2, dy + TILE_SIZE/2,
+            draw_text(dr, dx + TILE_SIZE/2, dy + TILE_SIZE/2,
                       FONT_VARIABLE, TILE_SIZE*3/5,
 		      ALIGN_VCENTRE | ALIGN_HCENTRE, ccol, str);
         }
     } else {
-        draw_rect(fe, dx, dy, TILE_SIZE, TILE_SIZE,
+        draw_rect(dr, dx, dy, TILE_SIZE, TILE_SIZE,
                   (ds_flags & DF_LIT) ? lit : COL_BACKGROUND);
-        draw_rect_outline(fe, dx, dy, TILE_SIZE, TILE_SIZE, COL_GRID);
+        draw_rect_outline(dr, dx, dy, TILE_SIZE, TILE_SIZE, COL_GRID);
         if (ds_flags & DF_LIGHT) {
             int lcol = (ds_flags & DF_OVERLAP) ? COL_ERROR : COL_LIGHT;
-            draw_circle(fe, dx + TILE_SIZE/2, dy + TILE_SIZE/2, TILE_RADIUS,
+            draw_circle(dr, dx + TILE_SIZE/2, dy + TILE_SIZE/2, TILE_RADIUS,
                         lcol, COL_BLACK);
-        } else if (ds_flags & DF_IMPOSSIBLE) {
-            int rlen = TILE_SIZE / 4;
-            draw_rect(fe, dx + TILE_SIZE/2 - rlen/2, dy + TILE_SIZE/2 - rlen/2,
-                      rlen, rlen, COL_BLACK);
+        } else if ((ds_flags & DF_IMPOSSIBLE)) {
+            static int draw_blobs_when_lit = -1;
+            if (draw_blobs_when_lit < 0) {
+		char *env = getenv("LIGHTUP_LIT_BLOBS");
+		draw_blobs_when_lit = (!env || (env[0] == 'y' ||
+                                                env[0] == 'Y'));
+            }
+            if (!(ds_flags & DF_LIT) || draw_blobs_when_lit) {
+                int rlen = TILE_SIZE / 4;
+                draw_rect(dr, dx + TILE_SIZE/2 - rlen/2,
+                          dy + TILE_SIZE/2 - rlen/2,
+                          rlen, rlen, COL_BLACK);
+            }
         }
     }
 
     if (ds_flags & DF_CURSOR) {
         int coff = TILE_SIZE/8;
-        draw_rect_outline(fe, dx + coff, dy + coff,
+        draw_rect_outline(dr, dx + coff, dy + coff,
                           TILE_SIZE - coff*2, TILE_SIZE - coff*2, COL_CURSOR);
     }
 
-    draw_update(fe, dx, dy, TILE_SIZE, TILE_SIZE);
+    draw_update(dr, dx, dy, TILE_SIZE, TILE_SIZE);
 }
 
-static void game_redraw(frontend *fe, game_drawstate *ds, game_state *oldstate,
-			game_state *state, int dir, game_ui *ui,
-			float animtime, float flashtime)
+static void game_redraw(drawing *dr, game_drawstate *ds,
+                        const game_state *oldstate, const game_state *state,
+                        int dir, const game_ui *ui,
+                        float animtime, float flashtime)
 {
     int flashing = FALSE;
     int x,y;
@@ -1682,16 +2170,16 @@ static void game_redraw(frontend *fe, game_drawstate *ds, game_state *oldstate,
     if (flashtime) flashing = (int)(flashtime * 3 / FLASH_TIME) != 1;
 
     if (!ds->started) {
-        draw_rect(fe, 0, 0,
+        draw_rect(dr, 0, 0,
                   TILE_SIZE * ds->w + 2 * BORDER,
                   TILE_SIZE * ds->h + 2 * BORDER, COL_BACKGROUND);
 
-        draw_rect_outline(fe, COORD(0)-1, COORD(0)-1,
+        draw_rect_outline(dr, COORD(0)-1, COORD(0)-1,
                           TILE_SIZE * ds->w + 2,
                           TILE_SIZE * ds->h + 2,
                           COL_GRID);
 
-        draw_update(fe, 0, 0,
+        draw_update(dr, 0, 0,
                     TILE_SIZE * ds->w + 2 * BORDER,
                     TILE_SIZE * ds->h + 2 * BORDER);
         ds->started = 1;
@@ -1702,20 +2190,20 @@ static void game_redraw(frontend *fe, game_drawstate *ds, game_state *oldstate,
             unsigned int ds_flags = tile_flags(ds, state, ui, x, y, flashing);
             if (ds_flags != GRID(ds, flags, x, y)) {
                 GRID(ds, flags, x, y) = ds_flags;
-                tile_redraw(fe, ds, state, x, y);
+                tile_redraw(dr, ds, state, x, y);
             }
         }
     }
 }
 
-static float game_anim_length(game_state *oldstate, game_state *newstate,
-			      int dir, game_ui *ui)
+static float game_anim_length(const game_state *oldstate,
+                              const game_state *newstate, int dir, game_ui *ui)
 {
     return 0.0F;
 }
 
-static float game_flash_length(game_state *oldstate, game_state *newstate,
-			       int dir, game_ui *ui)
+static float game_flash_length(const game_state *oldstate,
+                               const game_state *newstate, int dir, game_ui *ui)
 {
     if (!oldstate->completed && newstate->completed &&
         !oldstate->used_solve && !newstate->used_solve)
@@ -1723,22 +2211,84 @@ static float game_flash_length(game_state *oldstate, game_state *newstate,
     return 0.0F;
 }
 
-static int game_wants_statusbar(void)
+static int game_status(const game_state *state)
 {
-    return FALSE;
+    return state->completed ? +1 : 0;
 }
 
-static int game_timing_state(game_state *state, game_ui *ui)
+static int game_timing_state(const game_state *state, game_ui *ui)
 {
     return TRUE;
 }
 
+static void game_print_size(const game_params *params, float *x, float *y)
+{
+    int pw, ph;
+
+    /*
+     * I'll use 6mm squares by default.
+     */
+    game_compute_size(params, 600, &pw, &ph);
+    *x = pw / 100.0F;
+    *y = ph / 100.0F;
+}
+
+static void game_print(drawing *dr, const game_state *state, int tilesize)
+{
+    int w = state->w, h = state->h;
+    int ink = print_mono_colour(dr, 0);
+    int paper = print_mono_colour(dr, 1);
+    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, TILE_SIZE / 16);
+    draw_rect_outline(dr, COORD(0), COORD(0),
+		      TILE_SIZE * w, TILE_SIZE * h, ink);
+
+    /*
+     * Grid.
+     */
+    print_line_width(dr, TILE_SIZE / 24);
+    for (x = 1; x < w; x++)
+	draw_line(dr, COORD(x), COORD(0), COORD(x), COORD(h), ink);
+    for (y = 1; y < h; y++)
+	draw_line(dr, COORD(0), COORD(y), COORD(w), COORD(y), ink);
+
+    /*
+     * Grid contents.
+     */
+    for (y = 0; y < h; y++)
+	for (x = 0; x < w; x++) {
+            unsigned int ds_flags = tile_flags(ds, state, NULL, x, y, FALSE);
+	    int dx = COORD(x), dy = COORD(y);
+	    if (ds_flags & DF_BLACK) {
+		draw_rect(dr, dx, dy, TILE_SIZE, TILE_SIZE, ink);
+		if (ds_flags & DF_NUMBERED) {
+		    char str[32];
+		    sprintf(str, "%d", GRID(state, lights, x, y));
+		    draw_text(dr, dx + TILE_SIZE/2, dy + TILE_SIZE/2,
+			      FONT_VARIABLE, TILE_SIZE*3/5,
+			      ALIGN_VCENTRE | ALIGN_HCENTRE, paper, str);
+		}
+	    } else if (ds_flags & DF_LIGHT) {
+		draw_circle(dr, dx + TILE_SIZE/2, dy + TILE_SIZE/2,
+			    TILE_RADIUS, -1, ink);
+	    }
+	}
+}
+
 #ifdef COMBINED
 #define thegame lightup
 #endif
 
 const struct game thegame = {
-    "Light Up", "games.lightup",
+    "Light Up", "games.lightup", "lightup",
     default_params,
     game_fetch_preset,
     decode_params,
@@ -1753,7 +2303,7 @@ const struct game thegame = {
     dup_game,
     free_game,
     TRUE, solve_game,
-    TRUE, game_text_format,
+    TRUE, game_can_format_as_text_now, game_text_format,
     new_ui,
     free_ui,
     encode_ui,
@@ -1768,9 +2318,88 @@ const struct game thegame = {
     game_redraw,
     game_anim_length,
     game_flash_length,
-    game_wants_statusbar,
+    game_status,
+    TRUE, FALSE, game_print_size, game_print,
+    FALSE,			       /* wants_statusbar */
     FALSE, game_timing_state,
-    0,				       /* mouse_priorities */
+    0,				       /* flags */
 };
 
+#ifdef STANDALONE_SOLVER
+
+int main(int argc, char **argv)
+{
+    game_params *p;
+    game_state *s;
+    char *id = NULL, *desc, *err, *result;
+    int nsol, diff, really_verbose = 0;
+    unsigned int sflags;
+
+    while (--argc > 0) {
+        char *p = *++argv;
+        if (!strcmp(p, "-v")) {
+            really_verbose++;
+        } else if (*p == '-') {
+            fprintf(stderr, "%s: unrecognised option `%s'\n", argv[0], p);
+            return 1;
+        } else {
+            id = p;
+        }
+    }
+
+    if (!id) {
+        fprintf(stderr, "usage: %s [-v] <game_id>\n", argv[0]);
+        return 1;
+    }
+
+    desc = strchr(id, ':');
+    if (!desc) {
+        fprintf(stderr, "%s: game id expects a colon in it\n", argv[0]);
+        return 1;
+    }
+    *desc++ = '\0';
+
+    p = default_params();
+    decode_params(p, id);
+    err = validate_desc(p, desc);
+    if (err) {
+        fprintf(stderr, "%s: %s\n", argv[0], err);
+        return 1;
+    }
+    s = new_game(NULL, p, desc);
+
+    /* Run the solvers easiest to hardest until we find one that
+     * can solve our puzzle. If it's soluble we know that the
+     * hardest (recursive) solver will always find the solution. */
+    nsol = sflags = 0;
+    for (diff = 0; diff <= DIFFCOUNT; diff++) {
+        printf("\nSolving with difficulty %d.\n", diff);
+        sflags = flags_from_difficulty(diff);
+        unplace_lights(s);
+        nsol = dosolve(s, sflags, NULL);
+        if (nsol == 1) break;
+    }
+
+    printf("\n");
+    if (nsol == 0) {
+        printf("Puzzle has no solution.\n");
+    } else if (nsol < 0) {
+        printf("Unable to find a unique solution.\n");
+    } else if (nsol > 1) {
+        printf("Puzzle has multiple solutions.\n");
+    } else {
+        verbose = really_verbose;
+        unplace_lights(s);
+        printf("Puzzle has difficulty %d: solving...\n", diff);
+        dosolve(s, sflags, NULL); /* sflags from last successful solve */
+        result = game_text_format(s);
+        printf("%s", result);
+        sfree(result);
+    }
+
+    return 0;
+}
+
+#endif
+
 /* vim: set shiftwidth=4 tabstop=8: */