1 files changed, 2179 insertions, 0 deletions

diff --git a/apps/plugins/puzzles/src/filling.c b/apps/plugins/puzzles/src/filling.c
new file mode 100644
index 0000000000..d8d0c8cbb0
--- /dev/null
+++ b/apps/plugins/puzzles/src/filling.c
@@ -0,0 +1,2179 @@
+/* -*- tab-width: 8; indent-tabs-mode: t -*-
+ * filling.c: An implementation of the Nikoli game fillomino.
+ * Copyright (C) 2007 Jonas Kölker.  See LICENSE for the license.
+ */
+
+/* TODO:
+ *
+ *  - use a typedef instead of int for numbers on the board
+ *     + replace int with something else (signed short?)
+ *        - the type should be signed (for -board[i] and -SENTINEL)
+ *        - the type should be somewhat big: board[i] = i
+ *        - Using shorts gives us 181x181 puzzles as upper bound.
+ *
+ *  - in board generation, after having merged regions such that no
+ *    more merges are necessary, try splitting (big) regions.
+ *     + it seems that smaller regions make for better puzzles; see
+ *       for instance the 7x7 puzzle in this file (grep for 7x7:).
+ *
+ *  - symmetric hints (solo-style)
+ *     + right now that means including _many_ hints, and the puzzles
+ *       won't look any nicer.  Not worth it (at the moment).
+ *
+ *  - make the solver do recursion/backtracking.
+ *     + This is for user-submitted puzzles, not for puzzle
+ *       generation (on the other hand, never say never).
+ *
+ *  - prove that only w=h=2 needs a special case
+ *
+ *  - solo-like pencil marks?
+ *
+ *  - a user says that the difficulty is unevenly distributed.
+ *     + partition into levels?  Will they be non-crap?
+ *
+ *  - Allow square contents > 9?
+ *     + I could use letters for digits (solo does this), but
+ *       letters don't have numeric significance (normal people hate
+ *       base36), which is relevant here (much more than in solo).
+ *     + [click, 1, 0, enter] => [10 in clicked square]?
+ *     + How much information is needed to solve?  Does one need to
+ *       know the algorithm by which the largest number is set?
+ *
+ *  - eliminate puzzle instances with done chunks (1's in particular)?
+ *     + that's what the qsort call is all about.
+ *     + the 1's don't bother me that much.
+ *     + but this takes a LONG time (not always possible)?
+ *        - this may be affected by solver (lack of) quality.
+ *        - weed them out by construction instead of post-cons check
+ *           + but that interleaves make_board and new_game_desc: you
+ *             have to alternate between changing the board and
+ *             changing the hint set (instead of just creating the
+ *             board once, then changing the hint set once -> done).
+ *
+ *  - use binary search when discovering the minimal sovable point
+ *     + profile to show a need (but when the solver gets slower...)
+ *     + 7x9 @ .011s, 9x13 @ .075s, 17x13 @ .661s (all avg with n=100)
+ *     + but the hints are independent, not linear, so... what?
+ */
+
+#include <assert.h>
+#include <ctype.h>
+#include <math.h>
+#include <stdarg.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+
+#include "puzzles.h"
+
+static unsigned char verbose;
+
+static void printv(char *fmt, ...) {
+#ifndef PALM
+    if (verbose) {
+        va_list va;
+        va_start(va, fmt);
+        vprintf(fmt, va);
+        va_end(va);
+    }
+#endif
+}
+
+/*****************************************************************************
+ * GAME CONFIGURATION AND PARAMETERS                                         *
+ *****************************************************************************/
+
+struct game_params {
+    int w, h;
+};
+
+struct shared_state {
+    struct game_params params;
+    int *clues;
+    int refcnt;
+};
+
+struct game_state {
+    int *board;
+    struct shared_state *shared;
+    int completed, cheated;
+};
+
+static const struct game_params filling_defaults[3] = {
+    {9, 7}, {13, 9}, {17, 13}
+};
+
+static game_params *default_params(void)
+{
+    game_params *ret = snew(game_params);
+
+    *ret = filling_defaults[1]; /* struct copy */
+
+    return ret;
+}
+
+static int game_fetch_preset(int i, char **name, game_params **params)
+{
+    char buf[64];
+
+    if (i < 0 || i >= lenof(filling_defaults)) return FALSE;
+    *params = snew(game_params);
+    **params = filling_defaults[i]; /* struct copy */
+    sprintf(buf, "%dx%d", filling_defaults[i].w, filling_defaults[i].h);
+    *name = dupstr(buf);
+
+    return TRUE;
+}
+
+static void free_params(game_params *params)
+{
+    sfree(params);
+}
+
+static game_params *dup_params(const game_params *params)
+{
+    game_params *ret = snew(game_params);
+    *ret = *params; /* struct copy */
+    return ret;
+}
+
+static void decode_params(game_params *ret, char const *string)
+{
+    ret->w = ret->h = atoi(string);
+    while (*string && isdigit((unsigned char) *string)) ++string;
+    if (*string == 'x') ret->h = atoi(++string);
+}
+
+static char *encode_params(const game_params *params, int full)
+{
+    char buf[64];
+    sprintf(buf, "%dx%d", params->w, params->h);
+    return dupstr(buf);
+}
+
+static config_item *game_configure(const game_params *params)
+{
+    config_item *ret;
+    char buf[64];
+
+    ret = snewn(3, config_item);
+
+    ret[0].name = "Width";
+    ret[0].type = C_STRING;
+    sprintf(buf, "%d", params->w);
+    ret[0].sval = dupstr(buf);
+    ret[0].ival = 0;
+
+    ret[1].name = "Height";
+    ret[1].type = C_STRING;
+    sprintf(buf, "%d", params->h);
+    ret[1].sval = dupstr(buf);
+    ret[1].ival = 0;
+
+    ret[2].name = NULL;
+    ret[2].type = C_END;
+    ret[2].sval = NULL;
+    ret[2].ival = 0;
+
+    return ret;
+}
+
+static game_params *custom_params(const config_item *cfg)
+{
+    game_params *ret = snew(game_params);
+
+    ret->w = atoi(cfg[0].sval);
+    ret->h = atoi(cfg[1].sval);
+
+    return ret;
+}
+
+static char *validate_params(const game_params *params, int full)
+{
+    if (params->w < 1) return "Width must be at least one";
+    if (params->h < 1) return "Height must be at least one";
+
+    return NULL;
+}
+
+/*****************************************************************************
+ * STRINGIFICATION OF GAME STATE                                             *
+ *****************************************************************************/
+
+#define EMPTY 0
+
+/* Example of plaintext rendering:
+ *  +---+---+---+---+---+---+---+
+ *  | 6 |   |   | 2 |   |   | 2 |
+ *  +---+---+---+---+---+---+---+
+ *  |   | 3 |   | 6 |   | 3 |   |
+ *  +---+---+---+---+---+---+---+
+ *  | 3 |   |   |   |   |   | 1 |
+ *  +---+---+---+---+---+---+---+
+ *  |   | 2 | 3 |   | 4 | 2 |   |
+ *  +---+---+---+---+---+---+---+
+ *  | 2 |   |   |   |   |   | 3 |
+ *  +---+---+---+---+---+---+---+
+ *  |   | 5 |   | 1 |   | 4 |   |
+ *  +---+---+---+---+---+---+---+
+ *  | 4 |   |   | 3 |   |   | 3 |
+ *  +---+---+---+---+---+---+---+
+ *
+ * This puzzle instance is taken from the nikoli website
+ * Encoded (unsolved and solved), the strings are these:
+ * 7x7:6002002030603030000010230420200000305010404003003
+ * 7x7:6662232336663232331311235422255544325413434443313
+ */
+static char *board_to_string(int *board, int w, int h) {
+    const int sz = w * h;
+    const int chw = (4*w + 2); /* +2 for trailing '+' and '\n' */
+    const int chh = (2*h + 1); /* +1: n fence segments, n+1 posts */
+    const int chlen = chw * chh;
+    char *repr = snewn(chlen + 1, char);
+    int i;
+
+    assert(board);
+
+    /* build the first line ("^(\+---){n}\+$") */
+    for (i = 0; i < w; ++i) {
+        repr[4*i + 0] = '+';
+        repr[4*i + 1] = '-';
+        repr[4*i + 2] = '-';
+        repr[4*i + 3] = '-';
+    }
+    repr[4*i + 0] = '+';
+    repr[4*i + 1] = '\n';
+
+    /* ... and copy it onto the odd-numbered lines */
+    for (i = 0; i < h; ++i) memcpy(repr + (2*i + 2) * chw, repr, chw);
+
+    /* build the second line ("^(\|\t){n}\|$") */
+    for (i = 0; i < w; ++i) {
+        repr[chw + 4*i + 0] = '|';
+        repr[chw + 4*i + 1] = ' ';
+        repr[chw + 4*i + 2] = ' ';
+        repr[chw + 4*i + 3] = ' ';
+    }
+    repr[chw + 4*i + 0] = '|';
+    repr[chw + 4*i + 1] = '\n';
+
+    /* ... and copy it onto the even-numbered lines */
+    for (i = 1; i < h; ++i) memcpy(repr + (2*i + 1) * chw, repr + chw, chw);
+
+    /* fill in the numbers */
+    for (i = 0; i < sz; ++i) {
+        const int x = i % w;
+        const int y = i / w;
+        if (board[i] == EMPTY) continue;
+        repr[chw*(2*y + 1) + (4*x + 2)] = board[i] + '0';
+    }
+
+    repr[chlen] = '\0';
+    return repr;
+}
+
+static int game_can_format_as_text_now(const game_params *params)
+{
+    return TRUE;
+}
+
+static char *game_text_format(const game_state *state)
+{
+    const int w = state->shared->params.w;
+    const int h = state->shared->params.h;
+    return board_to_string(state->board, w, h);
+}
+
+/*****************************************************************************
+ * GAME GENERATION AND SOLVER                                                *
+ *****************************************************************************/
+
+static const int dx[4] = {-1, 1, 0, 0};
+static const int dy[4] = {0, 0, -1, 1};
+
+struct solver_state
+{
+    int *dsf;
+    int *board;
+    int *connected;
+    int nempty;
+
+    /* Used internally by learn_bitmap_deductions; kept here to avoid
+     * mallocing/freeing them every time that function is called. */
+    int *bm, *bmdsf, *bmminsize;
+};
+
+static void print_board(int *board, int w, int h) {
+    if (verbose) {
+        char *repr = board_to_string(board, w, h);
+        printv("%s\n", repr);
+        free(repr);
+    }
+}
+
+static game_state *new_game(midend *, const game_params *, const char *);
+static void free_game(game_state *);
+
+#define SENTINEL sz
+
+static int mark_region(int *board, int w, int h, int i, int n, int m) {
+    int j;
+
+    board[i] = -1;
+
+    for (j = 0; j < 4; ++j) {
+        const int x = (i % w) + dx[j], y = (i / w) + dy[j], ii = w*y + x;
+        if (x < 0 || x >= w || y < 0 || y >= h) continue;
+        if (board[ii] == m) return FALSE;
+        if (board[ii] != n) continue;
+        if (!mark_region(board, w, h, ii, n, m)) return FALSE;
+    }
+    return TRUE;
+}
+
+static int region_size(int *board, int w, int h, int i) {
+    const int sz = w * h;
+    int j, size, copy;
+    if (board[i] == 0) return 0;
+    copy = board[i];
+    mark_region(board, w, h, i, board[i], SENTINEL);
+    for (size = j = 0; j < sz; ++j) {
+        if (board[j] != -1) continue;
+        ++size;
+        board[j] = copy;
+    }
+    return size;
+}
+
+static void merge_ones(int *board, int w, int h)
+{
+    const int sz = w * h;
+    const int maxsize = min(max(max(w, h), 3), 9);
+    int i, j, k, change;
+    do {
+        change = FALSE;
+        for (i = 0; i < sz; ++i) {
+            if (board[i] != 1) continue;
+
+            for (j = 0; j < 4; ++j, board[i] = 1) {
+                const int x = (i % w) + dx[j], y = (i / w) + dy[j];
+                int oldsize, newsize, ok, ii = w*y + x;
+                if (x < 0 || x >= w || y < 0 || y >= h) continue;
+                if (board[ii] == maxsize) continue;
+
+                oldsize = board[ii];
+                board[i] = oldsize;
+                newsize = region_size(board, w, h, i);
+
+                if (newsize > maxsize) continue;
+
+                ok = mark_region(board, w, h, i, oldsize, newsize);
+
+                for (k = 0; k < sz; ++k)
+                    if (board[k] == -1)
+                        board[k] = ok ? newsize : oldsize;
+
+                if (ok) break;
+            }
+            if (j < 4) change = TRUE;
+        }
+    } while (change);
+}
+
+/* generate a random valid board; uses validate_board. */
+static void make_board(int *board, int w, int h, random_state *rs) {
+    const int sz = w * h;
+
+    /* w=h=2 is a special case which requires a number > max(w, h) */
+    /* TODO prove that this is the case ONLY for w=h=2. */
+    const int maxsize = min(max(max(w, h), 3), 9);
+
+    /* Note that if 1 in {w, h} then it's impossible to have a region
+     * of size > w*h, so the special case only affects w=h=2. */
+
+    int i, change, *dsf;
+
+    assert(w >= 1);
+    assert(h >= 1);
+    assert(board);
+
+    /* I abuse the board variable: when generating the puzzle, it
+     * contains a shuffled list of numbers {0, ..., sz-1}. */
+    for (i = 0; i < sz; ++i) board[i] = i;
+
+    dsf = snewn(sz, int);
+retry:
+    dsf_init(dsf, sz);
+    shuffle(board, sz, sizeof (int), rs);
+
+    do {
+        change = FALSE; /* as long as the board potentially has errors */
+        for (i = 0; i < sz; ++i) {
+            const int square = dsf_canonify(dsf, board[i]);
+            const int size = dsf_size(dsf, square);
+            int merge = SENTINEL, min = maxsize - size + 1, error = FALSE;
+            int neighbour, neighbour_size, j;
+
+            for (j = 0; j < 4; ++j) {
+                const int x = (board[i] % w) + dx[j];
+                const int y = (board[i] / w) + dy[j];
+                if (x < 0 || x >= w || y < 0 || y >= h) continue;
+
+                neighbour = dsf_canonify(dsf, w*y + x);
+                if (square == neighbour) continue;
+
+                neighbour_size = dsf_size(dsf, neighbour);
+                if (size == neighbour_size) error = TRUE;
+
+                /* find the smallest neighbour to merge with, which
+                 * wouldn't make the region too large.  (This is
+                 * guaranteed by the initial value of `min'.) */
+                if (neighbour_size < min) {
+                    min = neighbour_size;
+                    merge = neighbour;
+                }
+            }
+
+            /* if this square is not in error, leave it be */
+            if (!error) continue;
+
+            /* if it is, but we can't fix it, retry the whole board.
+             * Maybe we could fix it by merging the conflicting
+             * neighbouring region(s) into some of their neighbours,
+             * but just restarting works out fine. */
+            if (merge == SENTINEL) goto retry;
+
+            /* merge with the smallest neighbouring workable region. */
+            dsf_merge(dsf, square, merge);
+            change = TRUE;
+        }
+    } while (change);
+
+    for (i = 0; i < sz; ++i) board[i] = dsf_size(dsf, i);
+    merge_ones(board, w, h);
+
+    sfree(dsf);
+}
+
+static void merge(int *dsf, int *connected, int a, int b) {
+    int c;
+    assert(dsf);
+    assert(connected);
+    a = dsf_canonify(dsf, a);
+    b = dsf_canonify(dsf, b);
+    if (a == b) return;
+    dsf_merge(dsf, a, b);
+    c = connected[a];
+    connected[a] = connected[b];
+    connected[b] = c;
+}
+
+static void *memdup(const void *ptr, size_t len, size_t esz) {
+    void *dup = smalloc(len * esz);
+    assert(ptr);
+    memcpy(dup, ptr, len * esz);
+    return dup;
+}
+
+static void expand(struct solver_state *s, int w, int h, int t, int f) {
+    int j;
+    assert(s);
+    assert(s->board[t] == EMPTY); /* expand to empty square */
+    assert(s->board[f] != EMPTY); /* expand from non-empty square */
+    printv(
+        "learn: expanding %d from (%d, %d) into (%d, %d)\n",
+        s->board[f], f % w, f / w, t % w, t / w);
+    s->board[t] = s->board[f];
+    for (j = 0; j < 4; ++j) {
+        const int x = (t % w) + dx[j];
+        const int y = (t / w) + dy[j];
+        const int idx = w*y + x;
+        if (x < 0 || x >= w || y < 0 || y >= h) continue;
+        if (s->board[idx] != s->board[t]) continue;
+        merge(s->dsf, s->connected, t, idx);
+    }
+    --s->nempty;
+}
+
+static void clear_count(int *board, int sz) {
+    int i;
+    for (i = 0; i < sz; ++i) {
+        if (board[i] >= 0) continue;
+        else if (board[i] == -SENTINEL) board[i] = EMPTY;
+        else board[i] = -board[i];
+    }
+}
+
+static void flood_count(int *board, int w, int h, int i, int n, int *c) {
+    const int sz = w * h;
+    int k;
+
+    if (board[i] == EMPTY) board[i] = -SENTINEL;
+    else if (board[i] == n) board[i] = -board[i];
+    else return;
+
+    if (--*c == 0) return;
+
+    for (k = 0; k < 4; ++k) {
+        const int x = (i % w) + dx[k];
+        const int y = (i / w) + dy[k];
+        const int idx = w*y + x;
+        if (x < 0 || x >= w || y < 0 || y >= h) continue;
+        flood_count(board, w, h, idx, n, c);
+        if (*c == 0) return;
+    }
+}
+
+static int check_capacity(int *board, int w, int h, int i) {
+    int n = board[i];
+    flood_count(board, w, h, i, board[i], &n);
+    clear_count(board, w * h);
+    return n == 0;
+}
+
+static int expandsize(const int *board, int *dsf, int w, int h, int i, int n) {
+    int j;
+    int nhits = 0;
+    int hits[4];
+    int size = 1;
+    for (j = 0; j < 4; ++j) {
+        const int x = (i % w) + dx[j];
+        const int y = (i / w) + dy[j];
+        const int idx = w*y + x;
+        int root;
+        int m;
+        if (x < 0 || x >= w || y < 0 || y >= h) continue;
+        if (board[idx] != n) continue;
+        root = dsf_canonify(dsf, idx);
+        for (m = 0; m < nhits && root != hits[m]; ++m);
+        if (m < nhits) continue;
+        printv("\t  (%d, %d) contrib %d to size\n", x, y, dsf[root] >> 2);
+        size += dsf_size(dsf, root);
+        assert(dsf_size(dsf, root) >= 1);
+        hits[nhits++] = root;
+    }
+    return size;
+}
+
+/*
+ *  +---+---+---+---+---+---+---+
+ *  | 6 |   |   | 2 |   |   | 2 |
+ *  +---+---+---+---+---+---+---+
+ *  |   | 3 |   | 6 |   | 3 |   |
+ *  +---+---+---+---+---+---+---+
+ *  | 3 |   |   |   |   |   | 1 |
+ *  +---+---+---+---+---+---+---+
+ *  |   | 2 | 3 |   | 4 | 2 |   |
+ *  +---+---+---+---+---+---+---+
+ *  | 2 |   |   |   |   |   | 3 |
+ *  +---+---+---+---+---+---+---+
+ *  |   | 5 |   | 1 |   | 4 |   |
+ *  +---+---+---+---+---+---+---+
+ *  | 4 |   |   | 3 |   |   | 3 |
+ *  +---+---+---+---+---+---+---+
+ */
+
+/* Solving techniques:
+ *
+ * CONNECTED COMPONENT FORCED EXPANSION (too big):
+ * When a CC can only be expanded in one direction, because all the
+ * other ones would make the CC too big.
+ *  +---+---+---+---+---+
+ *  | 2 | 2 |   | 2 | _ |
+ *  +---+---+---+---+---+
+ *
+ * CONNECTED COMPONENT FORCED EXPANSION (too small):
+ * When a CC must include a particular square, because otherwise there
+ * would not be enough room to complete it.  This includes squares not
+ * adjacent to the CC through learn_critical_square.
+ *  +---+---+
+ *  | 2 | _ |
+ *  +---+---+
+ *
+ * DROPPING IN A ONE:
+ * When an empty square has no neighbouring empty squares and only a 1
+ * will go into the square (or other CCs would be too big).
+ *  +---+---+---+
+ *  | 2 | 2 | _ |
+ *  +---+---+---+
+ *
+ * TODO: generalise DROPPING IN A ONE: find the size of the CC of
+ * empty squares and a list of all adjacent numbers.  See if only one
+ * number in {1, ..., size} u {all adjacent numbers} is possible.
+ * Probably this is only effective for a CC size < n for some n (4?)
+ *
+ * TODO: backtracking.
+ */
+
+static void filled_square(struct solver_state *s, int w, int h, int i) {
+    int j;
+    for (j = 0; j < 4; ++j) {
+        const int x = (i % w) + dx[j];
+        const int y = (i / w) + dy[j];
+        const int idx = w*y + x;
+        if (x < 0 || x >= w || y < 0 || y >= h) continue;
+        if (s->board[i] == s->board[idx])
+            merge(s->dsf, s->connected, i, idx);
+    }
+}
+
+static void init_solver_state(struct solver_state *s, int w, int h) {
+    const int sz = w * h;
+    int i;
+    assert(s);
+
+    s->nempty = 0;
+    for (i = 0; i < sz; ++i) s->connected[i] = i;
+    for (i = 0; i < sz; ++i)
+        if (s->board[i] == EMPTY) ++s->nempty;
+        else filled_square(s, w, h, i);
+}
+
+static int learn_expand_or_one(struct solver_state *s, int w, int h) {
+    const int sz = w * h;
+    int i;
+    int learn = FALSE;
+
+    assert(s);
+
+    for (i = 0; i < sz; ++i) {
+        int j;
+        int one = TRUE;
+
+        if (s->board[i] != EMPTY) continue;
+
+        for (j = 0; j < 4; ++j) {
+            const int x = (i % w) + dx[j];
+            const int y = (i / w) + dy[j];
+            const int idx = w*y + x;
+            if (x < 0 || x >= w || y < 0 || y >= h) continue;
+            if (s->board[idx] == EMPTY) {
+                one = FALSE;
+                continue;
+            }
+            if (one &&
+                (s->board[idx] == 1 ||
+                 (s->board[idx] >= expandsize(s->board, s->dsf, w, h,
+                                              i, s->board[idx]))))
+                one = FALSE;
+            if (dsf_size(s->dsf, idx) == s->board[idx]) continue;
+            assert(s->board[i] == EMPTY);
+            s->board[i] = -SENTINEL;
+            if (check_capacity(s->board, w, h, idx)) continue;
+            assert(s->board[i] == EMPTY);
+            printv("learn: expanding in one\n");
+            expand(s, w, h, i, idx);
+            learn = TRUE;
+            break;
+        }
+
+        if (j == 4 && one) {
+            printv("learn: one at (%d, %d)\n", i % w, i / w);
+            assert(s->board[i] == EMPTY);
+            s->board[i] = 1;
+            assert(s->nempty);
+            --s->nempty;
+            learn = TRUE;
+        }
+    }
+    return learn;
+}
+
+static int learn_blocked_expansion(struct solver_state *s, int w, int h) {
+    const int sz = w * h;
+    int i;
+    int learn = FALSE;
+
+    assert(s);
+    /* for every connected component */
+    for (i = 0; i < sz; ++i) {
+        int exp = SENTINEL;
+        int j;
+
+        if (s->board[i] == EMPTY) continue;
+        j = dsf_canonify(s->dsf, i);
+
+        /* (but only for each connected component) */
+        if (i != j) continue;
+
+        /* (and not if it's already complete) */
+        if (dsf_size(s->dsf, j) == s->board[j]) continue;
+
+        /* for each square j _in_ the connected component */
+        do {
+            int k;
+            printv("  looking at (%d, %d)\n", j % w, j / w);
+
+            /* for each neighbouring square (idx) */
+            for (k = 0; k < 4; ++k) {
+                const int x = (j % w) + dx[k];
+                const int y = (j / w) + dy[k];
+                const int idx = w*y + x;
+                int size;
+                /* int l;
+                   int nhits = 0;
+                   int hits[4]; */
+                if (x < 0 || x >= w || y < 0 || y >= h) continue;
+                if (s->board[idx] != EMPTY) continue;
+                if (exp == idx) continue;
+                printv("\ttrying to expand onto (%d, %d)\n", x, y);
+
+                /* find out the would-be size of the new connected
+                 * component if we actually expanded into idx */
+                /*
+                size = 1;
+                for (l = 0; l < 4; ++l) {
+                    const int lx = x + dx[l];
+                    const int ly = y + dy[l];
+                    const int idxl = w*ly + lx;
+                    int root;
+                    int m;
+                    if (lx < 0 || lx >= w || ly < 0 || ly >= h) continue;
+                    if (board[idxl] != board[j]) continue;
+                    root = dsf_canonify(dsf, idxl);
+                    for (m = 0; m < nhits && root != hits[m]; ++m);
+                    if (m != nhits) continue;
+                    // printv("\t  (%d, %d) contributed %d to size\n", lx, ly, dsf[root] >> 2);
+                    size += dsf_size(dsf, root);
+                    assert(dsf_size(dsf, root) >= 1);
+                    hits[nhits++] = root;
+                }
+                */
+
+                size = expandsize(s->board, s->dsf, w, h, idx, s->board[j]);
+
+                /* ... and see if that size is too big, or if we
+                 * have other expansion candidates.  Otherwise
+                 * remember the (so far) only candidate. */
+
+                printv("\tthat would give a size of %d\n", size);
+                if (size > s->board[j]) continue;
+                /* printv("\tnow knowing %d expansions\n", nexpand + 1); */
+                if (exp != SENTINEL) goto next_i;
+                assert(exp != idx);
+                exp = idx;
+            }
+
+            j = s->connected[j]; /* next square in the same CC */
+            assert(s->board[i] == s->board[j]);
+        } while (j != i);
+        /* end: for each square j _in_ the connected component */
+
+        if (exp == SENTINEL) continue;
+        printv("learning to expand\n");
+        expand(s, w, h, exp, i);
+        learn = TRUE;
+
+        next_i:
+        ;
+    }
+    /* end: for each connected component */
+    return learn;
+}
+
+static int learn_critical_square(struct solver_state *s, int w, int h) {
+    const int sz = w * h;
+    int i;
+    int learn = FALSE;
+    assert(s);
+
+    /* for each connected component */
+    for (i = 0; i < sz; ++i) {
+        int j, slack;
+        if (s->board[i] == EMPTY) continue;
+        if (i != dsf_canonify(s->dsf, i)) continue;
+        slack = s->board[i] - dsf_size(s->dsf, i);
+        if (slack == 0) continue;
+        assert(s->board[i] != 1);
+        /* for each empty square */
+        for (j = 0; j < sz; ++j) {
+            if (s->board[j] == EMPTY) {
+                /* if it's too far away from the CC, don't bother */
+                int k = i, jx = j % w, jy = j / w;
+                do {
+                    int kx = k % w, ky = k / w;
+                    if (abs(kx - jx) + abs(ky - jy) <= slack) break;
+                    k = s->connected[k];
+                } while (i != k);
+                if (i == k) continue; /* not within range */
+            } else continue;
+            s->board[j] = -SENTINEL;
+            if (check_capacity(s->board, w, h, i)) continue;
+            /* if not expanding s->board[i] to s->board[j] implies
+             * that s->board[i] can't reach its full size, ... */
+            assert(s->nempty);
+            printv(
+                "learn: ds %d at (%d, %d) blocking (%d, %d)\n",
+                s->board[i], j % w, j / w, i % w, i / w);
+            --s->nempty;
+            s->board[j] = s->board[i];
+            filled_square(s, w, h, j);
+            learn = TRUE;
+        }
+    }
+    return learn;
+}
+
+#if 0
+static void print_bitmap(int *bitmap, int w, int h) {
+    if (verbose) {
+        int x, y;
+        for (y = 0; y < h; y++) {
+            for (x = 0; x < w; x++) {
+                printv(" %03x", bm[y*w+x]);
+            }
+            printv("\n");
+        }
+    }
+}
+#endif
+
+static int learn_bitmap_deductions(struct solver_state *s, int w, int h)
+{
+    const int sz = w * h;
+    int *bm = s->bm;
+    int *dsf = s->bmdsf;
+    int *minsize = s->bmminsize;
+    int x, y, i, j, n;
+    int learn = FALSE;
+
+    /*
+     * This function does deductions based on building up a bitmap
+     * which indicates the possible numbers that can appear in each
+     * grid square. If we can rule out all but one possibility for a
+     * particular square, then we've found out the value of that
+     * square. In particular, this is one of the few forms of
+     * deduction capable of inferring the existence of a 'ghost
+     * region', i.e. a region which has none of its squares filled in
+     * at all.
+     *
+     * The reasoning goes like this. A currently unfilled square S can
+     * turn out to contain digit n in exactly two ways: either S is
+     * part of an n-region which also includes some currently known
+     * connected component of squares with n in, or S is part of an
+     * n-region separate from _all_ currently known connected
+     * components. If we can rule out both possibilities, then square
+     * S can't contain digit n at all.
+     *
+     * The former possibility: if there's a region of size n
+     * containing both S and some existing component C, then that
+     * means the distance from S to C must be small enough that C
+     * could be extended to include S without becoming too big. So we
+     * can do a breadth-first search out from all existing components
+     * with n in them, to identify all the squares which could be
+     * joined to any of them.
+     *
+     * The latter possibility: if there's a region of size n that
+     * doesn't contain _any_ existing component, then it also can't
+     * contain any square adjacent to an existing component either. So
+     * we can identify all the EMPTY squares not adjacent to any
+     * existing square with n in, and group them into connected
+     * components; then any component of size less than n is ruled
+     * out, because there wouldn't be room to create a completely new
+     * n-region in it.
+     *
+     * In fact we process these possibilities in the other order.
+     * First we find all the squares not adjacent to an existing
+     * square with n in; then we winnow those by removing too-small
+     * connected components, to get the set of squares which could
+     * possibly be part of a brand new n-region; and finally we do the
+     * breadth-first search to add in the set of squares which could
+     * possibly be added to some existing n-region.
+     */
+
+    /*
+     * Start by initialising our bitmap to 'all numbers possible in
+     * all squares'.
+     */
+    for (y = 0; y < h; y++)
+        for (x = 0; x < w; x++)
+            bm[y*w+x] = (1 << 10) - (1 << 1); /* bits 1,2,...,9 now set */
+#if 0
+    printv("initial bitmap:\n");
+    print_bitmap(bm, w, h);
+#endif
+
+    /*
+     * Now completely zero out the bitmap for squares that are already
+     * filled in (we aren't interested in those anyway). Also, for any
+     * filled square, eliminate its number from all its neighbours
+     * (because, as discussed above, the neighbours couldn't be part
+     * of a _new_ region with that number in it, and that's the case
+     * we consider first).
+     */
+    for (y = 0; y < h; y++) {
+        for (x = 0; x < w; x++) {
+            i = y*w+x;
+            n = s->board[i];
+
+            if (n != EMPTY) {
+                bm[i] = 0;
+
+                if (x > 0)
+                    bm[i-1] &= ~(1 << n);
+                if (x+1 < w)
+                    bm[i+1] &= ~(1 << n);
+                if (y > 0)
+                    bm[i-w] &= ~(1 << n);
+                if (y+1 < h)
+                    bm[i+w] &= ~(1 << n);
+            }
+        }
+    }
+#if 0
+    printv("bitmap after filled squares:\n");
+    print_bitmap(bm, w, h);
+#endif
+
+    /*
+     * Now, for each n, we separately find the connected components of
+     * squares for which n is still a possibility. Then discard any
+     * component of size < n, because that component is too small to
+     * have a completely new n-region in it.
+     */
+    for (n = 1; n <= 9; n++) {
+        dsf_init(dsf, sz);
+
+        /* Build the dsf */
+        for (y = 0; y < h; y++)
+            for (x = 0; x+1 < w; x++)
+                if (bm[y*w+x] & bm[y*w+(x+1)] & (1 << n))
+                    dsf_merge(dsf, y*w+x, y*w+(x+1));
+        for (y = 0; y+1 < h; y++)
+            for (x = 0; x < w; x++)
+                if (bm[y*w+x] & bm[(y+1)*w+x] & (1 << n))
+                    dsf_merge(dsf, y*w+x, (y+1)*w+x);
+
+        /* Query the dsf */
+        for (i = 0; i < sz; i++)
+            if ((bm[i] & (1 << n)) && dsf_size(dsf, i) < n)
+                bm[i] &= ~(1 << n);
+    }
+#if 0
+    printv("bitmap after winnowing small components:\n");
+    print_bitmap(bm, w, h);
+#endif
+
+    /*
+     * Now our bitmap includes every square which could be part of a
+     * completely new region, of any size. Extend it to include
+     * squares which could be part of an existing region.
+     */
+    for (n = 1; n <= 9; n++) {
+        /*
+         * We're going to do a breadth-first search starting from
+         * existing connected components with cell value n, to find
+         * all cells they might possibly extend into.
+         *
+         * The quantity we compute, for each square, is 'minimum size
+         * that any existing CC would have to have if extended to
+         * include this square'. So squares already _in_ an existing
+         * CC are initialised to the size of that CC; then we search
+         * outwards using the rule that if a square's score is j, then
+         * its neighbours can't score more than j+1.
+         *
+         * Scores are capped at n+1, because if a square scores more
+         * than n then that's enough to know it can't possibly be
+         * reached by extending an existing region - we don't need to
+         * know exactly _how far_ out of reach it is.
+         */
+        for (i = 0; i < sz; i++) {
+            if (s->board[i] == n) {
+                /* Square is part of an existing CC. */
+                minsize[i] = dsf_size(s->dsf, i);
+            } else {
+                /* Otherwise, initialise to the maximum score n+1;
+                 * we'll reduce this later if we find a neighbouring
+                 * square with a lower score. */
+                minsize[i] = n+1;
+            }
+        }
+
+        for (j = 1; j < n; j++) {
+            /*
+             * Find neighbours of cells scoring j, and set their score
+             * to at most j+1.
+             *
+             * Doing the BFS this way means we need n passes over the
+             * grid, which isn't entirely optimal but it seems to be
+             * fast enough for the moment. This could probably be
+             * improved by keeping a linked-list queue of cells in
+             * some way, but I think you'd have to be a bit careful to
+             * insert things into the right place in the queue; this
+             * way is easier not to get wrong.
+             */
+            for (y = 0; y < h; y++) {
+                for (x = 0; x < w; x++) {
+                    i = y*w+x;
+                    if (minsize[i] == j) {
+                        if (x > 0 && minsize[i-1] > j+1)
+                            minsize[i-1] = j+1;
+                        if (x+1 < w && minsize[i+1] > j+1)
+                            minsize[i+1] = j+1;
+                        if (y > 0 && minsize[i-w] > j+1)
+                            minsize[i-w] = j+1;
+                        if (y+1 < h && minsize[i+w] > j+1)
+                            minsize[i+w] = j+1;
+                    }
+                }
+            }
+        }
+
+        /*
+         * Now, every cell scoring at most n should have its 1<<n bit
+         * in the bitmap reinstated, because we've found that it's
+         * potentially reachable by extending an existing CC.
+         */
+        for (i = 0; i < sz; i++)
+            if (minsize[i] <= n)
+                bm[i] |= 1<<n;
+    }
+#if 0
+    printv("bitmap after bfs:\n");
+    print_bitmap(bm, w, h);
+#endif
+
+    /*
+     * Now our bitmap is complete. Look for entries with only one bit
+     * set; those are squares with only one possible number, in which
+     * case we can fill that number in.
+     */
+    for (i = 0; i < sz; i++) {
+        if (bm[i] && !(bm[i] & (bm[i]-1))) { /* is bm[i] a power of two? */
+            int val = bm[i];
+
+            /* Integer log2, by simple binary search. */
+            n = 0;
+            if (val >> 8) { val >>= 8; n += 8; }
+            if (val >> 4) { val >>= 4; n += 4; }
+            if (val >> 2) { val >>= 2; n += 2; }
+            if (val >> 1) { val >>= 1; n += 1; }
+
+            /* Double-check that we ended up with a sensible
+             * answer. */
+            assert(1 <= n);
+            assert(n <= 9);
+            assert(bm[i] == (1 << n));
+
+            if (s->board[i] == EMPTY) {
+                printv("learn: %d is only possibility at (%d, %d)\n",
+                       n, i % w, i / w);
+                s->board[i] = n;
+                filled_square(s, w, h, i);
+                assert(s->nempty);
+                --s->nempty;
+                learn = TRUE;
+            }
+        }
+    }
+
+    return learn;
+}
+
+static int solver(const int *orig, int w, int h, char **solution) {
+    const int sz = w * h;
+
+    struct solver_state ss;
+    ss.board = memdup(orig, sz, sizeof (int));
+    ss.dsf = snew_dsf(sz); /* eqv classes: connected components */
+    ss.connected = snewn(sz, int); /* connected[n] := n.next; */
+    /* cyclic disjoint singly linked lists, same partitioning as dsf.
+     * The lists lets you iterate over a partition given any member */
+    ss.bm = snewn(sz, int);
+    ss.bmdsf = snew_dsf(sz);
+    ss.bmminsize = snewn(sz, int);
+
+    printv("trying to solve this:\n");
+    print_board(ss.board, w, h);
+
+    init_solver_state(&ss, w, h);
+    do {
+        if (learn_blocked_expansion(&ss, w, h)) continue;
+        if (learn_expand_or_one(&ss, w, h)) continue;
+        if (learn_critical_square(&ss, w, h)) continue;
+        if (learn_bitmap_deductions(&ss, w, h)) continue;
+        break;
+    } while (ss.nempty);
+
+    printv("best guess:\n");
+    print_board(ss.board, w, h);
+
+    if (solution) {
+        int i;
+        *solution = snewn(sz + 2, char);
+        **solution = 's';
+        for (i = 0; i < sz; ++i) (*solution)[i + 1] = ss.board[i] + '0';
+        (*solution)[sz + 1] = '\0';
+        /* We don't need the \0 for execute_move (the only user)
+         * I'm just being printf-friendly in case I wanna print */
+    }
+
+    sfree(ss.dsf);
+    sfree(ss.board);
+    sfree(ss.connected);
+    sfree(ss.bm);
+    sfree(ss.bmdsf);
+    sfree(ss.bmminsize);
+
+    return !ss.nempty;
+}
+
+static int *make_dsf(int *dsf, int *board, const int w, const int h) {
+    const int sz = w * h;
+    int i;
+
+    if (!dsf)
+        dsf = snew_dsf(w * h);
+    else
+        dsf_init(dsf, w * h);
+
+    for (i = 0; i < sz; ++i) {
+        int j;
+        for (j = 0; j < 4; ++j) {
+            const int x = (i % w) + dx[j];
+            const int y = (i / w) + dy[j];
+            const int k = w*y + x;
+            if (x < 0 || x >= w || y < 0 || y >= h) continue;
+            if (board[i] == board[k]) dsf_merge(dsf, i, k);
+        }
+    }
+    return dsf;
+}
+
+static void minimize_clue_set(int *board, int w, int h, random_state *rs)
+{
+    const int sz = w * h;
+    int *shuf = snewn(sz, int), i;
+    int *dsf, *next;
+
+    for (i = 0; i < sz; ++i) shuf[i] = i;
+    shuffle(shuf, sz, sizeof (int), rs);
+
+    /*
+     * First, try to eliminate an entire region at a time if possible,
+     * because inferring the existence of a completely unclued region
+     * is a particularly good aspect of this puzzle type and we want
+     * to encourage it to happen.
+     *
+     * Begin by identifying the regions as linked lists of cells using
+     * the 'next' array.
+     */
+    dsf = make_dsf(NULL, board, w, h);
+    next = snewn(sz, int);
+    for (i = 0; i < sz; ++i) {
+        int j = dsf_canonify(dsf, i);
+        if (i == j) {
+            /* First cell of a region; set next[i] = -1 to indicate
+             * end-of-list. */
+            next[i] = -1;
+        } else {
+            /* Add this cell to a region which already has a
+             * linked-list head, by pointing the canonical element j
+             * at this one, and pointing this one in turn at wherever
+             * j previously pointed. (This should end up with the
+             * elements linked in the order 1,n,n-1,n-2,...,2, which
+             * is a bit weird-looking, but any order is fine.)
+             */
+            assert(j < i);
+            next[i] = next[j];
+            next[j] = i;
+        }
+    }
+
+    /*
+     * Now loop over the grid cells in our shuffled order, and each
+     * time we encounter a region for the first time, try to remove it
+     * all. Then we set next[canonical index] to -2 rather than -1, to
+     * mark it as already tried.
+     *
+     * Doing this in a loop over _cells_, rather than extracting and
+     * shuffling a list of _regions_, is intended to skew the
+     * probabilities towards trying to remove larger regions first
+     * (but without anything as crudely predictable as enforcing that
+     * we _always_ process regions in descending size order). Region
+     * removals might well be mutually exclusive, and larger ghost
+     * regions are more interesting, so we want to bias towards them
+     * if we can.
+     */
+    for (i = 0; i < sz; ++i) {
+        int j = dsf_canonify(dsf, shuf[i]);
+        if (next[j] != -2) {
+            int tmp = board[j];
+            int k;
+
+            /* Blank out the whole thing. */
+            for (k = j; k >= 0; k = next[k])
+                board[k] = EMPTY;
+
+            if (!solver(board, w, h, NULL)) {
+                /* Wasn't still solvable; reinstate it all */
+                for (k = j; k >= 0; k = next[k])
+                    board[k] = tmp;
+            }
+
+            /* Either way, don't try this region again. */
+            next[j] = -2;
+        }
+    }
+    sfree(next);
+    sfree(dsf);
+
+    /*
+     * Now go through individual cells, in the same shuffled order,
+     * and try to remove each one by itself.
+     */
+    for (i = 0; i < sz; ++i) {
+        int tmp = board[shuf[i]];
+        board[shuf[i]] = EMPTY;
+        if (!solver(board, w, h, NULL)) board[shuf[i]] = tmp;
+    }
+
+    sfree(shuf);
+}
+
+static int encode_run(char *buffer, int run)
+{
+    int i = 0;
+    for (; run > 26; run -= 26)
+        buffer[i++] = 'z';
+    if (run)
+        buffer[i++] = 'a' - 1 + run;
+    return i;
+}
+
+static char *new_game_desc(const game_params *params, random_state *rs,
+                           char **aux, int interactive)
+{
+    const int w = params->w, h = params->h, sz = w * h;
+    int *board = snewn(sz, int), i, j, run;
+    char *description = snewn(sz + 1, char);
+
+    make_board(board, w, h, rs);
+    minimize_clue_set(board, w, h, rs);
+
+    for (run = j = i = 0; i < sz; ++i) {
+        assert(board[i] >= 0);
+        assert(board[i] < 10);
+        if (board[i] == 0) {
+            ++run;
+        } else {
+            j += encode_run(description + j, run);
+            run = 0;
+            description[j++] = board[i] + '0';
+        }
+    }
+    j += encode_run(description + j, run);
+    description[j++] = '\0';
+
+    sfree(board);
+
+    return sresize(description, j, char);
+}
+
+static char *validate_desc(const game_params *params, const char *desc)
+{
+    const int sz = params->w * params->h;
+    const char m = '0' + max(max(params->w, params->h), 3);
+    int area;
+
+    for (area = 0; *desc; ++desc) {
+        if (*desc >= 'a' && *desc <= 'z') area += *desc - 'a' + 1;
+        else if (*desc >= '0' && *desc <= m) ++area;
+        else {
+            static char s[] =  "Invalid character '%""' in game description";
+            int n = sprintf(s, "Invalid character '%1c' in game description",
+                            *desc);
+            assert(n + 1 <= lenof(s)); /* +1 for the terminating NUL */
+            return s;
+        }
+        if (area > sz) return "Too much data to fit in grid";
+    }
+    return (area < sz) ? "Not enough data to fill grid" : NULL;
+}
+
+static game_state *new_game(midend *me, const game_params *params,
+                            const char *desc)
+{
+    game_state *state = snew(game_state);
+    int sz = params->w * params->h;
+    int i;
+
+    state->cheated = state->completed = FALSE;
+    state->shared = snew(struct shared_state);
+    state->shared->refcnt = 1;
+    state->shared->params = *params; /* struct copy */
+    state->shared->clues = snewn(sz, int);
+
+    for (i = 0; *desc; ++desc) {
+        if (*desc >= 'a' && *desc <= 'z') {
+            int j = *desc - 'a' + 1;
+            assert(i + j <= sz);
+            for (; j; --j) state->shared->clues[i++] = 0;
+        } else state->shared->clues[i++] = *desc - '0';
+    }
+    state->board = memdup(state->shared->clues, sz, sizeof (int));
+
+    return state;
+}
+
+static game_state *dup_game(const game_state *state)
+{
+    const int sz = state->shared->params.w * state->shared->params.h;
+    game_state *ret = snew(game_state);
+
+    ret->board = memdup(state->board, sz, sizeof (int));
+    ret->shared = state->shared;
+    ret->cheated = state->cheated;
+    ret->completed = state->completed;
+    ++ret->shared->refcnt;
+
+    return ret;
+}
+
+static void free_game(game_state *state)
+{
+    assert(state);
+    sfree(state->board);
+    if (--state->shared->refcnt == 0) {
+        sfree(state->shared->clues);
+        sfree(state->shared);
+    }
+    sfree(state);
+}
+
+static char *solve_game(const game_state *state, const game_state *currstate,
+                        const char *aux, char **error)
+{
+    if (aux == NULL) {
+        const int w = state->shared->params.w;
+        const int h = state->shared->params.h;
+        char *new_aux;
+        if (!solver(state->board, w, h, &new_aux))
+            *error = "Sorry, I couldn't find a solution";
+        return new_aux;
+    }
+    return dupstr(aux);
+}
+
+/*****************************************************************************
+ * USER INTERFACE STATE AND ACTION                                           *
+ *****************************************************************************/
+
+struct game_ui {
+    int *sel; /* w*h highlighted squares, or NULL */
+    int cur_x, cur_y, cur_visible, keydragging;
+};
+
+static game_ui *new_ui(const game_state *state)
+{
+    game_ui *ui = snew(game_ui);
+
+    ui->sel = NULL;
+    ui->cur_x = ui->cur_y = ui->cur_visible = ui->keydragging = 0;
+
+    return ui;
+}
+
+static void free_ui(game_ui *ui)
+{
+    if (ui->sel)
+        sfree(ui->sel);
+    sfree(ui);
+}
+
+static char *encode_ui(const game_ui *ui)
+{
+    return NULL;
+}
+
+static void decode_ui(game_ui *ui, const char *encoding)
+{
+}
+
+static void game_changed_state(game_ui *ui, const game_state *oldstate,
+                               const game_state *newstate)
+{
+    /* Clear any selection */
+    if (ui->sel) {
+        sfree(ui->sel);
+        ui->sel = NULL;
+    }
+    ui->keydragging = FALSE;
+}
+
+#define PREFERRED_TILE_SIZE 32
+#define TILE_SIZE (ds->tilesize)
+#define BORDER (TILE_SIZE / 2)
+#define BORDER_WIDTH (max(TILE_SIZE / 32, 1))
+
+struct game_drawstate {
+    struct game_params params;
+    int tilesize;
+    int started;
+    int *v, *flags;
+    int *dsf_scratch, *border_scratch;
+};
+
+static char *interpret_move(const game_state *state, game_ui *ui,
+                            const game_drawstate *ds,
+                            int x, int y, int button)
+{
+    const int w = state->shared->params.w;
+    const int h = state->shared->params.h;
+
+    const int tx = (x + TILE_SIZE - BORDER) / TILE_SIZE - 1;
+    const int ty = (y + TILE_SIZE - BORDER) / TILE_SIZE - 1;
+
+    char *move = NULL;
+    int i;
+
+    assert(ui);
+    assert(ds);
+
+    button &= ~MOD_MASK;
+
+    if (button == LEFT_BUTTON || button == LEFT_DRAG) {
+        /* A left-click anywhere will clear the current selection. */
+        if (button == LEFT_BUTTON) {
+            if (ui->sel) {
+                sfree(ui->sel);
+                ui->sel = NULL;
+            }
+        }
+        if (tx >= 0 && tx < w && ty >= 0 && ty < h) {
+            if (!ui->sel) {
+                ui->sel = snewn(w*h, int);
+                memset(ui->sel, 0, w*h*sizeof(int));
+            }
+            if (!state->shared->clues[w*ty+tx])
+                ui->sel[w*ty+tx] = 1;
+        }
+        ui->cur_visible = 0;
+        return ""; /* redraw */
+    }
+
+    if (IS_CURSOR_MOVE(button)) {
+        ui->cur_visible = 1;
+        move_cursor(button, &ui->cur_x, &ui->cur_y, w, h, 0);
+        if (ui->keydragging) goto select_square;
+        return "";
+    }
+    if (button == CURSOR_SELECT) {
+        if (!ui->cur_visible) {
+            ui->cur_visible = 1;
+            return "";
+        }
+        ui->keydragging = !ui->keydragging;
+        if (!ui->keydragging) return "";
+
+      select_square:
+        if (!ui->sel) {
+            ui->sel = snewn(w*h, int);
+            memset(ui->sel, 0, w*h*sizeof(int));
+        }
+        if (!state->shared->clues[w*ui->cur_y + ui->cur_x])
+            ui->sel[w*ui->cur_y + ui->cur_x] = 1;
+        return "";
+    }
+    if (button == CURSOR_SELECT2) {
+        if (!ui->cur_visible) {
+            ui->cur_visible = 1;
+            return "";
+        }
+        if (!ui->sel) {
+            ui->sel = snewn(w*h, int);
+            memset(ui->sel, 0, w*h*sizeof(int));
+        }
+        ui->keydragging = FALSE;
+        if (!state->shared->clues[w*ui->cur_y + ui->cur_x])
+            ui->sel[w*ui->cur_y + ui->cur_x] ^= 1;
+        for (i = 0; i < w*h && !ui->sel[i]; i++);
+        if (i == w*h) {
+            sfree(ui->sel);
+            ui->sel = NULL;
+        }
+        return "";
+    }
+
+    if (button == '\b' || button == 27) {
+        sfree(ui->sel);
+        ui->sel = NULL;
+        ui->keydragging = FALSE;
+        return "";
+    }
+
+    if (button < '0' || button > '9') return NULL;
+    button -= '0';
+    if (button > (w == 2 && h == 2 ? 3 : max(w, h))) return NULL;
+    ui->keydragging = FALSE;
+
+    for (i = 0; i < w*h; i++) {
+        char buf[32];
+        if ((ui->sel && ui->sel[i]) ||
+            (!ui->sel && ui->cur_visible && (w*ui->cur_y+ui->cur_x) == i)) {
+            if (state->shared->clues[i] != 0) continue; /* in case cursor is on clue */
+            if (state->board[i] != button) {
+                sprintf(buf, "%s%d", move ? "," : "", i);
+                if (move) {
+                    move = srealloc(move, strlen(move)+strlen(buf)+1);
+                    strcat(move, buf);
+                } else {
+                    move = smalloc(strlen(buf)+1);
+                    strcpy(move, buf);
+                }
+            }
+        }
+    }
+    if (move) {
+        char buf[32];
+        sprintf(buf, "_%d", button);
+        move = srealloc(move, strlen(move)+strlen(buf)+1);
+        strcat(move, buf);
+    }
+    if (!ui->sel) return move ? move : NULL;
+    sfree(ui->sel);
+    ui->sel = NULL;
+    /* Need to update UI at least, as we cleared the selection */
+    return move ? move : "";
+}
+
+static game_state *execute_move(const game_state *state, const char *move)
+{
+    game_state *new_state = NULL;
+    const int sz = state->shared->params.w * state->shared->params.h;
+
+    if (*move == 's') {
+        int i = 0;
+        new_state = dup_game(state);
+        for (++move; i < sz; ++i) new_state->board[i] = move[i] - '0';
+        new_state->cheated = TRUE;
+    } else {
+        int value;
+        char *endptr, *delim = strchr(move, '_');
+        if (!delim) goto err;
+        value = strtol(delim+1, &endptr, 0);
+        if (*endptr || endptr == delim+1) goto err;
+        if (value < 0 || value > 9) goto err;
+        new_state = dup_game(state);
+        while (*move) {
+            const int i = strtol(move, &endptr, 0);
+            if (endptr == move) goto err;
+            if (i < 0 || i >= sz) goto err;
+            new_state->board[i] = value;
+            if (*endptr == '_') break;
+            if (*endptr != ',') goto err;
+            move = endptr + 1;
+        }
+    }
+
+    /*
+     * Check for completion.
+     */
+    if (!new_state->completed) {
+        const int w = new_state->shared->params.w;
+        const int h = new_state->shared->params.h;
+        const int sz = w * h;
+        int *dsf = make_dsf(NULL, new_state->board, w, h);
+        int i;
+        for (i = 0; i < sz && new_state->board[i] == dsf_size(dsf, i); ++i);
+        sfree(dsf);
+        if (i == sz)
+            new_state->completed = TRUE;
+    }
+
+    return new_state;
+
+err:
+    if (new_state) free_game(new_state);
+    return NULL;
+}
+
+/* ----------------------------------------------------------------------
+ * Drawing routines.
+ */
+
+#define FLASH_TIME 0.4F
+
+#define COL_CLUE COL_GRID
+enum {
+    COL_BACKGROUND,
+    COL_GRID,
+    COL_HIGHLIGHT,
+    COL_CORRECT,
+    COL_ERROR,
+    COL_USER,
+    COL_CURSOR,
+    NCOLOURS
+};
+
+static void game_compute_size(const game_params *params, int tilesize,
+                              int *x, int *y)
+{
+    *x = (params->w + 1) * tilesize;
+    *y = (params->h + 1) * tilesize;
+}
+
+static void game_set_size(drawing *dr, game_drawstate *ds,
+                          const game_params *params, int tilesize)
+{
+    ds->tilesize = tilesize;
+}
+
+static float *game_colours(frontend *fe, int *ncolours)
+{
+    float *ret = snewn(3 * NCOLOURS, float);
+
+    frontend_default_colour(fe, &ret[COL_BACKGROUND * 3]);
+
+    ret[COL_GRID * 3 + 0] = 0.0F;
+    ret[COL_GRID * 3 + 1] = 0.0F;
+    ret[COL_GRID * 3 + 2] = 0.0F;
+
+    ret[COL_HIGHLIGHT * 3 + 0] = 0.85F * ret[COL_BACKGROUND * 3 + 0];
+    ret[COL_HIGHLIGHT * 3 + 1] = 0.85F * ret[COL_BACKGROUND * 3 + 1];
+    ret[COL_HIGHLIGHT * 3 + 2] = 0.85F * ret[COL_BACKGROUND * 3 + 2];
+
+    ret[COL_CORRECT * 3 + 0] = 0.9F * ret[COL_BACKGROUND * 3 + 0];
+    ret[COL_CORRECT * 3 + 1] = 0.9F * ret[COL_BACKGROUND * 3 + 1];
+    ret[COL_CORRECT * 3 + 2] = 0.9F * ret[COL_BACKGROUND * 3 + 2];
+
+    ret[COL_CURSOR * 3 + 0] = 0.5F * ret[COL_BACKGROUND * 3 + 0];
+    ret[COL_CURSOR * 3 + 1] = 0.5F * ret[COL_BACKGROUND * 3 + 1];
+    ret[COL_CURSOR * 3 + 2] = 0.5F * ret[COL_BACKGROUND * 3 + 2];
+
+    ret[COL_ERROR * 3 + 0] = 1.0F;
+    ret[COL_ERROR * 3 + 1] = 0.85F * ret[COL_BACKGROUND * 3 + 1];
+    ret[COL_ERROR * 3 + 2] = 0.85F * ret[COL_BACKGROUND * 3 + 2];
+
+    ret[COL_USER * 3 + 0] = 0.0F;
+    ret[COL_USER * 3 + 1] = 0.6F * ret[COL_BACKGROUND * 3 + 1];
+    ret[COL_USER * 3 + 2] = 0.0F;
+
+    *ncolours = NCOLOURS;
+    return ret;
+}
+
+static game_drawstate *game_new_drawstate(drawing *dr, const game_state *state)
+{
+    struct game_drawstate *ds = snew(struct game_drawstate);
+    int i;
+
+    ds->tilesize = PREFERRED_TILE_SIZE;
+    ds->started = 0;
+    ds->params = state->shared->params;
+    ds->v = snewn(ds->params.w * ds->params.h, int);
+    ds->flags = snewn(ds->params.w * ds->params.h, int);
+    for (i = 0; i < ds->params.w * ds->params.h; i++)
+        ds->v[i] = ds->flags[i] = -1;
+    ds->border_scratch = snewn(ds->params.w * ds->params.h, int);
+    ds->dsf_scratch = NULL;
+
+    return ds;
+}
+
+static void game_free_drawstate(drawing *dr, game_drawstate *ds)
+{
+    sfree(ds->v);
+    sfree(ds->flags);
+    sfree(ds->border_scratch);
+    sfree(ds->dsf_scratch);
+    sfree(ds);
+}
+
+#define BORDER_U   0x001
+#define BORDER_D   0x002
+#define BORDER_L   0x004
+#define BORDER_R   0x008
+#define BORDER_UR  0x010
+#define BORDER_DR  0x020
+#define BORDER_UL  0x040
+#define BORDER_DL  0x080
+#define HIGH_BG    0x100
+#define CORRECT_BG 0x200
+#define ERROR_BG   0x400
+#define USER_COL   0x800
+#define CURSOR_SQ 0x1000
+
+static void draw_square(drawing *dr, game_drawstate *ds, int x, int y,
+                        int n, int flags)
+{
+    assert(dr);
+    assert(ds);
+
+    /*
+     * Clip to the grid square.
+     */
+    clip(dr, BORDER + x*TILE_SIZE, BORDER + y*TILE_SIZE,
+         TILE_SIZE, TILE_SIZE);
+
+    /*
+     * Clear the square.
+     */
+    draw_rect(dr,
+              BORDER + x*TILE_SIZE,
+              BORDER + y*TILE_SIZE,
+              TILE_SIZE,
+              TILE_SIZE,
+              (flags & HIGH_BG ? COL_HIGHLIGHT :
+               flags & ERROR_BG ? COL_ERROR :
+               flags & CORRECT_BG ? COL_CORRECT : COL_BACKGROUND));
+
+    /*
+     * Draw the grid lines.
+     */
+    draw_line(dr, BORDER + x*TILE_SIZE, BORDER + y*TILE_SIZE,
+              BORDER + (x+1)*TILE_SIZE, BORDER + y*TILE_SIZE, COL_GRID);
+    draw_line(dr, BORDER + x*TILE_SIZE, BORDER + y*TILE_SIZE,
+              BORDER + x*TILE_SIZE, BORDER + (y+1)*TILE_SIZE, COL_GRID);
+
+    /*
+     * Draw the number.
+     */
+    if (n) {
+        char buf[2];
+        buf[0] = n + '0';
+        buf[1] = '\0';
+        draw_text(dr,
+                  (x + 1) * TILE_SIZE,
+                  (y + 1) * TILE_SIZE,
+                  FONT_VARIABLE,
+                  TILE_SIZE / 2,
+                  ALIGN_VCENTRE | ALIGN_HCENTRE,
+                  flags & USER_COL ? COL_USER : COL_CLUE,
+                  buf);
+    }
+
+    /*
+     * Draw bold lines around the borders.
+     */
+    if (flags & BORDER_L)
+        draw_rect(dr,
+                  BORDER + x*TILE_SIZE + 1,
+                  BORDER + y*TILE_SIZE + 1,
+                  BORDER_WIDTH,
+                  TILE_SIZE - 1,
+                  COL_GRID);
+    if (flags & BORDER_U)
+        draw_rect(dr,
+                  BORDER + x*TILE_SIZE + 1,
+                  BORDER + y*TILE_SIZE + 1,
+                  TILE_SIZE - 1,
+                  BORDER_WIDTH,
+                  COL_GRID);
+    if (flags & BORDER_R)
+        draw_rect(dr,
+                  BORDER + (x+1)*TILE_SIZE - BORDER_WIDTH,
+                  BORDER + y*TILE_SIZE + 1,
+                  BORDER_WIDTH,
+                  TILE_SIZE - 1,
+                  COL_GRID);
+    if (flags & BORDER_D)
+        draw_rect(dr,
+                  BORDER + x*TILE_SIZE + 1,
+                  BORDER + (y+1)*TILE_SIZE - BORDER_WIDTH,
+                  TILE_SIZE - 1,
+                  BORDER_WIDTH,
+                  COL_GRID);
+    if (flags & BORDER_UL)
+        draw_rect(dr,
+                  BORDER + x*TILE_SIZE + 1,
+                  BORDER + y*TILE_SIZE + 1,
+                  BORDER_WIDTH,
+                  BORDER_WIDTH,
+                  COL_GRID);
+    if (flags & BORDER_UR)
+        draw_rect(dr,
+                  BORDER + (x+1)*TILE_SIZE - BORDER_WIDTH,
+                  BORDER + y*TILE_SIZE + 1,
+                  BORDER_WIDTH,
+                  BORDER_WIDTH,
+                  COL_GRID);
+    if (flags & BORDER_DL)
+        draw_rect(dr,
+                  BORDER + x*TILE_SIZE + 1,
+                  BORDER + (y+1)*TILE_SIZE - BORDER_WIDTH,
+                  BORDER_WIDTH,
+                  BORDER_WIDTH,
+                  COL_GRID);
+    if (flags & BORDER_DR)
+        draw_rect(dr,
+                  BORDER + (x+1)*TILE_SIZE - BORDER_WIDTH,
+                  BORDER + (y+1)*TILE_SIZE - BORDER_WIDTH,
+                  BORDER_WIDTH,
+                  BORDER_WIDTH,
+                  COL_GRID);
+
+    if (flags & CURSOR_SQ) {
+        int coff = TILE_SIZE/8;
+        draw_rect_outline(dr,
+                          BORDER + x*TILE_SIZE + coff,
+                          BORDER + y*TILE_SIZE + coff,
+                          TILE_SIZE - coff*2,
+                          TILE_SIZE - coff*2,
+                          COL_CURSOR);
+    }
+
+    unclip(dr);
+
+    draw_update(dr,
+                BORDER + x*TILE_SIZE,
+                BORDER + y*TILE_SIZE,
+                TILE_SIZE,
+                TILE_SIZE);
+}
+
+static void draw_grid(drawing *dr, game_drawstate *ds, const game_state *state,
+                      const game_ui *ui, int flashy, int borders, int shading)
+{
+    const int w = state->shared->params.w;
+    const int h = state->shared->params.h;
+    int x;
+    int y;
+
+    /*
+     * Build a dsf for the board in its current state, to use for
+     * highlights and hints.
+     */
+    ds->dsf_scratch = make_dsf(ds->dsf_scratch, state->board, w, h);
+
+    /*
+     * Work out where we're putting borders between the cells.
+     */
+    for (y = 0; y < w*h; y++)
+        ds->border_scratch[y] = 0;
+
+    for (y = 0; y < h; y++)
+        for (x = 0; x < w; x++) {
+            int dx, dy;
+            int v1, s1, v2, s2;
+
+            for (dx = 0; dx <= 1; dx++) {
+                int border = FALSE;
+
+                dy = 1 - dx;
+
+                if (x+dx >= w || y+dy >= h)
+                    continue;
+
+                v1 = state->board[y*w+x];
+                v2 = state->board[(y+dy)*w+(x+dx)];
+                s1 = dsf_size(ds->dsf_scratch, y*w+x);
+                s2 = dsf_size(ds->dsf_scratch, (y+dy)*w+(x+dx));
+
+                /*
+                 * We only ever draw a border between two cells if
+                 * they don't have the same contents.
+                 */
+                if (v1 != v2) {
+                    /*
+                     * But in that situation, we don't always draw
+                     * a border. We do if the two cells both
+                     * contain actual numbers...
+                     */
+                    if (v1 && v2)
+                        border = TRUE;
+
+                    /*
+                     * ... or if at least one of them is a
+                     * completed or overfull omino.
+                     */
+                    if (v1 && s1 >= v1)
+                        border = TRUE;
+                    if (v2 && s2 >= v2)
+                        border = TRUE;
+                }
+
+                if (border)
+                    ds->border_scratch[y*w+x] |= (dx ? 1 : 2);
+            }
+        }
+
+    /*
+     * Actually do the drawing.
+     */
+    for (y = 0; y < h; ++y)
+        for (x = 0; x < w; ++x) {
+            /*
+             * Determine what we need to draw in this square.
+             */
+            int i = y*w+x, v = state->board[i];
+            int flags = 0;
+
+            if (flashy || !shading) {
+                /* clear all background flags */
+            } else if (ui && ui->sel && ui->sel[i]) {
+                flags |= HIGH_BG;
+            } else if (v) {
+                int size = dsf_size(ds->dsf_scratch, i);
+                if (size == v)
+                    flags |= CORRECT_BG;
+                else if (size > v)
+                    flags |= ERROR_BG;
+                else {
+                    int rt = dsf_canonify(ds->dsf_scratch, i), j;
+                    for (j = 0; j < w*h; ++j) {
+                        int k;
+                        if (dsf_canonify(ds->dsf_scratch, j) != rt) continue;
+                        for (k = 0; k < 4; ++k) {
+                            const int xx = j % w + dx[k], yy = j / w + dy[k];
+                            if (xx >= 0 && xx < w && yy >= 0 && yy < h &&
+                                state->board[yy*w + xx] == EMPTY)
+                                goto noflag;
+                        }
+                    }
+                    flags |= ERROR_BG;
+                  noflag:
+                    ;
+                }
+            }
+            if (ui && ui->cur_visible && x == ui->cur_x && y == ui->cur_y)
+              flags |= CURSOR_SQ;
+
+            /*
+             * Borders at the very edges of the grid are
+             * independent of the `borders' flag.
+             */
+            if (x == 0)
+                flags |= BORDER_L;
+            if (y == 0)
+                flags |= BORDER_U;
+            if (x == w-1)
+                flags |= BORDER_R;
+            if (y == h-1)
+                flags |= BORDER_D;
+
+            if (borders) {
+                if (x == 0 || (ds->border_scratch[y*w+(x-1)] & 1))
+                    flags |= BORDER_L;
+                if (y == 0 || (ds->border_scratch[(y-1)*w+x] & 2))
+                    flags |= BORDER_U;
+                if (x == w-1 || (ds->border_scratch[y*w+x] & 1))
+                    flags |= BORDER_R;
+                if (y == h-1 || (ds->border_scratch[y*w+x] & 2))
+                    flags |= BORDER_D;
+
+                if (y > 0 && x > 0 && (ds->border_scratch[(y-1)*w+(x-1)]))
+                    flags |= BORDER_UL;
+                if (y > 0 && x < w-1 &&
+                    ((ds->border_scratch[(y-1)*w+x] & 1) ||
+                     (ds->border_scratch[(y-1)*w+(x+1)] & 2)))
+                    flags |= BORDER_UR;
+                if (y < h-1 && x > 0 &&
+                    ((ds->border_scratch[y*w+(x-1)] & 2) ||
+                     (ds->border_scratch[(y+1)*w+(x-1)] & 1)))
+                    flags |= BORDER_DL;
+                if (y < h-1 && x < w-1 &&
+                    ((ds->border_scratch[y*w+(x+1)] & 2) ||
+                     (ds->border_scratch[(y+1)*w+x] & 1)))
+                    flags |= BORDER_DR;
+            }
+
+            if (!state->shared->clues[y*w+x])
+                flags |= USER_COL;
+
+            if (ds->v[y*w+x] != v || ds->flags[y*w+x] != flags) {
+                draw_square(dr, ds, x, y, v, flags);
+                ds->v[y*w+x] = v;
+                ds->flags[y*w+x] = flags;
+            }
+        }
+}
+
+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)
+{
+    const int w = state->shared->params.w;
+    const int h = state->shared->params.h;
+
+    const int flashy =
+        flashtime > 0 &&
+        (flashtime <= FLASH_TIME/3 || flashtime >= FLASH_TIME*2/3);
+
+    if (!ds->started) {
+        /*
+         * The initial contents of the window are not guaranteed and
+         * can vary with front ends. To be on the safe side, all games
+         * should start by drawing a big background-colour rectangle
+         * covering the whole window.
+         */
+        draw_rect(dr, 0, 0, w*TILE_SIZE + 2*BORDER, h*TILE_SIZE + 2*BORDER,
+                  COL_BACKGROUND);
+
+        /*
+         * Smaller black rectangle which is the main grid.
+         */
+        draw_rect(dr, BORDER - BORDER_WIDTH, BORDER - BORDER_WIDTH,
+                  w*TILE_SIZE + 2*BORDER_WIDTH + 1,
+                  h*TILE_SIZE + 2*BORDER_WIDTH + 1,
+                  COL_GRID);
+
+        draw_update(dr, 0, 0, w*TILE_SIZE + 2*BORDER, h*TILE_SIZE + 2*BORDER);
+
+        ds->started = TRUE;
+    }
+
+    draw_grid(dr, ds, state, ui, flashy, TRUE, TRUE);
+}
+
+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(const game_state *oldstate,
+                               const game_state *newstate, int dir, game_ui *ui)
+{
+    assert(oldstate);
+    assert(newstate);
+    assert(newstate->shared);
+    assert(oldstate->shared == newstate->shared);
+    if (!oldstate->completed && newstate->completed &&
+        !oldstate->cheated && !newstate->cheated)
+        return FLASH_TIME;
+    return 0.0F;
+}
+
+static int game_status(const game_state *state)
+{
+    return state->completed ? +1 : 0;
+}
+
+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)
+{
+    const int w = state->shared->params.w;
+    const int h = state->shared->params.h;
+    int c, i, borders;
+
+    /* Ick: fake up `ds->tilesize' for macro expansion purposes */
+    game_drawstate *ds = game_new_drawstate(dr, state);
+    game_set_size(dr, ds, NULL, tilesize);
+
+    c = print_mono_colour(dr, 1); assert(c == COL_BACKGROUND);
+    c = print_mono_colour(dr, 0); assert(c == COL_GRID);
+    c = print_mono_colour(dr, 1); assert(c == COL_HIGHLIGHT);
+    c = print_mono_colour(dr, 1); assert(c == COL_CORRECT);
+    c = print_mono_colour(dr, 1); assert(c == COL_ERROR);
+    c = print_mono_colour(dr, 0); assert(c == COL_USER);
+
+    /*
+     * Border.
+     */
+    draw_rect(dr, BORDER - BORDER_WIDTH, BORDER - BORDER_WIDTH,
+              w*TILE_SIZE + 2*BORDER_WIDTH + 1,
+              h*TILE_SIZE + 2*BORDER_WIDTH + 1,
+              COL_GRID);
+
+    /*
+     * We'll draw borders between the ominoes iff the grid is not
+     * pristine. So scan it to see if it is.
+     */
+    borders = FALSE;
+    for (i = 0; i < w*h; i++)
+        if (state->board[i] && !state->shared->clues[i])
+            borders = TRUE;
+
+    /*
+     * Draw grid.
+     */
+    print_line_width(dr, TILE_SIZE / 64);
+    draw_grid(dr, ds, state, NULL, FALSE, borders, FALSE);
+
+    /*
+     * Clean up.
+     */
+    game_free_drawstate(dr, ds);
+}
+
+#ifdef COMBINED
+#define thegame filling
+#endif
+
+const struct game thegame = {
+    "Filling", "games.filling", "filling",
+    default_params,
+    game_fetch_preset, NULL,
+    decode_params,
+    encode_params,
+    free_params,
+    dup_params,
+    TRUE, game_configure, custom_params,
+    validate_params,
+    new_game_desc,
+    validate_desc,
+    new_game,
+    dup_game,
+    free_game,
+    TRUE, solve_game,
+    TRUE, game_can_format_as_text_now, game_text_format,
+    new_ui,
+    free_ui,
+    encode_ui,
+    decode_ui,
+    game_changed_state,
+    interpret_move,
+    execute_move,
+    PREFERRED_TILE_SIZE, game_compute_size, game_set_size,
+    game_colours,
+    game_new_drawstate,
+    game_free_drawstate,
+    game_redraw,
+    game_anim_length,
+    game_flash_length,
+    game_status,
+    TRUE, FALSE, game_print_size, game_print,
+    FALSE,                                 /* wants_statusbar */
+    FALSE, game_timing_state,
+    REQUIRE_NUMPAD,                    /* flags */
+};
+
+#ifdef STANDALONE_SOLVER /* solver? hah! */
+
+int main(int argc, char **argv) {
+    while (*++argv) {
+        game_params *params;
+        game_state *state;
+        char *par;
+        char *desc;
+
+        for (par = desc = *argv; *desc != '\0' && *desc != ':'; ++desc);
+        if (*desc == '\0') {
+            fprintf(stderr, "bad puzzle id: %s", par);
+            continue;
+        }
+
+        *desc++ = '\0';
+
+        params = snew(game_params);
+        decode_params(params, par);
+        state = new_game(NULL, params, desc);
+        if (solver(state->board, params->w, params->h, NULL))
+            printf("%s:%s: solvable\n", par, desc);
+        else
+            printf("%s:%s: not solvable\n", par, desc);
+    }
+    return 0;
+}
+
+#endif
+
+/* vim: set shiftwidth=4 tabstop=8: */