+/* 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.
+ */