+ game_desc = state_to_text(state);
+
+ free_game(state);
+
+ if (grid_desc) {
+ retval = snewn(strlen(grid_desc) + 1 + strlen(game_desc) + 1, char);
+ sprintf(retval, "%s%c%s", grid_desc, (int)GRID_DESC_SEP, game_desc);
+ sfree(grid_desc);
+ sfree(game_desc);
+ } else {
+ retval = game_desc;
+ }
+
+ 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,n2;
+ const char *dp;
+ char *grid_desc;
+ grid *g;
+ int num_faces, num_edges;
+
+ grid_desc = extract_grid_desc(&desc);
+ state->game_grid = g = loopy_generate_grid(params, grid_desc);
+ if (grid_desc) sfree(grid_desc);
+
+ dp = desc;
+
+ 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';
+ n2 = *dp - 'A' + 10;
+ if (n >= 0 && n < 10) {
+ state->clues[i] = n;
+ } else if (n2 >= 10 && n2 < 36) {
+ state->clues[i] = n2;
+ } 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 and Tricky Modes
+ * 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->dlines, opp_dline_index);
+ }
+ return FALSE;
+}
+
+
+/* Set pairs of lines around this face which are known to be identical, to
+ * the given line_state */
+static int face_setall_identical(solver_state *sstate, int face_index,
+ enum line_state line_new)
+{
+ /* can[dir] contains the canonical line associated with the line in
+ * direction dir from the square in question. Similarly inv[dir] is
+ * whether or not the line in question is inverse to its canonical
+ * element. */
+ int retval = FALSE;
+ game_state *state = sstate->state;
+ grid *g = state->game_grid;
+ grid_face *f = g->faces + face_index;
+ int N = f->order;
+ int i, j;
+ int can1, can2, inv1, inv2;
+
+ for (i = 0; i < N; i++) {
+ int line1_index = f->edges[i] - g->edges;
+ if (state->lines[line1_index] != LINE_UNKNOWN)
+ continue;
+ for (j = i + 1; j < N; j++) {
+ int line2_index = f->edges[j] - g->edges;
+ if (state->lines[line2_index] != LINE_UNKNOWN)
+ continue;
+
+ /* Found two UNKNOWNS */
+ can1 = edsf_canonify(sstate->linedsf, line1_index, &inv1);
+ can2 = edsf_canonify(sstate->linedsf, line2_index, &inv2);
+ if (can1 == can2 && inv1 == inv2) {
+ solver_set_line(sstate, line1_index, line_new);
+ solver_set_line(sstate, line2_index, line_new);
+ }
+ }
+ }
+ return retval;
+}
+
+/* Given a dot or face, and a count of LINE_UNKNOWNs, find them and
+ * return the edge indices into e. */
+static void find_unknowns(game_state *state,
+ grid_edge **edge_list, /* Edge list to search (from a face or a dot) */
+ int expected_count, /* Number of UNKNOWNs (comes from solver's cache) */
+ int *e /* Returned edge indices */)
+{
+ int c = 0;
+ grid *g = state->game_grid;
+ while (c < expected_count) {
+ int line_index = *edge_list - g->edges;
+ if (state->lines[line_index] == LINE_UNKNOWN) {
+ e[c] = line_index;
+ c++;
+ }
+ ++edge_list;
+ }
+}
+
+/* If we have a list of edges, and we know whether the number of YESs should
+ * be odd or even, and there are only a few UNKNOWNs, we can do some simple
+ * linedsf deductions. This can be used for both face and dot deductions.
+ * Returns the difficulty level of the next solver that should be used,
+ * or DIFF_MAX if no progress was made. */
+static int parity_deductions(solver_state *sstate,
+ grid_edge **edge_list, /* Edge list (from a face or a dot) */
+ int total_parity, /* Expected number of YESs modulo 2 (either 0 or 1) */
+ int unknown_count)
+{
+ game_state *state = sstate->state;
+ int diff = DIFF_MAX;
+ int *linedsf = sstate->linedsf;
+
+ if (unknown_count == 2) {
+ /* Lines are known alike/opposite, depending on inv. */
+ int e[2];
+ find_unknowns(state, edge_list, 2, e);
+ if (merge_lines(sstate, e[0], e[1], total_parity))
+ diff = min(diff, DIFF_HARD);
+ } else if (unknown_count == 3) {
+ int e[3];
+ int can[3]; /* canonical edges */
+ int inv[3]; /* whether can[x] is inverse to e[x] */
+ find_unknowns(state, edge_list, 3, e);
+ can[0] = edsf_canonify(linedsf, e[0], inv);
+ can[1] = edsf_canonify(linedsf, e[1], inv+1);
+ can[2] = edsf_canonify(linedsf, e[2], inv+2);
+ if (can[0] == can[1]) {
+ if (solver_set_line(sstate, e[2], (total_parity^inv[0]^inv[1]) ?
+ LINE_YES : LINE_NO))
+ diff = min(diff, DIFF_EASY);
+ }
+ if (can[0] == can[2]) {
+ if (solver_set_line(sstate, e[1], (total_parity^inv[0]^inv[2]) ?
+ LINE_YES : LINE_NO))
+ diff = min(diff, DIFF_EASY);
+ }
+ if (can[1] == can[2]) {
+ if (solver_set_line(sstate, e[0], (total_parity^inv[1]^inv[2]) ?
+ LINE_YES : LINE_NO))
+ diff = min(diff, DIFF_EASY);
+ }
+ } else if (unknown_count == 4) {
+ int e[4];
+ int can[4]; /* canonical edges */
+ int inv[4]; /* whether can[x] is inverse to e[x] */
+ find_unknowns(state, edge_list, 4, e);
+ can[0] = edsf_canonify(linedsf, e[0], inv);
+ can[1] = edsf_canonify(linedsf, e[1], inv+1);
+ can[2] = edsf_canonify(linedsf, e[2], inv+2);
+ can[3] = edsf_canonify(linedsf, e[3], inv+3);
+ if (can[0] == can[1]) {
+ if (merge_lines(sstate, e[2], e[3], total_parity^inv[0]^inv[1]))
+ diff = min(diff, DIFF_HARD);
+ } else if (can[0] == can[2]) {
+ if (merge_lines(sstate, e[1], e[3], total_parity^inv[0]^inv[2]))
+ diff = min(diff, DIFF_HARD);
+ } else if (can[0] == can[3]) {
+ if (merge_lines(sstate, e[1], e[2], total_parity^inv[0]^inv[3]))
+ diff = min(diff, DIFF_HARD);
+ } else if (can[1] == can[2]) {
+ if (merge_lines(sstate, e[0], e[3], total_parity^inv[1]^inv[2]))
+ diff = min(diff, DIFF_HARD);
+ } else if (can[1] == can[3]) {
+ if (merge_lines(sstate, e[0], e[2], total_parity^inv[1]^inv[3]))
+ diff = min(diff, DIFF_HARD);
+ } else if (can[2] == can[3]) {
+ if (merge_lines(sstate, e[0], e[1], total_parity^inv[2]^inv[3]))
+ diff = min(diff, DIFF_HARD);
+ }
+ }
+ return diff;
+}
+
+
+/*
+ * These are the main solver functions.
+ *
+ * Their return values are diff values corresponding to the lowest mode solver
+ * that would notice the work that they have done. For example if the normal
+ * mode solver adds actual lines or crosses, it will return DIFF_EASY as the
+ * easy mode solver might be able to make progress using that. It doesn't make
+ * sense for one of them to return a diff value higher than that of the
+ * function itself.
+ *
+ * Each function returns the lowest value it can, as early as possible, in
+ * order to try and pass as much work as possible back to the lower level
+ * solvers which progress more quickly.
+ */
+
+/* PROPOSED NEW DESIGN:
+ * We have a work queue consisting of 'events' notifying us that something has
+ * happened that a particular solver mode might be interested in. For example
+ * the hard mode solver might do something that helps the normal mode solver at
+ * dot [x,y] in which case it will enqueue an event recording this fact. Then
+ * we pull events off the work queue, and hand each in turn to the solver that
+ * is interested in them. If a solver reports that it failed we pass the same
+ * event on to progressively more advanced solvers and the loop detector. Once
+ * we've exhausted an event, or it has helped us progress, we drop it and
+ * continue to the next one. The events are sorted first in order of solver
+ * complexity (easy first) then order of insertion (oldest first).
+ * Once we run out of events we loop over each permitted solver in turn
+ * (easiest first) until either a deduction is made (and an event therefore
+ * emerges) or no further deductions can be made (in which case we've failed).
+ *
+ * QUESTIONS:
+ * * How do we 'loop over' a solver when both dots and squares are concerned.
+ * Answer: first all squares then all dots.
+ */
+
+static int trivial_deductions(solver_state *sstate)
+{
+ int i, current_yes, current_no;
+ game_state *state = sstate->state;
+ grid *g = state->game_grid;
+ int diff = DIFF_MAX;
+
+ /* Per-face deductions */
+ for (i = 0; i < g->num_faces; i++) {
+ grid_face *f = g->faces + i;
+
+ if (sstate->face_solved[i])
+ continue;
+
+ current_yes = sstate->face_yes_count[i];
+ current_no = sstate->face_no_count[i];
+
+ if (current_yes + current_no == f->order) {
+ sstate->face_solved[i] = TRUE;
+ continue;