+ 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
+ * structure if our comparison function were nondeterministic :-). So with
+ * each face we associate a random number that does not change during a
+ * particular run of the generator, and use that as a secondary sort key.
+ * Yes, this means we will be biased towards particular random faces in
+ * any one run but that doesn't actually matter. */
+
+ lightable_faces_sorted = newtree234(white_sort_cmpfn);
+ darkable_faces_sorted = newtree234(black_sort_cmpfn);
+
+ /* Initialise the lists of lightable and darkable faces. This is
+ * slightly different from the code inside the while-loop, because we need
+ * to check every face of the board (the grid structure does not keep a
+ * list of the infinite face's neighbours). */
+ for (i = 0; i < num_faces; i++) {
+ grid_face *f = g->faces + i;
+ struct face_score *fs = face_scores + i;
+ if (board[i] != FACE_GREY) continue;
+ /* We need the full colourability check here, it's not enough simply
+ * to check neighbourhood. On some grids, a neighbour of the infinite
+ * face is not necessarily darkable. */
+ if (can_colour_face(g, board, i, FACE_BLACK)) {
+ fs->black_score = face_score(g, board, f, FACE_BLACK);
+ add234(darkable_faces_sorted, fs);
+ }
+ if (can_colour_face(g, board, i, FACE_WHITE)) {
+ fs->white_score = face_score(g, board, f, FACE_WHITE);
+ add234(lightable_faces_sorted, fs);
+ }
+ }
+
+ /* Colour faces one at a time until no more faces are colourable. */
+ while (TRUE)
+ {
+ enum face_colour colour;
+ struct face_score *fs_white, *fs_black;
+ int c_lightable = count234(lightable_faces_sorted);
+ int c_darkable = count234(darkable_faces_sorted);
+ if (c_lightable == 0 && c_darkable == 0) {
+ /* No more faces we can use at all. */
+ break;
+ }
+ assert(c_lightable != 0 && c_darkable != 0);
+
+ fs_white = (struct face_score *)index234(lightable_faces_sorted, 0);
+ fs_black = (struct face_score *)index234(darkable_faces_sorted, 0);
+
+ /* Choose a colour, and colour the best available face
+ * with that colour. */
+ colour = random_upto(rs, 2) ? FACE_WHITE : FACE_BLACK;
+
+ if (colour == FACE_WHITE)
+ fs = fs_white;
+ else
+ fs = fs_black;
+ assert(fs);
+ i = fs - face_scores;
+ assert(board[i] == FACE_GREY);
+ board[i] = colour;
+
+ /* Remove this newly-coloured face from the lists. These lists should
+ * only contain grey faces. */
+ del234(lightable_faces_sorted, fs);
+ del234(darkable_faces_sorted, fs);
+
+ /* Remember which face we've just coloured */
+ cur_face = g->faces + i;
+
+ /* The face we've just coloured potentially affects the colourability
+ * and the scores of any neighbouring faces (touching at a corner or
+ * edge). So the search needs to be conducted around all faces
+ * touching the one we've just lit. Iterate over its corners, then
+ * over each corner's faces. For each such face, we remove it from
+ * the lists, recalculate any scores, then add it back to the lists
+ * (depending on whether it is lightable, darkable or both). */
+ for (i = 0; i < cur_face->order; i++) {
+ grid_dot *d = cur_face->dots[i];
+ for (j = 0; j < d->order; j++) {
+ grid_face *f = d->faces[j];
+ int fi; /* face index of f */
+
+ if (f == NULL)
+ continue;
+ if (f == cur_face)
+ continue;
+
+ /* If the face is already coloured, it won't be on our
+ * lightable/darkable lists anyway, so we can skip it without
+ * bothering with the removal step. */
+ if (FACE_COLOUR(f) != FACE_GREY) continue;
+
+ /* Find the face index and face_score* corresponding to f */
+ fi = f - g->faces;
+ fs = face_scores + fi;
+
+ /* Remove from lightable list if it's in there. We do this,
+ * even if it is still lightable, because the score might
+ * be different, and we need to remove-then-add to maintain
+ * correct sort order. */
+ del234(lightable_faces_sorted, fs);
+ if (can_colour_face(g, board, fi, FACE_WHITE)) {
+ fs->white_score = face_score(g, board, f, FACE_WHITE);
+ add234(lightable_faces_sorted, fs);
+ }
+ /* Do the same for darkable list. */
+ del234(darkable_faces_sorted, fs);
+ if (can_colour_face(g, board, fi, FACE_BLACK)) {
+ fs->black_score = face_score(g, board, f, FACE_BLACK);
+ add234(darkable_faces_sorted, fs);