sgt-puzzles/flip.c

/*
 * flip.c: Puzzle involving lighting up all the squares on a grid,
 * where each click toggles an overlapping set of lights.
 */

#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 "tree234.h"

enum {
    COL_BACKGROUND,
    COL_WRONG,
    COL_RIGHT,
    COL_GRID,
    COL_DIAG,
    COL_HINT,
    COL_CURSOR,
    NCOLOURS
};

#define PREFERRED_TILE_SIZE 48
#define TILE_SIZE (ds->tilesize)
#define BORDER    (TILE_SIZE / 2)
#define COORD(x)  ( (x) * TILE_SIZE + BORDER )
#define FROMCOORD(x)  ( ((x) - BORDER + TILE_SIZE) / TILE_SIZE - 1 )

#define ANIM_TIME 0.25F
#define FLASH_FRAME 0.07F

/*
 * Possible ways to decide which lights are toggled by each click.
 * Essentially, each of these describes a means of inventing a
 * matrix over GF(2).
 */
enum {
    CROSSES, RANDOM
};

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

/*
 * This structure is shared between all the game_states describing
 * a particular game, so it's reference-counted.
 */
struct matrix {
    int refcount;
    unsigned char *matrix;             /* array of (w*h) by (w*h) */
};

struct game_state {
    int w, h;
    int moves;
    bool completed, cheated, hints_active;
    unsigned char *grid;               /* array of w*h */
    struct matrix *matrix;
};

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

    ret->w = ret->h = 5;
    ret->matrix_type = CROSSES;

    return ret;
}

static const struct game_params flip_presets[] = {
    {3, 3, CROSSES},
    {4, 4, CROSSES},
    {5, 5, CROSSES},
    {3, 3, RANDOM},
    {4, 4, RANDOM},
    {5, 5, RANDOM},
};

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

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

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

    sprintf(str, "%dx%d %s", ret->w, ret->h,
            ret->matrix_type == CROSSES ? "Crosses" : "Random");

    *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 *ret, char const *string)
{
    ret->w = ret->h = atoi(string);
    while (*string && isdigit((unsigned char)*string)) string++;
    if (*string == 'x') {
        string++;
        ret->h = atoi(string);
        while (*string && isdigit((unsigned char)*string)) string++;
    }
    if (*string == 'r') {
        string++;
        ret->matrix_type = RANDOM;
    } else if (*string == 'c') {
        string++;
        ret->matrix_type = CROSSES;
    }
}

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

    sprintf(data, "%dx%d%s", params->w, params->h,
            !full ? "" : params->matrix_type == CROSSES ? "c" : "r");

    return dupstr(data);
}

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

    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 = "Shape type";
    ret[2].type = C_CHOICES;
    ret[2].u.choices.choicenames = ":Crosses:Random";
    ret[2].u.choices.selected = params->matrix_type;

    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->matrix_type = cfg[2].u.choices.selected;

    return ret;
}

static const char *validate_params(const game_params *params, bool full)
{
    int wh;

    if (params->w <= 0 || params->h <= 0)
        return "Width and height must both be greater than zero";
    if (params->w > (INT_MAX - 3) / params->h)
        return "Width times height must not be unreasonably large";
    wh = params->w * params->h;
    if (wh > (INT_MAX - 3) / wh)
        return "Width times height is too large";    
   return NULL;
}

static char *encode_bitmap(unsigned char *bmp, int len)
{
    int slen = (len + 3) / 4;
    char *ret;
    int i;

    ret = snewn(slen + 1, char);
    for (i = 0; i < slen; i++) {
        int j, v;
        v = 0;
        for (j = 0; j < 4; j++)
            if (i*4+j < len && bmp[i*4+j])
                v |= 8 >> j;
        ret[i] = "0123456789abcdef"[v];
    }
    ret[slen] = '\0';
    return ret;
}

static void decode_bitmap(unsigned char *bmp, int len, const char *hex)
{
    int slen = (len + 3) / 4;
    int i;

    for (i = 0; i < slen; i++) {
        int j, v, c = hex[i];
        if (c >= '0' && c <= '9')
            v = c - '0';
        else if (c >= 'A' && c <= 'F')
            v = c - 'A' + 10;
        else if (c >= 'a' && c <= 'f')
            v = c - 'a' + 10;
        else
            v = 0;                     /* shouldn't happen */
        for (j = 0; j < 4; j++) {
            if (i*4+j < len) {
                if (v & (8 >> j))
                    bmp[i*4+j] = 1;
                else
                    bmp[i*4+j] = 0;
            }
        }
    }
}

/*
 * Structure used during random matrix generation, and a compare
 * function to permit storage in a tree234.
 */
struct sq {
    int cx, cy;                        /* coords of click square */
    int x, y;                          /* coords of output square */
    /*
     * Number of click squares which currently affect this output
     * square.
     */
    int coverage;
    /*
     * Number of output squares currently affected by this click
     * square.
     */
    int ominosize;
};
#define SORT(field) do { \
    if (a->field < b->field) \
        return -1; \
    else if (a->field > b->field) \
        return +1; \
} while (0)
/*
 * Compare function for choosing the next square to add. We must
 * sort by coverage, then by omino size, then everything else.
 */
static int sqcmp_pick(void *av, void *bv)
{
    struct sq *a = (struct sq *)av;
    struct sq *b = (struct sq *)bv;
    SORT(coverage);
    SORT(ominosize);
    SORT(cy);
    SORT(cx);
    SORT(y);
    SORT(x);
    return 0;
}
/*
 * Compare function for adjusting the coverage figures after a
 * change. We sort first by coverage and output square, then by
 * everything else.
 */
static int sqcmp_cov(void *av, void *bv)
{
    struct sq *a = (struct sq *)av;
    struct sq *b = (struct sq *)bv;
    SORT(coverage);
    SORT(y);
    SORT(x);
    SORT(ominosize);
    SORT(cy);
    SORT(cx);
    return 0;
}
/*
 * Compare function for adjusting the omino sizes after a change.
 * We sort first by omino size and input square, then by everything
 * else.
 */
static int sqcmp_osize(void *av, void *bv)
{
    struct sq *a = (struct sq *)av;
    struct sq *b = (struct sq *)bv;
    SORT(ominosize);
    SORT(cy);
    SORT(cx);
    SORT(coverage);
    SORT(y);
    SORT(x);
    return 0;
}
static void addsq(tree234 *t, int w, int h, int cx, int cy,
                  int x, int y, unsigned char *matrix)
{
    int wh = w * h;
    struct sq *sq;
    int i;

    if (x < 0 || x >= w || y < 0 || y >= h)
        return;
    if (abs(x-cx) > 1 || abs(y-cy) > 1)
        return;
    if (matrix[(cy*w+cx) * wh + y*w+x])
        return;

    sq = snew(struct sq);
    sq->cx = cx;
    sq->cy = cy;
    sq->x = x;
    sq->y = y;
    sq->coverage = sq->ominosize = 0;
    for (i = 0; i < wh; i++) {
        if (matrix[i * wh + y*w+x])
            sq->coverage++;
        if (matrix[(cy*w+cx) * wh + i])
            sq->ominosize++;
    }

    if (add234(t, sq) != sq)
        sfree(sq);                     /* already there */
}
static void addneighbours(tree234 *t, int w, int h, int cx, int cy,
                          int x, int y, unsigned char *matrix)
{
    addsq(t, w, h, cx, cy, x-1, y, matrix);
    addsq(t, w, h, cx, cy, x+1, y, matrix);
    addsq(t, w, h, cx, cy, x, y-1, matrix);
    addsq(t, w, h, cx, cy, x, y+1, matrix);
}

static char *new_game_desc(const game_params *params, random_state *rs,
			   char **aux, bool interactive)
{
    int w = params->w, h = params->h, wh = w * h;
    int i, j;
    unsigned char *matrix, *grid;
    char *mbmp, *gbmp, *ret;

    matrix = snewn(wh * wh, unsigned char);
    grid = snewn(wh, unsigned char);

    /*
     * First set up the matrix.
     */
    switch (params->matrix_type) {
      case CROSSES:
        for (i = 0; i < wh; i++) {
            int ix = i % w, iy = i / w;
            for (j = 0; j < wh; j++) {
                int jx = j % w, jy = j / w;
                if (abs(jx - ix) + abs(jy - iy) <= 1)
                    matrix[i*wh+j] = 1;
                else
                    matrix[i*wh+j] = 0;
            }
        }
        break;
      case RANDOM:
        while (1) {
            tree234 *pick, *cov, *osize;
            int limit;

            pick = newtree234(sqcmp_pick);
            cov = newtree234(sqcmp_cov);
            osize = newtree234(sqcmp_osize);

            memset(matrix, 0, wh * wh);
            for (i = 0; i < wh; i++) {
                matrix[i*wh+i] = 1;
            }

            for (i = 0; i < wh; i++) {
                int ix = i % w, iy = i / w;
                addneighbours(pick, w, h, ix, iy, ix, iy, matrix);
                addneighbours(cov, w, h, ix, iy, ix, iy, matrix);
                addneighbours(osize, w, h, ix, iy, ix, iy, matrix);
            }

            /*
             * Repeatedly choose a square to add to the matrix,
             * until we have enough. I'll arbitrarily choose our
             * limit to be the same as the total number of set bits
             * in the crosses matrix.
             */
            limit = 4*wh - 2*(w+h);    /* centre squares already present */

            while (limit-- > 0) {
                struct sq *sq, *sq2, sqlocal;
                int k;

                /*
                 * Find the lowest element in the pick tree.
                 */
                sq = index234(pick, 0);

                /*
                 * Find the highest element with the same coverage
                 * and omino size, by setting all other elements to
                 * lots.
                 */
                sqlocal = *sq;
                sqlocal.cx = sqlocal.cy = sqlocal.x = sqlocal.y = wh;
                sq = findrelpos234(pick, &sqlocal, NULL, REL234_LT, &k);
                assert(sq != 0);

                /*
                 * Pick at random from all elements up to k of the
                 * pick tree.
                 */
                k = random_upto(rs, k+1);
                sq = delpos234(pick, k);
                del234(cov, sq);
                del234(osize, sq);

                /*
                 * Add this square to the matrix.
                 */
                matrix[(sq->cy * w + sq->cx) * wh + (sq->y * w + sq->x)] = 1;

                /*
                 * Correct the matrix coverage field of any sq
                 * which points at this output square.
                 */
                sqlocal = *sq;
                sqlocal.cx = sqlocal.cy = sqlocal.ominosize = -1;
                while ((sq2 = findrel234(cov, &sqlocal, NULL,
                                         REL234_GT)) != NULL &&
                       sq2->coverage == sq->coverage &&
                       sq2->x == sq->x && sq2->y == sq->y) {
                    del234(pick, sq2);
                    del234(cov, sq2);
                    del234(osize, sq2);
                    sq2->coverage++;
                    add234(pick, sq2);
                    add234(cov, sq2);
                    add234(osize, sq2);
                }

                /*
                 * Correct the omino size field of any sq which
                 * points at this input square.
                 */
                sqlocal = *sq;
                sqlocal.x = sqlocal.y = sqlocal.coverage = -1;
                while ((sq2 = findrel234(osize, &sqlocal, NULL,
                                         REL234_GT)) != NULL &&
                       sq2->ominosize == sq->ominosize &&
                       sq2->cx == sq->cx && sq2->cy == sq->cy) {
                    del234(pick, sq2);
                    del234(cov, sq2);
                    del234(osize, sq2);
                    sq2->ominosize++;
                    add234(pick, sq2);
                    add234(cov, sq2);
                    add234(osize, sq2);
                }

                /*
                 * The sq we actually picked out of the tree is
                 * finished with; but its neighbours now need to
                 * appear.
                 */
                addneighbours(pick, w,h, sq->cx,sq->cy, sq->x,sq->y, matrix);
                addneighbours(cov, w,h, sq->cx,sq->cy, sq->x,sq->y, matrix);
                addneighbours(osize, w,h, sq->cx,sq->cy, sq->x,sq->y, matrix);
                sfree(sq);
            }

            /*
             * Free all remaining sq structures.
             */
            {
                struct sq *sq;
                while ((sq = delpos234(pick, 0)) != NULL)
                    sfree(sq);
            }
            freetree234(pick);
            freetree234(cov);
            freetree234(osize);

            /*
             * Finally, check to see if any two matrix rows are
             * exactly identical. If so, this is not an acceptable
             * matrix, and we give up and go round again.
             * 
             * I haven't been immediately able to think of a
             * plausible means of algorithmically avoiding this
             * situation (by, say, making a small perturbation to
             * an offending matrix), so for the moment I'm just
             * going to deal with it by throwing the whole thing
             * away. I suspect this will lead to scalability
             * problems (since most of the things happening in
             * these matrices are local, the chance of _some_
             * neighbourhood having two identical regions will
             * increase with the grid area), but so far this puzzle
             * seems to be really hard at large sizes so I'm not
             * massively worried yet. Anyone needs this done
             * better, they're welcome to submit a patch.
             */
            for (i = 0; i < wh; i++) {
                for (j = 0; j < wh; j++)
                    if (i != j &&
                        !memcmp(matrix + i * wh, matrix + j * wh, wh))
                        break;
                if (j < wh)
                    break;
            }
            if (i == wh)
                break;                 /* no matches found */
        }
        break;
    }

    /*
     * Now invent a random initial set of lights.
     * 
     * At first glance it looks as if it might be quite difficult
     * to choose equiprobably from all soluble light sets. After
     * all, soluble light sets are those in the image space of the
     * transformation matrix; so first we'd have to identify that
     * space and its dimension, then pick a random coordinate for
     * each basis vector and recombine. Lot of fiddly matrix
     * algebra there.
     * 
     * However, vector spaces are nicely orthogonal and relieve us
     * of all that difficulty. For every point in the image space,
     * there are precisely as many points in the input space that
     * map to it as there are elements in the kernel of the
     * transformation matrix (because adding any kernel element to
     * the input does not change the output, and because any two
     * inputs mapping to the same output must differ by an element
     * of the kernel because that's what the kernel _is_); and
     * these cosets are all disjoint (obviously, since no input
     * point can map to more than one output point) and cover the
     * whole space (equally obviously, because no input point can
     * map to fewer than one output point!).
     *
     * So the input space contains the same number of points for
     * each point in the output space; thus, we can simply choose
     * equiprobably from elements of the _input_ space, and filter
     * the result through the transformation matrix in the obvious
     * way, and we thereby guarantee to choose equiprobably from
     * all the output points. Phew!
     */
    while (1) {
        memset(grid, 0, wh);
        for (i = 0; i < wh; i++) {
            int v = random_upto(rs, 2);
            if (v) {
                for (j = 0; j < wh; j++)
                    grid[j] ^= matrix[i*wh+j];
            }
        }
        /*
         * Ensure we don't have the starting state already!
         */
        for (i = 0; i < wh; i++)
            if (grid[i])
                break;
        if (i < wh)
            break;
    }

    /*
     * Now encode the matrix and the starting grid as a game
     * description. We'll do this by concatenating two great big
     * hex bitmaps.
     */
    mbmp = encode_bitmap(matrix, wh*wh);
    gbmp = encode_bitmap(grid, wh);
    ret = snewn(strlen(mbmp) + strlen(gbmp) + 2, char);
    sprintf(ret, "%s,%s", mbmp, gbmp);
    sfree(mbmp);
    sfree(gbmp);
    sfree(matrix);
    sfree(grid);
    return ret;
}

static const char *validate_desc(const game_params *params, const char *desc)
{
    int w = params->w, h = params->h, wh = w * h;
    int mlen = (wh*wh+3)/4, glen = (wh+3)/4;

    if (strspn(desc, "0123456789abcdefABCDEF") != mlen)
        return "Matrix description is wrong length";
    if (desc[mlen] != ',')
        return "Expected comma after matrix description";
    if (strspn(desc+mlen+1, "0123456789abcdefABCDEF") != glen)
        return "Grid description is wrong length";
    if (desc[mlen+1+glen])
        return "Unexpected data after grid description";

    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;
    int mlen = (wh*wh+3)/4;

    game_state *state = snew(game_state);

    state->w = w;
    state->h = h;
    state->completed = false;
    state->cheated = false;
    state->hints_active = false;
    state->moves = 0;
    state->matrix = snew(struct matrix);
    state->matrix->refcount = 1;
    state->matrix->matrix = snewn(wh*wh, unsigned char);
    decode_bitmap(state->matrix->matrix, wh*wh, desc);
    state->grid = snewn(wh, unsigned char);
    decode_bitmap(state->grid, wh, desc + mlen + 1);

    return state;
}

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

    ret->w = state->w;
    ret->h = state->h;
    ret->completed = state->completed;
    ret->cheated = state->cheated;
    ret->hints_active = state->hints_active;
    ret->moves = state->moves;
    ret->matrix = state->matrix;
    state->matrix->refcount++;
    ret->grid = snewn(ret->w * ret->h, unsigned char);
    memcpy(ret->grid, state->grid, ret->w * ret->h);

    return ret;
}

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

static void rowxor(unsigned char *row1, unsigned char *row2, int len)
{
    int i;
    for (i = 0; i < len; i++)
	row1[i] ^= row2[i];
}

static char *solve_game(const game_state *state, const game_state *currstate,
                        const char *aux, const char **error)
{
    int w = state->w, h = state->h, wh = w * h;
    unsigned char *equations, *solution, *shortest;
    int *und, nund;
    int rowsdone, colsdone;
    int i, j, k, len, bestlen;
    char *ret;

    /*
     * Set up a list of simultaneous equations. Each one is of
     * length (wh+1) and has wh coefficients followed by a value.
     */
    equations = snewn((wh + 1) * wh, unsigned char);
    for (i = 0; i < wh; i++) {
	for (j = 0; j < wh; j++)
	    equations[i * (wh+1) + j] = currstate->matrix->matrix[j*wh+i];
	equations[i * (wh+1) + wh] = currstate->grid[i] & 1;
    }

    /*
     * Perform Gaussian elimination over GF(2).
     */
    rowsdone = colsdone = 0;
    nund = 0;
    und = snewn(wh, int);
    do {
	/*
	 * Find the leftmost column which has a 1 in it somewhere
	 * outside the first `rowsdone' rows.
	 */
	j = -1;
	for (i = colsdone; i < wh; i++) {
	    for (j = rowsdone; j < wh; j++)
		if (equations[j * (wh+1) + i])
		    break;
	    if (j < wh)
		break;		       /* found one */
	    /*
	     * This is a column which will not have an equation
	     * controlling it. Mark it as undetermined.
	     */
	    und[nund++] = i;
	}

	/*
	 * If there wasn't one, then we've finished: all remaining
	 * equations are of the form 0 = constant. Check to see if
	 * any of them wants 0 to be equal to 1; this is the
	 * condition which indicates an insoluble problem
	 * (therefore _hopefully_ one typed in by a user!).
	 */
	if (i == wh) {
	    for (j = rowsdone; j < wh; j++)
		if (equations[j * (wh+1) + wh]) {
		    *error = "No solution exists for this position";
		    sfree(equations);
		    sfree(und);
		    return NULL;
		}
	    break;
	}

	/*
	 * We've found a 1. It's in column i, and the topmost 1 in
	 * that column is in row j. Do a row-XOR to move it up to
	 * the topmost row if it isn't already there.
	 */
	assert(j != -1);
	if (j > rowsdone)
	    rowxor(equations + rowsdone*(wh+1), equations + j*(wh+1), wh+1);

	/*
	 * Do row-XORs to eliminate that 1 from all rows below the
	 * topmost row.
	 */
	for (j = rowsdone + 1; j < wh; j++)
	    if (equations[j*(wh+1) + i])
		rowxor(equations + j*(wh+1),
		       equations + rowsdone*(wh+1), wh+1);

	/*
	 * Mark this row and column as done.
	 */
	rowsdone++;
	colsdone = i+1;

	/*
	 * If we've done all the rows, terminate.
	 */
    } while (rowsdone < wh);

    /*
     * If we reach here, we have the ability to produce a solution.
     * So we go through _all_ possible solutions (each
     * corresponding to a set of arbitrary choices of those
     * components not directly determined by an equation), and pick
     * one requiring the smallest number of flips.
     */
    solution = snewn(wh, unsigned char);
    shortest = snewn(wh, unsigned char);
    memset(solution, 0, wh);
    bestlen = wh + 1;
    while (1) {
	/*
	 * Find a solution based on the current values of the
	 * undetermined variables.
	 */
	for (j = rowsdone; j-- ;) {
	    int v;

	    /*
	     * Find the leftmost set bit in this equation.
	     */
	    for (i = 0; i < wh; i++)
		if (equations[j * (wh+1) + i])
		    break;
	    assert(i < wh);		       /* there must have been one! */

	    /*
	     * Compute this variable using the rest.
	     */
	    v = equations[j * (wh+1) + wh];
	    for (k = i+1; k < wh; k++)
		if (equations[j * (wh+1) + k])
		    v ^= solution[k];

	    solution[i] = v;
	}

	/*
	 * Compare this solution to the current best one, and
	 * replace the best one if this one is shorter.
	 */
	len = 0;
	for (i = 0; i < wh; i++)
	    if (solution[i])
		len++;
	if (len < bestlen) {
	    bestlen = len;
	    memcpy(shortest, solution, wh);
	}

	/*
	 * Now increment the binary number given by the
	 * undetermined variables: turn all 1s into 0s until we see
	 * a 0, at which point we turn it into a 1.
	 */
	for (i = 0; i < nund; i++) {
	    solution[und[i]] = !solution[und[i]];
	    if (solution[und[i]])
		break;
	}

	/*
	 * If we didn't find a 0 at any point, we have wrapped
	 * round and are back at the start, i.e. we have enumerated
	 * all solutions.
	 */
	if (i == nund)
	    break;
    }

    /*
     * We have a solution. Produce a move string encoding the
     * solution.
     */
    ret = snewn(wh + 2, char);
    ret[0] = 'S';
    for (i = 0; i < wh; i++)
	ret[i+1] = shortest[i] ? '1' : '0';
    ret[wh+1] = '\0';

    sfree(shortest);
    sfree(solution);
    sfree(equations);
    sfree(und);

    return ret;
}

static bool game_can_format_as_text_now(const game_params *params)
{
    return true;
}

#define RIGHT 1
#define DOWN gw

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

    memset(board, ' ', len - 1);

    for (r = 0; r < h; ++r) {
	for (c = 0; c < w; ++c) {
	    int cell = r*ch*gw + c*cw, center = cell+(ch/2)*DOWN + cw/2*RIGHT;
	    char flip = (state->grid[r*w + c] & 1) ? '#' : '.';
	    for (dy = -1 + (r == 0); dy <= 1 - (r == h - 1); ++dy)
		for (dx = -1 + (c == 0); dx <= 1 - (c == w - 1); ++dx)
		    if (state->matrix->matrix[(r*w+c)*wh + ((r+dy)*w + c+dx)])
			board[center + dy*DOWN + dx*RIGHT] = flip;
	    board[cell] = '+';
	    for (dx = 1; dx < cw; ++dx) board[cell+dx*RIGHT] = '-';
	    for (dy = 1; dy < ch; ++dy) board[cell+dy*DOWN] = '|';
	}
	board[r*ch*gw + gw - 2] = '+';
	board[r*ch*gw + gw - 1] = '\n';
	for (dy = 1; dy < ch; ++dy) {
	    board[r*ch*gw + gw - 2 + dy*DOWN] = '|';
	    board[r*ch*gw + gw - 1 + dy*DOWN] = '\n';
	}
    }
    memset(board + len - gw, '-', gw - 2);
    for (c = 0; c <= w; ++c) board[len - gw + cw*c] = '+';
    board[len - 1] = '\n';
    board[len] = '\0';
    return board;
}

#undef RIGHT
#undef DOWN

struct game_ui {
    int cx, cy;
    bool cdraw;
};

static game_ui *new_ui(const game_state *state)
{
    game_ui *ui = snew(game_ui);
    ui->cx = ui->cy = 0;
    ui->cdraw = 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)
{
    if (IS_CURSOR_SELECT(button)) return "Flip";
    return "";
}

struct game_drawstate {
    int w, h;
    bool started;
    unsigned char *tiles;
    int tilesize;
};

static char *interpret_move(const game_state *state, game_ui *ui,
                            const game_drawstate *ds,
                            int x, int y, int button)
{
    int w = state->w, h = state->h, wh = w * h;
    char buf[80], *nullret = MOVE_UNUSED;

    if (button == LEFT_BUTTON || IS_CURSOR_SELECT(button)) {
        int tx, ty;
        if (button == LEFT_BUTTON) {
            tx = FROMCOORD(x), ty = FROMCOORD(y);
            ui->cdraw = false;
        } else {
            tx = ui->cx; ty = ui->cy;
            ui->cdraw = true;
        }
        nullret = MOVE_UI_UPDATE;

        if (tx >= 0 && tx < w && ty >= 0 && ty < h) {
            /*
             * It's just possible that a manually entered game ID
             * will have at least one square do nothing whatsoever.
             * If so, we avoid encoding a move at all.
             */
            int i = ty*w+tx, j;
            bool makemove = false;
            for (j = 0; j < wh; j++) {
                if (state->matrix->matrix[i*wh+j])
                    makemove = true;
            }
            if (makemove) {
                sprintf(buf, "M%d,%d", tx, ty);
                return dupstr(buf);
            } else {
                return MOVE_NO_EFFECT;
            }
        }
    }
    else if (IS_CURSOR_MOVE(button)) {
        int dx = 0, dy = 0;
        switch (button) {
        case CURSOR_UP:         dy = -1; break;
        case CURSOR_DOWN:       dy = 1; break;
        case CURSOR_RIGHT:      dx = 1; break;
        case CURSOR_LEFT:       dx = -1; break;
        default: assert(!"shouldn't get here");
        }
        ui->cx += dx; ui->cy += dy;
        ui->cx = min(max(ui->cx, 0), state->w - 1);
        ui->cy = min(max(ui->cy, 0), state->h - 1);
        ui->cdraw = true;
        nullret = MOVE_UI_UPDATE;
    }

    return nullret;
}

static game_state *execute_move(const game_state *from, const char *move)
{
    int w = from->w, h = from->h, wh = w * h;
    game_state *ret;
    int x, y;

    if (move[0] == 'S' && strlen(move) == wh+1) {
	int i;

	ret = dup_game(from);
	ret->hints_active = true;
	ret->cheated = true;
	for (i = 0; i < wh; i++) {
	    ret->grid[i] &= ~2;
	    if (move[i+1] != '0')
		ret->grid[i] |= 2;
	}
	return ret;
    } else if (move[0] == 'M' &&
	       sscanf(move+1, "%d,%d", &x, &y) == 2 &&
	x >= 0 && x < w && y >= 0 && y < h) {
	int i, j;
        bool done;

	ret = dup_game(from);

	if (!ret->completed)
	    ret->moves++;

	i = y * w + x;

	done = true;
	for (j = 0; j < wh; j++) {
	    ret->grid[j] ^= ret->matrix->matrix[i*wh+j];
	    if (ret->grid[j] & 1)
		done = false;
	}
	ret->grid[i] ^= 2;	       /* toggle hint */
	if (done) {
	    ret->completed = true;
	    ret->hints_active = false;
	}

	return ret;
    } else
	return NULL;		       /* can't parse move string */
}

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

static void game_compute_size(const game_params *params, int tilesize,
                              const game_ui *ui, int *x, int *y)
{
    /* Ick: fake up `ds->tilesize' for macro expansion purposes */
    struct { int tilesize; } ads, *ds = &ads;
    ads.tilesize = tilesize;

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

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_WRONG * 3 + 0] = ret[COL_BACKGROUND * 3 + 0] / 3;
    ret[COL_WRONG * 3 + 1] = ret[COL_BACKGROUND * 3 + 1] / 3;
    ret[COL_WRONG * 3 + 2] = ret[COL_BACKGROUND * 3 + 2] / 3;

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

    ret[COL_GRID * 3 + 0] = ret[COL_BACKGROUND * 3 + 0] / 1.5F;
    ret[COL_GRID * 3 + 1] = ret[COL_BACKGROUND * 3 + 1] / 1.5F;
    ret[COL_GRID * 3 + 2] = ret[COL_BACKGROUND * 3 + 2] / 1.5F;

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

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

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

    *ncolours = NCOLOURS;
    return ret;
}

static game_drawstate *game_new_drawstate(drawing *dr, const game_state *state)
{
    struct game_drawstate *ds = snew(struct game_drawstate);
    int i;

    ds->started = false;
    ds->w = state->w;
    ds->h = state->h;
    ds->tiles = snewn(ds->w*ds->h, unsigned char);
    ds->tilesize = 0;                  /* haven't decided yet */
    for (i = 0; i < ds->w*ds->h; i++)
        ds->tiles[i] = -1;

    return ds;
}

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

static void draw_tile(drawing *dr, game_drawstate *ds, const game_state *state,
                      int x, int y, int tile, bool anim, float animtime)
{
    int w = ds->w, h = ds->h, wh = w * h;
    int bx = x * TILE_SIZE + BORDER, by = y * TILE_SIZE + BORDER;
    int i, j, dcol = (tile & 4) ? COL_CURSOR : COL_DIAG;

    clip(dr, bx+1, by+1, TILE_SIZE-1, TILE_SIZE-1);

    draw_rect(dr, bx+1, by+1, TILE_SIZE-1, TILE_SIZE-1,
              anim ? COL_BACKGROUND : tile & 1 ? COL_WRONG : COL_RIGHT);
    if (anim) {
	/*
	 * Draw a polygon indicating that the square is diagonally
	 * flipping over.
	 */
	int coords[8], colour;

	coords[0] = bx + TILE_SIZE;
	coords[1] = by;
	coords[2] = bx + (int)((float)TILE_SIZE * animtime);
	coords[3] = by + (int)((float)TILE_SIZE * animtime);
	coords[4] = bx;
	coords[5] = by + TILE_SIZE;
	coords[6] = bx + TILE_SIZE - (int)((float)TILE_SIZE * animtime);
	coords[7] = by + TILE_SIZE - (int)((float)TILE_SIZE * animtime);

	colour = (tile & 1 ? COL_WRONG : COL_RIGHT);
	if (animtime < 0.5F)
	    colour = COL_WRONG + COL_RIGHT - colour;

	draw_polygon(dr, coords, 4, colour, COL_GRID);
    }

    /*
     * Draw a little diagram in the tile which indicates which
     * surrounding tiles flip when this one is clicked.
     */
    for (i = 0; i < h; i++)
	for (j = 0; j < w; j++)
	    if (state->matrix->matrix[(y*w+x)*wh + i*w+j]) {
		int ox = j - x, oy = i - y;
		int td = TILE_SIZE / 16 ? TILE_SIZE / 16 : 1;
		int cx = (bx + TILE_SIZE/2) + (2 * ox - 1) * td;
		int cy = (by + TILE_SIZE/2) + (2 * oy - 1) * td;
		if (ox == 0 && oy == 0)
                    draw_rect(dr, cx, cy, 2*td+1, 2*td+1, dcol);
                else {
                    draw_line(dr, cx, cy, cx+2*td, cy, dcol);
                    draw_line(dr, cx, cy+2*td, cx+2*td, cy+2*td, dcol);
                    draw_line(dr, cx, cy, cx, cy+2*td, dcol);
                    draw_line(dr, cx+2*td, cy, cx+2*td, cy+2*td, dcol);
                }
	    }

    /*
     * Draw a hint rectangle if required.
     */
    if (tile & 2) {
	int x1 = bx + TILE_SIZE / 20, x2 = bx + TILE_SIZE - TILE_SIZE / 20;
	int y1 = by + TILE_SIZE / 20, y2 = by + TILE_SIZE - TILE_SIZE / 20;
	int i = 3;
	while (i--) {
	    draw_line(dr, x1, y1, x2, y1, COL_HINT);
	    draw_line(dr, x1, y2, x2, y2, COL_HINT);
	    draw_line(dr, x1, y1, x1, y2, COL_HINT);
	    draw_line(dr, x2, y1, x2, y2, COL_HINT);
	    x1++, y1++, x2--, y2--;
	}
    }

    unclip(dr);

    draw_update(dr, bx+1, by+1, TILE_SIZE-1, TILE_SIZE-1);
}

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 = ds->w, h = ds->h, wh = w * h;
    int i, flashframe;

    if (!ds->started) {
        /*
         * Draw the grid lines.
         */
        for (i = 0; i <= w; i++)
            draw_line(dr, i * TILE_SIZE + BORDER, BORDER,
                      i * TILE_SIZE + BORDER, h * TILE_SIZE + BORDER,
                      COL_GRID);
        for (i = 0; i <= h; i++)
            draw_line(dr, BORDER, i * TILE_SIZE + BORDER,
                      w * TILE_SIZE + BORDER, i * TILE_SIZE + BORDER,
                      COL_GRID);

        draw_update(dr, 0, 0, TILE_SIZE * w + 2 * BORDER,
                    TILE_SIZE * h + 2 * BORDER);

        ds->started = true;
    }

    if (flashtime)
	flashframe = (int)(flashtime / FLASH_FRAME);
    else
	flashframe = -1;

    animtime /= ANIM_TIME;	       /* scale it so it goes from 0 to 1 */

    for (i = 0; i < wh; i++) {
        int x = i % w, y = i / w;
	int fx, fy, fd;
	int v = state->grid[i];
	int vv;

	if (flashframe >= 0) {
	    fx = (w+1)/2 - min(x+1, w-x);
	    fy = (h+1)/2 - min(y+1, h-y);
	    fd = max(fx, fy);
	    if (fd == flashframe)
		v |= 1;
	    else if (fd == flashframe - 1)
		v &= ~1;
	}

	if (!state->hints_active)
	    v &= ~2;
        if (ui->cdraw && ui->cx == x && ui->cy == y)
            v |= 4;

	if (oldstate && ((state->grid[i] ^ oldstate->grid[i]) &~ 2))
	    vv = 255;		       /* means `animated' */
	else
	    vv = v;

        if (ds->tiles[i] == 255 || vv == 255 || ds->tiles[i] != vv) {
            draw_tile(dr, ds, state, x, y, v, vv == 255, animtime);
            ds->tiles[i] = vv;
        }
    }

    {
	char buf[256];

	sprintf(buf, "%sMoves: %d",
		(state->completed ? 
		 (state->cheated ? "Auto-solved. " : "COMPLETED! ") :
		 (state->cheated ? "Auto-solver used. " : "")),
		state->moves);

	status_bar(dr, buf);
    }
}

static float game_anim_length(const game_state *oldstate,
                              const game_state *newstate, int dir, game_ui *ui)
{
    return ANIM_TIME;
}

static float game_flash_length(const game_state *oldstate,
                               const game_state *newstate, int dir, game_ui *ui)
{
    if (!oldstate->completed && newstate->completed)
        return FLASH_FRAME * (max((newstate->w+1)/2, (newstate->h+1)/2)+1);

    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->cdraw)
    {
        *x = COORD(ui->cx);
        *y = COORD(ui->cy);
        *w = *h = TILE_SIZE;
    }
}

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

#ifdef COMBINED
#define thegame flip
#endif

const struct game thegame = {
    "Flip", "games.flip", "flip",
    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_TILE_SIZE, game_compute_size, game_set_size,
    game_colours,
    game_new_drawstate,
    game_free_drawstate,
    game_redraw,
    game_anim_length,
    game_flash_length,
    game_get_cursor_location,
    game_status,
    false, false, NULL, NULL,          /* print_size, print */
    true,			       /* wants_statusbar */
    false, NULL,                       /* timing_state */
    0,				       /* flags */
};