+static char *encode_ui(game_ui *ui)
+{
+ return NULL;
+}
+
+static void decode_ui(game_ui *ui, char *encoding)
+{
+}
+
+static void game_changed_state(game_ui *ui, game_state *oldstate,
+ game_state *newstate)
+{
+}
+
+static void game_compute_size(game_params *params, int tilesize,
+ int *x, int *y)
+{
+ grid *g;
+ params_generate_grid(params);
+ g = params->game_grid;
+ int grid_width = g->highest_x - g->lowest_x;
+ int grid_height = g->highest_y - g->lowest_y;
+ /* multiply first to minimise rounding error on integer division */
+ int rendered_width = grid_width * tilesize / g->tilesize;
+ int 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,
+ game_params *params, int tilesize)
+{
+ ds->tilesize = tilesize;
+}
+
+static float *game_colours(frontend *fe, int *ncolours)
+{
+ float *ret = snewn(4 * 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;
+
+ ret[COL_LINEUNKNOWN * 3 + 0] = 0.8F;
+ ret[COL_LINEUNKNOWN * 3 + 1] = 0.8F;
+ 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;
+
+ *ncolours = NCOLOURS;
+ return ret;
+}
+
+static game_drawstate *game_new_drawstate(drawing *dr, 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;
+
+ 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->flashing = 0;
+
+ memset(ds->lines, LINE_UNKNOWN, num_edges);
+ memset(ds->clue_error, 0, num_faces);
+ memset(ds->clue_satisfied, 0, num_faces);
+
+ return ds;
+}
+
+static void game_free_drawstate(drawing *dr, game_drawstate *ds)
+{
+ sfree(ds->clue_error);
+ sfree(ds->clue_satisfied);
+ sfree(ds->lines);
+ sfree(ds);
+}
+
+static int game_timing_state(game_state *state, game_ui *ui)
+{
+ return TRUE;
+}
+
+static float game_anim_length(game_state *oldstate, game_state *newstate,
+ int dir, game_ui *ui)
+{
+ return 0.0F;
+}
+
+static int game_can_format_as_text_now(game_params *params)
+{
+ if (params->type != 0)
+ return FALSE;
+ return TRUE;
+}
+
+static char *game_text_format(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++) {
+ f = g->faces + i;
+ assert(f->order == 4);
+ /* Cell coordinates, from (0,0) to (w-1,h-1) */
+ int x1 = (f->dots[0]->x - g->lowest_x) / cell_size;
+ int x2 = (f->dots[2]->x - g->lowest_x) / cell_size;
+ int y1 = (f->dots[0]->y - g->lowest_y) / cell_size;
+ int 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->hard->linedsf, i, &inv_tmp);
+ inverse ^= inv_tmp;
+ j = edsf_canonify(sstate->hard->linedsf, j, &inv_tmp);
+ inverse ^= inv_tmp;
+
+ edsf_merge(sstate->hard->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
+ */
+
+/* We're going to store a list of current candidate faces for lighting.
+ * Each face gets a 'score', which tells us how adding that face right
+ * now would affect the length of the solution loop. We're trying to
+ * maximise that quantity so will bias our random selection of faces to
+ * light towards those with high scores */
+struct face {
+ int score;
+ unsigned long random;
+ grid_face *f;
+};
+
+static int get_face_cmpfn(void *v1, void *v2)
+{
+ struct face *f1 = v1;
+ struct face *f2 = v2;
+ /* These grid_face pointers always point into the same list of
+ * 'grid_face's, so it's valid to subtract them. */
+ return f1->f - f2->f;
+}
+
+static int face_sort_cmpfn(void *v1, void *v2)
+{
+ struct face *f1 = v1;
+ struct face *f2 = v2;
+ int r;
+
+ r = f2->score - f1->score;
+ if (r) {
+ return r;
+ }
+
+ if (f1->random < f2->random)
+ return -1;
+ else if (f1->random > f2->random)
+ return 1;
+
+ /*
+ * It's _just_ possible that two faces might have been given
+ * the same random value. In that situation, fall back to
+ * comparing based on the positions within the grid's face-list.
+ * This introduces a tiny directional bias, but not a significant one.
+ */
+ return get_face_cmpfn(f1, f2);
+}
+
+enum { FACE_LIT, FACE_UNLIT };
+
+/* face should be of type grid_face* here. */
+#define FACE_LIT_STATE(face) \
+ ( (face) == NULL ? FACE_UNLIT : \
+ board[(face) - g->faces] )
+
+/* 'board' is an array of these enums, indicating which faces are
+ * currently lit. Returns whether it's legal to light up the
+ * given face. */
+static int can_light_face(grid *g, char* board, int face_index)
+{
+ int i, j;
+ grid_face *test_face = g->faces + face_index;
+ grid_face *starting_face, *current_face;
+ int transitions;
+ int current_state, s;
+ int found_lit_neighbour = FALSE;
+ assert(board[face_index] == FACE_UNLIT);
+
+ /* Can only consider a face for lighting if it's adjacent to an
+ * already lit face. */
+ for (i = 0; i < test_face->order; i++) {
+ grid_edge *e = test_face->edges[i];
+ grid_face *f = (e->face1 == test_face) ? e->face2 : e->face1;
+ if (FACE_LIT_STATE(f) == FACE_LIT) {
+ found_lit_neighbour = TRUE;
+ break;
+ }
+ }
+ if (!found_lit_neighbour)
+ return FALSE;
+
+ /* Need to avoid creating a loop of lit faces around some unlit faces.
+ * Also need to avoid meeting another lit face at a corner, with
+ * unlit faces in between. Here's a simple test that (I believe) takes
+ * care of both these conditions:
+ *
+ * Take the circular path formed by this face's edges, and inflate it
+ * slightly outwards. Imagine walking around this path and consider
+ * the faces that you visit in sequence. This will include all faces
+ * touching the given face, either along an edge or just at a corner.
+ * Count the number of LIT/UNLIT transitions you encounter, as you walk
+ * along the complete loop. This will obviously turn out to be an even
+ * number.
+ * If 0, we're either in a completely unlit zone, or this face is a hole
+ * in a completely lit zone. If the former, we would create a brand new
+ * island by lighting this face. And the latter ought to be impossible -
+ * it would mean there's already a lit loop, so something went wrong
+ * earlier.
+ * If 4 or greater, there are too many separate lit regions touching this
+ * face, and lighting it up would create a loop or a corner-violation.
+ * The only allowed case is when the count is exactly 2. */
+
+ /* i points to a dot around the test face.
+ * j points to a face around the i^th dot.
+ * The current face will always be:
+ * test_face->dots[i]->faces[j]
+ * We assume dots go clockwise around the test face,
+ * and faces go clockwise around dots. */
+ i = j = 0;
+ starting_face = test_face->dots[0]->faces[0];
+ if (starting_face == test_face) {
+ j = 1;
+ starting_face = test_face->dots[0]->faces[1];
+ }
+ current_face = starting_face;
+ transitions = 0;
+ current_state = FACE_LIT_STATE(current_face);
+
+ do {
+ /* Advance to next face.
+ * Need to loop here because it might take several goes to
+ * find it. */
+ while (TRUE) {
+ j++;
+ if (j == test_face->dots[i]->order)
+ j = 0;
+
+ if (test_face->dots[i]->faces[j] == test_face) {
+ /* Advance to next dot round test_face, then
+ * find current_face around new dot
+ * and advance to the next face clockwise */
+ i++;
+ if (i == test_face->order)
+ i = 0;
+ for (j = 0; j < test_face->dots[i]->order; j++) {
+ if (test_face->dots[i]->faces[j] == current_face)
+ break;
+ }
+ /* Must actually find current_face around new dot,
+ * or else something's wrong with the grid. */
+ assert(j != test_face->dots[i]->order);
+ /* Found, so advance to next face and try again */
+ } else {
+ break;
+ }
+ }
+ /* (i,j) are now advanced to next face */
+ current_face = test_face->dots[i]->faces[j];
+ s = FACE_LIT_STATE(current_face);
+ if (s != current_state) {
+ ++transitions;
+ current_state = s;
+ if (transitions > 2)
+ return FALSE; /* no point in continuing */
+ }
+ } while (current_face != starting_face);
+
+ return (transitions == 2) ? TRUE : FALSE;
+}
+
+/* The 'score' of a face reflects its current desirability for selection
+ * as the next face to light. We want to encourage moving into uncharted
+ * areas so we give scores according to how many of the face's neighbours
+ * are currently unlit. */
+static int face_score(grid *g, char *board, grid_face *face)
+{
+ /* Simple formula: score = neighbours unlit - neighbours lit */
+ int lit_count = 0, unlit_count = 0;
+ int i;
+ grid_face *f;
+ grid_edge *e;
+ for (i = 0; i < face->order; i++) {
+ e = face->edges[i];
+ f = (e->face1 == face) ? e->face2 : e->face1;
+ if (FACE_LIT_STATE(f) == FACE_LIT)
+ ++lit_count;
+ else
+ ++unlit_count;
+ }
+ return unlit_count - lit_count;
+}
+
+/* Generate a new complete set of clues for the given game_state. */
+static void add_full_clues(game_state *state, random_state *rs)
+{
+ signed char *clues = state->clues;
+ char *board;
+ grid *g = state->game_grid;
+ int i, j, c;
+ int num_faces = g->num_faces;
+ int first_time = TRUE;
+
+ struct face *face, *tmpface;
+ struct face face_pos;
+
+ /* These will contain exactly the same information, sorted into different
+ * orders */
+ tree234 *lightable_faces_sorted, *lightable_faces_gettable;
+
+#define IS_LIGHTING_CANDIDATE(i) \
+ (board[i] == FACE_UNLIT && \
+ can_light_face(g, board, i))
+
+ board = snewn(num_faces, char);
+
+ /* Make a board */
+ memset(board, FACE_UNLIT, num_faces);
+
+ /* We need a way of favouring faces that will increase our loopiness.
+ * We do this by maintaining a list of all candidate faces sorted by
+ * their score and choose randomly from that with appropriate skew.
+ * In order to avoid consistently biasing towards particular faces, we