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