sgt-puzzles/tents.c

/*
 * tents.c: Puzzle involving placing tents next to trees subject to
 * some confusing conditions.
 * 
 * TODO:
 *
 *  - it might be nice to make setter-provided tent/nontent clues
 *    inviolable?
 *     * on the other hand, this would introduce considerable extra
 *       complexity and size into the game state; also inviolable
 *       clues would have to be marked as such somehow, in an
 *       intrusive and annoying manner. Since they're never
 *       generated by _my_ generator, I'm currently more inclined
 *       not to bother.
 * 
 *  - more difficult levels at the top end?
 *     * for example, sometimes we can deduce that two BLANKs in
 *       the same row are each adjacent to the same unattached tree
 *       and to nothing else, implying that they can't both be
 *       tents; this enables us to rule out some extra combinations
 *       in the row-based deduction loop, and hence deduce more
 *       from the number in that row than we could otherwise do.
 *     * that by itself doesn't seem worth implementing a new
 *       difficulty level for, but if I can find a few more things
 *       like that then it might become worthwhile.
 *     * I wonder if there's a sensible heuristic for where to
 *       guess which would make a recursive solver viable?
 */

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>
#include <ctype.h>
#include <limits.h>
#ifdef NO_TGMATH_H
#  include <math.h>
#else
#  include <tgmath.h>
#endif

#include "puzzles.h"
#include "matching.h"

/*
 * Design discussion
 * -----------------
 * 
 * The rules of this puzzle as available on the WWW are poorly
 * specified. The bits about tents having to be orthogonally
 * adjacent to trees, tents not being even diagonally adjacent to
 * one another, and the number of tents in each row and column
 * being given are simple enough; the difficult bit is the
 * tent-to-tree matching.
 * 
 * Some sources use simplistic wordings such as `each tree is
 * exactly connected to only one tent', which is extremely unclear:
 * it's easy to read erroneously as `each tree is _orthogonally
 * adjacent_ to exactly one tent', which is definitely incorrect.
 * Even the most coherent sources I've found don't do a much better
 * job of stating the rule.
 * 
 * A more precise statement of the rule is that it must be possible
 * to find a bijection f between tents and trees such that each
 * tree T is orthogonally adjacent to the tent f(T), but that a
 * tent is permitted to be adjacent to other trees in addition to
 * its own. This slightly non-obvious criterion is what gives this
 * puzzle most of its subtlety.
 * 
 * However, there's a particularly subtle ambiguity left over. Is
 * the bijection between tents and trees required to be _unique_?
 * In other words, is that bijection conceptually something the
 * player should be able to exhibit as part of the solution (even
 * if they aren't actually required to do so)? Or is it sufficient
 * to have a unique _placement_ of the tents which gives rise to at
 * least one suitable bijection?
 * 
 * The puzzle shown to the right of this       .T. 2      *T* 2
 * paragraph illustrates the problem. There    T.T 0  ->  T-T 0
 * are two distinct bijections available.      .T. 2      *T* 2
 * The answer to the above question will
 * determine whether it's a valid puzzle.      202        202
 * 
 * This is an important question, because it affects both the
 * player and the generator. Eventually I found all the instances
 * of this puzzle I could Google up, solved them all by hand, and
 * verified that in all cases the tree/tent matching was uniquely
 * determined given the tree and tent positions. Therefore, the
 * puzzle as implemented in this source file takes the following
 * policy:
 * 
 *  - When checking a user-supplied solution for correctness, only
 *    verify that there exists _at least_ one matching.
 *  - When generating a puzzle, enforce that there must be
 *    _exactly_ one.
 * 
 * Algorithmic implications
 * ------------------------
 * 
 * Another way of phrasing the tree/tent matching criterion is to
 * say that the bipartite adjacency graph between trees and tents
 * has a perfect matching. That is, if you construct a graph which
 * has a vertex per tree and a vertex per tent, and an edge between
 * any tree and tent which are orthogonally adjacent, it is
 * possible to find a set of N edges of that graph (where N is the
 * number of trees and also the number of tents) which between them
 * connect every tree to every tent.
 * 
 * The most efficient known algorithms for finding such a matching
 * given a graph, as far as I'm aware, are the Munkres assignment
 * algorithm (also known as the Hungarian algorithm) and the
 * Ford-Fulkerson algorithm (for finding optimal flows in
 * networks). Each of these takes O(N^3) running time; so we're
 * talking O(N^3) time to verify any candidate solution to this
 * puzzle. That's just about OK if you're doing it once per mouse
 * click (and in fact not even that, since the sensible thing to do
 * is check all the _other_ puzzle criteria and only wade into this
 * quagmire if none are violated); but if the solver had to keep
 * doing N^3 work internally, then it would probably end up with
 * more like N^5 or N^6 running time, and grid generation would
 * become very clunky.
 * 
 * Fortunately, I've been able to prove a very useful property of
 * _unique_ perfect matchings, by adapting the proof of Hall's
 * Marriage Theorem. For those unaware of Hall's Theorem, I'll
 * recap it and its proof: it states that a bipartite graph
 * contains a perfect matching iff every set of vertices on the
 * left side of the graph have a neighbourhood _at least_ as big on
 * the right.
 * 
 * This condition is obviously satisfied if a perfect matching does
 * exist; each left-side node has a distinct right-side node which
 * is the one assigned to it by the matching, and thus any set of n
 * left vertices must have a combined neighbourhood containing at
 * least the n corresponding right vertices, and possibly others
 * too. Alternatively, imagine if you had (say) three left-side
 * nodes all of which were connected to only two right-side nodes
 * between them: any perfect matching would have to assign one of
 * those two right nodes to each of the three left nodes, and still
 * give the three left nodes a different right node each. This is
 * of course impossible.
 *
 * To prove the converse (that if every subset of left vertices
 * satisfies the Hall condition then a perfect matching exists),
 * consider trying to find a proper subset of the left vertices
 * which _exactly_ satisfies the Hall condition: that is, its right
 * neighbourhood is precisely the same size as it. If we can find
 * such a subset, then we can split the bipartite graph into two
 * smaller ones: one consisting of the left subset and its right
 * neighbourhood, the other consisting of everything else. Edges
 * from the left side of the former graph to the right side of the
 * latter do not exist, by construction; edges from the right side
 * of the former to the left of the latter cannot be part of any
 * perfect matching because otherwise the left subset would not be
 * left with enough distinct right vertices to connect to (this is
 * exactly the same deduction used in Solo's set analysis). You can
 * then prove (left as an exercise) that both these smaller graphs
 * still satisfy the Hall condition, and therefore the proof will
 * follow by induction.
 * 
 * There's one other possibility, which is the case where _no_
 * proper subset of the left vertices has a right neighbourhood of
 * exactly the same size. That is, every left subset has a strictly
 * _larger_ right neighbourhood. In this situation, we can simply
 * remove an _arbitrary_ edge from the graph. This cannot reduce
 * the size of any left subset's right neighbourhood by more than
 * one, so if all neighbourhoods were strictly bigger than they
 * needed to be initially, they must now still be _at least as big_
 * as they need to be. So we can keep throwing out arbitrary edges
 * until we find a set which exactly satisfies the Hall condition,
 * and then proceed as above. []
 * 
 * That's Hall's theorem. I now build on this by examining the
 * circumstances in which a bipartite graph can have a _unique_
 * perfect matching. It is clear that in the second case, where no
 * left subset exactly satisfies the Hall condition and so we can
 * remove an arbitrary edge, there cannot be a unique perfect
 * matching: given one perfect matching, we choose our arbitrary
 * removed edge to be one of those contained in it, and then we can
 * still find a perfect matching in the remaining graph, which will
 * be a distinct perfect matching in the original.
 * 
 * So it is a necessary condition for a unique perfect matching
 * that there must be at least one proper left subset which
 * _exactly_ satisfies the Hall condition. But now consider the
 * smaller graph constructed by taking that left subset and its
 * neighbourhood: if the graph as a whole had a unique perfect
 * matching, then so must this smaller one, which means we can find
 * a proper left subset _again_, and so on. Repeating this process
 * must eventually reduce us to a graph with only one left-side
 * vertex (so there are no proper subsets at all); this vertex must
 * be connected to only one right-side vertex, and hence must be so
 * in the original graph as well (by construction). So we can
 * discard this vertex pair from the graph, and any other edges
 * that involved it (which will by construction be from other left
 * vertices only), and the resulting smaller graph still has a
 * unique perfect matching which means we can do the same thing
 * again.
 * 
 * In other words, given any bipartite graph with a unique perfect
 * matching, we can find that matching by the following extremely
 * simple algorithm:
 * 
 *  - Find a left-side vertex which is only connected to one
 *    right-side vertex.
 *  - Assign those vertices to one another, and therefore discard
 *    any other edges connecting to that right vertex.
 *  - Repeat until all vertices have been matched.
 * 
 * This algorithm can be run in O(V+E) time (where V is the number
 * of vertices and E is the number of edges in the graph), and the
 * only way it can fail is if there is not a unique perfect
 * matching (either because there is no matching at all, or because
 * it isn't unique; but it can't distinguish those cases).
 * 
 * Thus, the internal solver in this source file can be confident
 * that if the tree/tent matching is uniquely determined by the
 * tree and tent positions, it can find it using only this kind of
 * obvious and simple operation: assign a tree to a tent if it
 * cannot possibly belong to any other tent, and vice versa. If the
 * solver were _only_ trying to determine the matching, even that
 * `vice versa' wouldn't be required; but it can come in handy when
 * not all the tents have been placed yet. I can therefore be
 * reasonably confident that as long as my solver doesn't need to
 * cope with grids that have a non-unique matching, it will also
 * not need to do anything complicated like set analysis between
 * trees and tents.
 */

/*
 * 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
static bool verbose = false;
#elif defined SOLVER_DIAGNOSTICS
#define verbose true
#endif

/*
 * 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(TRICKY,Tricky,t)
#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 tents_diffnames[] = { DIFFLIST(TITLE) };
static char const tents_diffchars[] = DIFFLIST(ENCODE);
#define DIFFCONFIG DIFFLIST(CONFIG)

enum {
    COL_BACKGROUND,
    COL_GRID,
    COL_GRASS,
    COL_TREETRUNK,
    COL_TREELEAF,
    COL_TENT,
    COL_ERROR,
    COL_ERRTEXT,
    COL_ERRTRUNK,
    NCOLOURS
};

enum { BLANK, TREE, TENT, NONTENT, MAGIC };

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

struct numbers {
    int refcount;
    int *numbers;
};

struct game_state {
    game_params p;
    char *grid;
    struct numbers *numbers;
    bool completed, used_solve;
};

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

    ret->w = ret->h = 8;
    ret->diff = DIFF_EASY;

    return ret;
}

static const struct game_params tents_presets[] = {
    {8, 8, DIFF_EASY},
    {8, 8, DIFF_TRICKY},
    {10, 10, DIFF_EASY},
    {10, 10, DIFF_TRICKY},
    {15, 15, DIFF_EASY},
    {15, 15, DIFF_TRICKY},
};

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

    if (i < 0 || i >= lenof(tents_presets))
        return false;

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

    sprintf(str, "%dx%d %s", ret->w, ret->h, tents_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)
{
    params->w = params->h = atoi(string);
    while (*string && isdigit((unsigned char)*string)) string++;
    if (*string == 'x') {
        string++;
        params->h = atoi(string);
	while (*string && isdigit((unsigned char)*string)) string++;
    }
    if (*string == 'd') {
	int i;
	string++;
	for (i = 0; i < DIFFCOUNT; i++)
	    if (*string == tents_diffchars[i])
		params->diff = i;
	if (*string) string++;
    }
}

static char *encode_params(const game_params *params, bool full)
{
    char buf[120];

    sprintf(buf, "%dx%d", params->w, params->h);
    if (full)
	sprintf(buf + strlen(buf), "d%c",
		tents_diffchars[params->diff]);
    return dupstr(buf);
}

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

    ret = snewn(4, config_item);

    ret[0].name = "Width";
    ret[0].type = C_STRING;
    sprintf(buf, "%d", params->w);
    ret[0].u.string.sval = dupstr(buf);

    ret[1].name = "Height";
    ret[1].type = C_STRING;
    sprintf(buf, "%d", params->h);
    ret[1].u.string.sval = dupstr(buf);

    ret[2].name = "Difficulty";
    ret[2].type = C_CHOICES;
    ret[2].u.choices.choicenames = DIFFCONFIG;
    ret[2].u.choices.selected = params->diff;

    ret[3].name = NULL;
    ret[3].type = C_END;

    return ret;
}

static game_params *custom_params(const config_item *cfg)
{
    game_params *ret = snew(game_params);

    ret->w = atoi(cfg[0].u.string.sval);
    ret->h = atoi(cfg[1].u.string.sval);
    ret->diff = cfg[2].u.choices.selected;

    return ret;
}

static const char *validate_params(const game_params *params, bool full)
{
    /*
     * Generating anything under 4x4 runs into trouble of one kind
     * or another.
     */
    if (params->w < 4 || params->h < 4)
	return "Width and height must both be at least four";
    if (params->w > (INT_MAX - 1) / params->h)
        return "Width times height must not be unreasonably large";
    return NULL;
}

/*
 * Scratch space for solver.
 */
enum { N, U, L, R, D, MAXDIR };	       /* link directions */
#define dx(d) ( ((d)==R) - ((d)==L) )
#define dy(d) ( ((d)==D) - ((d)==U) )
#define F(d) ( U + D - (d) )
struct solver_scratch {
    char *links;		       /* mapping between trees and tents */
    int *locs;
    char *place, *mrows, *trows;
};

static struct solver_scratch *new_scratch(int w, int h)
{
    struct solver_scratch *ret = snew(struct solver_scratch);

    ret->links = snewn(w*h, char);
    ret->locs = snewn(max(w, h), int);
    ret->place = snewn(max(w, h), char);
    ret->mrows = snewn(3 * max(w, h), char);
    ret->trows = snewn(3 * max(w, h), char);

    return ret;
}

static void free_scratch(struct solver_scratch *sc)
{
    sfree(sc->trows);
    sfree(sc->mrows);
    sfree(sc->place);
    sfree(sc->locs);
    sfree(sc->links);
    sfree(sc);
}

/*
 * Solver. Returns 0 for impossibility, 1 for success, 2 for
 * ambiguity or failure to converge.
 */
static int tents_solve(int w, int h, const char *grid, int *numbers,
		       char *soln, struct solver_scratch *sc, int diff)
{
    int x, y, d, i, j;
    char *mrow, *trow, *trow1, *trow2;

    /*
     * Set up solver data.
     */
    memset(sc->links, N, w*h);

    /*
     * Set up solution array.
     */
    memcpy(soln, grid, w*h);

    /*
     * Main solver loop.
     */
    while (1) {
	bool done_something = false;

	/*
	 * Any tent which has only one unattached tree adjacent to
	 * it can be tied to that tree.
	 */
	for (y = 0; y < h; y++)
	    for (x = 0; x < w; x++)
		if (soln[y*w+x] == TENT && !sc->links[y*w+x]) {
		    int linkd = 0;

		    for (d = 1; d < MAXDIR; d++) {
			int x2 = x + dx(d), y2 = y + dy(d);
			if (x2 >= 0 && x2 < w && y2 >= 0 && y2 < h &&
			    soln[y2*w+x2] == TREE &&
			    !sc->links[y2*w+x2]) {
			    if (linkd)
				break; /* found more than one */
			    else
				linkd = d;
			}
		    }

		    if (d == MAXDIR && linkd == 0) {
#ifdef SOLVER_DIAGNOSTICS
			if (verbose)
			    printf("tent at %d,%d cannot link to anything\n",
				   x, y);
#endif
			return 0;      /* no solution exists */
		    } else if (d == MAXDIR) {
			int x2 = x + dx(linkd), y2 = y + dy(linkd);

#ifdef SOLVER_DIAGNOSTICS
			if (verbose)
			    printf("tent at %d,%d can only link to tree at"
				   " %d,%d\n", x, y, x2, y2);
#endif

			sc->links[y*w+x] = linkd;
			sc->links[y2*w+x2] = F(linkd);
			done_something = true;
		    }
		}

	if (done_something)
	    continue;
	if (diff < 0)
	    break;		       /* don't do anything else! */

	/*
	 * Mark a blank square as NONTENT if it is not orthogonally
	 * adjacent to any unmatched tree.
	 */
	for (y = 0; y < h; y++)
	    for (x = 0; x < w; x++)
		if (soln[y*w+x] == BLANK) {
		    bool can_be_tent = false;

		    for (d = 1; d < MAXDIR; d++) {
			int x2 = x + dx(d), y2 = y + dy(d);
			if (x2 >= 0 && x2 < w && y2 >= 0 && y2 < h &&
			    soln[y2*w+x2] == TREE &&
			    !sc->links[y2*w+x2])
			    can_be_tent = true;
		    }

		    if (!can_be_tent) {
#ifdef SOLVER_DIAGNOSTICS
			if (verbose)
			    printf("%d,%d cannot be a tent (no adjacent"
				   " unmatched tree)\n", x, y);
#endif
			soln[y*w+x] = NONTENT;
			done_something = true;
		    }
		}

	if (done_something)
	    continue;

	/*
	 * Mark a blank square as NONTENT if it is (perhaps
	 * diagonally) adjacent to any other tent.
	 */
	for (y = 0; y < h; y++)
	    for (x = 0; x < w; x++)
		if (soln[y*w+x] == BLANK) {
		    int dx, dy;
                    bool imposs = false;

		    for (dy = -1; dy <= +1; dy++)
			for (dx = -1; dx <= +1; dx++)
			    if (dy || dx) {
				int x2 = x + dx, y2 = y + dy;
				if (x2 >= 0 && x2 < w && y2 >= 0 && y2 < h &&
				    soln[y2*w+x2] == TENT)
				    imposs = true;
			    }

		    if (imposs) {
#ifdef SOLVER_DIAGNOSTICS
			if (verbose)
			    printf("%d,%d cannot be a tent (adjacent tent)\n",
				   x, y);
#endif
			soln[y*w+x] = NONTENT;
			done_something = true;
		    }
		}

	if (done_something)
	    continue;

	/*
	 * Any tree which has exactly one {unattached tent, BLANK}
	 * adjacent to it must have its tent in that square.
	 */
	for (y = 0; y < h; y++)
	    for (x = 0; x < w; x++)
		if (soln[y*w+x] == TREE && !sc->links[y*w+x]) {
		    int linkd = 0, linkd2 = 0, nd = 0;

		    for (d = 1; d < MAXDIR; d++) {
			int x2 = x + dx(d), y2 = y + dy(d);
			if (!(x2 >= 0 && x2 < w && y2 >= 0 && y2 < h))
			    continue;
			if (soln[y2*w+x2] == BLANK ||
			    (soln[y2*w+x2] == TENT && !sc->links[y2*w+x2])) {
			    if (linkd)
				linkd2 = d;
			    else
				linkd = d;
			    nd++;
			}
		    }

		    if (nd == 0) {
#ifdef SOLVER_DIAGNOSTICS
			if (verbose)
			    printf("tree at %d,%d cannot link to anything\n",
				   x, y);
#endif
			return 0;      /* no solution exists */
		    } else if (nd == 1) {
			int x2 = x + dx(linkd), y2 = y + dy(linkd);

#ifdef SOLVER_DIAGNOSTICS
			if (verbose)
			    printf("tree at %d,%d can only link to tent at"
				   " %d,%d\n", x, y, x2, y2);
#endif
			soln[y2*w+x2] = TENT;
			sc->links[y*w+x] = linkd;
			sc->links[y2*w+x2] = F(linkd);
			done_something = true;
		    } else if (nd == 2 && (!dx(linkd) != !dx(linkd2)) &&
			       diff >= DIFF_TRICKY) {
			/*
			 * If there are two possible places where
			 * this tree's tent can go, and they are
			 * diagonally separated rather than being
			 * on opposite sides of the tree, then the
			 * square (other than the tree square)
			 * which is adjacent to both of them must
			 * be a non-tent.
			 */
			int x2 = x + dx(linkd) + dx(linkd2);
			int y2 = y + dy(linkd) + dy(linkd2);
			assert(x2 >= 0 && x2 < w && y2 >= 0 && y2 < h);
			if (soln[y2*w+x2] == BLANK) {
#ifdef SOLVER_DIAGNOSTICS
			    if (verbose)
				printf("possible tent locations for tree at"
				       " %d,%d rule out tent at %d,%d\n",
				       x, y, x2, y2);
#endif
			    soln[y2*w+x2] = NONTENT;
			    done_something = true;
			}
		    }
		}

	if (done_something)
	    continue;

	/*
	 * If localised deductions about the trees and tents
	 * themselves haven't helped us, it's time to resort to the
	 * numbers round the grid edge. For each row and column, we
	 * go through all possible combinations of locations for
	 * the unplaced tents, rule out any which have adjacent
	 * tents, and spot any square which is given the same state
	 * by all remaining combinations.
	 */
	for (i = 0; i < w+h; i++) {
	    int start, step, len, start1, start2, n, k;

	    if (i < w) {
		/*
		 * This is the number for a column.
		 */
		start = i;
		step = w;
		len = h;
		if (i > 0)
		    start1 = start - 1;
		else
		    start1 = -1;
		if (i+1 < w)
		    start2 = start + 1;
		else
		    start2 = -1;
	    } else {
		/*
		 * This is the number for a row.
		 */
		start = (i-w)*w;
		step = 1;
		len = w;
		if (i > w)
		    start1 = start - w;
		else
		    start1 = -1;
		if (i+1 < w+h)
		    start2 = start + w;
		else
		    start2 = -1;
	    }

	    if (diff < DIFF_TRICKY) {
		/*
		 * In Easy mode, we don't look at the effect of one
		 * row on the next (i.e. ruling out a square if all
		 * possibilities for an adjacent row place a tent
		 * next to it).
		 */
		start1 = start2 = -1;
	    }

	    k = numbers[i];

	    /*
	     * Count and store the locations of the free squares,
	     * and also count the number of tents already placed.
	     */
	    n = 0;
	    for (j = 0; j < len; j++) {
		if (soln[start+j*step] == TENT)
		    k--;	       /* one fewer tent to place */
		else if (soln[start+j*step] == BLANK)
		    sc->locs[n++] = j;
	    }

	    if (n == 0)
		continue;	       /* nothing left to do here */

	    /*
	     * Now we know we're placing k tents in n squares. Set
	     * up the first possibility.
	     */
	    for (j = 0; j < n; j++)
		sc->place[j] = (j < k ? TENT : NONTENT);

	    /*
	     * We're aiming to find squares in this row which are
	     * invariant over all valid possibilities. Thus, we
	     * maintain the current state of that invariance. We
	     * start everything off at MAGIC to indicate that it
	     * hasn't been set up yet.
	     */
	    mrow = sc->mrows;
	    trow = sc->trows;
	    trow1 = sc->trows + len;
	    trow2 = sc->trows + 2*len;
	    memset(mrow, MAGIC, 3*len);

	    /*
	     * And iterate over all possibilities.
	     */
	    while (1) {
		int p;
                bool valid;

		/*
		 * See if this possibility is valid. The only way
		 * it can fail to be valid is if it contains two
		 * adjacent tents. (Other forms of invalidity, such
		 * as containing a tent adjacent to one already
		 * placed, will have been dealt with already by
		 * other parts of the solver.)
		 */
		valid = true;
		for (j = 0; j+1 < n; j++)
		    if (sc->place[j] == TENT &&
			sc->place[j+1] == TENT &&
			sc->locs[j+1] == sc->locs[j]+1) {
			valid = false;
			break;
		    }

		if (valid) {
		    /*
		     * Merge this valid combination into mrow.
		     */
		    memset(trow, MAGIC, len);
		    memset(trow+len, BLANK, 2*len);
		    for (j = 0; j < n; j++) {
			trow[sc->locs[j]] = sc->place[j];
			if (sc->place[j] == TENT) {
			    int jj;
			    for (jj = sc->locs[j]-1; jj <= sc->locs[j]+1; jj++)
				if (jj >= 0 && jj < len)
				    trow1[jj] = trow2[jj] = NONTENT;
			}
		    }

		    for (j = 0; j < 3*len; j++) {
			if (trow[j] == MAGIC)
			    continue;
			if (mrow[j] == MAGIC || mrow[j] == trow[j]) {
			    /*
			     * Either this is the first valid
			     * placement we've found at all, or
			     * this square's contents are
			     * consistent with every previous valid
			     * combination.
			     */
			    mrow[j] = trow[j];
			} else {
			    /*
			     * This square's contents fail to match
			     * what they were in a different
			     * combination, so we cannot deduce
			     * anything about this square.
			     */
			    mrow[j] = BLANK;
			}
		    }
		}

		/*
		 * Find the next combination of k choices from n.
		 * We do this by finding the rightmost tent which
		 * can be moved one place right, doing so, and
		 * shunting all tents to the right of that as far
		 * left as they can go.
		 */
		p = 0;
		for (j = n-1; j > 0; j--) {
		    if (sc->place[j] == TENT)
			p++;
		    if (sc->place[j] == NONTENT && sc->place[j-1] == TENT) {
			sc->place[j-1] = NONTENT;
			sc->place[j] = TENT;
			while (p--)
			    sc->place[++j] = TENT;
			while (++j < n)
			    sc->place[j] = NONTENT;
			break;
		    }
		}
		if (j <= 0)
		    break;	       /* we've finished */
	    }

	    /*
	     * It's just possible that _no_ placement was valid, in
	     * which case we have an internally inconsistent
	     * puzzle.
	     */
	    if (mrow[sc->locs[0]] == MAGIC)
		return 0;	       /* inconsistent */

	    /*
	     * Now go through mrow and see if there's anything
	     * we've deduced which wasn't already mentioned in soln.
	     */
	    for (j = 0; j < len; j++) {
		int whichrow;

		for (whichrow = 0; whichrow < 3; whichrow++) {
		    char *mthis = mrow + whichrow * len;
		    int tstart = (whichrow == 0 ? start :
				  whichrow == 1 ? start1 : start2);
		    if (tstart >= 0 &&
			mthis[j] != MAGIC && mthis[j] != BLANK &&
			soln[tstart+j*step] == BLANK) {
			int pos = tstart+j*step;

#ifdef SOLVER_DIAGNOSTICS
			if (verbose)
			    printf("%s %d forces %s at %d,%d\n",
				   step==1 ? "row" : "column",
				   step==1 ? start/w : start,
				   mthis[j] == TENT ? "tent" : "non-tent",
				   pos % w, pos / w);
#endif
			soln[pos] = mthis[j];
			done_something = true;
		    }
		}
	    }
	}

	if (done_something)
	    continue;

	if (!done_something)
	    break;
    }

    /*
     * The solver has nothing further it can do. Return 1 if both
     * soln and sc->links are completely filled in, or 2 otherwise.
     */
    for (y = 0; y < h; y++)
	for (x = 0; x < w; x++) {
	    if (soln[y*w+x] == BLANK)
		return 2;
	    if (soln[y*w+x] != NONTENT && sc->links[y*w+x] == 0)
		return 2;
	}

    return 1;
}

static char *new_game_desc(const game_params *params_in, random_state *rs,
			   char **aux, bool interactive)
{
    game_params params_copy = *params_in; /* structure copy */
    game_params *params = &params_copy;
    int w = params->w, h = params->h;
    int ntrees = w * h / 5;
    char *grid = snewn(w*h, char);
    char *puzzle = snewn(w*h, char);
    int *numbers = snewn(w+h, int);
    char *soln = snewn(w*h, char);
    int *order = snewn(w*h, int);
    int *treemap = snewn(w*h, int);
    int maxedges = ntrees*4 + w*h;
    int *adjdata = snewn(maxedges, int);
    int **adjlists = snewn(ntrees, int *);
    int *adjsizes = snewn(ntrees, int);
    int *outr = snewn(4*ntrees, int);
    struct solver_scratch *sc = new_scratch(w, h);
    char *ret, *p;
    int i, j, nl, nr;
    int *adjptr;

    /*
     * Since this puzzle has many global deductions and doesn't
     * permit limited clue sets, generating grids for this puzzle
     * is hard enough that I see no better option than to simply
     * generate a solution and see if it's unique and has the
     * required difficulty. This turns out to be computationally
     * plausible as well.
     * 
     * We chose our tree count (hence also tent count) by dividing
     * the total grid area by five above. Why five? Well, w*h/4 is
     * the maximum number of tents you can _possibly_ fit into the
     * grid without violating the separation criterion, and to
     * achieve that you are constrained to a very small set of
     * possible layouts (the obvious one with a tent at every
     * (even,even) coordinate, and trivial variations thereon). So
     * if we reduce the tent count a bit more, we enable more
     * random-looking placement; 5 turns out to be a plausible
     * figure which yields sensible puzzles. Increasing the tent
     * count would give puzzles whose solutions were too regimented
     * and could be solved by the use of that knowledge (and would
     * also take longer to find a viable placement); decreasing it
     * would make the grids emptier and more boring.
     * 
     * Actually generating a grid is a matter of first placing the
     * tents, and then placing the trees by the use of matching.c
     * (finding a distinct square adjacent to every tent). We do it
     * this way round because otherwise satisfying the tent
     * separation condition would become onerous: most randomly
     * chosen tent layouts do not satisfy this condition, so we'd
     * have gone to a lot of work before finding that a candidate
     * layout was unusable. Instead, we place the tents first and
     * ensure they meet the separation criterion _before_ doing
     * lots of computation; this works much better.
     * 
     * This generation strategy can fail at many points, including
     * as early as tent placement (if you get a bad random order in
     * which to greedily try the grid squares, you won't even
     * manage to find enough mutually non-adjacent squares to put
     * the tents in). Then it can fail if matching.c doesn't manage
     * to find a good enough matching (i.e. the tent placements don't
     * admit any adequate tree placements); and finally it can fail
     * if the solver finds that the problem has the wrong
     * difficulty (including being actually non-unique). All of
     * these, however, are insufficiently frequent to cause
     * trouble.
     */

    if (params->diff > DIFF_EASY && params->w <= 4 && params->h <= 4)
	params->diff = DIFF_EASY;      /* downgrade to prevent tight loop */

    while (1) {
	/*
	 * Make a list of grid squares which we'll permute as we pick
	 * the tent locations.
         *
         * We'll also need to index all the potential tree squares,
         * i.e. the ones adjacent to the tents.
	 */
	for (i = 0; i < w*h; i++) {
	    order[i] = i;
	    treemap[i] = -1;
        }

	/*
	 * Place tents at random without making any two adjacent.
	 */
	memset(grid, BLANK, w*h);
	j = ntrees;
        nr = 0;
        /* Loop end condition: either j==0 (we've placed all the
         * tents), or the number of grid squares we have yet to try
         * is too few to fit the remaining tents into. */
	for (i = 0; j > 0 && i+j <= w*h; i++) {
            int which, x, y, d, tmp;
	    int dy, dx;
            bool ok = true;

            which = i + random_upto(rs, w*h - i);
            tmp = order[which];
            order[which] = order[i];
            order[i] = tmp;

	    x = order[i] % w;
            y = order[i] / w;

	    for (dy = -1; dy <= +1; dy++)
		for (dx = -1; dx <= +1; dx++)
		    if (x+dx >= 0 && x+dx < w &&
			y+dy >= 0 && y+dy < h &&
			grid[(y+dy)*w+(x+dx)] == TENT)
			ok = false;

	    if (ok) {
		grid[order[i]] = TENT;
                for (d = 1; d < MAXDIR; d++) {
                    int x2 = x + dx(d), y2 = y + dy(d);
                    if (x2 >= 0 && x2 < w && y2 >= 0 && y2 < h &&
                        treemap[y2*w+x2] == -1) {
                        treemap[y2*w+x2] = nr++;
                    }
                }
		j--;
	    }
	}
	if (j > 0)
	    continue;		       /* couldn't place all the tents */

	/*
	 * Build up the graph for matching.c.
	 */
        adjptr = adjdata;
        nl = 0;
	for (i = 0; i < w*h; i++) {
	    if (grid[i] == TENT) {
                int d, x = i % w, y = i / w;
                adjlists[nl] = adjptr;
                for (d = 1; d < MAXDIR; d++) {
                    int x2 = x + dx(d), y2 = y + dy(d);
                    if (x2 >= 0 && x2 < w && y2 >= 0 && y2 < h) {
                        assert(treemap[y2*w+x2] != -1);
                        *adjptr++ = treemap[y2*w+x2];
		    }
		}
                adjsizes[nl] = adjptr - adjlists[nl];
                nl++;
	    }
	}

	/*
	 * Call the matching algorithm to actually place the trees.
	 */
	j = matching(ntrees, nr, adjlists, adjsizes, rs, NULL, outr);

	if (j < ntrees)
	    continue;		       /* couldn't place all the trees */

	/*
	 * Fill in the trees in the grid, by cross-referencing treemap
	 * (which maps a grid square to its index as known to
	 * matching()) against the output from matching().
         *
         * Note that for these purposes we don't actually care _which_
         * tent each potential tree square is assigned to - we only
         * care whether it was assigned to any tent at all, in order
         * to decide whether to put a tree in it.
	 */
	for (i = 0; i < w*h; i++)
            if (treemap[i] != -1 && outr[treemap[i]] != -1)
		grid[i] = TREE;

	/*
	 * I think it looks ugly if there isn't at least one of
	 * _something_ (tent or tree) in each row and each column
	 * of the grid. This doesn't give any information away
	 * since a completely empty row/column is instantly obvious
	 * from the clues (it has no trees and a zero).
	 */
	for (i = 0; i < w; i++) {
	    for (j = 0; j < h; j++) {
		if (grid[j*w+i] != BLANK)
		    break;	       /* found something in this column */
	    }
	    if (j == h)
		break;		       /* found empty column */
	}
	if (i < w)
	    continue;		       /* a column was empty */

	for (j = 0; j < h; j++) {
	    for (i = 0; i < w; i++) {
		if (grid[j*w+i] != BLANK)
		    break;	       /* found something in this row */
	    }
	    if (i == w)
		break;		       /* found empty row */
	}
	if (j < h)
	    continue;		       /* a row was empty */

	/*
	 * Now set up the numbers round the edge.
	 */
	for (i = 0; i < w; i++) {
	    int n = 0;
	    for (j = 0; j < h; j++)
		if (grid[j*w+i] == TENT)
		    n++;
	    numbers[i] = n;
	}
	for (i = 0; i < h; i++) {
	    int n = 0;
	    for (j = 0; j < w; j++)
		if (grid[i*w+j] == TENT)
		    n++;
	    numbers[w+i] = n;
	}

	/*
	 * And now actually solve the puzzle, to see whether it's
	 * unique and has the required difficulty.
	 */
        for (i = 0; i < w*h; i++)
            puzzle[i] = grid[i] == TREE ? TREE : BLANK;
	i = tents_solve(w, h, puzzle, numbers, soln, sc, params->diff-1);
	j = tents_solve(w, h, puzzle, numbers, soln, sc, params->diff);

        /*
         * We expect solving with difficulty params->diff to have
         * succeeded (otherwise the problem is too hard), and
         * solving with diff-1 to have failed (otherwise it's too
         * easy).
         */
	if (i == 2 && j == 1)
	    break;
    }

    /*
     * That's it. Encode as a game ID.
     */
    ret = snewn((w+h)*40 + ntrees + (w*h)/26 + 1, char);
    p = ret;
    j = 0;
    for (i = 0; i <= w*h; i++) {
	bool c = (i < w*h ? grid[i] == TREE : true);
	if (c) {
	    *p++ = (j == 0 ? '_' : j-1 + 'a');
	    j = 0;
	} else {
	    j++;
	    while (j > 25) {
		*p++ = 'z';
		j -= 25;
	    }
	}
    }
    for (i = 0; i < w+h; i++)
	p += sprintf(p, ",%d", numbers[i]);
    *p++ = '\0';
    ret = sresize(ret, p - ret, char);

    /*
     * And encode the solution as an aux_info.
     */
    *aux = snewn(ntrees * 40, char);
    p = *aux;
    *p++ = 'S';
    for (i = 0; i < w*h; i++)
        if (grid[i] == TENT)
            p += sprintf(p, ";T%d,%d", i%w, i/w);
    *p++ = '\0';
    *aux = sresize(*aux, p - *aux, char);

    free_scratch(sc);
    sfree(outr);
    sfree(adjdata);
    sfree(adjlists);
    sfree(adjsizes);
    sfree(treemap);
    sfree(order);
    sfree(soln);
    sfree(numbers);
    sfree(puzzle);
    sfree(grid);

    return ret;
}

/*
 * Grid description format:
 * 
 * _ = tree
 * a = 1 BLANK then TREE
 * ...
 * y = 25 BLANKs then TREE
 * z = 25 BLANKs
 * ! = set previous square to TENT
 * - = set previous square to NONTENT
 *
 * Last character must be one that would insert a tree as the first
 * square after the grid.
 */

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

    area = 0;
    while (*desc && *desc != ',') {
	if (*desc == '_')
            area++;
	else if (*desc >= 'a' && *desc < 'z')
            area += *desc - 'a' + 2;
	else if (*desc == 'z')
            area += 25;
        else if (*desc == '!' || *desc == '-') {
            if (area == 0 || area > w * h)
                return "Tent or non-tent placed off the grid";
        } else
            return "Invalid character in grid specification";

	desc++;
    }
    if (area < w * h + 1)
	return "Not enough data to fill grid";
    else if (area > w * h + 1)
	return "Too much data to fill grid";

    for (i = 0; i < w+h; i++) {
	if (!*desc)
            return "Not enough numbers given after grid specification";
        else if (*desc != ',')
            return "Invalid character in number list";
	desc++;
	while (*desc && isdigit((unsigned char)*desc)) desc++;
    }

    if (*desc)
        return "Unexpected additional data at end of game description";
    return NULL;
}

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

    state->p = *params;		       /* structure copy */
    state->grid = snewn(w*h, char);
    state->numbers = snew(struct numbers);
    state->numbers->refcount = 1;
    state->numbers->numbers = snewn(w+h, int);
    state->completed = state->used_solve = false;

    i = 0;
    memset(state->grid, BLANK, w*h);

    while (*desc) {
	int run, type;

	type = TREE;

	if (*desc == '_')
	    run = 0;
	else if (*desc >= 'a' && *desc < 'z')
	    run = *desc - ('a'-1);
	else if (*desc == 'z') {
	    run = 25;
	    type = BLANK;
	} else {
	    assert(*desc == '!' || *desc == '-');
	    run = -1;
	    type = (*desc == '!' ? TENT : NONTENT);
	}

	desc++;

	i += run;
	assert(i >= 0 && i <= w*h);
	if (i == w*h) {
	    assert(type == TREE);
	    break;
	} else {
	    if (type != BLANK)
		state->grid[i++] = type;
	}
    }

    for (i = 0; i < w+h; i++) {
	assert(*desc == ',');
	desc++;
	state->numbers->numbers[i] = atoi(desc);
	while (*desc && isdigit((unsigned char)*desc)) desc++;
    }

    assert(!*desc);

    return state;
}

static game_state *dup_game(const game_state *state)
{
    int w = state->p.w, h = state->p.h;
    game_state *ret = snew(game_state);

    ret->p = state->p;		       /* structure copy */
    ret->grid = snewn(w*h, char);
    memcpy(ret->grid, state->grid, w*h);
    ret->numbers = state->numbers;
    state->numbers->refcount++;
    ret->completed = state->completed;
    ret->used_solve = state->used_solve;

    return ret;
}

static void free_game(game_state *state)
{
    if (--state->numbers->refcount <= 0) {
	sfree(state->numbers->numbers);
	sfree(state->numbers);
    }
    sfree(state->grid);
    sfree(state);
}

static char *solve_game(const game_state *state, const game_state *currstate,
                        const char *aux, const char **error)
{
    int w = state->p.w, h = state->p.h;

    if (aux) {
	/*
	 * If we already have the solution, save ourselves some
	 * time.
	 */
        return dupstr(aux);
    } else {
	struct solver_scratch *sc = new_scratch(w, h);
        char *soln;
        int ret;
        char *move, *p;
        int i;

	soln = snewn(w*h, char);
	ret = tents_solve(w, h, state->grid, state->numbers->numbers,
                          soln, sc, DIFFCOUNT-1);
	free_scratch(sc);
	if (ret != 1) {
	    sfree(soln);
	    if (ret == 0)
		*error = "This puzzle is not self-consistent";
	    else
		*error = "Unable to find a unique solution for this puzzle";
            return NULL;
	}

        /*
         * Construct a move string which turns the current state
         * into the solved state.
         */
        move = snewn(w*h * 40, char);
        p = move;
        *p++ = 'S';
        for (i = 0; i < w*h; i++)
            if (soln[i] == TENT)
                p += sprintf(p, ";T%d,%d", i%w, i/w);
        *p++ = '\0';
        move = sresize(move, p - move, char);

	sfree(soln);

        return move;
    }
}

static bool game_can_format_as_text_now(const game_params *params)
{
    return params->w <= 1998 && params->h <= 1998; /* 999 tents */
}

static char *game_text_format(const game_state *state)
{
    int w = state->p.w, h = state->p.h, r, c;
    int cw = 4, ch = 2, gw = (w+1)*cw + 2, gh = (h+1)*ch + 1, len = gw * gh;
    char *board = snewn(len + 1, char);

    sprintf(board, "%*s\n", len - 2, "");
    for (r = 0; r <= h; ++r) {
	for (c = 0; c <= w; ++c) {
	    int cell = r*ch*gw + cw*c, center = cell + gw*ch/2 + cw/2;
	    int i = r*w + c, n = 1000;

	    if (r == h && c == w) /* NOP */;
	    else if (c == w) n = state->numbers->numbers[w + r];
	    else if (r == h) n = state->numbers->numbers[c];
	    else switch (state->grid[i]) {
		case BLANK: board[center] = '.'; break;
		case TREE: board[center] = 'T'; break;
		case TENT: memcpy(board + center - 1, "//\\", 3); break;
		case NONTENT: break;
		default: memcpy(board + center - 1, "wtf", 3);
		}

	    if (n < 100) {
                board[center] = '0' + n % 10;
                if (n >= 10) board[center - 1] = '0' + n / 10;
            } else if (n < 1000) {
                board[center + 1] = '0' + n % 10;
                board[center] = '0' + n / 10 % 10;
                board[center - 1] = '0' + n / 100;
	    }

	    board[cell] = '+';
	    memset(board + cell + 1, '-', cw - 1);
	    for (i = 1; i < ch; ++i) board[cell + i*gw] = '|';
	}

	for (c = 0; c < ch; ++c) {
	    board[(r*ch+c)*gw + gw - 2] =
		c == 0 ? '+' : r < h ? '|' : ' ';
	    board[(r*ch+c)*gw + gw - 1] = '\n';
	}
    }

    memset(board + len - gw, '-', gw - 2 - cw);
    for (c = 0; c <= w; ++c) board[len - gw + cw*c] = '+';

    return board;
}

struct game_ui {
    int dsx, dsy;                      /* coords of drag start */
    int dex, dey;                      /* coords of drag end */
    int drag_button;                   /* -1 for none, or a button code */
    bool drag_ok;                      /* dragged off the window, to cancel */

    int cx, cy;                        /* cursor position. */
    bool cdisp;                        /* is cursor displayed? */
};

static game_ui *new_ui(const game_state *state)
{
    game_ui *ui = snew(game_ui);
    ui->dsx = ui->dsy = -1;
    ui->dex = ui->dey = -1;
    ui->drag_button = -1;
    ui->drag_ok = false;
    ui->cx = ui->cy = 0;
    ui->cdisp = getenv_bool("PUZZLES_SHOW_CURSOR", false);
    return ui;
}

static void free_ui(game_ui *ui)
{
    sfree(ui);
}

static void game_changed_state(game_ui *ui, const game_state *oldstate,
                               const game_state *newstate)
{
}

static const char *current_key_label(const game_ui *ui,
                                     const game_state *state, int button)
{
    int w = state->p.w;
    int v = state->grid[ui->cy*w+ui->cx];

    if (IS_CURSOR_SELECT(button) && ui->cdisp) {
        switch (v) {
          case BLANK:
            return button == CURSOR_SELECT ? "Tent" : "Green";
          case TENT: case NONTENT: return "Clear";
        }
    }
    return "";
}

struct game_drawstate {
    int tilesize;
    bool started;
    game_params p;
    int *drawn, *numbersdrawn;
    int cx, cy;         /* last-drawn cursor pos, or (-1,-1) if absent. */
};

#define PREFERRED_TILESIZE 32
#define TILESIZE (ds->tilesize)
#define TLBORDER (TILESIZE/2)
#define BRBORDER (TILESIZE*3/2)
#define COORD(x)  ( (x) * TILESIZE + TLBORDER )
#define FROMCOORD(x)  ( ((x) - TLBORDER + TILESIZE) / TILESIZE - 1 )

#define FLASH_TIME 0.30F

static int drag_xform(const game_ui *ui, int x, int y, int v)
{
    int xmin, ymin, xmax, ymax;

    xmin = min(ui->dsx, ui->dex);
    xmax = max(ui->dsx, ui->dex);
    ymin = min(ui->dsy, ui->dey);
    ymax = max(ui->dsy, ui->dey);

#ifndef STYLUS_BASED
    /*
     * Left-dragging has no effect, so we treat a left-drag as a
     * single click on dsx,dsy.
     */
    if (ui->drag_button == LEFT_BUTTON) {
        xmin = xmax = ui->dsx;
        ymin = ymax = ui->dsy;
    }
#endif

    if (x < xmin || x > xmax || y < ymin || y > ymax)
        return v;                      /* no change outside drag area */

    if (v == TREE)
        return v;                      /* trees are inviolate always */

    if (xmin == xmax && ymin == ymax) {
        /*
         * Results of a simple click. Left button sets blanks to
         * tents; right button sets blanks to non-tents; either
         * button clears a non-blank square.
         * If stylus-based however, it loops instead.
         */
        if (ui->drag_button == LEFT_BUTTON)
#ifdef STYLUS_BASED
            v = (v == BLANK ? TENT : (v == TENT ? NONTENT : BLANK));
        else
            v = (v == BLANK ? NONTENT : (v == NONTENT ? TENT : BLANK));
#else
            v = (v == BLANK ? TENT : BLANK);
        else
            v = (v == BLANK ? NONTENT : BLANK);
#endif
    } else {
        /*
         * Results of a drag. Left-dragging has no effect.
         * Right-dragging sets all blank squares to non-tents and
         * has no effect on anything else.
         */
        if (ui->drag_button == RIGHT_BUTTON)
            v = (v == BLANK ? NONTENT : v);
        else
#ifdef STYLUS_BASED
            v = (v == BLANK ? NONTENT : v);
#else
            /* do nothing */;
#endif
    }

    return v;
}

static char *interpret_move(const game_state *state, game_ui *ui,
                            const game_drawstate *ds,
                            int x, int y, int button)
{
    int w = state->p.w, h = state->p.h;
    char tmpbuf[80];
    bool shift = button & MOD_SHFT, control = button & MOD_CTRL;

    button &= ~MOD_MASK;

    if (button == LEFT_BUTTON || button == RIGHT_BUTTON) {
        x = FROMCOORD(x);
        y = FROMCOORD(y);
        if (x < 0 || y < 0 || x >= w || y >= h)
            return NULL;

        ui->drag_button = button;
        ui->dsx = ui->dex = x;
        ui->dsy = ui->dey = y;
        ui->drag_ok = true;
        ui->cdisp = false;
        return MOVE_UI_UPDATE;
    }

    if ((IS_MOUSE_DRAG(button) || IS_MOUSE_RELEASE(button)) &&
        ui->drag_button > 0) {
        int xmin, ymin, xmax, ymax;
        char *buf;
        const char *sep;
        int buflen, bufsize, tmplen;

        x = FROMCOORD(x);
        y = FROMCOORD(y);
        if (x < 0 || y < 0 || x >= w || y >= h) {
            ui->drag_ok = false;
        } else {
            /*
             * Drags are limited to one row or column. Hence, we
             * work out which coordinate is closer to the drag
             * start, and move it _to_ the drag start.
             */
            if (abs(x - ui->dsx) < abs(y - ui->dsy))
                x = ui->dsx;
            else
                y = ui->dsy;

            ui->dex = x;
            ui->dey = y;

            ui->drag_ok = true;
        }

        if (IS_MOUSE_DRAG(button))
            return MOVE_UI_UPDATE;

        /*
         * The drag has been released. Enact it.
         */
        if (!ui->drag_ok) {
            ui->drag_button = -1;
            return MOVE_UI_UPDATE;          /* drag was just cancelled */
        }

        xmin = min(ui->dsx, ui->dex);
        xmax = max(ui->dsx, ui->dex);
        ymin = min(ui->dsy, ui->dey);
        ymax = max(ui->dsy, ui->dey);
        assert(0 <= xmin && xmin <= xmax && xmax < w);
        assert(0 <= ymin && ymin <= ymax && ymax < h);

        buflen = 0;
        bufsize = 256;
        buf = snewn(bufsize, char);
        sep = "";
        for (y = ymin; y <= ymax; y++)
            for (x = xmin; x <= xmax; x++) {
                int v = drag_xform(ui, x, y, state->grid[y*w+x]);
                if (state->grid[y*w+x] != v) {
                    tmplen = sprintf(tmpbuf, "%s%c%d,%d", sep,
                                     (int)(v == BLANK ? 'B' :
                                           v == TENT ? 'T' : 'N'),
                                     x, y);
                    sep = ";";

                    if (buflen + tmplen >= bufsize) {
                        bufsize = buflen + tmplen + 256;
                        buf = sresize(buf, bufsize, char);
                    }

                    strcpy(buf+buflen, tmpbuf);
                    buflen += tmplen;
                }
            }

        ui->drag_button = -1;          /* drag is terminated */

        if (buflen == 0) {
            sfree(buf);
            return MOVE_UI_UPDATE;          /* drag was terminated */
        } else {
            buf[buflen] = '\0';
            return buf;
        }
    }

    if (IS_CURSOR_MOVE(button)) {
        ui->cdisp = true;
        if (shift || control) {
            int len = 0, i, indices[2];
            indices[0] = ui->cx + w * ui->cy;
            move_cursor(button, &ui->cx, &ui->cy, w, h, false);
            indices[1] = ui->cx + w * ui->cy;

            /* NONTENTify all unique traversed eligible squares */
            for (i = 0; i <= (indices[0] != indices[1]); ++i)
                if (state->grid[indices[i]] == BLANK ||
                    (control && state->grid[indices[i]] == TENT)) {
                    len += sprintf(tmpbuf + len, "%sN%d,%d", len ? ";" : "",
                                   indices[i] % w, indices[i] / w);
                    assert(len < lenof(tmpbuf));
                }

            tmpbuf[len] = '\0';
            if (len) return dupstr(tmpbuf);
        } else
            move_cursor(button, &ui->cx, &ui->cy, w, h, false);
        return MOVE_UI_UPDATE;
    }
    if (ui->cdisp) {
        char rep = 0;
        int v = state->grid[ui->cy*w+ui->cx];

        if (v != TREE) {
#ifdef SINGLE_CURSOR_SELECT
            if (button == CURSOR_SELECT)
                /* SELECT cycles T, N, B */
                rep = v == BLANK ? 'T' : v == TENT ? 'N' : 'B';
#else
            if (button == CURSOR_SELECT)
                rep = v == BLANK ? 'T' : 'B';
            else if (button == CURSOR_SELECT2)
                rep = v == BLANK ? 'N' : 'B';
            else if (button == 'T' || button == 'N' || button == 'B')
                rep = (char)button;
#endif
        }

        if (rep) {
            sprintf(tmpbuf, "%c%d,%d", (int)rep, ui->cx, ui->cy);
            return dupstr(tmpbuf);
        }
    } else if (IS_CURSOR_SELECT(button)) {
        ui->cdisp = true;
        return MOVE_UI_UPDATE;
    }

    return NULL;
}

static game_state *execute_move(const game_state *state, const char *move)
{
    int w = state->p.w, h = state->p.h;
    char c;
    int x, y, m, n, i, j;
    game_state *ret = dup_game(state);

    while (*move) {
        c = *move;
	if (c == 'S') {
            int i;
	    ret->used_solve = true;
            /*
             * Set all non-tree squares to NONTENT. The rest of the
             * solve move will fill the tents in over the top.
             */
            for (i = 0; i < w*h; i++)
                if (ret->grid[i] != TREE)
                    ret->grid[i] = NONTENT;
	    move++;
	} else if (c == 'B' || c == 'T' || c == 'N') {
            move++;
            if (sscanf(move, "%d,%d%n", &x, &y, &n) != 2 ||
                x < 0 || y < 0 || x >= w || y >= h) {
                free_game(ret);
                return NULL;
            }
            if (ret->grid[y*w+x] == TREE) {
                free_game(ret);
                return NULL;
            }
            ret->grid[y*w+x] = (c == 'B' ? BLANK : c == 'T' ? TENT : NONTENT);
            move += n;
        } else {
            free_game(ret);
            return NULL;
        }
        if (*move == ';')
            move++;
        else if (*move) {
            free_game(ret);
            return NULL;
        }
    }

    /*
     * Check for completion.
     */
    for (i = n = m = 0; i < w*h; i++) {
        if (ret->grid[i] == TENT)
            n++;
        else if (ret->grid[i] == TREE)
            m++;
    }
    if (n == m) {
        int *gridids, *adjdata, **adjlists, *adjsizes, *adjptr;

        /*
         * We have the right number of tents, which is a
         * precondition for the game being complete. Now check that
         * the numbers add up.
         */
	for (i = 0; i < w; i++) {
	    n = 0;
	    for (j = 0; j < h; j++)
		if (ret->grid[j*w+i] == TENT)
		    n++;
	    if (ret->numbers->numbers[i] != n)
                goto completion_check_done;
	}
	for (i = 0; i < h; i++) {
            n = 0;
	    for (j = 0; j < w; j++)
		if (ret->grid[i*w+j] == TENT)
		    n++;
	    if (ret->numbers->numbers[w+i] != n)
                goto completion_check_done;
	}
        /*
         * Also, check that no two tents are adjacent.
         */
        for (y = 0; y < h; y++)
            for (x = 0; x < w; x++) {
                if (x+1 < w &&
                    ret->grid[y*w+x] == TENT && ret->grid[y*w+x+1] == TENT)
                    goto completion_check_done;
                if (y+1 < h &&
                    ret->grid[y*w+x] == TENT && ret->grid[(y+1)*w+x] == TENT)
                    goto completion_check_done;
                if (x+1 < w && y+1 < h) {
                    if (ret->grid[y*w+x] == TENT &&
                        ret->grid[(y+1)*w+(x+1)] == TENT)
                        goto completion_check_done;
                    if (ret->grid[(y+1)*w+x] == TENT &&
                        ret->grid[y*w+(x+1)] == TENT)
                        goto completion_check_done;
                }
            }

        /*
         * OK; we have the right number of tents, they match the
         * numeric clues, and they satisfy the non-adjacency
         * criterion. Finally, we need to verify that they can be
         * placed in a one-to-one matching with the trees such that
         * every tent is orthogonally adjacent to its tree.
         * 
         * This bit is where the hard work comes in: we have to do
         * it by finding such a matching using matching.c.
         */
        gridids = snewn(w*h, int);
        adjdata = snewn(m*4, int);
        adjlists = snewn(m, int *);
        adjsizes = snewn(m, int);

        /* Assign each tent and tree a consecutive vertex id for
         * matching(). */
        for (i = n = 0; i < w*h; i++) {
            if (ret->grid[i] == TENT)
                gridids[i] = n++;
        }
        assert(n == m);
        for (i = n = 0; i < w*h; i++) {
            if (ret->grid[i] == TREE)
                gridids[i] = n++;
        }
        assert(n == m);

        /* Build the vertices' adjacency lists. */
        adjptr = adjdata;
        for (y = 0; y < h; y++)
            for (x = 0; x < w; x++)
                if (ret->grid[y*w+x] == TREE) {
                    int d, treeid = gridids[y*w+x];
                    adjlists[treeid] = adjptr;

                    /*
                     * Here we use the direction enum declared for
                     * the solver. We make use of the fact that the
                     * directions are declared in the order
                     * U,L,R,D, meaning that we go through the four
                     * neighbours of any square in numerically
                     * increasing order.
                     */
		    for (d = 1; d < MAXDIR; d++) {
			int x2 = x + dx(d), y2 = y + dy(d);
			if (x2 >= 0 && x2 < w && y2 >= 0 && y2 < h &&
                            ret->grid[y2*w+x2] == TENT) {
                            *adjptr++ = gridids[y2*w+x2];
                        }
                    }
                    adjsizes[treeid] = adjptr - adjlists[treeid];
                }

	n = matching(m, m, adjlists, adjsizes, NULL, NULL, NULL);

        sfree(gridids);
        sfree(adjdata);
        sfree(adjlists);
        sfree(adjsizes);

        if (n != m)
            goto completion_check_done;

        /*
         * We haven't managed to fault the grid on any count. Score!
         */
        ret->completed = true;
    }
    completion_check_done:

    return ret;
}

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

static void game_compute_size(const game_params *params, int tilesize,
                              const game_ui *ui, int *x, int *y)
{
    /* fool the macros */
    struct dummy { int tilesize; } dummy, *ds = &dummy;
    dummy.tilesize = tilesize;

    *x = TLBORDER + BRBORDER + TILESIZE * params->w;
    *y = TLBORDER + BRBORDER + TILESIZE * params->h;
}

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

static float *game_colours(frontend *fe, int *ncolours)
{
    float *ret = snewn(3 * NCOLOURS, float);

    frontend_default_colour(fe, &ret[COL_BACKGROUND * 3]);

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

    ret[COL_GRASS * 3 + 0] = 0.7F;
    ret[COL_GRASS * 3 + 1] = 1.0F;
    ret[COL_GRASS * 3 + 2] = 0.5F;

    ret[COL_TREETRUNK * 3 + 0] = 0.6F;
    ret[COL_TREETRUNK * 3 + 1] = 0.4F;
    ret[COL_TREETRUNK * 3 + 2] = 0.0F;

    ret[COL_TREELEAF * 3 + 0] = 0.0F;
    ret[COL_TREELEAF * 3 + 1] = 0.7F;
    ret[COL_TREELEAF * 3 + 2] = 0.0F;

    ret[COL_TENT * 3 + 0] = 0.8F;
    ret[COL_TENT * 3 + 1] = 0.7F;
    ret[COL_TENT * 3 + 2] = 0.0F;

    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;

    ret[COL_ERRTRUNK * 3 + 0] = 0.6F;
    ret[COL_ERRTRUNK * 3 + 1] = 0.0F;
    ret[COL_ERRTRUNK * 3 + 2] = 0.0F;

    *ncolours = NCOLOURS;
    return ret;
}

static game_drawstate *game_new_drawstate(drawing *dr, const game_state *state)
{
    int w = state->p.w, h = state->p.h;
    struct game_drawstate *ds = snew(struct game_drawstate);
    int i;

    ds->tilesize = 0;
    ds->started = false;
    ds->p = state->p;                  /* structure copy */
    ds->drawn = snewn(w*h, int);
    for (i = 0; i < w*h; i++)
	ds->drawn[i] = MAGIC;
    ds->numbersdrawn = snewn(w+h, int);
    for (i = 0; i < w+h; i++)
	ds->numbersdrawn[i] = 2;
    ds->cx = ds->cy = -1;

    return ds;
}

static void game_free_drawstate(drawing *dr, game_drawstate *ds)
{
    sfree(ds->drawn);
    sfree(ds->numbersdrawn);
    sfree(ds);
}

enum {
    ERR_ADJ_TOPLEFT = 4,
    ERR_ADJ_TOP,
    ERR_ADJ_TOPRIGHT,
    ERR_ADJ_LEFT,
    ERR_ADJ_RIGHT,
    ERR_ADJ_BOTLEFT,
    ERR_ADJ_BOT,
    ERR_ADJ_BOTRIGHT,
    ERR_OVERCOMMITTED
};

static int *find_errors(const game_state *state, char *grid)
{
    int w = state->p.w, h = state->p.h;
    int *ret = snewn(w*h + w + h, int);
    int *tmp = snewn(w*h, int);
    DSF *dsf;
    int x, y;

    /*
     * This function goes through a grid and works out where to
     * highlight play errors in red. The aim is that it should
     * produce at least one error highlight for any complete grid
     * (or complete piece of grid) violating a puzzle constraint, so
     * that a grid containing no BLANK squares is either a win or is
     * marked up in some way that indicates why not.
     *
     * So it's easy enough to highlight errors in the numeric clues
     * - just light up any row or column number which is not
     * fulfilled - and it's just as easy to highlight adjacent
     * tents. The difficult bit is highlighting failures in the
     * tent/tree matching criterion.
     *
     * A natural approach would seem to be to apply the matching.c
     * algorithm to find the tent/tree matching; if this fails, it
     * could be made to produce as a by-product some set of trees
     * which have too few tents between them (or vice versa). However,
     * it's bad for localising errors, because it's not easy to make
     * the algorithm narrow down to the _smallest_ such set of trees:
     * if trees A and B have only one tent between them, for instance,
     * it might perfectly well highlight not only A and B but also
     * trees C and D which are correctly matched on the far side of
     * the grid, on the grounds that those four trees between them
     * have only three tents.
     *
     * Also, that approach fares badly when you introduce the
     * additional requirement that incomplete grids should have
     * errors highlighted only when they can be proved to be errors
     * - so that trees should not be marked as having too few tents
     * if there are enough BLANK squares remaining around them that
     * could be turned into the missing tents (to do so would be
     * patronising, since the overwhelming likelihood is not that
     * the player has forgotten to put a tree there but that they
     * have merely not put one there _yet_). However, tents with too
     * few trees can be marked immediately, since those are
     * definitely player error.
     *
     * So I adopt an alternative approach, which is to consider the
     * bipartite adjacency graph between trees and tents
     * ('bipartite' in the sense that for these purposes I
     * deliberately ignore two adjacent trees or two adjacent
     * tents), divide that graph up into its connected components
     * using a dsf, and look for components which contain different
     * numbers of trees and tents. This allows me to highlight
     * groups of tents with too few trees between them immediately,
     * and then in order to find groups of trees with too few tents
     * I redo the same process but counting BLANKs as potential
     * tents (so that the only trees highlighted are those
     * surrounded by enough NONTENTs to make it impossible to give
     * them enough tents).
     *
     * However, this technique is incomplete: it is not a sufficient
     * condition for the existence of a perfect matching that every
     * connected component of the graph has the same number of tents
     * and trees. An example of a graph which satisfies the latter
     * condition but still has no perfect matching is
     * 
     *     A    B    C
     *     |   /   ,/|
     *     |  /  ,'/ |
     *     | / ,' /  |
     *     |/,'  /   |
     *     1    2    3
     *
     * which can be realised in Tents as
     * 
     *       B
     *     A 1 C 2
     *         3
     *
     * The matching-error highlighter described above will not mark
     * this construction as erroneous. However, something else will:
     * the three tents in the above diagram (let us suppose A,B,C
     * are the tents, though it doesn't matter which) contain two
     * diagonally adjacent pairs. So there will be _an_ error
     * highlighted for the above layout, even though not all types
     * of error will be highlighted.
     *
     * And in fact we can prove that this will always be the case:
     * that the shortcomings of the matching-error highlighter will
     * always be made up for by the easy tent adjacency highlighter.
     *
     * Lemma: Let G be a bipartite graph between n trees and n
     * tents, which is connected, and in which no tree has degree
     * more than two (but a tent may). Then G has a perfect matching.
     * 
     * (Note: in the statement and proof of the Lemma I will
     * consistently use 'tree' to indicate a type of graph vertex as
     * opposed to a tent, and not to indicate a tree in the graph-
     * theoretic sense.)
     *
     * Proof:
     * 
     * If we can find a tent of degree 1 joined to a tree of degree
     * 2, then any perfect matching must pair that tent with that
     * tree. Hence, we can remove both, leaving a smaller graph G'
     * which still satisfies all the conditions of the Lemma, and
     * which has a perfect matching iff G does.
     *
     * So, wlog, we may assume G contains no tent of degree 1 joined
     * to a tree of degree 2; if it does, we can reduce it as above.
     *
     * If G has no tent of degree 1 at all, then every tent has
     * degree at least two, so there are at least 2n edges in the
     * graph. But every tree has degree at most two, so there are at
     * most 2n edges. Hence there must be exactly 2n edges, so every
     * tree and every tent must have degree exactly two, which means
     * that the whole graph consists of a single loop (by
     * connectedness), and therefore certainly has a perfect
     * matching.
     *
     * Alternatively, if G does have a tent of degree 1 but it is
     * not connected to a tree of degree 2, then the tree it is
     * connected to must have degree 1 - and, by connectedness, that
     * must mean that that tent and that tree between them form the
     * entire graph. This trivial graph has a trivial perfect
     * matching. []
     *
     * That proves the lemma. Hence, in any case where the matching-
     * error highlighter fails to highlight an erroneous component
     * (because it has the same number of tents as trees, but they
     * cannot be matched up), the above lemma tells us that there
     * must be a tree with degree more than 2, i.e. a tree
     * orthogonally adjacent to at least three tents. But in that
     * case, there must be some pair of those three tents which are
     * diagonally adjacent to each other, so the tent-adjacency
     * highlighter will necessarily show an error. So any filled
     * layout in Tents which is not a correct solution to the puzzle
     * must have _some_ error highlighted by the subroutine below.
     *
     * (Of course it would be nicer if we could highlight all
     * errors: in the above example layout, we would like to
     * highlight tents A,B as having too few trees between them, and
     * trees 2,3 as having too few tents, in addition to marking the
     * adjacency problems. But I can't immediately think of any way
     * to find the smallest sets of such tents and trees without an
     * O(2^N) loop over all subsets of a given component.)
     */

    /*
     * ret[0] through to ret[w*h-1] give error markers for the grid
     * squares. After that, ret[w*h] to ret[w*h+w-1] give error
     * markers for the column numbers, and ret[w*h+w] to
     * ret[w*h+w+h-1] for the row numbers.
     */

    /*
     * Spot tent-adjacency violations.
     */
    for (x = 0; x < w*h; x++)
	ret[x] = 0;
    for (y = 0; y < h; y++) {
	for (x = 0; x < w; x++) {
	    if (y+1 < h && x+1 < w &&
		((grid[y*w+x] == TENT &&
		  grid[(y+1)*w+(x+1)] == TENT) ||
		 (grid[(y+1)*w+x] == TENT &&
		  grid[y*w+(x+1)] == TENT))) {
		ret[y*w+x] |= 1 << ERR_ADJ_BOTRIGHT;
		ret[(y+1)*w+x] |= 1 << ERR_ADJ_TOPRIGHT;
		ret[y*w+(x+1)] |= 1 << ERR_ADJ_BOTLEFT;
		ret[(y+1)*w+(x+1)] |= 1 << ERR_ADJ_TOPLEFT;
	    }
	    if (y+1 < h &&
		grid[y*w+x] == TENT &&
		grid[(y+1)*w+x] == TENT) {
		ret[y*w+x] |= 1 << ERR_ADJ_BOT;
		ret[(y+1)*w+x] |= 1 << ERR_ADJ_TOP;
	    }
	    if (x+1 < w &&
		grid[y*w+x] == TENT &&
		grid[y*w+(x+1)] == TENT) {
		ret[y*w+x] |= 1 << ERR_ADJ_RIGHT;
		ret[y*w+(x+1)] |= 1 << ERR_ADJ_LEFT;
	    }
	}
    }

    /*
     * Spot numeric clue violations.
     */
    for (x = 0; x < w; x++) {
	int tents = 0, maybetents = 0;
	for (y = 0; y < h; y++) {
	    if (grid[y*w+x] == TENT)
		tents++;
	    else if (grid[y*w+x] == BLANK)
		maybetents++;
	}
	ret[w*h+x] = (tents > state->numbers->numbers[x] ||
		      tents + maybetents < state->numbers->numbers[x]);
    }
    for (y = 0; y < h; y++) {
	int tents = 0, maybetents = 0;
	for (x = 0; x < w; x++) {
	    if (grid[y*w+x] == TENT)
		tents++;
	    else if (grid[y*w+x] == BLANK)
		maybetents++;
	}
	ret[w*h+w+y] = (tents > state->numbers->numbers[w+y] ||
			tents + maybetents < state->numbers->numbers[w+y]);
    }

    /*
     * Identify groups of tents with too few trees between them,
     * which we do by constructing the connected components of the
     * bipartite adjacency graph between tents and trees
     * ('bipartite' in the sense that we deliberately ignore
     * adjacency between tents or between trees), and highlighting
     * all the tents in any component which has a smaller tree
     * count.
     */
    dsf = dsf_new(w*h);
    /* Construct the equivalence classes. */
    for (y = 0; y < h; y++) {
	for (x = 0; x < w-1; x++) {
	    if ((grid[y*w+x] == TREE && grid[y*w+x+1] == TENT) ||
		(grid[y*w+x] == TENT && grid[y*w+x+1] == TREE))
		dsf_merge(dsf, y*w+x, y*w+x+1);
	}
    }
    for (y = 0; y < h-1; y++) {
	for (x = 0; x < w; x++) {
	    if ((grid[y*w+x] == TREE && grid[(y+1)*w+x] == TENT) ||
		(grid[y*w+x] == TENT && grid[(y+1)*w+x] == TREE))
		dsf_merge(dsf, y*w+x, (y+1)*w+x);
	}
    }
    /* Count up the tent/tree difference in each one. */
    for (x = 0; x < w*h; x++)
	tmp[x] = 0;
    for (x = 0; x < w*h; x++) {
	y = dsf_canonify(dsf, x);
	if (grid[x] == TREE)
	    tmp[y]++;
	else if (grid[x] == TENT)
	    tmp[y]--;
    }
    /* And highlight any tent belonging to an equivalence class with
     * a score less than zero. */
    for (x = 0; x < w*h; x++) {
	y = dsf_canonify(dsf, x);
	if (grid[x] == TENT && tmp[y] < 0)
	    ret[x] |= 1 << ERR_OVERCOMMITTED;
    }

    /*
     * Identify groups of trees with too few tents between them.
     * This is done similarly, except that we now count BLANK as
     * equivalent to TENT, i.e. we only highlight such trees when
     * the user hasn't even left _room_ to provide tents for them
     * all. (Otherwise, we'd highlight all trees red right at the
     * start of the game, before the user had done anything wrong!)
     */
#define TENT(x) ((x)==TENT || (x)==BLANK)
    dsf_reinit(dsf);
    /* Construct the equivalence classes. */
    for (y = 0; y < h; y++) {
	for (x = 0; x < w-1; x++) {
	    if ((grid[y*w+x] == TREE && TENT(grid[y*w+x+1])) ||
		(TENT(grid[y*w+x]) && grid[y*w+x+1] == TREE))
		dsf_merge(dsf, y*w+x, y*w+x+1);
	}
    }
    for (y = 0; y < h-1; y++) {
	for (x = 0; x < w; x++) {
	    if ((grid[y*w+x] == TREE && TENT(grid[(y+1)*w+x])) ||
		(TENT(grid[y*w+x]) && grid[(y+1)*w+x] == TREE))
		dsf_merge(dsf, y*w+x, (y+1)*w+x);
	}
    }
    /* Count up the tent/tree difference in each one. */
    for (x = 0; x < w*h; x++)
	tmp[x] = 0;
    for (x = 0; x < w*h; x++) {
	y = dsf_canonify(dsf, x);
	if (grid[x] == TREE)
	    tmp[y]++;
	else if (TENT(grid[x]))
	    tmp[y]--;
    }
    /* And highlight any tree belonging to an equivalence class with
     * a score more than zero. */
    for (x = 0; x < w*h; x++) {
	y = dsf_canonify(dsf, x);
	if (grid[x] == TREE && tmp[y] > 0)
	    ret[x] |= 1 << ERR_OVERCOMMITTED;
    }
#undef TENT

    sfree(tmp);
    dsf_free(dsf);
    return ret;
}

static void draw_err_adj(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_tile(drawing *dr, game_drawstate *ds,
                      int x, int y, int v, bool cur, bool printing)
{
    int err;
    int tx = COORD(x), ty = COORD(y);
    int cx = tx + TILESIZE/2, cy = ty + TILESIZE/2;

    err = v & ~15;
    v &= 15;

    clip(dr, tx, ty, TILESIZE, TILESIZE);

    if (!printing) {
	draw_rect(dr, tx, ty, TILESIZE, TILESIZE, COL_GRID);
	draw_rect(dr, tx+1, ty+1, TILESIZE-1, TILESIZE-1,
		  (v == BLANK ? COL_BACKGROUND : COL_GRASS));
    }

    if (v == TREE) {
	int i;

	(printing ? draw_rect_outline : draw_rect)
	(dr, cx-TILESIZE/15, ty+TILESIZE*3/10,
	 2*(TILESIZE/15)+1, (TILESIZE*9/10 - TILESIZE*3/10),
	 (err & (1<<ERR_OVERCOMMITTED) ? COL_ERRTRUNK : COL_TREETRUNK));

	for (i = 0; i < (printing ? 2 : 1); i++) {
	    int col = (i == 1 ? COL_BACKGROUND :
		       (err & (1<<ERR_OVERCOMMITTED) ? COL_ERROR : 
			COL_TREELEAF));
	    int sub = i * (TILESIZE/32);
	    draw_circle(dr, cx, ty+TILESIZE*4/10, TILESIZE/4 - sub,
			col, col);
	    draw_circle(dr, cx+TILESIZE/5, ty+TILESIZE/4, TILESIZE/8 - sub,
			col, col);
	    draw_circle(dr, cx-TILESIZE/5, ty+TILESIZE/4, TILESIZE/8 - sub,
			col, col);
	    draw_circle(dr, cx+TILESIZE/4, ty+TILESIZE*6/13, TILESIZE/8 - sub,
			col, col);
	    draw_circle(dr, cx-TILESIZE/4, ty+TILESIZE*6/13, TILESIZE/8 - sub,
			col, col);
	}
    } else if (v == TENT) {
        int coords[6];
	int col;
        coords[0] = cx - TILESIZE/3;
        coords[1] = cy + TILESIZE/3;
        coords[2] = cx + TILESIZE/3;
        coords[3] = cy + TILESIZE/3;
        coords[4] = cx;
        coords[5] = cy - TILESIZE/3;
	col = (err & (1<<ERR_OVERCOMMITTED) ? COL_ERROR : COL_TENT);
        draw_polygon(dr, coords, 3, (printing ? -1 : col), col);
    }

    if (err & (1 << ERR_ADJ_TOPLEFT))
	draw_err_adj(dr, ds, tx, ty);
    if (err & (1 << ERR_ADJ_TOP))
	draw_err_adj(dr, ds, tx+TILESIZE/2, ty);
    if (err & (1 << ERR_ADJ_TOPRIGHT))
	draw_err_adj(dr, ds, tx+TILESIZE, ty);
    if (err & (1 << ERR_ADJ_LEFT))
	draw_err_adj(dr, ds, tx, ty+TILESIZE/2);
    if (err & (1 << ERR_ADJ_RIGHT))
	draw_err_adj(dr, ds, tx+TILESIZE, ty+TILESIZE/2);
    if (err & (1 << ERR_ADJ_BOTLEFT))
	draw_err_adj(dr, ds, tx, ty+TILESIZE);
    if (err & (1 << ERR_ADJ_BOT))
	draw_err_adj(dr, ds, tx+TILESIZE/2, ty+TILESIZE);
    if (err & (1 << ERR_ADJ_BOTRIGHT))
	draw_err_adj(dr, ds, tx+TILESIZE, ty+TILESIZE);

    if (cur) {
      int coff = TILESIZE/8;
      draw_rect_outline(dr, tx + coff, ty + coff,
                        TILESIZE - coff*2 + 1, TILESIZE - coff*2 + 1,
			COL_GRID);
    }

    unclip(dr);
    draw_update(dr, tx+1, ty+1, TILESIZE-1, TILESIZE-1);
}

/*
 * Internal redraw function, used for printing as well as drawing.
 */
static void int_redraw(drawing *dr, game_drawstate *ds,
                       const game_state *oldstate, const game_state *state,
                       int dir, const game_ui *ui,
		       float animtime, float flashtime, bool printing)
{
    int w = state->p.w, h = state->p.h;
    int x, y;
    bool flashing;
    int cx = -1, cy = -1;
    bool cmoved = false;
    char *tmpgrid;
    int *errors;

    if (ui) {
      if (ui->cdisp) { cx = ui->cx; cy = ui->cy; }
      if (cx != ds->cx || cy != ds->cy) cmoved = true;
    }

    if (printing || !ds->started) {
	if (printing)
	    print_line_width(dr, TILESIZE/64);

        /*
         * Draw the grid.
         */
        for (y = 0; y <= h; y++)
            draw_line(dr, COORD(0), COORD(y), COORD(w), COORD(y), COL_GRID);
        for (x = 0; x <= w; x++)
            draw_line(dr, COORD(x), COORD(0), COORD(x), COORD(h), COL_GRID);
    }

    if (flashtime > 0)
	flashing = (int)(flashtime * 3 / FLASH_TIME) != 1;
    else
	flashing = false;

    /*
     * Find errors. For this we use _part_ of the information from a
     * currently active drag: we transform dsx,dsy but not anything
     * else. (This seems to strike a good compromise between having
     * the error highlights respond instantly to single clicks, but
     * not giving constant feedback during a right-drag.)
     */
    if (ui && ui->drag_button >= 0) {
	tmpgrid = snewn(w*h, char);
	memcpy(tmpgrid, state->grid, w*h);
	tmpgrid[ui->dsy * w + ui->dsx] =
	    drag_xform(ui, ui->dsx, ui->dsy, tmpgrid[ui->dsy * w + ui->dsx]);
	errors = find_errors(state, tmpgrid);
	sfree(tmpgrid);
    } else {
	errors = find_errors(state, state->grid);
    }

    /*
     * Draw the grid.
     */
    for (y = 0; y < h; y++) {
        for (x = 0; x < w; x++) {
            int v = state->grid[y*w+x];
            bool credraw = false;

            /*
             * We deliberately do not take drag_ok into account
             * here, because user feedback suggests that it's
             * marginally nicer not to have the drag effects
             * flickering on and off disconcertingly.
             */
            if (ui && ui->drag_button >= 0)
                v = drag_xform(ui, x, y, v);

            if (flashing && (v == TREE || v == TENT))
                v = NONTENT;

            if (cmoved) {
              if ((x == cx && y == cy) ||
                  (x == ds->cx && y == ds->cy)) credraw = true;
            }

	    v |= errors[y*w+x];

            if (printing || ds->drawn[y*w+x] != v || credraw) {
                draw_tile(dr, ds, x, y, v, (x == cx && y == cy), printing);
                if (!printing)
		    ds->drawn[y*w+x] = v;
            }
        }
    }

    /*
     * Draw (or redraw, if their error-highlighted state has
     * changed) the numbers.
     */
    for (x = 0; x < w; x++) {
	if (printing || ds->numbersdrawn[x] != errors[w*h+x]) {
	    char buf[80];
	    draw_rect(dr, COORD(x), COORD(h)+1, TILESIZE, BRBORDER-1,
		      COL_BACKGROUND);
	    sprintf(buf, "%d", state->numbers->numbers[x]);
	    draw_text(dr, COORD(x) + TILESIZE/2, COORD(h+1),
		      FONT_VARIABLE, TILESIZE/2, ALIGN_HCENTRE|ALIGN_VNORMAL,
		      (errors[w*h+x] ? COL_ERROR : COL_GRID), buf);
	    draw_update(dr, COORD(x), COORD(h)+1, TILESIZE, BRBORDER-1);
	    if (!printing)
                ds->numbersdrawn[x] = errors[w*h+x];
	}
    }
    for (y = 0; y < h; y++) {
	if (printing || ds->numbersdrawn[w+y] != errors[w*h+w+y]) {
	    char buf[80];
	    draw_rect(dr, COORD(w)+1, COORD(y), BRBORDER-1, TILESIZE,
		      COL_BACKGROUND);
	    sprintf(buf, "%d", state->numbers->numbers[w+y]);
	    draw_text(dr, COORD(w+1), COORD(y) + TILESIZE/2,
		      FONT_VARIABLE, TILESIZE/2, ALIGN_HRIGHT|ALIGN_VCENTRE,
		      (errors[w*h+w+y] ? COL_ERROR : COL_GRID), buf);
	    draw_update(dr, COORD(w)+1, COORD(y), BRBORDER-1, TILESIZE);
	    if (!printing)
                ds->numbersdrawn[w+y] = errors[w*h+w+y];
	}
    }

    if (cmoved) {
	ds->cx = cx;
	ds->cy = cy;
    }

    sfree(errors);
}

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_redraw(dr, ds, oldstate, state, dir, ui, animtime, flashtime, false);
}

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->used_solve && !newstate->used_solve)
        return FLASH_TIME;

    return 0.0F;
}

static void game_get_cursor_location(const game_ui *ui,
                                     const game_drawstate *ds,
                                     const game_state *state,
                                     const game_params *params,
                                     int *x, int *y, int *w, int *h)
{
    if(ui->cdisp) {
        *x = COORD(ui->cx);
        *y = COORD(ui->cy);
        *w = *h = TILESIZE;
    }
}

static int game_status(const game_state *state)
{
    return state->completed ? +1 : 0;
}

static void game_print_size(const game_params *params, const game_ui *ui,
                            float *x, float *y)
{
    int pw, ph;

    /*
     * I'll use 6mm squares by default.
     */
    game_compute_size(params, 600, ui, &pw, &ph);
    *x = pw / 100.0F;
    *y = ph / 100.0F;
}

static void game_print(drawing *dr, const game_state *state, const game_ui *ui,
                       int tilesize)
{
    int c;

    /* Ick: fake up `ds->tilesize' for macro expansion purposes */
    game_drawstate ads, *ds = &ads;
    game_set_size(dr, ds, NULL, tilesize);

    c = print_mono_colour(dr, 1); assert(c == COL_BACKGROUND);
    c = print_mono_colour(dr, 0); assert(c == COL_GRID);
    c = print_mono_colour(dr, 1); assert(c == COL_GRASS);
    c = print_mono_colour(dr, 0); assert(c == COL_TREETRUNK);
    c = print_mono_colour(dr, 0); assert(c == COL_TREELEAF);
    c = print_mono_colour(dr, 0); assert(c == COL_TENT);

    int_redraw(dr, ds, NULL, state, +1, NULL, 0.0F, 0.0F, true);
}

#ifdef COMBINED
#define thegame tents
#endif

const struct game thegame = {
    "Tents", "games.tents", "tents",
    default_params,
    game_fetch_preset, NULL,
    decode_params,
    encode_params,
    free_params,
    dup_params,
    true, game_configure, custom_params,
    validate_params,
    new_game_desc,
    validate_desc,
    new_game,
    dup_game,
    free_game,
    true, solve_game,
    true, game_can_format_as_text_now, game_text_format,
    NULL, NULL, /* get_prefs, set_prefs */
    new_ui,
    free_ui,
    NULL, /* encode_ui */
    NULL, /* decode_ui */
    NULL, /* game_request_keys */
    game_changed_state,
    current_key_label,
    interpret_move,
    execute_move,
    PREFERRED_TILESIZE, game_compute_size, game_set_size,
    game_colours,
    game_new_drawstate,
    game_free_drawstate,
    game_redraw,
    game_anim_length,
    game_flash_length,
    game_get_cursor_location,
    game_status,
    true, false, game_print_size, game_print,
    false,			       /* wants_statusbar */
    false, NULL,                       /* timing_state */
    REQUIRE_RBUTTON,		       /* flags */
};

#ifdef STANDALONE_SOLVER

#include <stdarg.h>

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

    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);
    s2 = new_game(NULL, p, desc);

    sc = new_scratch(p->w, p->h);

    /*
     * 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++) {
	ret = tents_solve(p->w, p->h, s->grid, s->numbers->numbers,
			  s2->grid, sc, diff);
	if (ret < 2)
	    break;
    }

    if (diff == DIFFCOUNT) {
	if (grade)
	    printf("Difficulty rating: too hard to solve internally\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", tents_diffnames[diff]);
	} else {
	    verbose = really_verbose;
	    ret = tents_solve(p->w, p->h, s->grid, s->numbers->numbers,
			      s2->grid, sc, diff);
	    if (ret == 0)
		printf("Puzzle is inconsistent\n");
	    else
		fputs(game_text_format(s2), stdout);
	}
    }

    return 0;
}

#endif

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