+static void free_ui(game_ui *ui)
+{
+}
+
+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;
+ int grid_width, grid_height, rendered_width, rendered_height;
+
+ params_generate_grid(params);
+ g = params->game_grid;
+ grid_width = g->highest_x - g->lowest_x;
+ grid_height = g->highest_y - g->lowest_y;
+ /* 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,
+ 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;
+
+ /* 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, 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++) {
+ 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
+ */
+
+/* We're going to store lists of current candidate faces for colouring black
+ * or white.
+ * Each face gets a 'score', which tells us how adding that face right
+ * now would affect the curliness of the solution loop. We're trying to
+ * maximise that quantity so will bias our random selection of faces to
+ * colour those with high scores */
+struct face_score {
+ int white_score;
+ int black_score;
+ unsigned long random;
+ /* No need to store a grid_face* here. The 'face_scores' array will
+ * be a list of 'face_score' objects, one for each face of the grid, so
+ * the position (index) within the 'face_scores' array will determine
+ * which face corresponds to a particular face_score.
+ * Having a single 'face_scores' array for all faces simplifies memory
+ * management, and probably improves performance, because we don't have to
+ * malloc/free each individual face_score, and we don't have to maintain
+ * a mapping from grid_face* pointers to face_score* pointers.
+ */
+};
+
+static int generic_sort_cmpfn(void *v1, void *v2, size_t offset)
+{
+ struct face_score *f1 = v1;
+ struct face_score *f2 = v2;
+ int r;
+
+ r = *(int *)((char *)f2 + offset) - *(int *)((char *)f1 + offset);
+ 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 face_scores list.
+ * This introduces a tiny directional bias, but not a significant one.
+ */
+ return f1 - f2;
+}
+
+static int white_sort_cmpfn(void *v1, void *v2)
+{
+ return generic_sort_cmpfn(v1, v2, offsetof(struct face_score,white_score));
+}
+
+static int black_sort_cmpfn(void *v1, void *v2)
+{
+ return generic_sort_cmpfn(v1, v2, offsetof(struct face_score,black_score));
+}
+
+enum face_colour { FACE_WHITE, FACE_GREY, FACE_BLACK };
+
+/* face should be of type grid_face* here. */
+#define FACE_COLOUR(face) \
+ ( (face) == NULL ? FACE_BLACK : \
+ board[(face) - g->faces] )
+
+/* 'board' is an array of these enums, indicating which faces are
+ * currently black/white/grey. 'colour' is FACE_WHITE or FACE_BLACK.
+ * Returns whether it's legal to colour the given face with this colour. */
+static int can_colour_face(grid *g, char* board, int face_index,
+ enum face_colour colour)
+{
+ int i, j;
+ grid_face *test_face = g->faces + face_index;
+ grid_face *starting_face, *current_face;
+ int transitions;
+ int current_state, s; /* booleans: equal or not-equal to 'colour' */
+ int found_same_coloured_neighbour = FALSE;
+ assert(board[face_index] != colour);
+
+ /* Can only consider a face for colouring if it's adjacent to a face
+ * with the same colour. */
+ 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_COLOUR(f) == colour) {
+ found_same_coloured_neighbour = TRUE;
+ break;
+ }
+ }
+ if (!found_same_coloured_neighbour)
+ return FALSE;
+
+ /* Need to avoid creating a loop of faces of this colour around some
+ * differently-coloured faces.
+ * Also need to avoid meeting a same-coloured face at a corner, with
+ * other-coloured 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 'colour'/not-'colour' 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 the middle of an "island" of this colour (should
+ * be impossible as we're not supposed to create black or white loops),
+ * or we're about to start a new island - also not allowed.
+ * If 4 or greater, there are too many separate coloured regions touching
+ * this face, and colouring it 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_COLOUR(current_face) == colour);
+
+ 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_COLOUR(current_face) == colour);
+ 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;
+}
+
+/* Count the number of neighbours of 'face', having colour 'colour' */
+static int face_num_neighbours(grid *g, char *board, grid_face *face,
+ enum face_colour colour)
+{
+ int colour_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_COLOUR(f) == colour)
+ ++colour_count;
+ }
+ return colour_count;
+}
+
+/* The 'score' of a face reflects its current desirability for selection
+ * as the next face to colour white or black. We want to encourage moving
+ * into grey areas and increasing loopiness, so we give scores according to
+ * how many of the face's neighbours are currently coloured the same as the
+ * proposed colour. */
+static int face_score(grid *g, char *board, grid_face *face,
+ enum face_colour colour)
+{
+ /* Simple formula: score = 0 - num. same-coloured neighbours,
+ * so a higher score means fewer same-coloured neighbours. */
+ return -face_num_neighbours(g, board, face, colour);
+}
+
+/* Generate a new complete set of clues for the given game_state.
+ * The method is to generate a WHITE/BLACK colouring of all the faces,
+ * such that the WHITE faces will define the inside of the path, and the
+ * BLACK faces define the outside.
+ * To do this, we initially colour all faces GREY. The infinite space outside
+ * the grid is coloured BLACK, and we choose a random face to colour WHITE.
+ * Then we gradually grow the BLACK and the WHITE regions, eliminating GREY
+ * faces, until the grid is filled with BLACK/WHITE. As we grow the regions,
+ * we avoid creating loops of a single colour, to preserve the topological
+ * shape of the WHITE and BLACK regions.
+ * We also try to make the boundary as loopy and twisty as possible, to avoid
+ * generating paths that are uninteresting.
+ * The algorithm works by choosing a BLACK/WHITE colour, then choosing a GREY
+ * face that can be coloured with that colour (without violating the
+ * topological shape of that region). It's not obvious, but I think this
+ * algorithm is guaranteed to terminate without leaving any GREY faces behind.
+ * Indeed, if there are any GREY faces at all, both the WHITE and BLACK
+ * regions can be grown.
+ * This is checked using assert()ions, and I haven't seen any failures yet.
+ *
+ * Hand-wavy proof: imagine what can go wrong...
+ *
+ * Could the white faces get completely cut off by the black faces, and still
+ * leave some grey faces remaining?
+ * No, because then the black faces would form a loop around both the white
+ * faces and the grey faces, which is disallowed because we continually
+ * maintain the correct topological shape of the black region.
+ * Similarly, the black faces can never get cut off by the white faces. That
+ * means both the WHITE and BLACK regions always have some room to grow into
+ * the GREY regions.
+ * Could it be that we can't colour some GREY face, because there are too many
+ * WHITE/BLACK transitions as we walk round the face? (see the
+ * can_colour_face() function for details)
+ * No. Imagine otherwise, and we see WHITE/BLACK/WHITE/BLACK as we walk
+ * around the face. The two WHITE faces would be connected by a WHITE path,
+ * and the BLACK faces would be connected by a BLACK path. These paths would
+ * have to cross, which is impossible.
+ * Another thing that could go wrong: perhaps we can't find any GREY face to
+ * colour WHITE, because it would create a loop-violation or a corner-violation
+ * with the other WHITE faces?
+ * This is a little bit tricky to prove impossible. Imagine you have such a
+ * GREY face (that is, if you coloured it WHITE, you would create a WHITE loop
+ * or corner violation).
+ * That would cut all the non-white area into two blobs. One of those blobs
+ * must be free of BLACK faces (because the BLACK stuff is a connected blob).
+ * So we have a connected GREY area, completely surrounded by WHITE
+ * (including the GREY face we've tentatively coloured WHITE).
+ * A well-known result in graph theory says that you can always find a GREY
+ * face whose removal leaves the remaining GREY area connected. And it says
+ * there are at least two such faces, so we can always choose the one that
+ * isn't the "tentative" GREY face. Colouring that face WHITE leaves
+ * everything nice and connected, including that "tentative" GREY face which
+ * acts as a gateway to the rest of the non-WHITE grid.
+ */
+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;
+ int num_faces = g->num_faces;
+ struct face_score *face_scores; /* Array of face_score objects */
+ struct face_score *fs; /* Points somewhere in the above list */
+ struct grid_face *cur_face;
+ tree234 *lightable_faces_sorted;
+ tree234 *darkable_faces_sorted;
+ int *face_list;
+ int do_random_pass;
+
+ board = snewn(num_faces, char);
+
+ /* Make a board */
+ memset(board, FACE_GREY, num_faces);
+
+ /* Create and initialise the list of face_scores */
+ face_scores = snewn(num_faces, struct face_score);
+ for (i = 0; i < num_faces; i++) {
+ face_scores[i].random = random_bits(rs, 31);
+ face_scores[i].black_score = face_scores[i].white_score = 0;
+ }
+
+ /* Colour a random, finite face white. The infinite face is implicitly
+ * coloured black. Together, they will seed the random growth process
+ * for the black and white areas. */
+ i = random_upto(rs, num_faces);
+ board[i] = FACE_WHITE;
+
+ /* 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
+ * need the sort order _within_ each group of scores to be completely
+ * random. But it would be abusing the hospitality of the tree234 data