Enhance Filling's solver to handle large ghost regions.

[sgt-puzzles.git] / map.c

/*
 * map.c: Game involving four-colouring a map.
 */

/*
 * TODO:
 * 
 *  - clue marking
 *  - better four-colouring algorithm?
 */

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>
#include <ctype.h>
#include <math.h>

#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 = FALSE;
#elif defined SOLVER_DIAGNOSTICS
#define verbose TRUE
#endif

/*
 * I don't seriously anticipate wanting to change the number of
 * colours used in this game, but it doesn't cost much to use a
 * #define just in case :-)
 */
#define FOUR 4
#define THREE (FOUR-1)
#define FIVE (FOUR+1)
#define SIX (FOUR+2)

/*
 * Ghastly run-time configuration option, just for Gareth (again).
 */
static int flash_type = -1;
static float flash_length;

/*
 * Difficulty levels. I do some macro ickery here to ensure that my
 * enum and the various forms of my name list always match up.
 */
#define DIFFLIST(A) \
    A(EASY,Easy,e) \
    A(NORMAL,Normal,n) \
    A(HARD,Hard,h) \
    A(RECURSE,Unreasonable,u)
#define ENUM(upper,title,lower) DIFF_ ## upper,
#define TITLE(upper,title,lower) #title,
#define ENCODE(upper,title,lower) #lower
#define CONFIG(upper,title,lower) ":" #title
enum { DIFFLIST(ENUM) DIFFCOUNT };
static char const *const map_diffnames[] = { DIFFLIST(TITLE) };
static char const map_diffchars[] = DIFFLIST(ENCODE);
#define DIFFCONFIG DIFFLIST(CONFIG)

enum { TE, BE, LE, RE };               /* top/bottom/left/right edges */

enum {
    COL_BACKGROUND,
    COL_GRID,
    COL_0, COL_1, COL_2, COL_3,
    COL_ERROR, COL_ERRTEXT,
    NCOLOURS
};

struct game_params {
    int w, h, n, diff;
};

struct map {
    int refcount;
    int *map;
    int *graph;
    int n;
    int ngraph;
    int *immutable;
    int *edgex, *edgey;                /* position of a point on each edge */
    int *regionx, *regiony;            /* position of a point in each region */
};

struct game_state {
    game_params p;
    struct map *map;
    int *colouring, *pencil;
    int completed, cheated;
};

static game_params *default_params(void)
{
    game_params *ret = snew(game_params);

#ifdef PORTRAIT_SCREEN
    ret->w = 16;
    ret->h = 18;
#else
    ret->w = 20;
    ret->h = 15;
#endif
    ret->n = 30;
    ret->diff = DIFF_NORMAL;

    return ret;
}

static const struct game_params map_presets[] = {
#ifdef PORTRAIT_SCREEN
    {16, 18, 30, DIFF_EASY},
    {16, 18, 30, DIFF_NORMAL},
    {16, 18, 30, DIFF_HARD},
    {16, 18, 30, DIFF_RECURSE},
    {25, 30, 75, DIFF_NORMAL},
    {25, 30, 75, DIFF_HARD},
#else
    {20, 15, 30, DIFF_EASY},
    {20, 15, 30, DIFF_NORMAL},
    {20, 15, 30, DIFF_HARD},
    {20, 15, 30, DIFF_RECURSE},
    {30, 25, 75, DIFF_NORMAL},
    {30, 25, 75, DIFF_HARD},
#endif
};

static int game_fetch_preset(int i, char **name, game_params **params)
{
    game_params *ret;
    char str[80];

    if (i < 0 || i >= lenof(map_presets))
        return FALSE;

    ret = snew(game_params);
    *ret = map_presets[i];

    sprintf(str, "%dx%d, %d regions, %s", ret->w, ret->h, ret->n,
            map_diffnames[ret->diff]);

    *name = dupstr(str);
    *params = ret;
    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;                    /* structure copy */
    return ret;
}

static void decode_params(game_params *params, char const *string)
{
    char const *p = string;

    params->w = atoi(p);
    while (*p && isdigit((unsigned char)*p)) p++;
    if (*p == 'x') {
        p++;
        params->h = atoi(p);
        while (*p && isdigit((unsigned char)*p)) p++;
    } else {
        params->h = params->w;
    }
    if (*p == 'n') {
        p++;
        params->n = atoi(p);
        while (*p && (*p == '.' || isdigit((unsigned char)*p))) p++;
    } else {
        params->n = params->w * params->h / 8;
    }
    if (*p == 'd') {
        int i;
        p++;
        for (i = 0; i < DIFFCOUNT; i++)
            if (*p == map_diffchars[i])
                params->diff = i;
        if (*p) p++;
    }
}

static char *encode_params(const game_params *params, int full)
{
    char ret[400];

    sprintf(ret, "%dx%dn%d", params->w, params->h, params->n);
    if (full)
        sprintf(ret + strlen(ret), "d%c", map_diffchars[params->diff]);

    return dupstr(ret);
}

static config_item *game_configure(const game_params *params)
{
    config_item *ret;
    char buf[80];

    ret = snewn(5, 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 = "Regions";
    ret[2].type = C_STRING;
    sprintf(buf, "%d", params->n);
    ret[2].sval = dupstr(buf);
    ret[2].ival = 0;

    ret[3].name = "Difficulty";
    ret[3].type = C_CHOICES;
    ret[3].sval = DIFFCONFIG;
    ret[3].ival = params->diff;

    ret[4].name = NULL;
    ret[4].type = C_END;
    ret[4].sval = NULL;
    ret[4].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);
    ret->n = atoi(cfg[2].sval);
    ret->diff = cfg[3].ival;

    return ret;
}

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 two";
    if (params->n < 5)
        return "Must have at least five regions";
    if (params->n > params->w * params->h)
        return "Too many regions to fit in grid";
    return NULL;
}

/* ----------------------------------------------------------------------
 * Cumulative frequency table functions.
 */

/*
 * Initialise a cumulative frequency table. (Hardly worth writing
 * this function; all it does is to initialise everything in the
 * array to zero.)
 */
static void cf_init(int *table, int n)
{
    int i;

    for (i = 0; i < n; i++)
        table[i] = 0;
}

/*
 * Increment the count of symbol `sym' by `count'.
 */
static void cf_add(int *table, int n, int sym, int count)
{
    int bit;

    bit = 1;
    while (sym != 0) {
        if (sym & bit) {
            table[sym] += count;
            sym &= ~bit;
        }
        bit <<= 1;
    }

    table[0] += count;
}

/*
 * Cumulative frequency lookup: return the total count of symbols
 * with value less than `sym'.
 */
static int cf_clookup(int *table, int n, int sym)
{
    int bit, index, limit, count;

    if (sym == 0)
        return 0;

    assert(0 < sym && sym <= n);

    count = table[0];                  /* start with the whole table size */

    bit = 1;
    while (bit < n)
        bit <<= 1;

    limit = n;

    while (bit > 0) {
        /*
         * Find the least number with its lowest set bit in this
         * position which is greater than or equal to sym.
         */
        index = ((sym + bit - 1) &~ (bit * 2 - 1)) + bit;

        if (index < limit) {
            count -= table[index];
            limit = index;
        }

        bit >>= 1;
    }

    return count;
}

/*
 * Single frequency lookup: return the count of symbol `sym'.
 */
static int cf_slookup(int *table, int n, int sym)
{
    int count, bit;

    assert(0 <= sym && sym < n);

    count = table[sym];

    for (bit = 1; sym+bit < n && !(sym & bit); bit <<= 1)
        count -= table[sym+bit];

    return count;
}

/*
 * Return the largest symbol index such that the cumulative
 * frequency up to that symbol is less than _or equal to_ count.
 */
static int cf_whichsym(int *table, int n, int count) {
    int bit, sym, top;

    assert(count >= 0 && count < table[0]);

    bit = 1;
    while (bit < n)
        bit <<= 1;

    sym = 0;
    top = table[0];

    while (bit > 0) {
        if (sym+bit < n) {
            if (count >= top - table[sym+bit])
                sym += bit;
            else
                top -= table[sym+bit];
        }

        bit >>= 1;
    }

    return sym;
}

/* ----------------------------------------------------------------------
 * Map generation.
 * 
 * FIXME: this isn't entirely optimal at present, because it
 * inherently prioritises growing the largest region since there
 * are more squares adjacent to it. This acts as a destabilising
 * influence leading to a few large regions and mostly small ones.
 * It might be better to do it some other way.
 */

#define WEIGHT_INCREASED 2             /* for increased perimeter */
#define WEIGHT_DECREASED 4             /* for decreased perimeter */
#define WEIGHT_UNCHANGED 3             /* for unchanged perimeter */

/*
 * Look at a square and decide which colours can be extended into
 * it.
 * 
 * If called with index < 0, it adds together one of
 * WEIGHT_INCREASED, WEIGHT_DECREASED or WEIGHT_UNCHANGED for each
 * colour that has a valid extension (according to the effect that
 * it would have on the perimeter of the region being extended) and
 * returns the overall total.
 * 
 * If called with index >= 0, it returns one of the possible
 * colours depending on the value of index, in such a way that the
 * number of possible inputs which would give rise to a given
 * return value correspond to the weight of that value.
 */
static int extend_options(int w, int h, int n, int *map,
                          int x, int y, int index)
{
    int c, i, dx, dy;
    int col[8];
    int total = 0;

    if (map[y*w+x] >= 0) {
        assert(index < 0);
        return 0;                      /* can't do this square at all */
    }

    /*
     * Fetch the eight neighbours of this square, in order around
     * the square.
     */
    for (dy = -1; dy <= +1; dy++)
        for (dx = -1; dx <= +1; dx++) {
            int index = (dy < 0 ? 6-dx : dy > 0 ? 2+dx : 2*(1+dx));
            if (x+dx >= 0 && x+dx < w && y+dy >= 0 && y+dy < h)
                col[index] = map[(y+dy)*w+(x+dx)];
            else
                col[index] = -1;
        }

    /*
     * Iterate over each colour that might be feasible.
     * 
     * FIXME: this routine currently has O(n) running time. We
     * could turn it into O(FOUR) by only bothering to iterate over
     * the colours mentioned in the four neighbouring squares.
     */

    for (c = 0; c < n; c++) {
        int count, neighbours, runs;

        /*
         * One of the even indices of col (representing the
         * orthogonal neighbours of this square) must be equal to
         * c, or else this square is not adjacent to region c and
         * obviously cannot become an extension of it at this time.
         */
        neighbours = 0;
        for (i = 0; i < 8; i += 2)
            if (col[i] == c)
                neighbours++;
        if (!neighbours)
            continue;

        /*
         * Now we know this square is adjacent to region c. The
         * next question is, would extending it cause the region to
         * become non-simply-connected? If so, we mustn't do it.
         * 
         * We determine this by looking around col to see if we can
         * find more than one separate run of colour c.
         */
        runs = 0;
        for (i = 0; i < 8; i++)
            if (col[i] == c && col[(i+1) & 7] != c)
                runs++;
        if (runs > 1)
            continue;

        assert(runs == 1);

        /*
         * This square is a possibility. Determine its effect on
         * the region's perimeter (computed from the number of
         * orthogonal neighbours - 1 means a perimeter increase, 3
         * a decrease, 2 no change; 4 is impossible because the
         * region would already not be simply connected) and we're
         * done.
         */
        assert(neighbours > 0 && neighbours < 4);
        count = (neighbours == 1 ? WEIGHT_INCREASED :
                 neighbours == 2 ? WEIGHT_UNCHANGED : WEIGHT_DECREASED);

        total += count;
        if (index >= 0 && index < count)
            return c;
        else
            index -= count;
    }

    assert(index < 0);

    return total;
}

static void genmap(int w, int h, int n, int *map, random_state *rs)
{
    int wh = w*h;
    int x, y, i, k;
    int *tmp;

    assert(n <= wh);
    tmp = snewn(wh, int);

    /*
     * Clear the map, and set up `tmp' as a list of grid indices.
     */
    for (i = 0; i < wh; i++) {
        map[i] = -1;
        tmp[i] = i;
    }

    /*
     * Place the region seeds by selecting n members from `tmp'.
     */
    k = wh;
    for (i = 0; i < n; i++) {
        int j = random_upto(rs, k);
        map[tmp[j]] = i;
        tmp[j] = tmp[--k];
    }

    /*
     * Re-initialise `tmp' as a cumulative frequency table. This
     * will store the number of possible region colours we can
     * extend into each square.
     */
    cf_init(tmp, wh);

    /*
     * Go through the grid and set up the initial cumulative
     * frequencies.
     */
    for (y = 0; y < h; y++)
        for (x = 0; x < w; x++)
            cf_add(tmp, wh, y*w+x,
                   extend_options(w, h, n, map, x, y, -1));

    /*
     * Now repeatedly choose a square we can extend a region into,
     * and do so.
     */
    while (tmp[0] > 0) {
        int k = random_upto(rs, tmp[0]);
        int sq;
        int colour;
        int xx, yy;

        sq = cf_whichsym(tmp, wh, k);
        k -= cf_clookup(tmp, wh, sq);
        x = sq % w;
        y = sq / w;
        colour = extend_options(w, h, n, map, x, y, k);

        map[sq] = colour;

        /*
         * Re-scan the nine cells around the one we've just
         * modified.
         */
        for (yy = max(y-1, 0); yy < min(y+2, h); yy++)
            for (xx = max(x-1, 0); xx < min(x+2, w); xx++) {
                cf_add(tmp, wh, yy*w+xx,
                       -cf_slookup(tmp, wh, yy*w+xx) +
                       extend_options(w, h, n, map, xx, yy, -1));
            }
    }

    /*
     * Finally, go through and normalise the region labels into
     * order, meaning that indistinguishable maps are actually
     * identical.
     */
    for (i = 0; i < n; i++)
        tmp[i] = -1;
    k = 0;
    for (i = 0; i < wh; i++) {
        assert(map[i] >= 0);
        if (tmp[map[i]] < 0)
            tmp[map[i]] = k++;
        map[i] = tmp[map[i]];
    }

    sfree(tmp);
}

/* ----------------------------------------------------------------------
 * Functions to handle graphs.
 */

/*
 * Having got a map in a square grid, convert it into a graph
 * representation.
 */
static int gengraph(int w, int h, int n, int *map, int *graph)
{
    int i, j, x, y;

    /*
     * Start by setting the graph up as an adjacency matrix. We'll
     * turn it into a list later.
     */
    for (i = 0; i < n*n; i++)
        graph[i] = 0;

    /*
     * Iterate over the map looking for all adjacencies.
     */
    for (y = 0; y < h; y++)
        for (x = 0; x < w; x++) {
            int v, vx, vy;
            v = map[y*w+x];
            if (x+1 < w && (vx = map[y*w+(x+1)]) != v)
                graph[v*n+vx] = graph[vx*n+v] = 1;
            if (y+1 < h && (vy = map[(y+1)*w+x]) != v)
                graph[v*n+vy] = graph[vy*n+v] = 1;
        }

    /*
     * Turn the matrix into a list.
     */
    for (i = j = 0; i < n*n; i++)
        if (graph[i])
            graph[j++] = i;

    return j;
}

static int graph_edge_index(int *graph, int n, int ngraph, int i, int j)
{
    int v = i*n+j;
    int top, bot, mid;

    bot = -1;
    top = ngraph;
    while (top - bot > 1) {
        mid = (top + bot) / 2;
        if (graph[mid] == v)
            return mid;
        else if (graph[mid] < v)
            bot = mid;
        else
            top = mid;
    }
    return -1;
}

#define graph_adjacent(graph, n, ngraph, i, j) \
    (graph_edge_index((graph), (n), (ngraph), (i), (j)) >= 0)

static int graph_vertex_start(int *graph, int n, int ngraph, int i)
{
    int v = i*n;
    int top, bot, mid;

    bot = -1;
    top = ngraph;
    while (top - bot > 1) {
        mid = (top + bot) / 2;
        if (graph[mid] < v)
            bot = mid;
        else
            top = mid;
    }
    return top;
}

/* ----------------------------------------------------------------------
 * Generate a four-colouring of a graph.
 *
 * FIXME: it would be nice if we could convert this recursion into
 * pseudo-recursion using some sort of explicit stack array, for
 * the sake of the Palm port and its limited stack.
 */

static int fourcolour_recurse(int *graph, int n, int ngraph,
                              int *colouring, int *scratch, random_state *rs)
{
    int nfree, nvert, start, i, j, k, c, ci;
    int cs[FOUR];

    /*
     * Find the smallest number of free colours in any uncoloured
     * vertex, and count the number of such vertices.
     */

    nfree = FIVE;                      /* start off bigger than FOUR! */
    nvert = 0;
    for (i = 0; i < n; i++)
        if (colouring[i] < 0 && scratch[i*FIVE+FOUR] <= nfree) {
            if (nfree > scratch[i*FIVE+FOUR]) {
                nfree = scratch[i*FIVE+FOUR];
                nvert = 0;
            }
            nvert++;
        }

    /*
     * If there aren't any uncoloured vertices at all, we're done.
     */
    if (nvert == 0)
        return TRUE;                   /* we've got a colouring! */

    /*
     * Pick a random vertex in that set.
     */
    j = random_upto(rs, nvert);
    for (i = 0; i < n; i++)
        if (colouring[i] < 0 && scratch[i*FIVE+FOUR] == nfree)
            if (j-- == 0)
                break;
    assert(i < n);
    start = graph_vertex_start(graph, n, ngraph, i);

    /*
     * Loop over the possible colours for i, and recurse for each
     * one.
     */
    ci = 0;
    for (c = 0; c < FOUR; c++)
        if (scratch[i*FIVE+c] == 0)
            cs[ci++] = c;
    shuffle(cs, ci, sizeof(*cs), rs);

    while (ci-- > 0) {
        c = cs[ci];

        /*
         * Fill in this colour.
         */
        colouring[i] = c;

        /*
         * Update the scratch space to reflect a new neighbour
         * of this colour for each neighbour of vertex i.
         */
        for (j = start; j < ngraph && graph[j] < n*(i+1); j++) {
            k = graph[j] - i*n;
            if (scratch[k*FIVE+c] == 0)
                scratch[k*FIVE+FOUR]--;
            scratch[k*FIVE+c]++;
        }

        /*
         * Recurse.
         */
        if (fourcolour_recurse(graph, n, ngraph, colouring, scratch, rs))
            return TRUE;               /* got one! */

        /*
         * If that didn't work, clean up and try again with a
         * different colour.
         */
        for (j = start; j < ngraph && graph[j] < n*(i+1); j++) {
            k = graph[j] - i*n;
            scratch[k*FIVE+c]--;
            if (scratch[k*FIVE+c] == 0)
                scratch[k*FIVE+FOUR]++;
        }
        colouring[i] = -1;
    }

    /*
     * If we reach here, we were unable to find a colouring at all.
     * (This doesn't necessarily mean the Four Colour Theorem is
     * violated; it might just mean we've gone down a dead end and
     * need to back up and look somewhere else. It's only an FCT
     * violation if we get all the way back up to the top level and
     * still fail.)
     */
    return FALSE;
}

static void fourcolour(int *graph, int n, int ngraph, int *colouring,
                       random_state *rs)
{
    int *scratch;
    int i;

    /*
     * For each vertex and each colour, we store the number of
     * neighbours that have that colour. Also, we store the number
     * of free colours for the vertex.
     */
    scratch = snewn(n * FIVE, int);
    for (i = 0; i < n * FIVE; i++)
        scratch[i] = (i % FIVE == FOUR ? FOUR : 0);

    /*
     * Clear the colouring to start with.
     */
    for (i = 0; i < n; i++)
        colouring[i] = -1;

    i = fourcolour_recurse(graph, n, ngraph, colouring, scratch, rs);
    assert(i);                         /* by the Four Colour Theorem :-) */

    sfree(scratch);
}

/* ----------------------------------------------------------------------
 * Non-recursive solver.
 */

struct solver_scratch {
    unsigned char *possible;           /* bitmap of colours for each region */

    int *graph;
    int n;
    int ngraph;

    int *bfsqueue;
    int *bfscolour;
#ifdef SOLVER_DIAGNOSTICS
    int *bfsprev;
#endif

    int depth;
};

static struct solver_scratch *new_scratch(int *graph, int n, int ngraph)
{
    struct solver_scratch *sc;

    sc = snew(struct solver_scratch);
    sc->graph = graph;
    sc->n = n;
    sc->ngraph = ngraph;
    sc->possible = snewn(n, unsigned char);
    sc->depth = 0;
    sc->bfsqueue = snewn(n, int);
    sc->bfscolour = snewn(n, int);
#ifdef SOLVER_DIAGNOSTICS
    sc->bfsprev = snewn(n, int);
#endif

    return sc;
}

static void free_scratch(struct solver_scratch *sc)
{
    sfree(sc->possible);
    sfree(sc->bfsqueue);
    sfree(sc->bfscolour);
#ifdef SOLVER_DIAGNOSTICS
    sfree(sc->bfsprev);
#endif
    sfree(sc);
}

/*
 * Count the bits in a word. Only needs to cope with FOUR bits.
 */
static int bitcount(int word)
{
    assert(FOUR <= 4);                 /* or this needs changing */
    word = ((word & 0xA) >> 1) + (word & 0x5);
    word = ((word & 0xC) >> 2) + (word & 0x3);
    return word;
}

#ifdef SOLVER_DIAGNOSTICS
static const char colnames[FOUR] = { 'R', 'Y', 'G', 'B' };
#endif

static int place_colour(struct solver_scratch *sc,
                        int *colouring, int index, int colour
#ifdef SOLVER_DIAGNOSTICS
                        , char *verb
#endif
                        )
{
    int *graph = sc->graph, n = sc->n, ngraph = sc->ngraph;
    int j, k;

    if (!(sc->possible[index] & (1 << colour))) {
#ifdef SOLVER_DIAGNOSTICS
        if (verbose)
            printf("%*scannot place %c in region %d\n", 2*sc->depth, "",
                   colnames[colour], index);
#endif
        return FALSE;                  /* can't do it */
    }

    sc->possible[index] = 1 << colour;
    colouring[index] = colour;

#ifdef SOLVER_DIAGNOSTICS
    if (verbose)
        printf("%*s%s %c in region %d\n", 2*sc->depth, "",
               verb, colnames[colour], index);
#endif

    /*
     * Rule out this colour from all the region's neighbours.
     */
    for (j = graph_vertex_start(graph, n, ngraph, index);
         j < ngraph && graph[j] < n*(index+1); j++) {
        k = graph[j] - index*n;
#ifdef SOLVER_DIAGNOSTICS
        if (verbose && (sc->possible[k] & (1 << colour)))
            printf("%*s  ruling out %c in region %d\n", 2*sc->depth, "",
                   colnames[colour], k);
#endif
        sc->possible[k] &= ~(1 << colour);
    }

    return TRUE;
}

#ifdef SOLVER_DIAGNOSTICS
static char *colourset(char *buf, int set)
{
    int i;
    char *p = buf;
    char *sep = "";

    for (i = 0; i < FOUR; i++)
        if (set & (1 << i)) {
            p += sprintf(p, "%s%c", sep, colnames[i]);
            sep = ",";
        }

    return buf;
}
#endif

/*
 * Returns 0 for impossible, 1 for success, 2 for failure to
 * converge (i.e. puzzle is either ambiguous or just too
 * difficult).
 */
static int map_solver(struct solver_scratch *sc,
                      int *graph, int n, int ngraph, int *colouring,
                      int difficulty)
{
    int i;

    if (sc->depth == 0) {
        /*
         * Initialise scratch space.
         */
        for (i = 0; i < n; i++)
            sc->possible[i] = (1 << FOUR) - 1;

        /*
         * Place clues.
         */
        for (i = 0; i < n; i++)
            if (colouring[i] >= 0) {
                if (!place_colour(sc, colouring, i, colouring[i]
#ifdef SOLVER_DIAGNOSTICS
                                  , "initial clue:"
#endif
                                  )) {
#ifdef SOLVER_DIAGNOSTICS
                    if (verbose)
                        printf("%*sinitial clue set is inconsistent\n",
                               2*sc->depth, "");
#endif
                    return 0;          /* the clues aren't even consistent! */
                }
            }
    }

    /*
     * Now repeatedly loop until we find nothing further to do.
     */
    while (1) {
        int done_something = FALSE;

        if (difficulty < DIFF_EASY)
            break;                     /* can't do anything at all! */

        /*
         * Simplest possible deduction: find a region with only one
         * possible colour.
         */
        for (i = 0; i < n; i++) if (colouring[i] < 0) {
            int p = sc->possible[i];

            if (p == 0) {
#ifdef SOLVER_DIAGNOSTICS
                if (verbose)
                    printf("%*sregion %d has no possible colours left\n",
                           2*sc->depth, "", i);
#endif
                return 0;              /* puzzle is inconsistent */
            }

            if ((p & (p-1)) == 0) {    /* p is a power of two */
                int c, ret;
                for (c = 0; c < FOUR; c++)
                    if (p == (1 << c))
                        break;
                assert(c < FOUR);
                ret = place_colour(sc, colouring, i, c
#ifdef SOLVER_DIAGNOSTICS
                                   , "placing"
#endif
                                   );
                /*
                 * place_colour() can only fail if colour c was not
                 * even a _possibility_ for region i, and we're
                 * pretty sure it was because we checked before
                 * calling place_colour(). So we can safely assert
                 * here rather than having to return a nice
                 * friendly error code.
                 */
                assert(ret);
                done_something = TRUE;
            }
        }

        if (done_something)
            continue;

        if (difficulty < DIFF_NORMAL)
            break;                     /* can't do anything harder */

        /*
         * Failing that, go up one level. Look for pairs of regions
         * which (a) both have the same pair of possible colours,
         * (b) are adjacent to one another, (c) are adjacent to the
         * same region, and (d) that region still thinks it has one
         * or both of those possible colours.
         * 
         * Simplest way to do this is by going through the graph
         * edge by edge, so that we start with property (b) and
         * then look for (a) and finally (c) and (d).
         */
        for (i = 0; i < ngraph; i++) {
            int j1 = graph[i] / n, j2 = graph[i] % n;
            int j, k, v, v2;
#ifdef SOLVER_DIAGNOSTICS
            int started = FALSE;
#endif

            if (j1 > j2)
                continue;              /* done it already, other way round */

            if (colouring[j1] >= 0 || colouring[j2] >= 0)
                continue;              /* they're not undecided */

            if (sc->possible[j1] != sc->possible[j2])
                continue;              /* they don't have the same possibles */

            v = sc->possible[j1];
            /*
             * See if v contains exactly two set bits.
             */
            v2 = v & -v;           /* find lowest set bit */
            v2 = v & ~v2;          /* clear it */
            if (v2 == 0 || (v2 & (v2-1)) != 0)   /* not power of 2 */
                continue;

            /*
             * We've found regions j1 and j2 satisfying properties
             * (a) and (b): they have two possible colours between
             * them, and since they're adjacent to one another they
             * must use _both_ those colours between them.
             * Therefore, if they are both adjacent to any other
             * region then that region cannot be either colour.
             * 
             * Go through the neighbours of j1 and see if any are
             * shared with j2.
             */
            for (j = graph_vertex_start(graph, n, ngraph, j1);
                 j < ngraph && graph[j] < n*(j1+1); j++) {
                k = graph[j] - j1*n;
                if (graph_adjacent(graph, n, ngraph, k, j2) &&
                    (sc->possible[k] & v)) {
#ifdef SOLVER_DIAGNOSTICS
                    if (verbose) {
                        char buf[80];
                        if (!started)
                            printf("%*sadjacent regions %d,%d share colours"
                                   " %s\n", 2*sc->depth, "", j1, j2,
                                   colourset(buf, v));
                        started = TRUE;
                        printf("%*s  ruling out %s in region %d\n",2*sc->depth,
                               "", colourset(buf, sc->possible[k] & v), k);
                    }
#endif
                    sc->possible[k] &= ~v;
                    done_something = TRUE;
                }
            }
        }

        if (done_something)
            continue;

        if (difficulty < DIFF_HARD)
            break;                     /* can't do anything harder */

        /*
         * Right; now we get creative. Now we're going to look for
         * `forcing chains'. A forcing chain is a path through the
         * graph with the following properties:
         * 
         *  (a) Each vertex on the path has precisely two possible
         *      colours.
         * 
         *  (b) Each pair of vertices which are adjacent on the
         *      path share at least one possible colour in common.
         * 
         *  (c) Each vertex in the middle of the path shares _both_
         *      of its colours with at least one of its neighbours
         *      (not the same one with both neighbours).
         * 
         * These together imply that at least one of the possible
         * colour choices at one end of the path forces _all_ the
         * rest of the colours along the path. In order to make
         * real use of this, we need further properties:
         * 
         *  (c) Ruling out some colour C from the vertex at one end
         *      of the path forces the vertex at the other end to
         *      take colour C.
         * 
         *  (d) The two end vertices are mutually adjacent to some
         *      third vertex.
         * 
         *  (e) That third vertex currently has C as a possibility.
         * 
         * If we can find all of that lot, we can deduce that at
         * least one of the two ends of the forcing chain has
         * colour C, and that therefore the mutually adjacent third
         * vertex does not.
         * 
         * To find forcing chains, we're going to start a bfs at
         * each suitable vertex of the graph, once for each of its
         * two possible colours.
         */
        for (i = 0; i < n; i++) {
            int c;

            if (colouring[i] >= 0 || bitcount(sc->possible[i]) != 2)
                continue;

            for (c = 0; c < FOUR; c++)
                if (sc->possible[i] & (1 << c)) {
                    int j, k, gi, origc, currc, head, tail;
                    /*
                     * Try a bfs from this vertex, ruling out
                     * colour c.
                     * 
                     * Within this loop, we work in colour bitmaps
                     * rather than actual colours, because
                     * converting back and forth is a needless
                     * computational expense.
                     */

                    origc = 1 << c;

                    for (j = 0; j < n; j++) {
                        sc->bfscolour[j] = -1;
#ifdef SOLVER_DIAGNOSTICS
                        sc->bfsprev[j] = -1;
#endif
                    }
                    head = tail = 0;
                    sc->bfsqueue[tail++] = i;
                    sc->bfscolour[i] = sc->possible[i] &~ origc;

                    while (head < tail) {
                        j = sc->bfsqueue[head++];
                        currc = sc->bfscolour[j];

                        /*
                         * Try neighbours of j.
                         */
                        for (gi = graph_vertex_start(graph, n, ngraph, j);
                             gi < ngraph && graph[gi] < n*(j+1); gi++) {
                            k = graph[gi] - j*n;

                            /*
                             * To continue with the bfs in vertex
                             * k, we need k to be
                             *  (a) not already visited
                             *  (b) have two possible colours
                             *  (c) those colours include currc.
                             */

                            if (sc->bfscolour[k] < 0 &&
                                colouring[k] < 0 &&
                                bitcount(sc->possible[k]) == 2 &&
                                (sc->possible[k] & currc)) {
                                sc->bfsqueue[tail++] = k;
                                sc->bfscolour[k] =
                                    sc->possible[k] &~ currc;
#ifdef SOLVER_DIAGNOSTICS
                                sc->bfsprev[k] = j;
#endif
                            }

                            /*
                             * One other possibility is that k
                             * might be the region in which we can
                             * make a real deduction: if it's
                             * adjacent to i, contains currc as a
                             * possibility, and currc is equal to
                             * the original colour we ruled out.
                             */
                            if (currc == origc &&
                                graph_adjacent(graph, n, ngraph, k, i) &&
                                (sc->possible[k] & currc)) {
#ifdef SOLVER_DIAGNOSTICS
                                if (verbose) {
                                    char buf[80], *sep = "";
                                    int r;

                                    printf("%*sforcing chain, colour %s, ",
                                           2*sc->depth, "",
                                           colourset(buf, origc));
                                    for (r = j; r != -1; r = sc->bfsprev[r]) {
                                        printf("%s%d", sep, r);
                                        sep = "-";
                                    }
                                    printf("\n%*s  ruling out %s in region"
                                           " %d\n", 2*sc->depth, "",
                                           colourset(buf, origc), k);
                                }
#endif
                                sc->possible[k] &= ~origc;
                                done_something = TRUE;
                            }
                        }
                    }

                    assert(tail <= n);
                }
        }

        if (!done_something)
            break;
    }

    /*
     * See if we've got a complete solution, and return if so.
     */
    for (i = 0; i < n; i++)
        if (colouring[i] < 0)
            break;
    if (i == n) {
#ifdef SOLVER_DIAGNOSTICS
        if (verbose)
            printf("%*sone solution found\n", 2*sc->depth, "");
#endif
        return 1;                      /* success! */
    }

    /*
     * If recursion is not permissible, we now give up.
     */
    if (difficulty < DIFF_RECURSE) {
#ifdef SOLVER_DIAGNOSTICS
        if (verbose)
            printf("%*sunable to proceed further without recursion\n",
                   2*sc->depth, "");
#endif
        return 2;                      /* unable to complete */
    }

    /*
     * Now we've got to do something recursive. So first hunt for a
     * currently-most-constrained region.
     */
    {
        int best, bestc;
        struct solver_scratch *rsc;
        int *subcolouring, *origcolouring;
        int ret, subret;
        int we_already_got_one;

        best = -1;
        bestc = FIVE;

        for (i = 0; i < n; i++) if (colouring[i] < 0) {
            int p = sc->possible[i];
            enum { compile_time_assertion = 1 / (FOUR <= 4) };
            int c;

            /* Count the set bits. */
            c = (p & 5) + ((p >> 1) & 5);
            c = (c & 3) + ((c >> 2) & 3);
            assert(c > 1);             /* or colouring[i] would be >= 0 */

            if (c < bestc) {
                best = i;
                bestc = c;
            }
        }

        assert(best >= 0);             /* or we'd be solved already */

#ifdef SOLVER_DIAGNOSTICS
        if (verbose)
            printf("%*srecursing on region %d\n", 2*sc->depth, "", best);
#endif

        /*
         * Now iterate over the possible colours for this region.
         */
        rsc = new_scratch(graph, n, ngraph);
        rsc->depth = sc->depth + 1;
        origcolouring = snewn(n, int);
        memcpy(origcolouring, colouring, n * sizeof(int));
        subcolouring = snewn(n, int);
        we_already_got_one = FALSE;
        ret = 0;

        for (i = 0; i < FOUR; i++) {
            if (!(sc->possible[best] & (1 << i)))
                continue;

            memcpy(rsc->possible, sc->possible, n);
            memcpy(subcolouring, origcolouring, n * sizeof(int));

            place_colour(rsc, subcolouring, best, i
#ifdef SOLVER_DIAGNOSTICS
                         , "trying"
#endif
                         );

            subret = map_solver(rsc, graph, n, ngraph,
                                subcolouring, difficulty);

#ifdef SOLVER_DIAGNOSTICS
            if (verbose) {
                printf("%*sretracting %c in region %d; found %s\n",
                       2*sc->depth, "", colnames[i], best,
                       subret == 0 ? "no solutions" :
                       subret == 1 ? "one solution" : "multiple solutions");
            }
#endif

            /*
             * If this possibility turned up more than one valid
             * solution, or if it turned up one and we already had
             * one, we're definitely ambiguous.
             */
            if (subret == 2 || (subret == 1 && we_already_got_one)) {
                ret = 2;
                break;
            }

            /*
             * If this possibility turned up one valid solution and
             * it's the first we've seen, copy it into the output.
             */
            if (subret == 1) {
                memcpy(colouring, subcolouring, n * sizeof(int));
                we_already_got_one = TRUE;
                ret = 1;
            }

            /*
             * Otherwise, this guess led to a contradiction, so we
             * do nothing.
             */
        }

        sfree(origcolouring);
        sfree(subcolouring);
        free_scratch(rsc);

#ifdef SOLVER_DIAGNOSTICS
        if (verbose && sc->depth == 0) {
            printf("%*s%s found\n",
                   2*sc->depth, "",
                   ret == 0 ? "no solutions" :
                   ret == 1 ? "one solution" : "multiple solutions");
        }
#endif
        return ret;
    }
}

/* ----------------------------------------------------------------------
 * Game generation main function.
 */

static char *new_game_desc(const game_params *params, random_state *rs,
                           char **aux, int interactive)
{
    struct solver_scratch *sc = NULL;
    int *map, *graph, ngraph, *colouring, *colouring2, *regions;
    int i, j, w, h, n, solveret, cfreq[FOUR];
    int wh;
    int mindiff, tries;
#ifdef GENERATION_DIAGNOSTICS
    int x, y;
#endif
    char *ret, buf[80];
    int retlen, retsize;

    w = params->w;
    h = params->h;
    n = params->n;
    wh = w*h;

    *aux = NULL;

    map = snewn(wh, int);
    graph = snewn(n*n, int);
    colouring = snewn(n, int);
    colouring2 = snewn(n, int);
    regions = snewn(n, int);

    /*
     * This is the minimum difficulty below which we'll completely
     * reject a map design. Normally we set this to one below the
     * requested difficulty, ensuring that we have the right
     * result. However, for particularly dense maps or maps with
     * particularly few regions it might not be possible to get the
     * desired difficulty, so we will eventually drop this down to
     * -1 to indicate that any old map will do.
     */
    mindiff = params->diff;
    tries = 50;

    while (1) {

        /*
         * Create the map.
         */
        genmap(w, h, n, map, rs);

#ifdef GENERATION_DIAGNOSTICS
        for (y = 0; y < h; y++) {
            for (x = 0; x < w; x++) {
                int v = map[y*w+x];
                if (v >= 62)
                    putchar('!');
                else if (v >= 36)
                    putchar('a' + v-36);
                else if (v >= 10)
                    putchar('A' + v-10);
                else
                    putchar('0' + v);
            }
            putchar('\n');
        }
#endif

        /*
         * Convert the map into a graph.
         */
        ngraph = gengraph(w, h, n, map, graph);

#ifdef GENERATION_DIAGNOSTICS
        for (i = 0; i < ngraph; i++)
            printf("%d-%d\n", graph[i]/n, graph[i]%n);
#endif

        /*
         * Colour the map.
         */
        fourcolour(graph, n, ngraph, colouring, rs);

#ifdef GENERATION_DIAGNOSTICS
        for (i = 0; i < n; i++)
            printf("%d: %d\n", i, colouring[i]);

        for (y = 0; y < h; y++) {
            for (x = 0; x < w; x++) {
                int v = colouring[map[y*w+x]];
                if (v >= 36)
                    putchar('a' + v-36);
                else if (v >= 10)
                    putchar('A' + v-10);
                else
                    putchar('0' + v);
            }
            putchar('\n');
        }
#endif

        /*
         * Encode the solution as an aux string.
         */
        if (*aux)                      /* in case we've come round again */
            sfree(*aux);
        retlen = retsize = 0;
        ret = NULL;
        for (i = 0; i < n; i++) {
            int len;

            if (colouring[i] < 0)
                continue;

            len = sprintf(buf, "%s%d:%d", i ? ";" : "S;", colouring[i], i);
            if (retlen + len >= retsize) {
                retsize = retlen + len + 256;
                ret = sresize(ret, retsize, char);
            }
            strcpy(ret + retlen, buf);
            retlen += len;
        }
        *aux = ret;

        /*
         * Remove the region colours one by one, keeping
         * solubility. Also ensure that there always remains at
         * least one region of every colour, so that the user can
         * drag from somewhere.
         */
        for (i = 0; i < FOUR; i++)
            cfreq[i] = 0;
        for (i = 0; i < n; i++) {
            regions[i] = i;
            cfreq[colouring[i]]++;
        }
        for (i = 0; i < FOUR; i++)
            if (cfreq[i] == 0)
                continue;

        shuffle(regions, n, sizeof(*regions), rs);

        if (sc) free_scratch(sc);
        sc = new_scratch(graph, n, ngraph);

        for (i = 0; i < n; i++) {
            j = regions[i];

            if (cfreq[colouring[j]] == 1)
                continue;              /* can't remove last region of colour */

            memcpy(colouring2, colouring, n*sizeof(int));
            colouring2[j] = -1;
            solveret = map_solver(sc, graph, n, ngraph, colouring2,
                                  params->diff);
            assert(solveret >= 0);             /* mustn't be impossible! */
            if (solveret == 1) {
                cfreq[colouring[j]]--;
                colouring[j] = -1;
            }
        }

#ifdef GENERATION_DIAGNOSTICS
        for (i = 0; i < n; i++)
            if (colouring[i] >= 0) {
                if (i >= 62)
                    putchar('!');
                else if (i >= 36)
                    putchar('a' + i-36);
                else if (i >= 10)
                    putchar('A' + i-10);
                else
                    putchar('0' + i);
                printf(": %d\n", colouring[i]);
            }
#endif

        /*
         * Finally, check that the puzzle is _at least_ as hard as
         * required, and indeed that it isn't already solved.
         * (Calling map_solver with negative difficulty ensures the
         * latter - if a solver which _does nothing_ can solve it,
         * it's too easy!)
         */
        memcpy(colouring2, colouring, n*sizeof(int));
        if (map_solver(sc, graph, n, ngraph, colouring2,
                       mindiff - 1) == 1) {
            /*
             * Drop minimum difficulty if necessary.
             */
            if (mindiff > 0 && (n < 9 || n > 2*wh/3)) {
                if (tries-- <= 0)
                    mindiff = 0;       /* give up and go for Easy */
            }
            continue;
        }

        break;
    }

    /*
     * Encode as a game ID. We do this by:
     * 
     *  - first going along the horizontal edges row by row, and
     *    then the vertical edges column by column
     *  - encoding the lengths of runs of edges and runs of
     *    non-edges
     *  - the decoder will reconstitute the region boundaries from
     *    this and automatically number them the same way we did
     *  - then we encode the initial region colours in a Slant-like
     *    fashion (digits 0-3 interspersed with letters giving
     *    lengths of runs of empty spaces).
     */
    retlen = retsize = 0;
    ret = NULL;

    {
        int run, pv;

        /*
         * Start with a notional non-edge, so that there'll be an
         * explicit `a' to distinguish the case where we start with
         * an edge.
         */
        run = 1;
        pv = 0;

        for (i = 0; i < w*(h-1) + (w-1)*h; i++) {
            int x, y, dx, dy, v;

            if (i < w*(h-1)) {
                /* Horizontal edge. */
                y = i / w;
                x = i % w;
                dx = 0;
                dy = 1;
            } else {
                /* Vertical edge. */
                x = (i - w*(h-1)) / h;
                y = (i - w*(h-1)) % h;
                dx = 1;
                dy = 0;
            }

            if (retlen + 10 >= retsize) {
                retsize = retlen + 256;
                ret = sresize(ret, retsize, char);
            }

            v = (map[y*w+x] != map[(y+dy)*w+(x+dx)]);

            if (pv != v) {
                ret[retlen++] = 'a'-1 + run;
                run = 1;
                pv = v;
            } else {
                /*
                 * 'z' is a special case in this encoding. Rather
                 * than meaning a run of 26 and a state switch, it
                 * means a run of 25 and _no_ state switch, because
                 * otherwise there'd be no way to encode runs of
                 * more than 26.
                 */
                if (run == 25) {
                    ret[retlen++] = 'z';
                    run = 0;
                }
                run++;
            }
        }

        ret[retlen++] = 'a'-1 + run;
        ret[retlen++] = ',';

        run = 0;
        for (i = 0; i < n; i++) {
            if (retlen + 10 >= retsize) {
                retsize = retlen + 256;
                ret = sresize(ret, retsize, char);
            }

            if (colouring[i] < 0) {
                /*
                 * In _this_ encoding, 'z' is a run of 26, since
                 * there's no implicit state switch after each run.
                 * Confusingly different, but more compact.
                 */
                if (run == 26) {
                    ret[retlen++] = 'z';
                    run = 0;
                }
                run++;
            } else {
                if (run > 0)
                    ret[retlen++] = 'a'-1 + run;
                ret[retlen++] = '0' + colouring[i];
                run = 0;
            }
        }
        if (run > 0)
            ret[retlen++] = 'a'-1 + run;
        ret[retlen] = '\0';

        assert(retlen < retsize);
    }

    free_scratch(sc);
    sfree(regions);
    sfree(colouring2);
    sfree(colouring);
    sfree(graph);
    sfree(map);

    return ret;
}

static char *parse_edge_list(const game_params *params, const char **desc,
                             int *map)
{
    int w = params->w, h = params->h, wh = w*h, n = params->n;
    int i, k, pos, state;
    const char *p = *desc;

    dsf_init(map+wh, wh);

    pos = -1;
    state = 0;

    /*
     * Parse the game description to get the list of edges, and
     * build up a disjoint set forest as we go (by identifying
     * pairs of squares whenever the edge list shows a non-edge).
     */
    while (*p && *p != ',') {
        if (*p < 'a' || *p > 'z')
            return "Unexpected character in edge list";
        if (*p == 'z')
            k = 25;
        else
            k = *p - 'a' + 1;
        while (k-- > 0) {
            int x, y, dx, dy;

            if (pos < 0) {
                pos++;
                continue;
            } else if (pos < w*(h-1)) {
                /* Horizontal edge. */
                y = pos / w;
                x = pos % w;
                dx = 0;
                dy = 1;
            } else if (pos < 2*wh-w-h) {
                /* Vertical edge. */
                x = (pos - w*(h-1)) / h;
                y = (pos - w*(h-1)) % h;
                dx = 1;
                dy = 0;
            } else
                return "Too much data in edge list";
            if (!state)
                dsf_merge(map+wh, y*w+x, (y+dy)*w+(x+dx));

            pos++;
        }
        if (*p != 'z')
            state = !state;
        p++;
    }
    assert(pos <= 2*wh-w-h);
    if (pos < 2*wh-w-h)
        return "Too little data in edge list";

    /*
     * Now go through again and allocate region numbers.
     */
    pos = 0;
    for (i = 0; i < wh; i++)
        map[i] = -1;
    for (i = 0; i < wh; i++) {
        k = dsf_canonify(map+wh, i);
        if (map[k] < 0)
            map[k] = pos++;
        map[i] = map[k];
    }
    if (pos != n)
        return "Edge list defines the wrong number of regions";

    *desc = p;

    return NULL;
}

static char *validate_desc(const game_params *params, const char *desc)
{
    int w = params->w, h = params->h, wh = w*h, n = params->n;
    int area;
    int *map;
    char *ret;

    map = snewn(2*wh, int);
    ret = parse_edge_list(params, &desc, map);
    sfree(map);
    if (ret)
        return ret;

    if (*desc != ',')
        return "Expected comma before clue list";
    desc++;                            /* eat comma */

    area = 0;
    while (*desc) {
        if (*desc >= '0' && *desc < '0'+FOUR)
            area++;
        else if (*desc >= 'a' && *desc <= 'z')
            area += *desc - 'a' + 1;
        else
            return "Unexpected character in clue list";
        desc++;
    }
    if (area < n)
        return "Too little data in clue list";
    else if (area > n)
        return "Too much data in clue list";

    return NULL;
}

static game_state *new_game(midend *me, const game_params *params,
                            const char *desc)
{
    int w = params->w, h = params->h, wh = w*h, n = params->n;
    int i, pos;
    const char *p;
    game_state *state = snew(game_state);

    state->p = *params;
    state->colouring = snewn(n, int);
    for (i = 0; i < n; i++)
        state->colouring[i] = -1;
    state->pencil = snewn(n, int);
    for (i = 0; i < n; i++)
        state->pencil[i] = 0;

    state->completed = state->cheated = FALSE;

    state->map = snew(struct map);
    state->map->refcount = 1;
    state->map->map = snewn(wh*4, int);
    state->map->graph = snewn(n*n, int);
    state->map->n = n;
    state->map->immutable = snewn(n, int);
    for (i = 0; i < n; i++)
        state->map->immutable[i] = FALSE;

    p = desc;

    {
        char *ret;
        ret = parse_edge_list(params, &p, state->map->map);
        assert(!ret);
    }

    /*
     * Set up the other three quadrants in `map'.
     */
    for (i = wh; i < 4*wh; i++)
        state->map->map[i] = state->map->map[i % wh];

    assert(*p == ',');
    p++;

    /*
     * Now process the clue list.
     */
    pos = 0;
    while (*p) {
        if (*p >= '0' && *p < '0'+FOUR) {
            state->colouring[pos] = *p - '0';
            state->map->immutable[pos] = TRUE;
            pos++;
        } else {
            assert(*p >= 'a' && *p <= 'z');
            pos += *p - 'a' + 1;
        }
        p++;
    }
    assert(pos == n);

    state->map->ngraph = gengraph(w, h, n, state->map->map, state->map->graph);

    /*
     * Attempt to smooth out some of the more jagged region
     * outlines by the judicious use of diagonally divided squares.
     */
    {
        random_state *rs = random_new(desc, strlen(desc));
        int *squares = snewn(wh, int);
        int done_something;

        for (i = 0; i < wh; i++)
            squares[i] = i;
        shuffle(squares, wh, sizeof(*squares), rs);

        do {
            done_something = FALSE;
            for (i = 0; i < wh; i++) {
                int y = squares[i] / w, x = squares[i] % w;
                int c = state->map->map[y*w+x];
                int tc, bc, lc, rc;

                if (x == 0 || x == w-1 || y == 0 || y == h-1)
                    continue;

                if (state->map->map[TE * wh + y*w+x] !=
                    state->map->map[BE * wh + y*w+x])
                    continue;

                tc = state->map->map[BE * wh + (y-1)*w+x];
                bc = state->map->map[TE * wh + (y+1)*w+x];
                lc = state->map->map[RE * wh + y*w+(x-1)];
                rc = state->map->map[LE * wh + y*w+(x+1)];

                /*
                 * If this square is adjacent on two sides to one
                 * region and on the other two sides to the other
                 * region, and is itself one of the two regions, we can
                 * adjust it so that it's a diagonal.
                 */
                if (tc != bc && (tc == c || bc == c)) {
                    if ((lc == tc && rc == bc) ||
                        (lc == bc && rc == tc)) {
                        state->map->map[TE * wh + y*w+x] = tc;
                        state->map->map[BE * wh + y*w+x] = bc;
                        state->map->map[LE * wh + y*w+x] = lc;
                        state->map->map[RE * wh + y*w+x] = rc;
                        done_something = TRUE;
                    }
                }
            }
        } while (done_something);
        sfree(squares);
        random_free(rs);
    }

    /*
     * Analyse the map to find a canonical line segment
     * corresponding to each edge, and a canonical point
     * corresponding to each region. The former are where we'll
     * eventually put error markers; the latter are where we'll put
     * per-region flags such as numbers (when in diagnostic mode).
     */
    {
        int *bestx, *besty, *an, pass;
        float *ax, *ay, *best;

        ax = snewn(state->map->ngraph + n, float);
        ay = snewn(state->map->ngraph + n, float);
        an = snewn(state->map->ngraph + n, int);
        bestx = snewn(state->map->ngraph + n, int);
        besty = snewn(state->map->ngraph + n, int);
        best = snewn(state->map->ngraph + n, float);

        for (i = 0; i < state->map->ngraph + n; i++) {
            bestx[i] = besty[i] = -1;
            best[i] = (float)(2*(w+h)+1);
            ax[i] = ay[i] = 0.0F;
            an[i] = 0;
        }

        /*
         * We make two passes over the map, finding all the line
         * segments separating regions and all the suitable points
         * within regions. In the first pass, we compute the
         * _average_ x and y coordinate of all the points in a
         * given class; in the second pass, for each such average
         * point, we find the candidate closest to it and call that
         * canonical.
         * 
         * Line segments are considered to have coordinates in
         * their centre. Thus, at least one coordinate for any line
         * segment is always something-and-a-half; so we store our
         * coordinates as twice their normal value.
         */
        for (pass = 0; pass < 2; pass++) {
            int x, y;

            for (y = 0; y < h; y++)
                for (x = 0; x < w; x++) {
                    int ex[4], ey[4], ea[4], eb[4], en = 0;

                    /*
                     * Look for an edge to the right of this
                     * square, an edge below it, and an edge in the
                     * middle of it. Also look to see if the point
                     * at the bottom right of this square is on an
                     * edge (and isn't a place where more than two
                     * regions meet).
                     */
                    if (x+1 < w) {
                        /* right edge */
                        ea[en] = state->map->map[RE * wh + y*w+x];
                        eb[en] = state->map->map[LE * wh + y*w+(x+1)];
                        ex[en] = (x+1)*2;
                        ey[en] = y*2+1;
                        en++;
                    }
                    if (y+1 < h) {
                        /* bottom edge */
                        ea[en] = state->map->map[BE * wh + y*w+x];
                        eb[en] = state->map->map[TE * wh + (y+1)*w+x];
                        ex[en] = x*2+1;
                        ey[en] = (y+1)*2;
                        en++;
                    }
                    /* diagonal edge */
                    ea[en] = state->map->map[TE * wh + y*w+x];
                    eb[en] = state->map->map[BE * wh + y*w+x];
                    ex[en] = x*2+1;
                    ey[en] = y*2+1;
                    en++;

                    if (x+1 < w && y+1 < h) {
                        /* bottom right corner */
                        int oct[8], othercol, nchanges;
                        oct[0] = state->map->map[RE * wh + y*w+x];
                        oct[1] = state->map->map[LE * wh + y*w+(x+1)];
                        oct[2] = state->map->map[BE * wh + y*w+(x+1)];
                        oct[3] = state->map->map[TE * wh + (y+1)*w+(x+1)];
                        oct[4] = state->map->map[LE * wh + (y+1)*w+(x+1)];
                        oct[5] = state->map->map[RE * wh + (y+1)*w+x];
                        oct[6] = state->map->map[TE * wh + (y+1)*w+x];
                        oct[7] = state->map->map[BE * wh + y*w+x];

                        othercol = -1;
                        nchanges = 0;
                        for (i = 0; i < 8; i++) {
                            if (oct[i] != oct[0]) {
                                if (othercol < 0)
                                    othercol = oct[i];
                                else if (othercol != oct[i])
                                    break;   /* three colours at this point */
                            }
                            if (oct[i] != oct[(i+1) & 7])
                                nchanges++;
                        }

                        /*
                         * Now if there are exactly two regions at
                         * this point (not one, and not three or
                         * more), and only two changes around the
                         * loop, then this is a valid place to put
                         * an error marker.
                         */
                        if (i == 8 && othercol >= 0 && nchanges == 2) {
                            ea[en] = oct[0];
                            eb[en] = othercol;
                            ex[en] = (x+1)*2;
                            ey[en] = (y+1)*2;
                            en++;
                        }

                        /*
                         * If there's exactly _one_ region at this
                         * point, on the other hand, it's a valid
                         * place to put a region centre.
                         */
                        if (othercol < 0) {
                            ea[en] = eb[en] = oct[0];
                            ex[en] = (x+1)*2;
                            ey[en] = (y+1)*2;
                            en++;
                        }
                    }

                    /*
                     * Now process the points we've found, one by
                     * one.
                     */
                    for (i = 0; i < en; i++) {
                        int emin = min(ea[i], eb[i]);
                        int emax = max(ea[i], eb[i]);
                        int gindex;

                        if (emin != emax) {
                            /* Graph edge */
                            gindex =
                                graph_edge_index(state->map->graph, n,
                                                 state->map->ngraph, emin,
                                                 emax);
                        } else {
                            /* Region number */
                            gindex = state->map->ngraph + emin;
                        }

                        assert(gindex >= 0);

                        if (pass == 0) {
                            /*
                             * In pass 0, accumulate the values
                             * we'll use to compute the average
                             * positions.
                             */
                            ax[gindex] += ex[i];
                            ay[gindex] += ey[i];
                            an[gindex] += 1;
                        } else {
                            /*
                             * In pass 1, work out whether this
                             * point is closer to the average than
                             * the last one we've seen.
                             */
                            float dx, dy, d;

                            assert(an[gindex] > 0);
                            dx = ex[i] - ax[gindex];
                            dy = ey[i] - ay[gindex];
                            d = (float)sqrt(dx*dx + dy*dy);
                            if (d < best[gindex]) {
                                best[gindex] = d;
                                bestx[gindex] = ex[i];
                                besty[gindex] = ey[i];
                            }
                        }
                    }
                }

            if (pass == 0) {
                for (i = 0; i < state->map->ngraph + n; i++)
                    if (an[i] > 0) {
                        ax[i] /= an[i];
                        ay[i] /= an[i];
                    }
            }
        }

        state->map->edgex = snewn(state->map->ngraph, int);
        state->map->edgey = snewn(state->map->ngraph, int);
        memcpy(state->map->edgex, bestx, state->map->ngraph * sizeof(int));
        memcpy(state->map->edgey, besty, state->map->ngraph * sizeof(int));

        state->map->regionx = snewn(n, int);
        state->map->regiony = snewn(n, int);
        memcpy(state->map->regionx, bestx + state->map->ngraph, n*sizeof(int));
        memcpy(state->map->regiony, besty + state->map->ngraph, n*sizeof(int));

        for (i = 0; i < state->map->ngraph; i++)
            if (state->map->edgex[i] < 0) {
                /* Find the other representation of this edge. */
                int e = state->map->graph[i];
                int iprime = graph_edge_index(state->map->graph, n,
                                              state->map->ngraph, e%n, e/n);
                assert(state->map->edgex[iprime] >= 0);
                state->map->edgex[i] = state->map->edgex[iprime];
                state->map->edgey[i] = state->map->edgey[iprime];
            }

        sfree(ax);
        sfree(ay);
        sfree(an);
        sfree(best);
        sfree(bestx);
        sfree(besty);
    }

    return state;
}

static game_state *dup_game(const game_state *state)
{
    game_state *ret = snew(game_state);

    ret->p = state->p;
    ret->colouring = snewn(state->p.n, int);
    memcpy(ret->colouring, state->colouring, state->p.n * sizeof(int));
    ret->pencil = snewn(state->p.n, int);
    memcpy(ret->pencil, state->pencil, state->p.n * sizeof(int));
    ret->map = state->map;
    ret->map->refcount++;
    ret->completed = state->completed;
    ret->cheated = state->cheated;

    return ret;
}

static void free_game(game_state *state)
{
    if (--state->map->refcount <= 0) {
        sfree(state->map->map);
        sfree(state->map->graph);
        sfree(state->map->immutable);
        sfree(state->map->edgex);
        sfree(state->map->edgey);
        sfree(state->map->regionx);
        sfree(state->map->regiony);
        sfree(state->map);
    }
    sfree(state->pencil);
    sfree(state->colouring);
    sfree(state);
}

static char *solve_game(const game_state *state, const game_state *currstate,
                        const char *aux, char **error)
{
    if (!aux) {
        /*
         * Use the solver.
         */
        int *colouring;
        struct solver_scratch *sc;
        int sret;
        int i;
        char *ret, buf[80];
        int retlen, retsize;

        colouring = snewn(state->map->n, int);
        memcpy(colouring, state->colouring, state->map->n * sizeof(int));

        sc = new_scratch(state->map->graph, state->map->n, state->map->ngraph);
        sret = map_solver(sc, state->map->graph, state->map->n,
                         state->map->ngraph, colouring, DIFFCOUNT-1);
        free_scratch(sc);

        if (sret != 1) {
            sfree(colouring);
            if (sret == 0)
                *error = "Puzzle is inconsistent";
            else
                *error = "Unable to find a unique solution for this puzzle";
            return NULL;
        }

        retsize = 64;
        ret = snewn(retsize, char);
        strcpy(ret, "S");
        retlen = 1;

        for (i = 0; i < state->map->n; i++) {
            int len;

            assert(colouring[i] >= 0);
            if (colouring[i] == currstate->colouring[i])
                continue;
            assert(!state->map->immutable[i]);

            len = sprintf(buf, ";%d:%d", colouring[i], i);
            if (retlen + len >= retsize) {
                retsize = retlen + len + 256;
                ret = sresize(ret, retsize, char);
            }
            strcpy(ret + retlen, buf);
            retlen += len;
        }

        sfree(colouring);

        return ret;
    }
    return dupstr(aux);
}

static int game_can_format_as_text_now(const game_params *params)
{
    return TRUE;
}

static char *game_text_format(const game_state *state)
{
    return NULL;
}

struct game_ui {
    /*
     * drag_colour:
     * 
     *  - -2 means no drag currently active.
     *  - >=0 means we're dragging a solid colour.
     *  - -1 means we're dragging a blank space, and drag_pencil
     *    might or might not add some pencil-mark stipples to that.
     */
    int drag_colour;
    int drag_pencil;
    int dragx, dragy;
    int show_numbers;

    int cur_x, cur_y, cur_visible, cur_moved, cur_lastmove;
};

static game_ui *new_ui(const game_state *state)
{
    game_ui *ui = snew(game_ui);
    ui->dragx = ui->dragy = -1;
    ui->drag_colour = -2;
    ui->drag_pencil = 0;
    ui->show_numbers = FALSE;
    ui->cur_x = ui->cur_y = ui->cur_visible = ui->cur_moved = 0;
    ui->cur_lastmove = 0;
    return ui;
}

static void free_ui(game_ui *ui)
{
    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)
{
}

struct game_drawstate {
    int tilesize;
    unsigned long *drawn, *todraw;
    int started;
    int dragx, dragy, drag_visible;
    blitter *bl;
};

/* Flags in `drawn'. */
#define ERR_BASE      0x00800000L
#define ERR_MASK      0xFF800000L
#define PENCIL_T_BASE 0x00080000L
#define PENCIL_T_MASK 0x00780000L
#define PENCIL_B_BASE 0x00008000L
#define PENCIL_B_MASK 0x00078000L
#define PENCIL_MASK   0x007F8000L
#define SHOW_NUMBERS  0x00004000L

#define TILESIZE (ds->tilesize)
#define BORDER (TILESIZE)
#define COORD(x)  ( (x) * TILESIZE + BORDER )
#define FROMCOORD(x)  ( ((x) - BORDER + TILESIZE) / TILESIZE - 1 )

 /*
  * EPSILON_FOO are epsilons added to absolute cursor position by
  * cursor movement, such that in pathological cases (e.g. a very
  * small diamond-shaped area) it's relatively easy to select the
  * region you wanted.
  */

#define EPSILON_X(button) (((button) == CURSOR_RIGHT) ? +1 : \
                           ((button) == CURSOR_LEFT)  ? -1 : 0)
#define EPSILON_Y(button) (((button) == CURSOR_DOWN)  ? +1 : \
                           ((button) == CURSOR_UP)    ? -1 : 0)


static int region_from_coords(const game_state *state,
                              const game_drawstate *ds, int x, int y)
{
    int w = state->p.w, h = state->p.h, wh = w*h /*, n = state->p.n */;
    int tx = FROMCOORD(x), ty = FROMCOORD(y);
    int dx = x - COORD(tx), dy = y - COORD(ty);
    int quadrant;

    if (tx < 0 || tx >= w || ty < 0 || ty >= h)
        return -1;                     /* border */

    quadrant = 2 * (dx > dy) + (TILESIZE - dx > dy);
    quadrant = (quadrant == 0 ? BE :
                quadrant == 1 ? LE :
                quadrant == 2 ? RE : TE);

    return state->map->map[quadrant * wh + ty*w+tx];
}

static char *interpret_move(const game_state *state, game_ui *ui,
                            const game_drawstate *ds,
                            int x, int y, int button)
{
    char *bufp, buf[256];
    int alt_button;

    /*
     * Enable or disable numeric labels on regions.
     */
    if (button == 'l' || button == 'L') {
        ui->show_numbers = !ui->show_numbers;
        return "";
    }

    if (IS_CURSOR_MOVE(button)) {
        move_cursor(button, &ui->cur_x, &ui->cur_y, state->p.w, state->p.h, 0);
        ui->cur_visible = 1;
        ui->cur_moved = 1;
        ui->cur_lastmove = button;
        ui->dragx = COORD(ui->cur_x) + TILESIZE/2 + EPSILON_X(button);
        ui->dragy = COORD(ui->cur_y) + TILESIZE/2 + EPSILON_Y(button);
        return "";
    }
    if (IS_CURSOR_SELECT(button)) {
        if (!ui->cur_visible) {
            ui->dragx = COORD(ui->cur_x) + TILESIZE/2 + EPSILON_X(ui->cur_lastmove);
            ui->dragy = COORD(ui->cur_y) + TILESIZE/2 + EPSILON_Y(ui->cur_lastmove);
            ui->cur_visible = 1;
            return "";
        }
        if (ui->drag_colour == -2) { /* not currently cursor-dragging, start. */
            int r = region_from_coords(state, ds, ui->dragx, ui->dragy);
            if (r >= 0) {
                ui->drag_colour = state->colouring[r];
                ui->drag_pencil = (ui->drag_colour >= 0) ? 0 : state->pencil[r];
            } else {
                ui->drag_colour = -1;
                ui->drag_pencil = 0;
            }
            ui->cur_moved = 0;
            return "";
        } else { /* currently cursor-dragging; drop the colour in the new region. */
            x = COORD(ui->cur_x) + TILESIZE/2 + EPSILON_X(ui->cur_lastmove);
            y = COORD(ui->cur_y) + TILESIZE/2 + EPSILON_Y(ui->cur_lastmove);
            alt_button = (button == CURSOR_SELECT2) ? 1 : 0;
            /* Double-select removes current colour. */
            if (!ui->cur_moved) ui->drag_colour = -1;
            goto drag_dropped;
        }
    }

    if (button == LEFT_BUTTON || button == RIGHT_BUTTON) {
        int r = region_from_coords(state, ds, x, y);

        if (r >= 0) {
            ui->drag_colour = state->colouring[r];
            ui->drag_pencil = state->pencil[r];
            if (ui->drag_colour >= 0)
                ui->drag_pencil = 0;  /* should be already, but double-check */
        } else {
            ui->drag_colour = -1;
            ui->drag_pencil = 0;
        }
        ui->dragx = x;
        ui->dragy = y;
        ui->cur_visible = 0;
        return "";
    }

    if ((button == LEFT_DRAG || button == RIGHT_DRAG) &&
        ui->drag_colour > -2) {
        ui->dragx = x;
        ui->dragy = y;
        return "";
    }

    if ((button == LEFT_RELEASE || button == RIGHT_RELEASE) &&
        ui->drag_colour > -2) {
        alt_button = (button == RIGHT_RELEASE) ? 1 : 0;
        goto drag_dropped;
    }

    return NULL;

drag_dropped:
    {
        int r = region_from_coords(state, ds, x, y);
        int c = ui->drag_colour;
        int p = ui->drag_pencil;
        int oldp;

        /*
         * Cancel the drag, whatever happens.
         */
        ui->drag_colour = -2;

        if (r < 0)
            return "";                 /* drag into border; do nothing else */

        if (state->map->immutable[r])
            return "";                 /* can't change this region */

        if (state->colouring[r] == c && state->pencil[r] == p)
            return "";                 /* don't _need_ to change this region */

        if (alt_button) {
            if (state->colouring[r] >= 0) {
                /* Can't pencil on a coloured region */
                return "";
            } else if (c >= 0) {
                /* Right-dragging from colour to blank toggles one pencil */
                p = state->pencil[r] ^ (1 << c);
                c = -1;
            }
            /* Otherwise, right-dragging from blank to blank is equivalent
             * to left-dragging. */
        }

        bufp = buf;
        oldp = state->pencil[r];
        if (c != state->colouring[r]) {
            bufp += sprintf(bufp, ";%c:%d", (int)(c < 0 ? 'C' : '0' + c), r);
            if (c >= 0)
                oldp = 0;
        }
        if (p != oldp) {
            int i;
            for (i = 0; i < FOUR; i++)
                if ((oldp ^ p) & (1 << i))
                    bufp += sprintf(bufp, ";p%c:%d", (int)('0' + i), r);
        }

        return dupstr(buf+1);          /* ignore first semicolon */
    }
}

static game_state *execute_move(const game_state *state, const char *move)
{
    int n = state->p.n;
    game_state *ret = dup_game(state);
    int c, k, adv, i;

    while (*move) {
        int pencil = FALSE;

        c = *move;
        if (c == 'p') {
            pencil = TRUE;
            c = *++move;
        }
        if ((c == 'C' || (c >= '0' && c < '0'+FOUR)) &&
            sscanf(move+1, ":%d%n", &k, &adv) == 1 &&
            k >= 0 && k < state->p.n) {
            move += 1 + adv;
            if (pencil) {
                if (ret->colouring[k] >= 0) {
                    free_game(ret);
                    return NULL;
                }
                if (c == 'C')
                    ret->pencil[k] = 0;
                else
                    ret->pencil[k] ^= 1 << (c - '0');
            } else {
                ret->colouring[k] = (c == 'C' ? -1 : c - '0');
                ret->pencil[k] = 0;
            }
        } else if (*move == 'S') {
            move++;
            ret->cheated = TRUE;
        } else {
            free_game(ret);
            return NULL;
        }

        if (*move && *move != ';') {
            free_game(ret);
            return NULL;
        }
        if (*move)
            move++;
    }

    /*
     * Check for completion.
     */
    if (!ret->completed) {
        int ok = TRUE;

        for (i = 0; i < n; i++)
            if (ret->colouring[i] < 0) {
                ok = FALSE;
                break;
            }

        if (ok) {
            for (i = 0; i < ret->map->ngraph; i++) {
                int j = ret->map->graph[i] / n;
                int k = ret->map->graph[i] % n;
                if (ret->colouring[j] == ret->colouring[k]) {
                    ok = FALSE;
                    break;
                }
            }
        }

        if (ok)
            ret->completed = TRUE;
    }

    return ret;
}

/* ----------------------------------------------------------------------
 * Drawing routines.
 */

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;
    ads.tilesize = tilesize;

    *x = params->w * TILESIZE + 2 * BORDER + 1;
    *y = params->h * TILESIZE + 2 * BORDER + 1;
}

static void game_set_size(drawing *dr, game_drawstate *ds,
                          const game_params *params, int tilesize)
{
    ds->tilesize = tilesize;

    assert(!ds->bl);                   /* set_size is never called twice */
    ds->bl = blitter_new(dr, TILESIZE+3, TILESIZE+3);
}

const float map_colours[FOUR][3] = {
#ifdef VIVID_COLOURS
    /* Use more vivid colours (e.g. on the Pocket PC) */
    {0.75F, 0.25F, 0.25F},
    {0.3F,  0.7F,  0.3F},
    {0.3F,  0.3F,  0.7F},
    {0.85F, 0.85F, 0.1F},
#else
    {0.7F, 0.5F, 0.4F},
    {0.8F, 0.7F, 0.4F},
    {0.5F, 0.6F, 0.4F},
    {0.55F, 0.45F, 0.35F},
#endif
};
const int map_hatching[FOUR] = {
    HATCH_VERT, HATCH_SLASH, HATCH_HORIZ, HATCH_BACKSLASH
};

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;

    memcpy(ret + COL_0 * 3, map_colours[0], 3 * sizeof(float));
    memcpy(ret + COL_1 * 3, map_colours[1], 3 * sizeof(float));
    memcpy(ret + COL_2 * 3, map_colours[2], 3 * sizeof(float));
    memcpy(ret + COL_3 * 3, map_colours[3], 3 * sizeof(float));

    ret[COL_ERROR * 3 + 0] = 1.0F;
    ret[COL_ERROR * 3 + 1] = 0.0F;
    ret[COL_ERROR * 3 + 2] = 0.0F;

    ret[COL_ERRTEXT * 3 + 0] = 1.0F;
    ret[COL_ERRTEXT * 3 + 1] = 1.0F;
    ret[COL_ERRTEXT * 3 + 2] = 1.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 = 0;
    ds->drawn = snewn(state->p.w * state->p.h, unsigned long);
    for (i = 0; i < state->p.w * state->p.h; i++)
        ds->drawn[i] = 0xFFFFL;
    ds->todraw = snewn(state->p.w * state->p.h, unsigned long);
    ds->started = FALSE;
    ds->bl = NULL;
    ds->drag_visible = FALSE;
    ds->dragx = ds->dragy = -1;

    return ds;
}

static void game_free_drawstate(drawing *dr, game_drawstate *ds)
{
    sfree(ds->drawn);
    sfree(ds->todraw);
    if (ds->bl)
        blitter_free(dr, ds->bl);
    sfree(ds);
}

static void draw_error(drawing *dr, game_drawstate *ds, int x, int y)
{
    int coords[8];
    int yext, xext;

    /*
     * Draw a diamond.
     */
    coords[0] = x - TILESIZE*2/5;
    coords[1] = y;
    coords[2] = x;
    coords[3] = y - TILESIZE*2/5;
    coords[4] = x + TILESIZE*2/5;
    coords[5] = y;
    coords[6] = x;
    coords[7] = y + TILESIZE*2/5;
    draw_polygon(dr, coords, 4, COL_ERROR, COL_GRID);

    /*
     * Draw an exclamation mark in the diamond. This turns out to
     * look unpleasantly off-centre if done via draw_text, so I do
     * it by hand on the basis that exclamation marks aren't that
     * difficult to draw...
     */
    xext = TILESIZE/16;
    yext = TILESIZE*2/5 - (xext*2+2);
    draw_rect(dr, x-xext, y-yext, xext*2+1, yext*2+1 - (xext*3),
              COL_ERRTEXT);
    draw_rect(dr, x-xext, y+yext-xext*2+1, xext*2+1, xext*2, COL_ERRTEXT);
}

static void draw_square(drawing *dr, game_drawstate *ds,
                        const game_params *params, struct map *map,
                        int x, int y, unsigned long v)
{
    int w = params->w, h = params->h, wh = w*h;
    int tv, bv, xo, yo, i, j, oldj;
    unsigned long errs, pencil, show_numbers;

    errs = v & ERR_MASK;
    v &= ~ERR_MASK;
    pencil = v & PENCIL_MASK;
    v &= ~PENCIL_MASK;
    show_numbers = v & SHOW_NUMBERS;
    v &= ~SHOW_NUMBERS;
    tv = v / FIVE;
    bv = v % FIVE;

    clip(dr, COORD(x), COORD(y), TILESIZE, TILESIZE);

    /*
     * Draw the region colour.
     */
    draw_rect(dr, COORD(x), COORD(y), TILESIZE, TILESIZE,
              (tv == FOUR ? COL_BACKGROUND : COL_0 + tv));
    /*
     * Draw the second region colour, if this is a diagonally
     * divided square.
     */
    if (map->map[TE * wh + y*w+x] != map->map[BE * wh + y*w+x]) {
        int coords[6];
        coords[0] = COORD(x)-1;
        coords[1] = COORD(y+1)+1;
        if (map->map[LE * wh + y*w+x] == map->map[TE * wh + y*w+x])
            coords[2] = COORD(x+1)+1;
        else
            coords[2] = COORD(x)-1;
        coords[3] = COORD(y)-1;
        coords[4] = COORD(x+1)+1;
        coords[5] = COORD(y+1)+1;
        draw_polygon(dr, coords, 3,
                     (bv == FOUR ? COL_BACKGROUND : COL_0 + bv), COL_GRID);
    }

    /*
     * Draw `pencil marks'. Currently we arrange these in a square
     * formation, which means we may be in trouble if the value of
     * FOUR changes later...
     */
    assert(FOUR == 4);
    for (yo = 0; yo < 4; yo++)
        for (xo = 0; xo < 4; xo++) {
            int te = map->map[TE * wh + y*w+x];
            int e, ee, c;

            e = (yo < xo && yo < 3-xo ? TE :
                 yo > xo && yo > 3-xo ? BE :
                 xo < 2 ? LE : RE);
            ee = map->map[e * wh + y*w+x];

            if (xo != (yo * 2 + 1) % 5)
                continue;
            c = yo;

            if (!(pencil & ((ee == te ? PENCIL_T_BASE : PENCIL_B_BASE) << c)))
                continue;

            if (yo == xo &&
                (map->map[TE * wh + y*w+x] != map->map[LE * wh + y*w+x]))
                continue;              /* avoid TL-BR diagonal line */
            if (yo == 3-xo &&
                (map->map[TE * wh + y*w+x] != map->map[RE * wh + y*w+x]))
                continue;              /* avoid BL-TR diagonal line */

            draw_circle(dr, COORD(x) + (xo+1)*TILESIZE/5,
                        COORD(y) + (yo+1)*TILESIZE/5,
                        TILESIZE/7, COL_0 + c, COL_0 + c);
        }

    /*
     * Draw the grid lines, if required.
     */
    if (x <= 0 || map->map[RE*wh+y*w+(x-1)] != map->map[LE*wh+y*w+x])
        draw_rect(dr, COORD(x), COORD(y), 1, TILESIZE, COL_GRID);
    if (y <= 0 || map->map[BE*wh+(y-1)*w+x] != map->map[TE*wh+y*w+x])
        draw_rect(dr, COORD(x), COORD(y), TILESIZE, 1, COL_GRID);
    if (x <= 0 || y <= 0 ||
        map->map[RE*wh+(y-1)*w+(x-1)] != map->map[TE*wh+y*w+x] ||
        map->map[BE*wh+(y-1)*w+(x-1)] != map->map[LE*wh+y*w+x])
        draw_rect(dr, COORD(x), COORD(y), 1, 1, COL_GRID);

    /*
     * Draw error markers.
     */
    for (yo = 0; yo < 3; yo++)
        for (xo = 0; xo < 3; xo++)
            if (errs & (ERR_BASE << (yo*3+xo)))
                draw_error(dr, ds,
                           (COORD(x)*2+TILESIZE*xo)/2,
                           (COORD(y)*2+TILESIZE*yo)/2);

    /*
     * Draw region numbers, if desired.
     */
    if (show_numbers) {
        oldj = -1;
        for (i = 0; i < 2; i++) {
            j = map->map[(i?BE:TE)*wh+y*w+x];
            if (oldj == j)
                continue;
            oldj = j;

            xo = map->regionx[j] - 2*x;
            yo = map->regiony[j] - 2*y;
            if (xo >= 0 && xo <= 2 && yo >= 0 && yo <= 2) {
                char buf[80];
                sprintf(buf, "%d", j);
                draw_text(dr, (COORD(x)*2+TILESIZE*xo)/2,
                          (COORD(y)*2+TILESIZE*yo)/2,
                          FONT_VARIABLE, 3*TILESIZE/5,
                          ALIGN_HCENTRE|ALIGN_VCENTRE,
                          COL_GRID, buf);
            }
        }
    }

    unclip(dr);

    draw_update(dr, COORD(x), COORD(y), TILESIZE, TILESIZE);
}

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 w = state->p.w, h = state->p.h, wh = w*h, n = state->p.n;
    int x, y, i;
    int flash;

    if (ds->drag_visible) {
        blitter_load(dr, ds->bl, ds->dragx, ds->dragy);
        draw_update(dr, ds->dragx, ds->dragy, TILESIZE + 3, TILESIZE + 3);
        ds->drag_visible = FALSE;
    }

    /*
     * 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.
     */
    if (!ds->started) {
        int ww, wh;

        game_compute_size(&state->p, TILESIZE, &ww, &wh);
        draw_rect(dr, 0, 0, ww, wh, COL_BACKGROUND);
        draw_rect(dr, COORD(0), COORD(0), w*TILESIZE+1, h*TILESIZE+1,
                  COL_GRID);

        draw_update(dr, 0, 0, ww, wh);
        ds->started = TRUE;
    }

    if (flashtime) {
        if (flash_type == 1)
            flash = (int)(flashtime * FOUR / flash_length);
        else
            flash = 1 + (int)(flashtime * THREE / flash_length);
    } else
        flash = -1;

    /*
     * Set up the `todraw' array.
     */
    for (y = 0; y < h; y++)
        for (x = 0; x < w; x++) {
            int tv = state->colouring[state->map->map[TE * wh + y*w+x]];
            int bv = state->colouring[state->map->map[BE * wh + y*w+x]];
            unsigned long v;

            if (tv < 0)
                tv = FOUR;
            if (bv < 0)
                bv = FOUR;

            if (flash >= 0) {
                if (flash_type == 1) {
                    if (tv == flash)
                        tv = FOUR;
                    if (bv == flash)
                        bv = FOUR;
                } else if (flash_type == 2) {
                    if (flash % 2)
                        tv = bv = FOUR;
                } else {
                    if (tv != FOUR)
                        tv = (tv + flash) % FOUR;
                    if (bv != FOUR)
                        bv = (bv + flash) % FOUR;
                }
            }

            v = tv * FIVE + bv;

            /*
             * Add pencil marks.
             */
            for (i = 0; i < FOUR; i++) {
                if (state->colouring[state->map->map[TE * wh + y*w+x]] < 0 &&
                    (state->pencil[state->map->map[TE * wh + y*w+x]] & (1<<i)))
                    v |= PENCIL_T_BASE << i;
                if (state->colouring[state->map->map[BE * wh + y*w+x]] < 0 &&
                    (state->pencil[state->map->map[BE * wh + y*w+x]] & (1<<i)))
                    v |= PENCIL_B_BASE << i;
            }

            if (ui->show_numbers)
                v |= SHOW_NUMBERS;

            ds->todraw[y*w+x] = v;
        }

    /*
     * Add error markers to the `todraw' array.
     */
    for (i = 0; i < state->map->ngraph; i++) {
        int v1 = state->map->graph[i] / n;
        int v2 = state->map->graph[i] % n;
        int xo, yo;

        if (state->colouring[v1] < 0 || state->colouring[v2] < 0)
            continue;
        if (state->colouring[v1] != state->colouring[v2])
            continue;

        x = state->map->edgex[i];
        y = state->map->edgey[i];

        xo = x % 2; x /= 2;
        yo = y % 2; y /= 2;

        ds->todraw[y*w+x] |= ERR_BASE << (yo*3+xo);
        if (xo == 0) {
            assert(x > 0);
            ds->todraw[y*w+(x-1)] |= ERR_BASE << (yo*3+2);
        }
        if (yo == 0) {
            assert(y > 0);
            ds->todraw[(y-1)*w+x] |= ERR_BASE << (2*3+xo);
        }
        if (xo == 0 && yo == 0) {
            assert(x > 0 && y > 0);
            ds->todraw[(y-1)*w+(x-1)] |= ERR_BASE << (2*3+2);
        }
    }

    /*
     * Now actually draw everything.
     */
    for (y = 0; y < h; y++)
        for (x = 0; x < w; x++) {
            unsigned long v = ds->todraw[y*w+x];
            if (ds->drawn[y*w+x] != v) {
                draw_square(dr, ds, &state->p, state->map, x, y, v);
                ds->drawn[y*w+x] = v;
            }
        }

    /*
     * Draw the dragged colour blob if any.
     */
    if ((ui->drag_colour > -2) || ui->cur_visible) {
        int bg, iscur = 0;
        if (ui->drag_colour >= 0)
            bg = COL_0 + ui->drag_colour;
        else if (ui->drag_colour == -1) {
            bg = COL_BACKGROUND;
        } else {
            int r = region_from_coords(state, ds, ui->dragx, ui->dragy);
            int c = (r < 0) ? -1 : state->colouring[r];
            assert(ui->cur_visible);
            /*bg = COL_GRID;*/
            bg = (c < 0) ? COL_BACKGROUND : COL_0 + c;
            iscur = 1;
        }

        ds->dragx = ui->dragx - TILESIZE/2 - 2;
        ds->dragy = ui->dragy - TILESIZE/2 - 2;
        blitter_save(dr, ds->bl, ds->dragx, ds->dragy);
        draw_circle(dr, ui->dragx, ui->dragy,
                    iscur ? TILESIZE/4 : TILESIZE/2, bg, COL_GRID);
        for (i = 0; i < FOUR; i++)
            if (ui->drag_pencil & (1 << i))
                draw_circle(dr, ui->dragx + ((i*4+2)%10-3) * TILESIZE/10,
                            ui->dragy + (i*2-3) * TILESIZE/10,
                            TILESIZE/8, COL_0 + i, COL_0 + i);
        draw_update(dr, ds->dragx, ds->dragy, TILESIZE + 3, TILESIZE + 3);
        ds->drag_visible = 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)
{
    if (!oldstate->completed && newstate->completed &&
        !oldstate->cheated && !newstate->cheated) {
        if (flash_type < 0) {
            char *env = getenv("MAP_ALTERNATIVE_FLASH");
            if (env)
                flash_type = atoi(env);
            else
                flash_type = 0;
            flash_length = (flash_type == 1 ? 0.50F : 0.30F);
        }
        return flash_length;
    } else
        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 4mm squares by default, I think. Simplest way to
     * compute this size is to compute the pixel puzzle size at a
     * given tile size and then scale.
     */
    game_compute_size(params, 400, &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->p.w, h = state->p.h, wh = w*h, n = state->p.n;
    int ink, c[FOUR], i;
    int x, y, r;
    int *coords, ncoords, coordsize;

    /* Ick: fake up `ds->tilesize' for macro expansion purposes */
    struct { int tilesize; } ads, *ds = &ads;
    /* We can't call game_set_size() here because we don't want a blitter */
    ads.tilesize = tilesize;

    ink = print_mono_colour(dr, 0);
    for (i = 0; i < FOUR; i++)
        c[i] = print_rgb_hatched_colour(dr, map_colours[i][0],
                                        map_colours[i][1], map_colours[i][2],
                                        map_hatching[i]);

    coordsize = 0;
    coords = NULL;

    print_line_width(dr, TILESIZE / 16);

    /*
     * Draw a single filled polygon around each region.
     */
    for (r = 0; r < n; r++) {
        int octants[8], lastdir, d1, d2, ox, oy;

        /*
         * Start by finding a point on the region boundary. Any
         * point will do. To do this, we'll search for a square
         * containing the region and then decide which corner of it
         * to use.
         */
        x = w;
        for (y = 0; y < h; y++) {
            for (x = 0; x < w; x++) {
                if (state->map->map[wh*0+y*w+x] == r ||
                    state->map->map[wh*1+y*w+x] == r ||
                    state->map->map[wh*2+y*w+x] == r ||
                    state->map->map[wh*3+y*w+x] == r)
                    break;
            }
            if (x < w)
                break;
        }
        assert(y < h && x < w);        /* we must have found one somewhere */
        /*
         * This is the first square in lexicographic order which
         * contains part of this region. Therefore, one of the top
         * two corners of the square must be what we're after. The
         * only case in which it isn't the top left one is if the
         * square is diagonally divided and the region is in the
         * bottom right half.
         */
        if (state->map->map[wh*TE+y*w+x] != r &&
            state->map->map[wh*LE+y*w+x] != r)
            x++;                       /* could just as well have done y++ */

        /*
         * Now we have a point on the region boundary. Trace around
         * the region until we come back to this point,
         * accumulating coordinates for a polygon draw operation as
         * we go.
         */
        lastdir = -1;
        ox = x;
        oy = y;
        ncoords = 0;

        do {
            /*
             * There are eight possible directions we could head in
             * from here. We identify them by octant numbers, and
             * we also use octant numbers to identify the spaces
             * between them:
             * 
             *   6   7   0
             *    \ 7|0 /
             *     \ | /
             *    6 \|/ 1
             * 5-----+-----1
             *    5 /|\ 2
             *     / | \
             *    / 4|3 \
             *   4   3   2
             */
            octants[0] = x<w && y>0 ? state->map->map[wh*LE+(y-1)*w+x] : -1;
            octants[1] = x<w && y>0 ? state->map->map[wh*BE+(y-1)*w+x] : -1;
            octants[2] = x<w && y<h ? state->map->map[wh*TE+y*w+x] : -1;
            octants[3] = x<w && y<h ? state->map->map[wh*LE+y*w+x] : -1;
            octants[4] = x>0 && y<h ? state->map->map[wh*RE+y*w+(x-1)] : -1;
            octants[5] = x>0 && y<h ? state->map->map[wh*TE+y*w+(x-1)] : -1;
            octants[6] = x>0 && y>0 ? state->map->map[wh*BE+(y-1)*w+(x-1)] :-1;
            octants[7] = x>0 && y>0 ? state->map->map[wh*RE+(y-1)*w+(x-1)] :-1;

            d1 = d2 = -1;
            for (i = 0; i < 8; i++)
                if ((octants[i] == r) ^ (octants[(i+1)%8] == r)) {
                    assert(d2 == -1);
                    if (d1 == -1)
                        d1 = i;
                    else
                        d2 = i;
                }

            assert(d1 != -1 && d2 != -1);
            if (d1 == lastdir)
                d1 = d2;

            /*
             * Now we're heading in direction d1. Save the current
             * coordinates.
             */
            if (ncoords + 2 > coordsize) {
                coordsize += 128;
                coords = sresize(coords, coordsize, int);
            }
            coords[ncoords++] = COORD(x);
            coords[ncoords++] = COORD(y);

            /*
             * Compute the new coordinates.
             */
            x += (d1 % 4 == 3 ? 0 : d1 < 4 ? +1 : -1);
            y += (d1 % 4 == 1 ? 0 : d1 > 1 && d1 < 5 ? +1 : -1);
            assert(x >= 0 && x <= w && y >= 0 && y <= h);

            lastdir = d1 ^ 4;
        } while (x != ox || y != oy);

        draw_polygon(dr, coords, ncoords/2,
                     state->colouring[r] >= 0 ?
                     c[state->colouring[r]] : -1, ink);
    }
    sfree(coords);
}

#ifdef COMBINED
#define thegame map
#endif

const struct game thegame = {
    "Map", "games.map", "map",
    default_params,
    game_fetch_preset,
    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,
    FALSE, game_can_format_as_text_now, game_text_format,
    new_ui,
    free_ui,
    encode_ui,
    decode_ui,
    game_changed_state,
    interpret_move,
    execute_move,
    20, 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, TRUE, game_print_size, game_print,
    FALSE,                             /* wants_statusbar */
    FALSE, game_timing_state,
    0,                                 /* flags */
};

#ifdef STANDALONE_SOLVER

int main(int argc, char **argv)
{
    game_params *p;
    game_state *s;
    char *id = NULL, *desc, *err;
    int grade = FALSE;
    int ret, diff, really_verbose = FALSE;
    struct solver_scratch *sc;
    int i;

    while (--argc > 0) {
        char *p = *++argv;
        if (!strcmp(p, "-v")) {
            really_verbose = TRUE;
        } else if (!strcmp(p, "-g")) {
            grade = TRUE;
        } else if (*p == '-') {
            fprintf(stderr, "%s: unrecognised option `%s'\n", argv[0], p);
            return 1;
        } else {
            id = p;
        }
    }

    if (!id) {
        fprintf(stderr, "usage: %s [-g | -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);

    sc = new_scratch(s->map->graph, s->map->n, s->map->ngraph);

    /*
     * When solving an Easy puzzle, we don't want to bother the
     * user with Hard-level deductions. For this reason, we grade
     * the puzzle internally before doing anything else.
     */
    ret = -1;                          /* placate optimiser */
    for (diff = 0; diff < DIFFCOUNT; diff++) {
        for (i = 0; i < s->map->n; i++)
            if (!s->map->immutable[i])
                s->colouring[i] = -1;
        ret = map_solver(sc, s->map->graph, s->map->n, s->map->ngraph,
                         s->colouring, diff);
        if (ret < 2)
            break;
    }

    if (diff == DIFFCOUNT) {
        if (grade)
            printf("Difficulty rating: harder than Hard, or ambiguous\n");
        else
            printf("Unable to find a unique solution\n");
    } else {
        if (grade) {
            if (ret == 0)
                printf("Difficulty rating: impossible (no solution exists)\n");
            else if (ret == 1)
                printf("Difficulty rating: %s\n", map_diffnames[diff]);
        } else {
            verbose = really_verbose;
            for (i = 0; i < s->map->n; i++)
                if (!s->map->immutable[i])
                    s->colouring[i] = -1;
            ret = map_solver(sc, s->map->graph, s->map->n, s->map->ngraph,
                             s->colouring, diff);
            if (ret == 0)
                printf("Puzzle is inconsistent\n");
            else {
                int col = 0;

                for (i = 0; i < s->map->n; i++) {
                    printf("%5d <- %c%c", i, colnames[s->colouring[i]],
                           (col < 6 && i+1 < s->map->n ? ' ' : '\n'));
                    if (++col == 7)
                        col = 0;
                }
            }
        }
    }

    return 0;
}

#endif

/* vim: set shiftwidth=4 tabstop=8: */