+ int len = 1; /* Counting 0 as a bit of a special case */
+ int i;
+
+ for (i = 1; i < n; i *= 10) {
+ len += max(n - i, 0);
+ }
+
+ return len;
+}
+
+static char *encode_solve_move(const game_state *state)
+{
+ int len;
+ char *ret, *p;
+ int i;
+ int num_edges = state->game_grid->num_edges;
+
+ /* This is going to return a string representing the moves needed to set
+ * every line in a grid to be the same as the ones in 'state'. The exact
+ * length of this string is predictable. */
+
+ len = 1; /* Count the 'S' prefix */
+ /* Numbers in all lines */
+ len += len_0_to_n(num_edges);
+ /* For each line we also have a letter */
+ len += num_edges;
+
+ ret = snewn(len + 1, char);
+ p = ret;
+
+ p += sprintf(p, "S");
+
+ for (i = 0; i < num_edges; i++) {
+ switch (state->lines[i]) {
+ case LINE_YES:
+ p += sprintf(p, "%dy", i);
+ break;
+ case LINE_NO:
+ p += sprintf(p, "%dn", i);
+ break;
+ }
+ }
+
+ /* No point in doing sums like that if they're going to be wrong */
+ assert(strlen(ret) <= (size_t)len);
+ return ret;
+}
+
+static game_ui *new_ui(game_state *state)
+{
+ return NULL;
+}
+
+static void free_ui(game_ui *ui)
+{
+}
+
+static char *encode_ui(game_ui *ui)
+{
+ return NULL;
+}
+
+static void decode_ui(game_ui *ui, char *encoding)
+{
+}
+
+static void game_changed_state(game_ui *ui, game_state *oldstate,
+ game_state *newstate)
+{
+}
+
+static void game_compute_size(game_params *params, int tilesize,
+ int *x, int *y)
+{
+ grid *g;
+ int grid_width, grid_height, rendered_width, rendered_height;
+
+ params_generate_grid(params);
+ g = params->game_grid;
+ grid_width = g->highest_x - g->lowest_x;
+ grid_height = g->highest_y - g->lowest_y;
+ /* multiply first to minimise rounding error on integer division */
+ rendered_width = grid_width * tilesize / g->tilesize;
+ rendered_height = grid_height * tilesize / g->tilesize;
+ *x = rendered_width + 2 * BORDER(tilesize) + 1;
+ *y = rendered_height + 2 * BORDER(tilesize) + 1;
+}
+
+static void game_set_size(drawing *dr, game_drawstate *ds,
+ game_params *params, int tilesize)
+{
+ ds->tilesize = tilesize;
+}
+
+static float *game_colours(frontend *fe, int *ncolours)
+{
+ float *ret = snewn(4 * NCOLOURS, float);
+
+ frontend_default_colour(fe, &ret[COL_BACKGROUND * 3]);
+
+ ret[COL_FOREGROUND * 3 + 0] = 0.0F;
+ ret[COL_FOREGROUND * 3 + 1] = 0.0F;
+ ret[COL_FOREGROUND * 3 + 2] = 0.0F;
+
+ ret[COL_LINEUNKNOWN * 3 + 0] = 0.8F;
+ ret[COL_LINEUNKNOWN * 3 + 1] = 0.8F;
+ ret[COL_LINEUNKNOWN * 3 + 2] = 0.0F;
+
+ ret[COL_HIGHLIGHT * 3 + 0] = 1.0F;
+ ret[COL_HIGHLIGHT * 3 + 1] = 1.0F;
+ ret[COL_HIGHLIGHT * 3 + 2] = 1.0F;
+
+ ret[COL_MISTAKE * 3 + 0] = 1.0F;
+ ret[COL_MISTAKE * 3 + 1] = 0.0F;
+ ret[COL_MISTAKE * 3 + 2] = 0.0F;
+
+ ret[COL_SATISFIED * 3 + 0] = 0.0F;
+ ret[COL_SATISFIED * 3 + 1] = 0.0F;
+ ret[COL_SATISFIED * 3 + 2] = 0.0F;
+
+ *ncolours = NCOLOURS;
+ return ret;
+}
+
+static game_drawstate *game_new_drawstate(drawing *dr, game_state *state)
+{
+ struct game_drawstate *ds = snew(struct game_drawstate);
+ int num_faces = state->game_grid->num_faces;
+ int num_edges = state->game_grid->num_edges;
+
+ ds->tilesize = 0;
+ ds->started = 0;
+ ds->lines = snewn(num_edges, char);
+ ds->clue_error = snewn(num_faces, char);
+ ds->clue_satisfied = snewn(num_faces, char);
+ ds->flashing = 0;
+
+ memset(ds->lines, LINE_UNKNOWN, num_edges);
+ memset(ds->clue_error, 0, num_faces);
+ memset(ds->clue_satisfied, 0, num_faces);
+
+ return ds;
+}
+
+static void game_free_drawstate(drawing *dr, game_drawstate *ds)
+{
+ sfree(ds->clue_error);
+ sfree(ds->clue_satisfied);
+ sfree(ds->lines);
+ sfree(ds);
+}
+
+static int game_timing_state(game_state *state, game_ui *ui)
+{
+ return TRUE;
+}
+
+static float game_anim_length(game_state *oldstate, game_state *newstate,
+ int dir, game_ui *ui)
+{
+ return 0.0F;
+}
+
+static int game_can_format_as_text_now(game_params *params)
+{
+ if (params->type != 0)
+ return FALSE;
+ return TRUE;
+}
+
+static char *game_text_format(game_state *state)
+{
+ int w, h, W, H;
+ int x, y, i;
+ int cell_size;
+ char *ret;
+ grid *g = state->game_grid;
+ grid_face *f;
+
+ assert(state->grid_type == 0);
+
+ /* Work out the basic size unit */
+ f = g->faces; /* first face */
+ assert(f->order == 4);
+ /* The dots are ordered clockwise, so the two opposite
+ * corners are guaranteed to span the square */
+ cell_size = abs(f->dots[0]->x - f->dots[2]->x);
+
+ w = (g->highest_x - g->lowest_x) / cell_size;
+ h = (g->highest_y - g->lowest_y) / cell_size;
+
+ /* Create a blank "canvas" to "draw" on */
+ W = 2 * w + 2;
+ H = 2 * h + 1;
+ ret = snewn(W * H + 1, char);
+ for (y = 0; y < H; y++) {
+ for (x = 0; x < W-1; x++) {
+ ret[y*W + x] = ' ';
+ }
+ ret[y*W + W-1] = '\n';
+ }
+ ret[H*W] = '\0';
+
+ /* Fill in edge info */
+ for (i = 0; i < g->num_edges; i++) {
+ grid_edge *e = g->edges + i;
+ /* Cell coordinates, from (0,0) to (w-1,h-1) */
+ int x1 = (e->dot1->x - g->lowest_x) / cell_size;
+ int x2 = (e->dot2->x - g->lowest_x) / cell_size;
+ int y1 = (e->dot1->y - g->lowest_y) / cell_size;
+ int y2 = (e->dot2->y - g->lowest_y) / cell_size;
+ /* Midpoint, in canvas coordinates (canvas coordinates are just twice
+ * cell coordinates) */
+ x = x1 + x2;
+ y = y1 + y2;
+ switch (state->lines[i]) {
+ case LINE_YES:
+ ret[y*W + x] = (y1 == y2) ? '-' : '|';
+ break;
+ case LINE_NO:
+ ret[y*W + x] = 'x';
+ break;
+ case LINE_UNKNOWN:
+ break; /* already a space */
+ default:
+ assert(!"Illegal line state");
+ }
+ }
+
+ /* Fill in clues */
+ for (i = 0; i < g->num_faces; i++) {
+ int x1, x2, y1, y2;
+
+ f = g->faces + i;
+ assert(f->order == 4);
+ /* Cell coordinates, from (0,0) to (w-1,h-1) */
+ x1 = (f->dots[0]->x - g->lowest_x) / cell_size;
+ x2 = (f->dots[2]->x - g->lowest_x) / cell_size;
+ y1 = (f->dots[0]->y - g->lowest_y) / cell_size;
+ y2 = (f->dots[2]->y - g->lowest_y) / cell_size;
+ /* Midpoint, in canvas coordinates */
+ x = x1 + x2;
+ y = y1 + y2;
+ ret[y*W + x] = CLUE2CHAR(state->clues[i]);
+ }
+ return ret;
+}
+
+/* ----------------------------------------------------------------------
+ * Debug code
+ */
+
+#ifdef DEBUG_CACHES
+static void check_caches(const solver_state* sstate)
+{
+ int i;
+ const game_state *state = sstate->state;
+ const grid *g = state->game_grid;
+
+ for (i = 0; i < g->num_dots; i++) {
+ assert(dot_order(state, i, LINE_YES) == sstate->dot_yes_count[i]);
+ assert(dot_order(state, i, LINE_NO) == sstate->dot_no_count[i]);
+ }
+
+ for (i = 0; i < g->num_faces; i++) {
+ assert(face_order(state, i, LINE_YES) == sstate->face_yes_count[i]);
+ assert(face_order(state, i, LINE_NO) == sstate->face_no_count[i]);
+ }
+}
+
+#if 0
+#define check_caches(s) \
+ do { \
+ fprintf(stderr, "check_caches at line %d\n", __LINE__); \
+ check_caches(s); \
+ } while (0)
+#endif
+#endif /* DEBUG_CACHES */
+
+/* ----------------------------------------------------------------------
+ * Solver utility functions
+ */
+
+/* Sets the line (with index i) to the new state 'line_new', and updates
+ * the cached counts of any affected faces and dots.
+ * Returns TRUE if this actually changed the line's state. */
+static int solver_set_line(solver_state *sstate, int i,
+ enum line_state line_new
+#ifdef SHOW_WORKING
+ , const char *reason
+#endif
+ )
+{
+ game_state *state = sstate->state;
+ grid *g;
+ grid_edge *e;
+
+ assert(line_new != LINE_UNKNOWN);
+
+ check_caches(sstate);
+
+ if (state->lines[i] == line_new) {
+ return FALSE; /* nothing changed */
+ }
+ state->lines[i] = line_new;
+
+#ifdef SHOW_WORKING
+ fprintf(stderr, "solver: set line [%d] to %s (%s)\n",
+ i, line_new == LINE_YES ? "YES" : "NO",
+ reason);
+#endif
+
+ g = state->game_grid;
+ e = g->edges + i;
+
+ /* Update the cache for both dots and both faces affected by this. */
+ if (line_new == LINE_YES) {
+ sstate->dot_yes_count[e->dot1 - g->dots]++;
+ sstate->dot_yes_count[e->dot2 - g->dots]++;
+ if (e->face1) {
+ sstate->face_yes_count[e->face1 - g->faces]++;
+ }
+ if (e->face2) {
+ sstate->face_yes_count[e->face2 - g->faces]++;
+ }
+ } else {
+ sstate->dot_no_count[e->dot1 - g->dots]++;
+ sstate->dot_no_count[e->dot2 - g->dots]++;
+ if (e->face1) {
+ sstate->face_no_count[e->face1 - g->faces]++;
+ }
+ if (e->face2) {
+ sstate->face_no_count[e->face2 - g->faces]++;
+ }
+ }
+
+ check_caches(sstate);
+ return TRUE;
+}
+
+#ifdef SHOW_WORKING
+#define solver_set_line(a, b, c) \
+ solver_set_line(a, b, c, __FUNCTION__)
+#endif
+
+/*
+ * Merge two dots due to the existence of an edge between them.
+ * Updates the dsf tracking equivalence classes, and keeps track of
+ * the length of path each dot is currently a part of.
+ * Returns TRUE if the dots were already linked, ie if they are part of a
+ * closed loop, and false otherwise.
+ */
+static int merge_dots(solver_state *sstate, int edge_index)
+{
+ int i, j, len;
+ grid *g = sstate->state->game_grid;
+ grid_edge *e = g->edges + edge_index;
+
+ i = e->dot1 - g->dots;
+ j = e->dot2 - g->dots;
+
+ i = dsf_canonify(sstate->dotdsf, i);
+ j = dsf_canonify(sstate->dotdsf, j);
+
+ if (i == j) {
+ return TRUE;
+ } else {
+ len = sstate->looplen[i] + sstate->looplen[j];
+ dsf_merge(sstate->dotdsf, i, j);
+ i = dsf_canonify(sstate->dotdsf, i);
+ sstate->looplen[i] = len;
+ return FALSE;
+ }
+}
+
+/* Merge two lines because the solver has deduced that they must be either
+ * identical or opposite. Returns TRUE if this is new information, otherwise
+ * FALSE. */
+static int merge_lines(solver_state *sstate, int i, int j, int inverse
+#ifdef SHOW_WORKING
+ , const char *reason
+#endif
+ )
+{
+ int inv_tmp;
+
+ assert(i < sstate->state->game_grid->num_edges);
+ assert(j < sstate->state->game_grid->num_edges);
+
+ i = edsf_canonify(sstate->hard->linedsf, i, &inv_tmp);
+ inverse ^= inv_tmp;
+ j = edsf_canonify(sstate->hard->linedsf, j, &inv_tmp);
+ inverse ^= inv_tmp;
+
+ edsf_merge(sstate->hard->linedsf, i, j, inverse);
+
+#ifdef SHOW_WORKING
+ if (i != j) {
+ fprintf(stderr, "%s [%d] [%d] %s(%s)\n",
+ __FUNCTION__, i, j,
+ inverse ? "inverse " : "", reason);
+ }
+#endif
+ return (i != j);
+}
+
+#ifdef SHOW_WORKING
+#define merge_lines(a, b, c, d) \
+ merge_lines(a, b, c, d, __FUNCTION__)
+#endif
+
+/* Count the number of lines of a particular type currently going into the
+ * given dot. */
+static int dot_order(const game_state* state, int dot, char line_type)
+{
+ int n = 0;
+ grid *g = state->game_grid;
+ grid_dot *d = g->dots + dot;
+ int i;
+
+ for (i = 0; i < d->order; i++) {
+ grid_edge *e = d->edges[i];
+ if (state->lines[e - g->edges] == line_type)
+ ++n;
+ }
+ return n;
+}
+
+/* Count the number of lines of a particular type currently surrounding the
+ * given face */
+static int face_order(const game_state* state, int face, char line_type)
+{
+ int n = 0;
+ grid *g = state->game_grid;
+ grid_face *f = g->faces + face;
+ int i;
+
+ for (i = 0; i < f->order; i++) {
+ grid_edge *e = f->edges[i];
+ if (state->lines[e - g->edges] == line_type)
+ ++n;
+ }
+ return n;
+}
+
+/* Set all lines bordering a dot of type old_type to type new_type
+ * Return value tells caller whether this function actually did anything */
+static int dot_setall(solver_state *sstate, int dot,
+ char old_type, char new_type)
+{
+ int retval = FALSE, r;
+ game_state *state = sstate->state;
+ grid *g;
+ grid_dot *d;
+ int i;
+
+ if (old_type == new_type)
+ return FALSE;
+
+ g = state->game_grid;
+ d = g->dots + dot;
+
+ for (i = 0; i < d->order; i++) {
+ int line_index = d->edges[i] - g->edges;
+ if (state->lines[line_index] == old_type) {
+ r = solver_set_line(sstate, line_index, new_type);
+ assert(r == TRUE);
+ retval = TRUE;
+ }
+ }
+ return retval;
+}
+
+/* Set all lines bordering a face of type old_type to type new_type */
+static int face_setall(solver_state *sstate, int face,
+ char old_type, char new_type)
+{
+ int retval = FALSE, r;
+ game_state *state = sstate->state;
+ grid *g;
+ grid_face *f;
+ int i;
+
+ if (old_type == new_type)
+ return FALSE;
+
+ g = state->game_grid;
+ f = g->faces + face;
+
+ for (i = 0; i < f->order; i++) {
+ int line_index = f->edges[i] - g->edges;
+ if (state->lines[line_index] == old_type) {
+ r = solver_set_line(sstate, line_index, new_type);
+ assert(r == TRUE);
+ retval = TRUE;
+ }
+ }
+ return retval;
+}
+
+/* ----------------------------------------------------------------------
+ * 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);