apps/plugins/test_touchscreen.c


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141

/***************************************************************************
 *             __________               __   ___.
 *   Open      \______   \ ____   ____ |  | _\_ |__   _______  ___
 *   Source     |       _//  _ \_/ ___\|  |/ /| __ \ /  _ \  \/  /
 *   Jukebox    |    |   (  <_> )  \___|    < | \_\ (  <_> > <  <
 *   Firmware   |____|_  /\____/ \___  >__|_ \|___  /\____/__/\_ \
 *                     \/            \/     \/    \/            \/
 * $Id$
 *
 * Copyright (C) 2008 Rob Purchase
 *
 * This program is free software; you can redistribute it and/or
 * modify it under the terms of the GNU General Public License
 * as published by the Free Software Foundation; either version 2
 * of the License, or (at your option) any later version.
 *
 * This software is distributed on an "AS IS" basis, WITHOUT WARRANTY OF ANY
 * KIND, either express or implied.
 *
 ****************************************************************************/
#include "plugin.h"

PLUGIN_HEADER

#if (CONFIG_KEYPAD == COWOND2_PAD)
#define TOUCHSCREEN_QUIT   BUTTON_POWER
#define TOUCHSCREEN_TOGGLE BUTTON_MENU
#elif (CONFIG_KEYPAD == MROBE500_PAD)
#define TOUCHSCREEN_QUIT   BUTTON_POWER
#define TOUCHSCREEN_TOGGLE BUTTON_RC_MODE
#endif

static const struct plugin_api* rb;

/* plugin entry point */
enum plugin_status plugin_start(const struct plugin_api* api, const void* parameter)
{
    int button = 0;
    enum touchscreen_mode mode = TOUCHSCREEN_BUTTON;

    /* standard stuff */
    (void)parameter;
    rb = api;
    
    rb->touchscreen_set_mode(mode);

    /* wait until user closes plugin */
    do
    {
        short x = 0;
        short y = 0;
        bool draw_rect = false;
        
        button = rb->button_get(true);

        if (button & BUTTON_TOPLEFT)
        {
            draw_rect = true;
            x = 0; y = 0;
        }
        else if (button & BUTTON_TOPMIDDLE)
        {
            draw_rect = true;
            x = LCD_WIDTH/3; y = 0;
        }
        else if (button & BUTTON_TOPRIGHT)
        {
            draw_rect = true;
            x = 2*(LCD_WIDTH/3); y = 0;
        }
        else if (button & BUTTON_MIDLEFT)
        {
            draw_rect = true;
            x = 0; y = LCD_HEIGHT/3;
        }
        else if (button & BUTTON_CENTER)
        {
            draw_rect = true;
            x = LCD_WIDTH/3; y = LCD_HEIGHT/3;
        }
        else if (button & BUTTON_MIDRIGHT)
        {
            draw_rect = true;
            x = 2*(LCD_WIDTH/3); y = LCD_HEIGHT/3;
        }
        else if (button & BUTTON_BOTTOMLEFT)
        {
            draw_rect = true;
            x = 0; y = 2*(LCD_HEIGHT/3);
        }
        else if (button & BUTTON_BOTTOMMIDDLE)
        {
            draw_rect = true;
            x = LCD_WIDTH/3; y = 2*(LCD_HEIGHT/3);
        }
        else if (button & BUTTON_BOTTOMRIGHT)
        {
            draw_rect = true;
            x = 2*(LCD_WIDTH/3); y = 2*(LCD_HEIGHT/3);
        }

        if (button & TOUCHSCREEN_TOGGLE && (button & BUTTON_REL))
        {
            mode = (mode == TOUCHSCREEN_POINT) ? TOUCHSCREEN_BUTTON : TOUCHSCREEN_POINT;
            rb->touchscreen_set_mode(mode);
        }
        
        if (button & BUTTON_REL) draw_rect = false;

        rb->lcd_clear_display();

        if (draw_rect)
        {
            rb->lcd_set_foreground(LCD_RGBPACK(0xc0, 0, 0));
            rb->lcd_fillrect(x, y, LCD_WIDTH/3, LCD_HEIGHT/3);
        }

        if (draw_rect || button & BUTTON_TOUCHSCREEN)
        {
            intptr_t button_data = rb->button_get_data();
            x = button_data >> 16;
            y = button_data & 0xffff;

            rb->lcd_set_foreground(LCD_RGBPACK(0, 0, 0xc0));
            rb->lcd_fillrect(x-7, y-7, 14, 14);
            
            /* in stylus mode, show REL position in black */
            if (mode == TOUCHSCREEN_POINT && (button & BUTTON_REL))
                rb->lcd_set_foreground(LCD_BLACK);
            else
                rb->lcd_set_foreground(LCD_WHITE);

            rb->lcd_hline(x-5, x+5, y);
            rb->lcd_vline(x, y-5, y+5);
        }
        rb->lcd_update();

    } while (button != TOUCHSCREEN_QUIT);

    return PLUGIN_OK;
}
/*
 * loopy.c:
 *
 * An implementation of the Nikoli game 'Loop the loop'.
 * (c) Mike Pinna, 2005, 2006
 * Substantially rewritten to allowing for more general types of grid.
 * (c) Lambros Lambrou 2008
 *
 * vim: set shiftwidth=4 :set textwidth=80:
 */

/*
 * Possible future solver enhancements:
 * 
 *  - There's an interesting deductive technique which makes use
 *    of topology rather than just graph theory. Each _face_ in
 *    the grid is either inside or outside the loop; you can tell
 *    that two faces are on the same side of the loop if they're
 *    separated by a LINE_NO (or, more generally, by a path
 *    crossing no LINE_UNKNOWNs and an even number of LINE_YESes),
 *    and on the opposite side of the loop if they're separated by
 *    a LINE_YES (or an odd number of LINE_YESes and no
 *    LINE_UNKNOWNs). Oh, and any face separated from the outside
 *    of the grid by a LINE_YES or a LINE_NO is on the inside or
 *    outside respectively. So if you can track this for all
 *    faces, you figure out the state of the line between a pair
 *    once their relative insideness is known.
 *     + The way I envisage this working is simply to keep an edsf
 * 	 of all _faces_, which indicates whether they're on
 * 	 opposite sides of the loop from one another. We also
 * 	 include a special entry in the edsf for the infinite
 * 	 exterior "face".
 *     + So, the simple way to do this is to just go through the
 * 	 edges: every time we see an edge in a state other than
 * 	 LINE_UNKNOWN which separates two faces that aren't in the
 * 	 same edsf class, we can rectify that by merging the
 * 	 classes. Then, conversely, an edge in LINE_UNKNOWN state
 * 	 which separates two faces that _are_ in the same edsf
 * 	 class can immediately have its state determined.
 *     + But you can go one better, if you're prepared to loop
 * 	 over all _pairs_ of edges. Suppose we have edges A and B,
 * 	 which respectively separate faces A1,A2 and B1,B2.
 * 	 Suppose that A,B are in the same edge-edsf class and that
 * 	 A1,B1 (wlog) are in the same face-edsf class; then we can
 * 	 immediately place A2,B2 into the same face-edsf class (as
 * 	 each other, not as A1 and A2) one way round or the other.
 * 	 And conversely again, if A1,B1 are in the same face-edsf
 * 	 class and so are A2,B2, then we can put A,B into the same
 * 	 face-edsf class.
 * 	  * Of course, this deduction requires a quadratic-time
 * 	    loop over all pairs of edges in the grid, so it should
 * 	    be reserved until there's nothing easier left to be
 * 	    done.
 * 
 *  - The generalised grid support has made me (SGT) notice a
 *    possible extension to the loop-avoidance code. When you have
 *    a path of connected edges such that no other edges at all
 *    are incident on any vertex in the middle of the path - or,
 *    alternatively, such that any such edges are already known to
 *    be LINE_NO - then you know those edges are either all
 *    LINE_YES or all LINE_NO. Hence you can mentally merge the
 *    entire path into a single long curly edge for the purposes
 *    of loop avoidance, and look directly at whether or not the
 *    extreme endpoints of the path are connected by some other
 *    route. I find this coming up fairly often when I play on the
 *    octagonal grid setting, so it might be worth implementing in
 *    the solver.
 *
 *  - (Just a speed optimisation.)  Consider some todo list queue where every
 *    time we modify something we mark it for consideration by other bits of
 *    the solver, to save iteration over things that have already been done.
 */

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

#include "puzzles.h"
#include "tree234.h"
#include "grid.h"
#include "loopgen.h"

/* Debugging options */

/*
#define DEBUG_CACHES
#define SHOW_WORKING
#define DEBUG_DLINES
*/

/* ----------------------------------------------------------------------
 * Struct, enum and function declarations
 */

enum {
    COL_BACKGROUND,
    COL_FOREGROUND,
    COL_LINEUNKNOWN,
    COL_HIGHLIGHT,
    COL_MISTAKE,
    COL_SATISFIED,
    COL_FAINT,
    NCOLOURS
};

struct game_state {
    grid *game_grid; /* ref-counted (internally) */

    /* Put -1 in a face that doesn't get a clue */
    signed char *clues;

    /* Array of line states, to store whether each line is
     * YES, NO or UNKNOWN */
    char *lines;

    unsigned char *line_errors;
    int exactly_one_loop;

    int solved;
    int cheated;

    /* Used in game_text_format(), so that it knows what type of
     * grid it's trying to render as ASCII text. */
    int grid_type;
};

enum solver_status {
    SOLVER_SOLVED,    /* This is the only solution the solver could find */
    SOLVER_MISTAKE,   /* This is definitely not a solution */
    SOLVER_AMBIGUOUS, /* This _might_ be an ambiguous solution */
    SOLVER_INCOMPLETE /* This may be a partial solution */
};

/* ------ Solver state ------ */
typedef struct solver_state {
    game_state *state;
    enum solver_status solver_status;
    /* NB looplen is the number of dots that are joined together at a point, ie a
     * looplen of 1 means there are no lines to a particular dot */
    int *looplen;

    /* Difficulty level of solver.  Used by solver functions that want to
     * vary their behaviour depending on the requested difficulty level. */
    int diff;

    /* caches */
    char *dot_yes_count;
    char *dot_no_count;
    char *face_yes_count;
    char *face_no_count;
    char *dot_solved, *face_solved;
    int *dotdsf;

    /* Information for Normal level deductions:
     * For each dline, store a bitmask for whether we know:
     * (bit 0) at least one is YES
     * (bit 1) at most one is YES */
    char *dlines;

    /* Hard level information */
    int *linedsf;
} solver_state;

/*
 * Difficulty levels. I do some macro ickery here to ensure that my
 * enum and the various forms of my name list always match up.
 */

#define DIFFLIST(A) \
    A(EASY,Easy,e) \
    A(NORMAL,Normal,n) \
    A(TRICKY,Tricky,t) \
    A(HARD,Hard,h)
#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) DIFF_MAX };
static char const *const diffnames[] = { DIFFLIST(TITLE) };
static char const diffchars[] = DIFFLIST(ENCODE);
#define DIFFCONFIG DIFFLIST(CONFIG)

/*
 * Solver routines, sorted roughly in order of computational cost.
 * The solver will run the faster deductions first, and slower deductions are
 * only invoked when the faster deductions are unable to make progress.
 * Each function is associated with a difficulty level, so that the generated
 * puzzles are solvable by applying only the functions with the chosen
 * difficulty level or lower.
 */
#define SOLVERLIST(A) \
    A(trivial_deductions, DIFF_EASY) \
    A(dline_deductions, DIFF_NORMAL) \
    A(linedsf_deductions, DIFF_HARD) \
    A(loop_deductions, DIFF_EASY)
#define SOLVER_FN_DECL(fn,diff) static int fn(solver_state *);
#define SOLVER_FN(fn,diff) &fn,
#define SOLVER_DIFF(fn,diff) diff,
SOLVERLIST(SOLVER_FN_DECL)
static int (*(solver_fns[]))(solver_state *) = { SOLVERLIST(SOLVER_FN) };
static int const solver_diffs[] = { SOLVERLIST(SOLVER_DIFF) };
static const int NUM_SOLVERS = sizeof(solver_diffs)/sizeof(*solver_diffs);

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

/* line_drawstate is the same as line_state, but with the extra ERROR
 * possibility.  The drawing code copies line_state to line_drawstate,
 * except in the case that the line is an error. */
enum line_state { LINE_YES, LINE_UNKNOWN, LINE_NO };
enum line_drawstate { DS_LINE_YES, DS_LINE_UNKNOWN,
                      DS_LINE_NO, DS_LINE_ERROR };

#define OPP(line_state) \
    (2 - line_state)


struct game_drawstate {
    int started;
    int tilesize;
    int flashing;
    int *textx, *texty;
    char *lines;
    char *clue_error;
    char *clue_satisfied;
};

static const char *validate_desc(const game_params *params, const char *desc);
static int dot_order(const game_state* state, int i, char line_type);
static int face_order(const game_state* state, int i, char line_type);
static solver_state *solve_game_rec(const solver_state *sstate);

#ifdef DEBUG_CACHES
static void check_caches(const solver_state* sstate);
#else
#define check_caches(s)
#endif

/*
 * Grid type config options available in Loopy.
 *
 * Annoyingly, we have to use an enum here which doesn't match up
 * exactly to the grid-type enum in grid.h. Values in params->types
 * are given by names such as LOOPY_GRID_SQUARE, which shouldn't be
 * confused with GRID_SQUARE which is the value you pass to grid_new()
 * and friends. So beware!
 *
 * (This is partly for historical reasons - Loopy's version of the
 * enum is encoded in game parameter strings, so we keep it for
 * backwards compatibility. But also, we need to store additional data
 * here alongside each enum value, such as names for the presets menu,
 * which isn't stored in grid.h; so we have to have our own list macro
 * here anyway, and C doesn't make it easy to enforce that that lines
 * up exactly with grid.h.)
 *
 * Do not add values to this list _except_ at the end, or old game ids
 * will stop working!
 */
#define GRIDLIST(A)                                             \
    A("Squares",SQUARE,3,3)                                     \
    A("Triangular",TRIANGULAR,3,3)                              \
    A("Honeycomb",HONEYCOMB,3,3)                                \
    A("Snub-Square",SNUBSQUARE,3,3)                             \
    A("Cairo",CAIRO,3,4)                                        \
    A("Great-Hexagonal",GREATHEXAGONAL,3,3)                     \
    A("Octagonal",OCTAGONAL,3,3)                                \
    A("Kites",KITE,3,3)                                         \
    A("Floret",FLORET,1,2)                                      \
    A("Dodecagonal",DODECAGONAL,2,2)                            \
    A("Great-Dodecagonal",GREATDODECAGONAL,2,2)                 \
    A("Penrose (kite/dart)",PENROSE_P2,3,3)                     \
    A("Penrose (rhombs)",PENROSE_P3,3,3)                        \
    A("Great-Great-Dodecagonal",GREATGREATDODECAGONAL,2,2)      \
    A("Kagome",KAGOME,3,3)                                      \
    /* end of list */

#define GRID_NAME(title,type,amin,omin) title,
#define GRID_CONFIG(title,type,amin,omin) ":" title
#define GRID_LOOPYTYPE(title,type,amin,omin) LOOPY_GRID_ ## type,
#define GRID_GRIDTYPE(title,type,amin,omin) GRID_ ## type,
#define GRID_SIZES(title,type,amin,omin) \
    {amin, omin, \
     "Width and height for this grid type must both be at least " #amin, \
     "At least one of width and height for this grid type must be at least " #omin,},
enum { GRIDLIST(GRID_LOOPYTYPE) LOOPY_GRID_DUMMY_TERMINATOR };
static char const *const gridnames[] = { GRIDLIST(GRID_NAME) };
#define GRID_CONFIGS GRIDLIST(GRID_CONFIG)
static grid_type grid_types[] = { GRIDLIST(GRID_GRIDTYPE) };
#define NUM_GRID_TYPES (sizeof(grid_types) / sizeof(grid_types[0]))
static const struct {
    int amin, omin;
    const char *aerr, *oerr;
} grid_size_limits[] = { GRIDLIST(GRID_SIZES) };

/* Generates a (dynamically allocated) new grid, according to the
 * type and size requested in params.  Does nothing if the grid is already
 * generated. */
static grid *loopy_generate_grid(const game_params *params,
                                 const char *grid_desc)
{
    return grid_new(grid_types[params->type], params->w, params->h, grid_desc);
}

/* ----------------------------------------------------------------------
 * Preprocessor magic
 */

/* General constants */
#define PREFERRED_TILE_SIZE 32
#define BORDER(tilesize) ((tilesize) / 2)
#define FLASH_TIME 0.5F

#define BIT_SET(field, bit) ((field) & (1<<(bit)))

#define SET_BIT(field, bit)  (BIT_SET(field, bit) ? FALSE : \
                              ((field) |= (1<<(bit)), TRUE))

#define CLEAR_BIT(field, bit) (BIT_SET(field, bit) ? \
                               ((field) &= ~(1<<(bit)), TRUE) : FALSE)

#define CLUE2CHAR(c) \
    ((c < 0) ? ' ' : c < 10 ? c + '0' : c - 10 + 'A')

/* ----------------------------------------------------------------------
 * General struct manipulation and other straightforward code
 */

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

    ret->game_grid = state->game_grid;
    ret->game_grid->refcount++;

    ret->solved = state->solved;
    ret->cheated = state->cheated;

    ret->clues = snewn(state->game_grid->num_faces, signed char);
    memcpy(ret->clues, state->clues, state->game_grid->num_faces);

    ret->lines = snewn(state->game_grid->num_edges, char);
    memcpy(ret->lines, state->lines, state->game_grid->num_edges);

    ret->line_errors = snewn(state->game_grid->num_edges, unsigned char);
    memcpy(ret->line_errors, state->line_errors, state->game_grid->num_edges);
    ret->exactly_one_loop = state->exactly_one_loop;

    ret->grid_type = state->grid_type;
    return ret;
}

static void free_game(game_state *state)
{
    if (state) {
        grid_free(state->game_grid);
        sfree(state->clues);
        sfree(state->lines);
        sfree(state->line_errors);
        sfree(state);
    }
}

static solver_state *new_solver_state(const game_state *state, int diff) {
    int i;
    int num_dots = state->game_grid->num_dots;
    int num_faces = state->game_grid->num_faces;
    int num_edges = state->game_grid->num_edges;
    solver_state *ret = snew(solver_state);

    ret->state = dup_game(state);

    ret->solver_status = SOLVER_INCOMPLETE;
    ret->diff = diff;

    ret->dotdsf = snew_dsf(num_dots);
    ret->looplen = snewn(num_dots, int);

    for (i = 0; i < num_dots; i++) {
        ret->looplen[i] = 1;
    }

    ret->dot_solved = snewn(num_dots, char);
    ret->face_solved = snewn(num_faces, char);
    memset(ret->dot_solved, FALSE, num_dots);
    memset(ret->face_solved, FALSE, num_faces);

    ret->dot_yes_count = snewn(num_dots, char);
    memset(ret->dot_yes_count, 0, num_dots);
    ret->dot_no_count = snewn(num_dots, char);
    memset(ret->dot_no_count, 0, num_dots);
    ret->face_yes_count = snewn(num_faces, char);
    memset(ret->face_yes_count, 0, num_faces);
    ret->face_no_count = snewn(num_faces, char);
    memset(ret->face_no_count, 0, num_faces);

    if (diff < DIFF_NORMAL) {
        ret->dlines = NULL;
    } else {
        ret->dlines = snewn(2*num_edges, char);
        memset(ret->dlines, 0, 2*num_edges);
    }

    if (diff < DIFF_HARD) {
        ret->linedsf = NULL;
    } else {
        ret->linedsf = snew_dsf(state->game_grid->num_edges);
    }

    return ret;
}

static void free_solver_state(solver_state *sstate) {
    if (sstate) {
        free_game(sstate->state);
        sfree(sstate->dotdsf);
        sfree(sstate->looplen);
        sfree(sstate->dot_solved);
        sfree(sstate->face_solved);
        sfree(sstate->dot_yes_count);
        sfree(sstate->dot_no_count);
        sfree(sstate->face_yes_count);
        sfree(sstate->face_no_count);

        /* OK, because sfree(NULL) is a no-op */
        sfree(sstate->dlines);
        sfree(sstate->linedsf);

        sfree(sstate);
    }
}

static solver_state *dup_solver_state(const solver_state *sstate) {
    game_state *state = sstate->state;
    int num_dots = state->game_grid->num_dots;
    int num_faces = state->game_grid->num_faces;
    int num_edges = state->game_grid->num_edges;
    solver_state *ret = snew(solver_state);

    ret->state = state = dup_game(sstate->state);

    ret->solver_status = sstate->solver_status;
    ret->diff = sstate->diff;

    ret->dotdsf = snewn(num_dots, int);
    ret->looplen = snewn(num_dots, int);
    memcpy(ret->dotdsf, sstate->dotdsf,
           num_dots * sizeof(int));
    memcpy(ret->looplen, sstate->looplen,
           num_dots * sizeof(int));

    ret->dot_solved = snewn(num_dots, char);
    ret->face_solved = snewn(num_faces, char);
    memcpy(ret->dot_solved, sstate->dot_solved, num_dots);
    memcpy(ret->face_solved, sstate->face_solved, num_faces);

    ret->dot_yes_count = snewn(num_dots, char);
    memcpy(ret->dot_yes_count, sstate->dot_yes_count, num_dots);
    ret->dot_no_count = snewn(num_dots, char);
    memcpy(ret->dot_no_count, sstate->dot_no_count, num_dots);

    ret->face_yes_count = snewn(num_faces, char);
    memcpy(ret->face_yes_count, sstate->face_yes_count, num_faces);
    ret->face_no_count = snewn(num_faces, char);
    memcpy(ret->face_no_count, sstate->face_no_count, num_faces);

    if (sstate->dlines) {
        ret->dlines = snewn(2*num_edges, char);
        memcpy(ret->dlines, sstate->dlines,
               2*num_edges);
    } else {
        ret->dlines = NULL;
    }

    if (sstate->linedsf) {
        ret->linedsf = snewn(num_edges, int);
        memcpy(ret->linedsf, sstate->linedsf,
               num_edges * sizeof(int));
    } else {
        ret->linedsf = NULL;
    }

    return ret;
}

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

#ifdef SLOW_SYSTEM
    ret->h = 7;
    ret->w = 7;
#else
    ret->h = 10;
    ret->w = 10;
#endif
    ret->diff = DIFF_EASY;
    ret->type = 0;

    return ret;
}

static game_params *dup_params(const game_params *params)
{
    game_params *ret = snew(game_params);

    *ret = *params;                       /* structure copy */
    return ret;
}

static const game_params loopy_presets_top[] = {
#ifdef SMALL_SCREEN
    {  7,  7, DIFF_EASY,   LOOPY_GRID_SQUARE },
    {  7,  7, DIFF_NORMAL, LOOPY_GRID_SQUARE },
    {  7,  7, DIFF_HARD,   LOOPY_GRID_SQUARE },
    {  7,  7, DIFF_HARD,   LOOPY_GRID_TRIANGULAR },
    {  5,  5, DIFF_HARD,   LOOPY_GRID_SNUBSQUARE },
    {  7,  7, DIFF_HARD,   LOOPY_GRID_CAIRO },
    {  5,  5, DIFF_HARD,   LOOPY_GRID_KITE },
    {  6,  6, DIFF_HARD,   LOOPY_GRID_PENROSE_P2 },
    {  6,  6, DIFF_HARD,   LOOPY_GRID_PENROSE_P3 },
#else
    {  7,  7, DIFF_EASY,   LOOPY_GRID_SQUARE },
    { 10, 10, DIFF_EASY,   LOOPY_GRID_SQUARE },
    {  7,  7, DIFF_NORMAL, LOOPY_GRID_SQUARE },
    { 10, 10, DIFF_NORMAL, LOOPY_GRID_SQUARE },
    {  7,  7, DIFF_HARD,   LOOPY_GRID_SQUARE },
    { 10, 10, DIFF_HARD,   LOOPY_GRID_SQUARE },
    { 12, 10, DIFF_HARD,   LOOPY_GRID_TRIANGULAR },
    {  7,  7, DIFF_HARD,   LOOPY_GRID_SNUBSQUARE },
    {  9,  9, DIFF_HARD,   LOOPY_GRID_CAIRO },
    {  5,  5, DIFF_HARD,   LOOPY_GRID_KITE },
    { 10, 10, DIFF_HARD,   LOOPY_GRID_PENROSE_P2 },
    { 10, 10, DIFF_HARD,   LOOPY_GRID_PENROSE_P3 },
#endif
};

static const game_params loopy_presets_more[] = {
#ifdef SMALL_SCREEN
    {  7,  7, DIFF_HARD,   LOOPY_GRID_HONEYCOMB },
    {  5,  4, DIFF_HARD,   LOOPY_GRID_GREATHEXAGONAL },
    {  5,  4, DIFF_HARD,   LOOPY_GRID_KAGOME },
    {  5,  5, DIFF_HARD,   LOOPY_GRID_OCTAGONAL },
    {  3,  3, DIFF_HARD,   LOOPY_GRID_FLORET },
    {  3,  3, DIFF_HARD,   LOOPY_GRID_DODECAGONAL },
    {  3,  3, DIFF_HARD,   LOOPY_GRID_GREATDODECAGONAL },
    {  3,  2, DIFF_HARD,   LOOPY_GRID_GREATGREATDODECAGONAL },
#else
    { 10, 10, DIFF_HARD,   LOOPY_GRID_HONEYCOMB },
    {  5,  4, DIFF_HARD,   LOOPY_GRID_GREATHEXAGONAL },
    {  5,  4, DIFF_HARD,   LOOPY_GRID_KAGOME },
    {  7,  7, DIFF_HARD,   LOOPY_GRID_OCTAGONAL },
    {  5,  5, DIFF_HARD,   LOOPY_GRID_FLORET },
    {  5,  4, DIFF_HARD,   LOOPY_GRID_DODECAGONAL },
    {  5,  4, DIFF_HARD,   LOOPY_GRID_GREATDODECAGONAL },
    {  5,  3, DIFF_HARD,   LOOPY_GRID_GREATGREATDODECAGONAL },
#endif
};

static void preset_menu_add_preset_with_title(struct preset_menu *menu,
                                              const game_params *params)
{
    char buf[80];
    game_params *dup_params;

    sprintf(buf, "%dx%d %s - %s", params->h, params->w,
            gridnames[params->type], diffnames[params->diff]);

    dup_params = snew(game_params);
    *dup_params = *params;

    preset_menu_add_preset(menu, dupstr(buf), dup_params);
}

static struct preset_menu *game_preset_menu(void)
{
    struct preset_menu *top, *more;
    int i;

    top = preset_menu_new();
    for (i = 0; i < lenof(loopy_presets_top); i++)
        preset_menu_add_preset_with_title(top, &loopy_presets_top[i]);

    more = preset_menu_add_submenu(top, dupstr("More..."));
    for (i = 0; i < lenof(loopy_presets_more); i++)
        preset_menu_add_preset_with_title(more, &loopy_presets_more[i]);

    return top;
}

static void free_params(game_params *params)
{
    sfree(params);
}

static void decode_params(game_params *params, char const *string)
{
    params->h = params->w = atoi(string);
    params->diff = DIFF_EASY;
    while (*string && isdigit((unsigned char)*string)) string++;
    if (*string == 'x') {
        string++;
        params->h = atoi(string);
        while (*string && isdigit((unsigned char)*string)) string++;
    }
    if (*string == 't') {
        string++;
        params->type = atoi(string);
        while (*string && isdigit((unsigned char)*string)) string++;
    }
    if (*string == 'd') {
        int i;
        string++;
        for (i = 0; i < DIFF_MAX; i++)
            if (*string == diffchars[i])
                params->diff = i;
        if (*string) string++;
    }
}

static char *encode_params(const game_params *params, int full)
{
    char str[80];
    sprintf(str, "%dx%dt%d", params->w, params->h, params->type);
    if (full)
        sprintf(str + strlen(str), "d%c", diffchars[params->diff]);
    return dupstr(str);
}

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

    ret = snewn(5, config_item);

    ret[0].name = "Width";
    ret[0].type = C_STRING;
    sprintf(buf, "%d", params->w);
    ret[0].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 = "Grid type";
    ret[2].type = C_CHOICES;
    ret[2].u.choices.choicenames = GRID_CONFIGS;
    ret[2].u.choices.selected = params->type;

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

    ret[4].name = NULL;
    ret[4].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->type = cfg[2].u.choices.selected;
    ret->diff = cfg[3].u.choices.selected;

    return ret;
}

static const char *validate_params(const game_params *params, int full)
{
    if (params->type < 0 || params->type >= NUM_GRID_TYPES)
        return "Illegal grid type";
    if (params->w < grid_size_limits[params->type].amin ||
	params->h < grid_size_limits[params->type].amin)
        return grid_size_limits[params->type].aerr;
    if (params->w < grid_size_limits[params->type].omin &&
	params->h < grid_size_limits[params->type].omin)
        return grid_size_limits[params->type].oerr;

    /*
     * This shouldn't be able to happen at all, since decode_params
     * and custom_params will never generate anything that isn't
     * within range.
     */
    assert(params->diff < DIFF_MAX);

    return NULL;
}

/* Returns a newly allocated string describing the current puzzle */
static char *state_to_text(const game_state *state)
{
    grid *g = state->game_grid;
    char *retval;
    int num_faces = g->num_faces;
    char *description = snewn(num_faces + 1, char);
    char *dp = description;
    int empty_count = 0;
    int i;

    for (i = 0; i < num_faces; i++) {
        if (state->clues[i] < 0) {
            if (empty_count > 25) {
                dp += sprintf(dp, "%c", (int)(empty_count + 'a' - 1));
                empty_count = 0;
            }
            empty_count++;
        } else {
            if (empty_count) {
                dp += sprintf(dp, "%c", (int)(empty_count + 'a' - 1));
                empty_count = 0;
            }
            dp += sprintf(dp, "%c", (int)CLUE2CHAR(state->clues[i]));
        }
    }

    if (empty_count)
        dp += sprintf(dp, "%c", (int)(empty_count + 'a' - 1));

    retval = dupstr(description);
    sfree(description);

    return retval;
}

#define GRID_DESC_SEP '_'

/* Splits up a (optional) grid_desc from the game desc. Returns the
 * grid_desc (which needs freeing) and updates the desc pointer to
 * start of real desc, or returns NULL if no desc. */
static char *extract_grid_desc(const char **desc)
{
    char *sep = strchr(*desc, GRID_DESC_SEP), *gd;
    int gd_len;

    if (!sep) return NULL;

    gd_len = sep - (*desc);
    gd = snewn(gd_len+1, char);
    memcpy(gd, *desc, gd_len);
    gd[gd_len] = '\0';

    *desc = sep+1;

    return gd;
}

/* We require that the params pass the test in validate_params and that the
 * description fills the entire game area */
static const char *validate_desc(const game_params *params, const char *desc)
{
    int count = 0;
    grid *g;
    char *grid_desc;
    const char *ret;

    /* It's pretty inefficient to do this just for validation. All we need to
     * know is the precise number of faces. */
    grid_desc = extract_grid_desc(&desc);
    ret = grid_validate_desc(grid_types[params->type], params->w, params->h, grid_desc);
    if (ret) return ret;

    g = loopy_generate_grid(params, grid_desc);
    if (grid_desc) sfree(grid_desc);

    for (; *desc; ++desc) {
        if ((*desc >= '0' && *desc <= '9') || (*desc >= 'A' && *desc <= 'Z')) {
            count++;
            continue;
        }
        if (*desc >= 'a') {
            count += *desc - 'a' + 1;
            continue;
        }
        return "Unknown character in description";
    }

    if (count < g->num_faces)
        return "Description too short for board size";
    if (count > g->num_faces)
        return "Description too long for board size";

    grid_free(g);

    return NULL;
}

/* Sums the lengths of the numbers in range [0,n) */
/* See equivalent function in solo.c for justification of this. */
static int len_0_to_n(int n)
{
    int len = 1; /* Counting 0 as a bit of a special case */
    int i;

    for (i = 1; i < n; i *= 10) {
        len += max(n - i, 0);
    }

    return len;
}

static char *encode_solve_move(const game_state *state)
{
    int len;
    char *ret, *p;
    int i;
    int num_edges = state->game_grid->num_edges;

    /* This is going to return a string representing the moves needed to set
     * every line in a grid to be the same as the ones in 'state'.  The exact
     * length of this string is predictable. */

    len = 1;  /* Count the 'S' prefix */
    /* Numbers in all lines */
    len += len_0_to_n(num_edges);
    /* For each line we also have a letter */
    len += num_edges;

    ret = snewn(len + 1, char);
    p = ret;

    p += sprintf(p, "S");

    for (i = 0; i < num_edges; i++) {
        switch (state->lines[i]) {
	  case LINE_YES:
	    p += sprintf(p, "%dy", i);
	    break;
	  case LINE_NO:
	    p += sprintf(p, "%dn", i);
	    break;
        }
    }

    /* No point in doing sums like that if they're going to be wrong */
    assert(strlen(ret) <= (size_t)len);
    return ret;
}

static game_ui *new_ui(const game_state *state)
{
    return NULL;
}

static void free_ui(game_ui *ui)
{
}

static char *encode_ui(const game_ui *ui)
{
    return NULL;
}

static void decode_ui(game_ui *ui, const char *encoding)
{
}

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

static void game_compute_size(const game_params *params, int tilesize,
                              int *x, int *y)
{
    int grid_width, grid_height, rendered_width, rendered_height;
    int g_tilesize;

    grid_compute_size(grid_types[params->type], params->w, params->h,
                      &g_tilesize, &grid_width, &grid_height);

    /* multiply first to minimise rounding error on integer division */
    rendered_width = grid_width * tilesize / g_tilesize;
    rendered_height = grid_height * tilesize / g_tilesize;
    *x = rendered_width + 2 * BORDER(tilesize) + 1;
    *y = rendered_height + 2 * BORDER(tilesize) + 1;
}

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_FOREGROUND * 3 + 0] = 0.0F;
    ret[COL_FOREGROUND * 3 + 1] = 0.0F;
    ret[COL_FOREGROUND * 3 + 2] = 0.0F;

    /*
     * We want COL_LINEUNKNOWN to be a yellow which is a bit darker
     * than the background. (I previously set it to 0.8,0.8,0, but
     * found that this went badly with the 0.8,0.8,0.8 favoured as a
     * background by the Java frontend.)
     */
    ret[COL_LINEUNKNOWN * 3 + 0] = ret[COL_BACKGROUND * 3 + 0] * 0.9F;
    ret[COL_LINEUNKNOWN * 3 + 1] = ret[COL_BACKGROUND * 3 + 1] * 0.9F;
    ret[COL_LINEUNKNOWN * 3 + 2] = 0.0F;

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

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

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

    /* We want the faint lines to be a bit darker than the background.
     * Except if the background is pretty dark already; then it ought to be a
     * bit lighter.  Oy vey.
     */
    ret[COL_FAINT * 3 + 0] = ret[COL_BACKGROUND * 3 + 0] * 0.9F;
    ret[COL_FAINT * 3 + 1] = ret[COL_BACKGROUND * 3 + 1] * 0.9F;
    ret[COL_FAINT * 3 + 2] = ret[COL_BACKGROUND * 3 + 2] * 0.9F;

    *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 num_faces = state->game_grid->num_faces;
    int num_edges = state->game_grid->num_edges;
    int i;

    ds->tilesize = 0;
    ds->started = 0;
    ds->lines = snewn(num_edges, char);
    ds->clue_error = snewn(num_faces, char);
    ds->clue_satisfied = snewn(num_faces, char);
    ds->textx = snewn(num_faces, int);
    ds->texty = snewn(num_faces, int);
    ds->flashing = 0;

    memset(ds->lines, LINE_UNKNOWN, num_edges);
    memset(ds->clue_error, 0, num_faces);
    memset(ds->clue_satisfied, 0, num_faces);
    for (i = 0; i < num_faces; i++)
        ds->textx[i] = ds->texty[i] = -1;

    return ds;
}

static void game_free_drawstate(drawing *dr, game_drawstate *ds)
{
    sfree(ds->textx);
    sfree(ds->texty);
    sfree(ds->clue_error);
    sfree(ds->clue_satisfied);
    sfree(ds->lines);
    sfree(ds);
}

static int game_timing_state(const game_state *state, game_ui *ui)
{
    return TRUE;
}

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

static int game_can_format_as_text_now(const game_params *params)
{
    if (params->type != 0)
        return FALSE;
    return TRUE;
}

static char *game_text_format(const game_state *state)
{
    int w, h, W, H;
    int x, y, i;
    int cell_size;
    char *ret;
    grid *g = state->game_grid;
    grid_face *f;

    assert(state->grid_type == 0);

    /* Work out the basic size unit */
    f = g->faces; /* first face */
    assert(f->order == 4);
    /* The dots are ordered clockwise, so the two opposite
     * corners are guaranteed to span the square */
    cell_size = abs(f->dots[0]->x - f->dots[2]->x);

    w = (g->highest_x - g->lowest_x) / cell_size;
    h = (g->highest_y - g->lowest_y) / cell_size;

    /* Create a blank "canvas" to "draw" on */
    W = 2 * w + 2;
    H = 2 * h + 1;
    ret = snewn(W * H + 1, char);
    for (y = 0; y < H; y++) {
        for (x = 0; x < W-1; x++) {
            ret[y*W + x] = ' ';
        }
        ret[y*W + W-1] = '\n';
    }
    ret[H*W] = '\0';

    /* Fill in edge info */
    for (i = 0; i < g->num_edges; i++) {
        grid_edge *e = g->edges + i;
        /* Cell coordinates, from (0,0) to (w-1,h-1) */
        int x1 = (e->dot1->x - g->lowest_x) / cell_size;
        int x2 = (e->dot2->x - g->lowest_x) / cell_size;
        int y1 = (e->dot1->y - g->lowest_y) / cell_size;
        int y2 = (e->dot2->y - g->lowest_y) / cell_size;
        /* Midpoint, in canvas coordinates (canvas coordinates are just twice
         * cell coordinates) */
        x = x1 + x2;
        y = y1 + y2;
        switch (state->lines[i]) {
	  case LINE_YES:
	    ret[y*W + x] = (y1 == y2) ? '-' : '|';
	    break;
	  case LINE_NO:
	    ret[y*W + x] = 'x';
	    break;
	  case LINE_UNKNOWN:
	    break; /* already a space */
	  default:
	    assert(!"Illegal line state");
        }
    }

    /* Fill in clues */
    for (i = 0; i < g->num_faces; i++) {
	int x1, x2, y1, y2;

        f = g->faces + i;
        assert(f->order == 4);
        /* Cell coordinates, from (0,0) to (w-1,h-1) */
	x1 = (f->dots[0]->x - g->lowest_x) / cell_size;
	x2 = (f->dots[2]->x - g->lowest_x) / cell_size;
	y1 = (f->dots[0]->y - g->lowest_y) / cell_size;
	y2 = (f->dots[2]->y - g->lowest_y) / cell_size;
        /* Midpoint, in canvas coordinates */
        x = x1 + x2;
        y = y1 + y2;
        ret[y*W + x] = CLUE2CHAR(state->clues[i]);
    }
    return ret;
}

/* ----------------------------------------------------------------------
 * Debug code
 */

#ifdef DEBUG_CACHES
static void check_caches(const solver_state* sstate)
{
    int i;
    const game_state *state = sstate->state;
    const grid *g = state->game_grid;

    for (i = 0; i < g->num_dots; i++) {
        assert(dot_order(state, i, LINE_YES) == sstate->dot_yes_count[i]);
        assert(dot_order(state, i, LINE_NO) == sstate->dot_no_count[i]);
    }

    for (i = 0; i < g->num_faces; i++) {
        assert(face_order(state, i, LINE_YES) == sstate->face_yes_count[i]);
        assert(face_order(state, i, LINE_NO) == sstate->face_no_count[i]);
    }
}

#if 0
#define check_caches(s) \
    do { \
        fprintf(stderr, "check_caches at line %d\n", __LINE__); \
        check_caches(s); \
    } while (0)
#endif
#endif /* DEBUG_CACHES */

/* ----------------------------------------------------------------------
 * Solver utility functions
 */

/* Sets the line (with index i) to the new state 'line_new', and updates
 * the cached counts of any affected faces and dots.
 * Returns TRUE if this actually changed the line's state. */
static int solver_set_line(solver_state *sstate, int i,
                           enum line_state line_new
#ifdef SHOW_WORKING
			   , const char *reason
#endif
			   )
{
    game_state *state = sstate->state;
    grid *g;
    grid_edge *e;

    assert(line_new != LINE_UNKNOWN);

    check_caches(sstate);

    if (state->lines[i] == line_new) {
        return FALSE; /* nothing changed */
    }
    state->lines[i] = line_new;

#ifdef SHOW_WORKING
    fprintf(stderr, "solver: set line [%d] to %s (%s)\n",
            i, line_new == LINE_YES ? "YES" : "NO",
            reason);
#endif

    g = state->game_grid;
    e = g->edges + i;

    /* Update the cache for both dots and both faces affected by this. */
    if (line_new == LINE_YES) {
        sstate->dot_yes_count[e->dot1 - g->dots]++;
        sstate->dot_yes_count[e->dot2 - g->dots]++;
        if (e->face1) {
            sstate->face_yes_count[e->face1 - g->faces]++;
        }
        if (e->face2) {
            sstate->face_yes_count[e->face2 - g->faces]++;
        }
    } else {
        sstate->dot_no_count[e->dot1 - g->dots]++;
        sstate->dot_no_count[e->dot2 - g->dots]++;
        if (e->face1) {
            sstate->face_no_count[e->face1 - g->faces]++;
        }
        if (e->face2) {
            sstate->face_no_count[e->face2 - g->faces]++;
        }
    }

    check_caches(sstate);
    return TRUE;
}

#ifdef SHOW_WORKING
#define solver_set_line(a, b, c) \
    solver_set_line(a, b, c, __FUNCTION__)
#endif

/*
 * Merge two dots due to the existence of an edge between them.
 * Updates the dsf tracking equivalence classes, and keeps track of
 * the length of path each dot is currently a part of.
 * Returns TRUE if the dots were already linked, ie if they are part of a
 * closed loop, and false otherwise.
 */
static int merge_dots(solver_state *sstate, int edge_index)
{
    int i, j, len;
    grid *g = sstate->state->game_grid;
    grid_edge *e = g->edges + edge_index;

    i = e->dot1 - g->dots;
    j = e->dot2 - g->dots;

    i = dsf_canonify(sstate->dotdsf, i);
    j = dsf_canonify(sstate->dotdsf, j);

    if (i == j) {
        return TRUE;
    } else {
        len = sstate->looplen[i] + sstate->looplen[j];
        dsf_merge(sstate->dotdsf, i, j);
        i = dsf_canonify(sstate->dotdsf, i);
        sstate->looplen[i] = len;
        return FALSE;
    }
}

/* Merge two lines because the solver has deduced that they must be either
 * identical or opposite.   Returns TRUE if this is new information, otherwise
 * FALSE. */
static int merge_lines(solver_state *sstate, int i, int j, int inverse
#ifdef SHOW_WORKING
                       , const char *reason
#endif
		       )
{
    int inv_tmp;

    assert(i < sstate->state->game_grid->num_edges);
    assert(j < sstate->state->game_grid->num_edges);

    i = edsf_canonify(sstate->linedsf, i, &inv_tmp);
    inverse ^= inv_tmp;
    j = edsf_canonify(sstate->linedsf, j, &inv_tmp);
    inverse ^= inv_tmp;

    edsf_merge(sstate->linedsf, i, j, inverse);

#ifdef SHOW_WORKING
    if (i != j) {
        fprintf(stderr, "%s [%d] [%d] %s(%s)\n",
                __FUNCTION__, i, j,
                inverse ? "inverse " : "", reason);
    }
#endif
    return (i != j);
}

#ifdef SHOW_WORKING
#define merge_lines(a, b, c, d) \
    merge_lines(a, b, c, d, __FUNCTION__)
#endif

/* Count the number of lines of a particular type currently going into the
 * given dot. */
static int dot_order(const game_state* state, int dot, char line_type)
{
    int n = 0;
    grid *g = state->game_grid;
    grid_dot *d = g->dots + dot;
    int i;

    for (i = 0; i < d->order; i++) {
        grid_edge *e = d->edges[i];
        if (state->lines[e - g->edges] == line_type)
            ++n;
    }
    return n;
}

/* Count the number of lines of a particular type currently surrounding the
 * given face */
static int face_order(const game_state* state, int face, char line_type)
{
    int n = 0;
    grid *g = state->game_grid;
    grid_face *f = g->faces + face;
    int i;

    for (i = 0; i < f->order; i++) {
        grid_edge *e = f->edges[i];
        if (state->lines[e - g->edges] == line_type)
            ++n;
    }
    return n;
}

/* Set all lines bordering a dot of type old_type to type new_type
 * Return value tells caller whether this function actually did anything */
static int dot_setall(solver_state *sstate, int dot,
		      char old_type, char new_type)
{
    int retval = FALSE, r;
    game_state *state = sstate->state;
    grid *g;
    grid_dot *d;
    int i;

    if (old_type == new_type)
        return FALSE;

    g = state->game_grid;
    d = g->dots + dot;

    for (i = 0; i < d->order; i++) {
        int line_index = d->edges[i] - g->edges;
        if (state->lines[line_index] == old_type) {
            r = solver_set_line(sstate, line_index, new_type);
            assert(r == TRUE);
            retval = TRUE;
        }
    }
    return retval;
}

/* Set all lines bordering a face of type old_type to type new_type */
static int face_setall(solver_state *sstate, int face,
                       char old_type, char new_type)
{
    int retval = FALSE, r;
    game_state *state = sstate->state;
    grid *g;
    grid_face *f;
    int i;

    if (old_type == new_type)
        return FALSE;

    g = state->game_grid;
    f = g->faces + face;

    for (i = 0; i < f->order; i++) {
        int line_index = f->edges[i] - g->edges;
        if (state->lines[line_index] == old_type) {
            r = solver_set_line(sstate, line_index, new_type);
            assert(r == TRUE);
            retval = TRUE;
        }
    }
    return retval;
}

/* ----------------------------------------------------------------------
 * Loop generation and clue removal
 */

static void add_full_clues(game_state *state, random_state *rs)
{
    signed char *clues = state->clues;
    grid *g = state->game_grid;
    char *board = snewn(g->num_faces, char);
    int i;

    generate_loop(g, board, rs, NULL, NULL);

    /* Fill out all the clues by initialising to 0, then iterating over
     * all edges and incrementing each clue as we find edges that border
     * between BLACK/WHITE faces.  While we're at it, we verify that the
     * algorithm does work, and there aren't any GREY faces still there. */
    memset(clues, 0, g->num_faces);
    for (i = 0; i < g->num_edges; i++) {
        grid_edge *e = g->edges + i;
        grid_face *f1 = e->face1;
        grid_face *f2 = e->face2;
        enum face_colour c1 = FACE_COLOUR(f1);
        enum face_colour c2 = FACE_COLOUR(f2);
        assert(c1 != FACE_GREY);
        assert(c2 != FACE_GREY);
        if (c1 != c2) {
            if (f1) clues[f1 - g->faces]++;
            if (f2) clues[f2 - g->faces]++;
        }
    }
    sfree(board);
}


static int game_has_unique_soln(const game_state *state, int diff)
{
    int ret;
    solver_state *sstate_new;
    solver_state *sstate = new_solver_state((game_state *)state, diff);

    sstate_new = solve_game_rec(sstate);

    assert(sstate_new->solver_status != SOLVER_MISTAKE);
    ret = (sstate_new->solver_status == SOLVER_SOLVED);

    free_solver_state(sstate_new);
    free_solver_state(sstate);

    return ret;
}


/* Remove clues one at a time at random. */
static game_state *remove_clues(game_state *state, random_state *rs,
                                int diff)
{
    int *face_list;
    int num_faces = state->game_grid->num_faces;
    game_state *ret = dup_game(state), *saved_ret;
    int n;

    /* We need to remove some clues.  We'll do this by forming a list of all
     * available clues, shuffling it, then going along one at a
     * time clearing each clue in turn for which doing so doesn't render the
     * board unsolvable. */
    face_list = snewn(num_faces, int);
    for (n = 0; n < num_faces; ++n) {
        face_list[n] = n;
    }

    shuffle(face_list, num_faces, sizeof(int), rs);

    for (n = 0; n < num_faces; ++n) {
        saved_ret = dup_game(ret);
        ret->clues[face_list[n]] = -1;

        if (game_has_unique_soln(ret, diff)) {
            free_game(saved_ret);
        } else {
            free_game(ret);
            ret = saved_ret;
        }
    }
    sfree(face_list);

    return ret;
}


static char *new_game_desc(const game_params *params, random_state *rs,
                           char **aux, int interactive)
{
    /* solution and description both use run-length encoding in obvious ways */
    char *retval, *game_desc, *grid_desc;
    grid *g;
    game_state *state = snew(game_state);
    game_state *state_new;

    grid_desc = grid_new_desc(grid_types[params->type], params->w, params->h, rs);
    state->game_grid = g = loopy_generate_grid(params, grid_desc);

    state->clues = snewn(g->num_faces, signed char);
    state->lines = snewn(g->num_edges, char);
    state->line_errors = snewn(g->num_edges, unsigned char);
    state->exactly_one_loop = FALSE;

    state->grid_type = params->type;

    newboard_please:

    memset(state->lines, LINE_UNKNOWN, g->num_edges);
    memset(state->line_errors, 0, g->num_edges);

    state->solved = state->cheated = FALSE;

    /* Get a new random solvable board with all its clues filled in.  Yes, this
     * can loop for ever if the params are suitably unfavourable, but
     * preventing games smaller than 4x4 seems to stop this happening */
    do {
        add_full_clues(state, rs);
    } while (!game_has_unique_soln(state, params->diff));

    state_new = remove_clues(state, rs, params->diff);
    free_game(state);
    state = state_new;


    if (params->diff > 0 && game_has_unique_soln(state, params->diff-1)) {
#ifdef SHOW_WORKING
        fprintf(stderr, "Rejecting board, it is too easy\n");
#endif
        goto newboard_please;
    }

    game_desc = state_to_text(state);

    free_game(state);

    if (grid_desc) {
        retval = snewn(strlen(grid_desc) + 1 + strlen(game_desc) + 1, char);
        sprintf(retval, "%s%c%s", grid_desc, (int)GRID_DESC_SEP, game_desc);
        sfree(grid_desc);
        sfree(game_desc);
    } else {
        retval = game_desc;
    }

    assert(!validate_desc(params, retval));

    return retval;
}

static game_state *new_game(midend *me, const game_params *params,
                            const char *desc)
{
    int i;
    game_state *state = snew(game_state);
    int empties_to_make = 0;
    int n,n2;
    const char *dp;
    char *grid_desc;
    grid *g;
    int num_faces, num_edges;

    grid_desc = extract_grid_desc(&desc);
    state->game_grid = g = loopy_generate_grid(params, grid_desc);
    if (grid_desc) sfree(grid_desc);

    dp = desc;

    num_faces = g->num_faces;
    num_edges = g->num_edges;

    state->clues = snewn(num_faces, signed char);
    state->lines = snewn(num_edges, char);
    state->line_errors = snewn(num_edges, unsigned char);
    state->exactly_one_loop = FALSE;

    state->solved = state->cheated = FALSE;

    state->grid_type = params->type;

    for (i = 0; i < num_faces; i++) {
        if (empties_to_make) {
            empties_to_make--;
            state->clues[i] = -1;
            continue;
        }

        assert(*dp);
        n = *dp - '0';
        n2 = *dp - 'A' + 10;
        if (n >= 0 && n < 10) {
            state->clues[i] = n;
	} else if (n2 >= 10 && n2 < 36) {
            state->clues[i] = n2;
        } else {
            n = *dp - 'a' + 1;
            assert(n > 0);
            state->clues[i] = -1;
            empties_to_make = n - 1;
        }
        ++dp;
    }

    memset(state->lines, LINE_UNKNOWN, num_edges);
    memset(state->line_errors, 0, num_edges);
    return state;
}

/* Calculates the line_errors data, and checks if the current state is a
 * solution */
static int check_completion(game_state *state)