+/* ----------------------------------------------------------------------
+ * 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
+ * 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(face_sort_cmpfn);
+ lightable_faces_gettable = newtree234(get_face_cmpfn);
+#define ADD_FACE(f) \
+ do { \
+ struct face *x = add234(lightable_faces_sorted, f); \
+ assert(x == f); \
+ x = add234(lightable_faces_gettable, f); \
+ assert(x == f); \
+ } while (0)
+
+#define REMOVE_FACE(f) \
+ do { \
+ struct face *x = del234(lightable_faces_sorted, f); \
+ assert(x); \
+ x = del234(lightable_faces_gettable, f); \
+ assert(x); \
+ } while (0)
+
+ /* Light faces one at a time until the board is interesting enough */
+ while (TRUE)
+ {
+ if (first_time) {
+ first_time = FALSE;
+ /* lightable_faces_xxx are empty, so start the process by
+ * lighting up the middle face. These tree234s should
+ * remain empty, consistent with what would happen if
+ * first_time were FALSE. */
+ board[g->middle_face - g->faces] = FACE_LIT;
+ face = snew(struct face);
+ face->f = g->middle_face;
+ /* No need to initialise any more of 'face' here, no other fields
+ * are used in this case. */
+ } else {
+ /* We have count234(lightable_faces_gettable) possibilities, and in
+ * lightable_faces_sorted they are sorted with the most desirable
+ * first. */
+ c = count234(lightable_faces_sorted);
+ if (c == 0)
+ break;
+ assert(c == count234(lightable_faces_gettable));
+
+ /* Check that the best face available is any good */
+ face = (struct face *)index234(lightable_faces_sorted, 0);
+ assert(face);
+
+ /*
+ * The situation for a general grid is slightly different from
+ * a square grid. Decreasing the perimeter should be allowed
+ * sometimes (think about creating a hexagon of lit triangles,
+ * for example). For if it were _never_ done, then the user would
+ * be able to illicitly deduce certain things. So we do it
+ * sometimes but not always.
+ */
+ if (face->score <= 0 && random_upto(rs, 2) == 0) {
+ break;
+ }
+
+ assert(face->f); /* not the infinite face */
+ assert(FACE_LIT_STATE(face->f) == FACE_UNLIT);
+
+ /* Update data structures */
+ /* Light up the face and remove it from the lists */
+ board[face->f - g->faces] = FACE_LIT;
+ REMOVE_FACE(face);
+ }
+
+ /* The face we've just lit up potentially affects the lightability
+ * 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 (i = 0; i < face->f->order; i++) {
+ grid_dot *d = face->f->dots[i];
+ for (j = 0; j < d->order; j++) {
+ grid_face *f2 = d->faces[j];
+ if (f2 == NULL)
+ continue;
+ if (f2 == face->f)
+ continue;
+ face_pos.f = f2;
+ tmpface = find234(lightable_faces_gettable, &face_pos, NULL);
+ if (tmpface) {
+ assert(tmpface->f == face_pos.f);
+ assert(FACE_LIT_STATE(tmpface->f) == FACE_UNLIT);
+ REMOVE_FACE(tmpface);
+ } else {
+ tmpface = snew(struct face);
+ tmpface->f = face_pos.f;
+ tmpface->random = random_bits(rs, 31);
+ }
+ tmpface->score = face_score(g, board, tmpface->f);
+
+ if (IS_LIGHTING_CANDIDATE(tmpface->f - g->faces)) {
+ ADD_FACE(tmpface);
+ } else {
+ sfree(tmpface);
+ }
+ }
+ }
+ sfree(face);
+ }
+
+ /* Clean up */
+ while ((face = delpos234(lightable_faces_gettable, 0)) != NULL)
+ sfree(face);
+ freetree234(lightable_faces_gettable);
+ freetree234(lightable_faces_sorted);
+
+ /* Fill out all the clues by initialising to 0, then iterating over
+ * all edges and incrementing each clue as we find edges that border
+ * between LIT/UNLIT faces */
+ memset(clues, 0, num_faces);
+ for (i = 0; i < g->num_edges; i++) {
+ grid_edge *e = g->edges + i;
+ grid_face *f1 = e->face1;
+ grid_face *f2 = e->face2;
+ if (FACE_LIT_STATE(f1) != FACE_LIT_STATE(f2)) {
+ if (f1) clues[f1 - g->faces]++;
+ if (f2) clues[f2 - g->faces]++;
+ }
+ }
+
+ sfree(board);
+}
+
+
+static int game_has_unique_soln(const game_state *state, int diff)
+{
+ int ret;
+ solver_state *sstate_new;
+ solver_state *sstate = new_solver_state((game_state *)state, diff);
+
+ sstate_new = solve_game_rec(sstate, diff);
+
+ assert(sstate_new->solver_status != SOLVER_MISTAKE);
+ ret = (sstate_new->solver_status == SOLVER_SOLVED);
+
+ free_solver_state(sstate_new);
+ free_solver_state(sstate);
+
+ return ret;
+}
+
+
+/* Remove clues one at a time at random. */
+static game_state *remove_clues(game_state *state, random_state *rs,
+ int diff)
+{
+ int *face_list;
+ int num_faces = state->game_grid->num_faces;
+ game_state *ret = dup_game(state), *saved_ret;
+ int n;
+
+ /* We need to remove some clues. We'll do this by forming a list of all
+ * available clues, shuffling it, then going along one at a
+ * time clearing each clue in turn for which doing so doesn't render the
+ * board unsolvable. */
+ face_list = snewn(num_faces, int);
+ for (n = 0; n < num_faces; ++n) {
+ face_list[n] = n;
+ }
+
+ shuffle(face_list, num_faces, sizeof(int), rs);
+
+ for (n = 0; n < num_faces; ++n) {
+ saved_ret = dup_game(ret);
+ ret->clues[face_list[n]] = -1;
+
+ if (game_has_unique_soln(ret, diff)) {
+ free_game(saved_ret);
+ } else {
+ free_game(ret);
+ ret = saved_ret;
+ }
+ }
+ sfree(face_list);
+
+ return ret;
+}
+
+
+static char *new_game_desc(game_params *params, random_state *rs,
+ char **aux, int interactive)
+{
+ /* solution and description both use run-length encoding in obvious ways */
+ char *retval;
+ grid *g;
+ game_state *state = snew(game_state);
+ game_state *state_new;
+ params_generate_grid(params);
+ state->game_grid = g = params->game_grid;
+ g->refcount++;
+ state->clues = snewn(g->num_faces, signed char);
+ state->lines = snewn(g->num_edges, char);
+ state->line_errors = snewn(g->num_edges, unsigned char);
+
+ state->grid_type = params->type;
+
+ newboard_please:
+
+ memset(state->lines, LINE_UNKNOWN, g->num_edges);
+ memset(state->line_errors, 0, g->num_edges);
+
+ state->solved = state->cheated = FALSE;
+
+ /* Get a new random solvable board with all its clues filled in. Yes, this
+ * can loop for ever if the params are suitably unfavourable, but
+ * preventing games smaller than 4x4 seems to stop this happening */
+ do {
+ add_full_clues(state, rs);
+ } while (!game_has_unique_soln(state, params->diff));
+
+ state_new = remove_clues(state, rs, params->diff);
+ free_game(state);
+ state = state_new;
+
+
+ if (params->diff > 0 && game_has_unique_soln(state, params->diff-1)) {
+#ifdef SHOW_WORKING
+ fprintf(stderr, "Rejecting board, it is too easy\n");
+#endif
+ goto newboard_please;
+ }
+
+ retval = state_to_text(state);
+
+ free_game(state);
+
+ assert(!validate_desc(params, retval));
+
+ return retval;
+}
+
+static game_state *new_game(midend *me, game_params *params, char *desc)
+{
+ int i;
+ game_state *state = snew(game_state);
+ int empties_to_make = 0;
+ int n;
+ const char *dp = desc;
+ grid *g;
+ int num_faces, num_edges;
+
+ params_generate_grid(params);
+ state->game_grid = g = params->game_grid;
+ g->refcount++;
+ num_faces = g->num_faces;
+ num_edges = g->num_edges;
+
+ state->clues = snewn(num_faces, signed char);
+ state->lines = snewn(num_edges, char);
+ state->line_errors = snewn(num_edges, unsigned char);
+
+ state->solved = state->cheated = FALSE;
+
+ state->grid_type = params->type;
+
+ for (i = 0; i < num_faces; i++) {
+ if (empties_to_make) {
+ empties_to_make--;
+ state->clues[i] = -1;
+ continue;
+ }
+
+ assert(*dp);
+ n = *dp - '0';
+ if (n >= 0 && n < 10) {
+ state->clues[i] = n;
+ } else {
+ n = *dp - 'a' + 1;
+ assert(n > 0);
+ state->clues[i] = -1;
+ empties_to_make = n - 1;
+ }
+ ++dp;
+ }
+
+ memset(state->lines, LINE_UNKNOWN, num_edges);
+ memset(state->line_errors, 0, num_edges);
+ return state;
+}
+
+/* Calculates the line_errors data, and checks if the current state is a
+ * solution */
+static int check_completion(game_state *state)
+{
+ grid *g = state->game_grid;
+ int *dsf;
+ int num_faces = g->num_faces;
+ int i;
+ int infinite_area, finite_area;
+ int loops_found = 0;
+ int found_edge_not_in_loop = FALSE;
+
+ memset(state->line_errors, 0, g->num_edges);
+
+ /* LL implementation of SGT's idea:
+ * A loop will partition the grid into an inside and an outside.
+ * If there is more than one loop, the grid will be partitioned into
+ * even more distinct regions. We can therefore track equivalence of
+ * faces, by saying that two faces are equivalent when there is a non-YES
+ * edge between them.
+ * We could keep track of the number of connected components, by counting
+ * the number of dsf-merges that aren't no-ops.
+ * But we're only interested in 3 separate cases:
+ * no loops, one loop, more than one loop.
+ *
+ * No loops: all faces are equivalent to the infinite face.
+ * One loop: only two equivalence classes - finite and infinite.
+ * >= 2 loops: there are 2 distinct finite regions.
+ *
+ * So we simply make two passes through all the edges.
+ * In the first pass, we dsf-merge the two faces bordering each non-YES
+ * edge.
+ * In the second pass, we look for YES-edges bordering:
+ * a) two non-equivalent faces.
+ * b) two non-equivalent faces, and one of them is part of a different
+ * finite area from the first finite area we've seen.
+ *
+ * An occurrence of a) means there is at least one loop.
+ * An occurrence of b) means there is more than one loop.
+ * Edges satisfying a) are marked as errors.
+ *
+ * While we're at it, we set a flag if we find a YES edge that is not
+ * part of a loop.
+ * This information will help decide, if there's a single loop, whether it
+ * is a candidate for being a solution (that is, all YES edges are part of
+ * this loop).
+ *
+ * If there is a candidate loop, we then go through all clues and check
+ * they are all satisfied. If so, we have found a solution and we can
+ * unmark all line_errors.
+ */
+
+ /* Infinite face is at the end - its index is num_faces.
+ * This macro is just to make this obvious! */
+ #define INF_FACE num_faces
+ dsf = snewn(num_faces + 1, int);
+ dsf_init(dsf, num_faces + 1);
+
+ /* First pass */
+ for (i = 0; i < g->num_edges; i++) {
+ grid_edge *e = g->edges + i;
+ int f1 = e->face1 ? e->face1 - g->faces : INF_FACE;
+ int f2 = e->face2 ? e->face2 - g->faces : INF_FACE;
+ if (state->lines[i] != LINE_YES)
+ dsf_merge(dsf, f1, f2);
+ }
+
+ /* Second pass */
+ infinite_area = dsf_canonify(dsf, INF_FACE);
+ finite_area = -1;
+ for (i = 0; i < g->num_edges; i++) {
+ grid_edge *e = g->edges + i;
+ int f1 = e->face1 ? e->face1 - g->faces : INF_FACE;
+ int can1 = dsf_canonify(dsf, f1);
+ int f2 = e->face2 ? e->face2 - g->faces : INF_FACE;
+ int can2 = dsf_canonify(dsf, f2);
+ if (state->lines[i] != LINE_YES) continue;
+
+ if (can1 == can2) {
+ /* Faces are equivalent, so this edge not part of a loop */
+ found_edge_not_in_loop = TRUE;
+ continue;
+ }
+ state->line_errors[i] = TRUE;
+ if (loops_found == 0) loops_found = 1;
+
+ /* Don't bother with further checks if we've already found 2 loops */
+ if (loops_found == 2) continue;
+
+ if (finite_area == -1) {
+ /* Found our first finite area */
+ if (can1 != infinite_area)
+ finite_area = can1;
+ else
+ finite_area = can2;
+ }
+
+ /* Have we found a second area? */
+ if (finite_area != -1) {
+ if (can1 != infinite_area && can1 != finite_area) {
+ loops_found = 2;
+ continue;
+ }
+ if (can2 != infinite_area && can2 != finite_area) {
+ loops_found = 2;
+ }
+ }
+ }
+
+/*
+ printf("loops_found = %d\n", loops_found);
+ printf("found_edge_not_in_loop = %s\n",
+ found_edge_not_in_loop ? "TRUE" : "FALSE");
+*/
+
+ sfree(dsf); /* No longer need the dsf */
+
+ /* Have we found a candidate loop? */
+ if (loops_found == 1 && !found_edge_not_in_loop) {
+ /* Yes, so check all clues are satisfied */
+ int found_clue_violation = FALSE;
+ for (i = 0; i < num_faces; i++) {
+ int c = state->clues[i];
+ if (c >= 0) {
+ if (face_order(state, i, LINE_YES) != c) {
+ found_clue_violation = TRUE;
+ break;
+ }
+ }
+ }
+
+ if (!found_clue_violation) {
+ /* The loop is good */
+ memset(state->line_errors, 0, g->num_edges);
+ return TRUE; /* No need to bother checking for dot violations */
+ }
+ }
+
+ /* Check for dot violations */
+ for (i = 0; i < g->num_dots; i++) {
+ int yes = dot_order(state, i, LINE_YES);
+ int unknown = dot_order(state, i, LINE_UNKNOWN);
+ if ((yes == 1 && unknown == 0) || (yes >= 3)) {
+ /* violation, so mark all YES edges as errors */
+ grid_dot *d = g->dots + i;
+ int j;
+ for (j = 0; j < d->order; j++) {
+ int e = d->edges[j] - g->edges;
+ if (state->lines[e] == LINE_YES)
+ state->line_errors[e] = TRUE;
+ }
+ }
+ }
+ return FALSE;
+}
+
+/* ----------------------------------------------------------------------
+ * Solver logic
+ *
+ * Our solver modes operate as follows. Each mode also uses the modes above it.
+ *
+ * Easy Mode
+ * Just implement the rules of the game.
+ *
+ * Normal Mode
+ * For each (adjacent) pair of lines through each dot we store a bit for
+ * whether at least one of them is on and whether at most one is on. (If we
+ * know both or neither is on that's already stored more directly.)
+ *
+ * Advanced Mode
+ * Use edsf data structure to make equivalence classes of lines that are
+ * known identical to or opposite to one another.
+ */
+
+
+/* DLines:
+ * For general grids, we consider "dlines" to be pairs of lines joined
+ * at a dot. The lines must be adjacent around the dot, so we can think of
+ * a dline as being a dot+face combination. Or, a dot+edge combination where
+ * the second edge is taken to be the next clockwise edge from the dot.
+ * Original loopy code didn't have this extra restriction of the lines being
+ * adjacent. From my tests with square grids, this extra restriction seems to
+ * take little, if anything, away from the quality of the puzzles.
+ * A dline can be uniquely identified by an edge/dot combination, given that
+ * a dline-pair always goes clockwise around its common dot. The edge/dot
+ * combination can be represented by an edge/bool combination - if bool is
+ * TRUE, use edge->dot1 else use edge->dot2. So the total number of dlines is
+ * exactly twice the number of edges in the grid - although the dlines
+ * spanning the infinite face are not all that useful to the solver.
+ * Note that, by convention, a dline goes clockwise around its common dot,
+ * which means the dline goes anti-clockwise around its common face.
+ */
+
+/* Helper functions for obtaining an index into an array of dlines, given
+ * various information. We assume the grid layout conventions about how
+ * the various lists are interleaved - see grid_make_consistent() for
+ * details. */
+
+/* i points to the first edge of the dline pair, reading clockwise around
+ * the dot. */
+static int dline_index_from_dot(grid *g, grid_dot *d, int i)
+{
+ grid_edge *e = d->edges[i];
+ int ret;
+#ifdef DEBUG_DLINES
+ grid_edge *e2;
+ int i2 = i+1;
+ if (i2 == d->order) i2 = 0;
+ e2 = d->edges[i2];
+#endif
+ ret = 2 * (e - g->edges) + ((e->dot1 == d) ? 1 : 0);
+#ifdef DEBUG_DLINES
+ printf("dline_index_from_dot: d=%d,i=%d, edges [%d,%d] - %d\n",
+ (int)(d - g->dots), i, (int)(e - g->edges),
+ (int)(e2 - g->edges), ret);
+#endif
+ return ret;
+}
+/* i points to the second edge of the dline pair, reading clockwise around
+ * the face. That is, the edges of the dline, starting at edge{i}, read
+ * anti-clockwise around the face. By layout conventions, the common dot
+ * of the dline will be f->dots[i] */
+static int dline_index_from_face(grid *g, grid_face *f, int i)
+{
+ grid_edge *e = f->edges[i];
+ grid_dot *d = f->dots[i];
+ int ret;
+#ifdef DEBUG_DLINES
+ grid_edge *e2;
+ int i2 = i - 1;
+ if (i2 < 0) i2 += f->order;
+ e2 = f->edges[i2];
+#endif
+ ret = 2 * (e - g->edges) + ((e->dot1 == d) ? 1 : 0);
+#ifdef DEBUG_DLINES
+ printf("dline_index_from_face: f=%d,i=%d, edges [%d,%d] - %d\n",
+ (int)(f - g->faces), i, (int)(e - g->edges),
+ (int)(e2 - g->edges), ret);
+#endif
+ return ret;
+}
+static int is_atleastone(const char *dline_array, int index)
+{
+ return BIT_SET(dline_array[index], 0);
+}
+static int set_atleastone(char *dline_array, int index)
+{
+ return SET_BIT(dline_array[index], 0);
+}
+static int is_atmostone(const char *dline_array, int index)
+{
+ return BIT_SET(dline_array[index], 1);
+}
+static int set_atmostone(char *dline_array, int index)
+{
+ return SET_BIT(dline_array[index], 1);
+}
+
+static void array_setall(char *array, char from, char to, int len)
+{
+ char *p = array, *p_old = p;
+ int len_remaining = len;
+
+ while ((p = memchr(p, from, len_remaining))) {
+ *p = to;
+ len_remaining -= p - p_old;
+ p_old = p;
+ }
+}
+
+/* Helper, called when doing dline dot deductions, in the case where we
+ * have 4 UNKNOWNs, and two of them (adjacent) have *exactly* one YES between
+ * them (because of dline atmostone/atleastone).
+ * On entry, edge points to the first of these two UNKNOWNs. This function
+ * will find the opposite UNKNOWNS (if they are adjacent to one another)
+ * and set their corresponding dline to atleastone. (Setting atmostone
+ * already happens in earlier dline deductions) */
+static int dline_set_opp_atleastone(solver_state *sstate,
+ grid_dot *d, int edge)
+{
+ game_state *state = sstate->state;
+ grid *g = state->game_grid;
+ int N = d->order;
+ int opp, opp2;
+ for (opp = 0; opp < N; opp++) {
+ int opp_dline_index;
+ if (opp == edge || opp == edge+1 || opp == edge-1)
+ continue;
+ if (opp == 0 && edge == N-1)
+ continue;
+ if (opp == N-1 && edge == 0)
+ continue;
+ opp2 = opp + 1;
+ if (opp2 == N) opp2 = 0;
+ /* Check if opp, opp2 point to LINE_UNKNOWNs */
+ if (state->lines[d->edges[opp] - g->edges] != LINE_UNKNOWN)
+ continue;
+ if (state->lines[d->edges[opp2] - g->edges] != LINE_UNKNOWN)
+ continue;
+ /* Found opposite UNKNOWNS and they're next to each other */
+ opp_dline_index = dline_index_from_dot(g, d, opp);
+ return set_atleastone(sstate->normal->dlines, opp_dline_index);
+ }
+ return FALSE;
+}