+ FORALL_SQUARES(state, i, j) {
+ if (CLUE_AT(state, i, j) < 0) {
+ if (empty_count > 25) {
+ dp += sprintf(dp, "%c", (int)(empty_count + 'a' - 1));
+ empty_count = 0;
+ }
+ empty_count++;
+ } else {
+ if (empty_count) {
+ dp += sprintf(dp, "%c", (int)(empty_count + 'a' - 1));
+ empty_count = 0;
+ }
+ dp += sprintf(dp, "%c", (int)CLUE2CHAR(CLUE_AT(state, i, j)));
+ }
+ }
+
+ if (empty_count)
+ dp += sprintf(dp, "%c", (int)(empty_count + 'a' - 1));
+
+ retval = dupstr(description);
+ sfree(description);
+
+ return retval;
+}
+
+/* We require that the params pass the test in validate_params and that the
+ * description fills the entire game area */
+static char *validate_desc(game_params *params, char *desc)
+{
+ int count = 0;
+
+ for (; *desc; ++desc) {
+ if (*desc >= '0' && *desc <= '9') {
+ count++;
+ continue;
+ }
+ if (*desc >= 'a') {
+ count += *desc - 'a' + 1;
+ continue;
+ }
+ return "Unknown character in description";
+ }
+
+ if (count < SQUARE_COUNT(params))
+ return "Description too short for board size";
+ if (count > SQUARE_COUNT(params))
+ return "Description too long for board size";
+
+ return NULL;
+}
+
+/* Sums the lengths of the numbers in range [0,n) */
+/* See equivalent function in solo.c for justification of this. */
+static int len_0_to_n(int n)
+{
+ 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, i, j;
+ char *ret, *p;
+ /* 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 horizontal lines */
+ /* Horizontal lines, x position */
+ len += len_0_to_n(state->w) * (state->h + 1);
+ /* Horizontal lines, y position */
+ len += len_0_to_n(state->h + 1) * (state->w);
+ /* Vertical lines, y position */
+ len += len_0_to_n(state->h) * (state->w + 1);
+ /* Vertical lines, x position */
+ len += len_0_to_n(state->w + 1) * (state->h);
+ /* For each line we also have two letters and a comma */
+ len += 3 * (LINE_COUNT(state));
+
+ ret = snewn(len + 1, char);
+ p = ret;
+
+ p += sprintf(p, "S");
+
+ FORALL_HL(state, i, j) {
+ switch (RIGHTOF_DOT(state, i, j)) {
+ case LINE_YES:
+ p += sprintf(p, "%d,%dhy", i, j);
+ break;
+ case LINE_NO:
+ p += sprintf(p, "%d,%dhn", i, j);
+ break;
+ }
+ }
+
+ FORALL_VL(state, i, j) {
+ switch (BELOW_DOT(state, i, j)) {
+ case LINE_YES:
+ p += sprintf(p, "%d,%dvy", i, j);
+ break;
+ case LINE_NO:
+ p += sprintf(p, "%d,%dvn", i, j);
+ 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)
+{
+}
+
+#define SIZE(d) ((d) * TILE_SIZE + 2 * BORDER + 1)
+
+static void game_compute_size(game_params *params, int tilesize,
+ int *x, int *y)
+{
+ struct { int tilesize; } ads, *ds = &ads;
+ ads.tilesize = tilesize;
+
+ *x = SIZE(params->w);
+ *y = SIZE(params->h);
+}
+
+static void game_set_size(drawing *dr, game_drawstate *ds,
+ game_params *params, int tilesize)
+{
+ ds->tilesize = tilesize;
+ ds->linewidth = max(1,tilesize/16);
+}
+
+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_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;
+
+ *ncolours = NCOLOURS;
+ return ret;
+}
+
+static game_drawstate *game_new_drawstate(drawing *dr, game_state *state)
+{
+ struct game_drawstate *ds = snew(struct game_drawstate);
+
+ ds->tilesize = ds->linewidth = 0;
+ ds->started = 0;
+ ds->hl = snewn(HL_COUNT(state), char);
+ ds->vl = snewn(VL_COUNT(state), char);
+ ds->clue_error = snewn(SQUARE_COUNT(state), char);
+ ds->flashing = 0;
+
+ memset(ds->hl, LINE_UNKNOWN, HL_COUNT(state));
+ memset(ds->vl, LINE_UNKNOWN, VL_COUNT(state));
+ memset(ds->clue_error, 0, SQUARE_COUNT(state));
+
+ return ds;
+}
+
+static void game_free_drawstate(drawing *dr, game_drawstate *ds)
+{
+ sfree(ds->clue_error);
+ sfree(ds->hl);
+ sfree(ds->vl);
+ 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 char *game_text_format(game_state *state)
+{
+ int i, j;
+ int len;
+ char *ret, *rp;
+
+ len = (2 * state->w + 2) * (2 * state->h + 1);
+ rp = ret = snewn(len + 1, char);
+
+#define DRAW_HL \
+ switch (ABOVE_SQUARE(state, i, j)) { \
+ case LINE_YES: \
+ rp += sprintf(rp, " -"); \
+ break; \
+ case LINE_NO: \
+ rp += sprintf(rp, " x"); \
+ break; \
+ case LINE_UNKNOWN: \
+ rp += sprintf(rp, " "); \
+ break; \
+ default: \
+ assert(!"Illegal line state for HL"); \
+ }
+
+#define DRAW_VL \
+ switch (LEFTOF_SQUARE(state, i, j)) { \
+ case LINE_YES: \
+ rp += sprintf(rp, "|"); \
+ break; \
+ case LINE_NO: \
+ rp += sprintf(rp, "x"); \
+ break; \
+ case LINE_UNKNOWN: \
+ rp += sprintf(rp, " "); \
+ break; \
+ default: \
+ assert(!"Illegal line state for VL"); \
+ }
+
+ for (j = 0; j < state->h; ++j) {
+ for (i = 0; i < state->w; ++i) {
+ DRAW_HL;
+ }
+ rp += sprintf(rp, " \n");
+ for (i = 0; i < state->w; ++i) {
+ DRAW_VL;
+ rp += sprintf(rp, "%c", (int)CLUE2CHAR(CLUE_AT(state, i, j)));
+ }
+ DRAW_VL;
+ rp += sprintf(rp, "\n");
+ }
+ for (i = 0; i < state->w; ++i) {
+ DRAW_HL;
+ }
+ rp += sprintf(rp, " \n");
+
+ assert(strlen(ret) == len);
+ return ret;
+}
+
+/* ----------------------------------------------------------------------
+ * Debug code
+ */
+
+#ifdef DEBUG_CACHES
+static void check_caches(const solver_state* sstate)
+{
+ int i, j;
+ const game_state *state = sstate->state;
+
+ FORALL_DOTS(state, i, j) {
+#if 0
+ fprintf(stderr, "dot [%d,%d] y: %d %d n: %d %d\n", i, j,
+ dot_order(state, i, j, LINE_YES),
+ sstate->dot_yescount[i + (state->w + 1) * j],
+ dot_order(state, i, j, LINE_NO),
+ sstate->dot_nocount[i + (state->w + 1) * j]);
+#endif
+
+ assert(dot_order(state, i, j, LINE_YES) ==
+ DOT_YES_COUNT(sstate, i, j));
+ assert(dot_order(state, i, j, LINE_NO) ==
+ DOT_NO_COUNT(sstate, i, j));
+ }
+
+ FORALL_SQUARES(state, i, j) {
+#if 0
+ fprintf(stderr, "square [%d,%d] y: %d %d n: %d %d\n", i, j,
+ square_order(state, i, j, LINE_YES),
+ sstate->square_yescount[i + state->w * j],
+ square_order(state, i, j, LINE_NO),
+ sstate->square_nocount[i + state->w * j]);
+#endif
+
+ assert(square_order(state, i, j, LINE_YES) ==
+ SQUARE_YES_COUNT(sstate, i, j));
+ assert(square_order(state, i, j, LINE_NO) ==
+ SQUARE_NO_COUNT(sstate, i, j));
+ }
+}
+
+#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
+ */
+
+static int set_line_bydot(solver_state *sstate, int x, int y, enum direction d,
+ enum line_state line_new
+#ifdef SHOW_WORKING
+ , const char *reason
+#endif
+ )
+{
+ game_state *state = sstate->state;
+
+ /* This line borders at most two squares in our board. We figure out the
+ * x and y positions of those squares so we can record that their yes or no
+ * counts have been changed */
+ int sq1_x=-1, sq1_y=-1, sq2_x=-1, sq2_y=-1;
+ int otherdot_x=-1, otherdot_y=-1;
+
+ int progress = FALSE;
+
+#if 0
+ fprintf(stderr, "set_line_bydot [%d,%d], %s, %d\n",
+ x, y, DIR2STR(d), line_new);
+#endif
+
+ assert(line_new != LINE_UNKNOWN);
+
+ check_caches(sstate);
+
+ switch (d) {
+ case LEFT:
+ assert(x > 0);
+
+ if (LEFTOF_DOT(state, x, y) != line_new) {
+ LV_LEFTOF_DOT(state, x, y) = line_new;
+
+ otherdot_x = x-1;
+ otherdot_y = y;
+
+ sq1_x = x-1;
+ sq1_y = y-1;
+ sq2_x = x-1;
+ sq2_y = y;
+
+ progress = TRUE;
+ }
+ break;
+ case RIGHT:
+ assert(x < state->w);
+ if (RIGHTOF_DOT(state, x, y) != line_new) {
+ LV_RIGHTOF_DOT(state, x, y) = line_new;
+
+ otherdot_x = x+1;
+ otherdot_y = y;
+
+ sq1_x = x;
+ sq1_y = y-1;
+ sq2_x = x;
+ sq2_y = y;
+
+ progress = TRUE;
+ }
+ break;
+ case UP:
+ assert(y > 0);
+ if (ABOVE_DOT(state, x, y) != line_new) {
+ LV_ABOVE_DOT(state, x, y) = line_new;
+
+ otherdot_x = x;
+ otherdot_y = y-1;
+
+ sq1_x = x-1;
+ sq1_y = y-1;
+ sq2_x = x;
+ sq2_y = y-1;
+
+ progress = TRUE;
+ }
+ break;
+ case DOWN:
+ assert(y < state->h);
+ if (BELOW_DOT(state, x, y) != line_new) {
+ LV_BELOW_DOT(state, x, y) = line_new;
+
+ otherdot_x = x;
+ otherdot_y = y+1;
+
+ sq1_x = x-1;
+ sq1_y = y;
+ sq2_x = x;
+ sq2_y = y;
+
+ progress = TRUE;
+ }
+ break;
+ }
+
+ if (!progress)
+ return progress;
+
+#ifdef SHOW_WORKING
+ fprintf(stderr, "set line [%d,%d] -> [%d,%d] to %s (%s)\n",
+ x, y, otherdot_x, otherdot_y, line_new == LINE_YES ? "YES" : "NO",
+ reason);
+#endif
+
+ /* Above we updated the cache for the dot that the line in question reaches
+ * from the dot we've been told about. Here we update that for the dot
+ * named in our arguments. */
+ if (line_new == LINE_YES) {
+ if (sq1_x >= 0 && sq1_y >= 0)
+ ++SQUARE_YES_COUNT(sstate, sq1_x, sq1_y);
+ if (sq2_x < state->w && sq2_y < state->h)
+ ++SQUARE_YES_COUNT(sstate, sq2_x, sq2_y);
+ ++DOT_YES_COUNT(sstate, x, y);
+ ++DOT_YES_COUNT(sstate, otherdot_x, otherdot_y);
+ } else {
+ if (sq1_x >= 0 && sq1_y >= 0)
+ ++SQUARE_NO_COUNT(sstate, sq1_x, sq1_y);
+ if (sq2_x < state->w && sq2_y < state->h)
+ ++SQUARE_NO_COUNT(sstate, sq2_x, sq2_y);
+ ++DOT_NO_COUNT(sstate, x, y);
+ ++DOT_NO_COUNT(sstate, otherdot_x, otherdot_y);
+ }
+
+ check_caches(sstate);
+ return progress;
+}
+
+#ifdef SHOW_WORKING
+#define set_line_bydot(a, b, c, d, e) \
+ set_line_bydot(a, b, c, d, e, __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 x1, int y1, int x2, int y2)
+{
+ int i, j, len;
+
+ i = y1 * (sstate->state->w + 1) + x1;
+ j = y2 * (sstate->state->w + 1) + x2;
+
+ 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;
+ }
+}
+
+/* Seriously, these should be functions */
+
+#define LINEDSF_INDEX(state, x, y, d) \
+ ((d == UP) ? ((y-1) * (state->w + 1) + x) : \
+ (d == DOWN) ? ((y) * (state->w + 1) + x) : \
+ (d == LEFT) ? ((y) * (state->w) + x-1 + VL_COUNT(state)) : \
+ (d == RIGHT) ? ((y) * (state->w) + x + VL_COUNT(state)) : \
+ (assert(!"bad direction value"), 0))
+
+static void linedsf_deindex(const game_state *state, int i,
+ int *px, int *py, enum direction *pd)
+{
+ int i_mod;
+ if (i < VL_COUNT(state)) {
+ *(pd) = DOWN;
+ *(px) = (i) % (state->w+1);
+ *(py) = (i) / (state->w+1);
+ } else {
+ i_mod = i - VL_COUNT(state);
+ *(pd) = RIGHT;
+ *(px) = (i_mod) % (state->w);
+ *(py) = (i_mod) / (state->w);
+ }
+}
+
+/* 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 x1, int y1, enum direction d1,
+ int x2, int y2, enum direction d2,
+ int inverse
+#ifdef SHOW_WORKING
+ , const char *reason
+#endif
+ )
+{
+ int i, j, inv_tmp;
+
+ i = LINEDSF_INDEX(sstate->state, x1, y1, d1);
+ j = LINEDSF_INDEX(sstate->state, x2, y2, d2);
+
+ assert(i < LINE_COUNT(sstate->state));
+ assert(j < LINE_COUNT(sstate->state));
+
+ 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] [%d,%d,%s] %s(%s)\n",
+ __FUNCTION__,
+ x1, y1, DIR2STR(d1),
+ x2, y2, DIR2STR(d2),
+ inverse ? "inverse " : "", reason);
+ }
+#endif
+ return (i != j);
+}
+
+#ifdef SHOW_WORKING
+#define merge_lines(a, b, c, d, e, f, g, h) \
+ merge_lines(a, b, c, d, e, f, g, h, __FUNCTION__)
+#endif
+
+/* Return 0 if the given lines are not in the same equivalence class, 1 if they
+ * are known identical, or 2 if they are known opposite */
+#if 0
+static int lines_related(solver_state *sstate,
+ int x1, int y1, enum direction d1,
+ int x2, int y2, enum direction d2)
+{
+ int i, j, inv1, inv2;
+
+ i = LINEDSF_INDEX(sstate->state, x1, y1, d1);
+ j = LINEDSF_INDEX(sstate->state, x2, y2, d2);
+
+ i = edsf_canonify(sstate->hard->linedsf, i, &inv1);
+ j = edsf_canonify(sstate->hard->linedsf, j, &inv2);
+
+ if (i == j)
+ return (inv1 == inv2) ? 1 : 2;
+ else
+ return 0;
+}
+#endif
+
+/* Count the number of lines of a particular type currently going into the
+ * given dot. Lines going off the edge of the board are assumed fixed no. */
+static int dot_order(const game_state* state, int i, int j, char line_type)
+{
+ int n = 0;
+
+ if (i > 0) {
+ if (line_type == LV_LEFTOF_DOT(state, i, j))
+ ++n;
+ } else {
+ if (line_type == LINE_NO)
+ ++n;
+ }
+ if (i < state->w) {
+ if (line_type == LV_RIGHTOF_DOT(state, i, j))
+ ++n;
+ } else {
+ if (line_type == LINE_NO)
+ ++n;
+ }
+ if (j > 0) {
+ if (line_type == LV_ABOVE_DOT(state, i, j))
+ ++n;
+ } else {
+ if (line_type == LINE_NO)
+ ++n;
+ }
+ if (j < state->h) {
+ if (line_type == LV_BELOW_DOT(state, i, j))
+ ++n;
+ } else {
+ if (line_type == LINE_NO)
+ ++n;
+ }
+
+ return n;
+}
+
+/* Count the number of lines of a particular type currently surrounding the
+ * given square */
+static int square_order(const game_state* state, int i, int j, char line_type)
+{
+ int n = 0;
+
+ if (ABOVE_SQUARE(state, i, j) == line_type)
+ ++n;
+ if (BELOW_SQUARE(state, i, j) == line_type)
+ ++n;
+ if (LEFTOF_SQUARE(state, i, j) == line_type)
+ ++n;
+ if (RIGHTOF_SQUARE(state, i, j) == 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 i, int j,
+ char old_type, char new_type)
+{
+ int retval = FALSE, r;
+ game_state *state = sstate->state;
+
+ if (old_type == new_type)
+ return FALSE;
+
+ if (i > 0 && LEFTOF_DOT(state, i, j) == old_type) {
+ r = set_line_bydot(sstate, i, j, LEFT, new_type);
+ assert(r == TRUE);
+ retval = TRUE;
+ }
+
+ if (i < state->w && RIGHTOF_DOT(state, i, j) == old_type) {
+ r = set_line_bydot(sstate, i, j, RIGHT, new_type);
+ assert(r == TRUE);
+ retval = TRUE;
+ }
+
+ if (j > 0 && ABOVE_DOT(state, i, j) == old_type) {
+ r = set_line_bydot(sstate, i, j, UP, new_type);
+ assert(r == TRUE);
+ retval = TRUE;
+ }
+
+ if (j < state->h && BELOW_DOT(state, i, j) == old_type) {
+ r = set_line_bydot(sstate, i, j, DOWN, new_type);
+ assert(r == TRUE);
+ retval = TRUE;
+ }
+
+ return retval;
+}
+
+/* Set all lines bordering a square of type old_type to type new_type */
+static int square_setall(solver_state *sstate, int i, int j,
+ char old_type, char new_type)
+{
+ int r = FALSE;
+ game_state *state = sstate->state;
+
+#if 0
+ fprintf(stderr, "square_setall [%d,%d] from %d to %d\n", i, j,
+ old_type, new_type);
+#endif
+ if (ABOVE_SQUARE(state, i, j) == old_type) {
+ r = set_line_bydot(sstate, i, j, RIGHT, new_type);
+ assert(r == TRUE);
+ }
+ if (BELOW_SQUARE(state, i, j) == old_type) {
+ r = set_line_bydot(sstate, i, j+1, RIGHT, new_type);
+ assert(r == TRUE);
+ }
+ if (LEFTOF_SQUARE(state, i, j) == old_type) {
+ r = set_line_bydot(sstate, i, j, DOWN, new_type);
+ assert(r == TRUE);
+ }
+ if (RIGHTOF_SQUARE(state, i, j) == old_type) {
+ r = set_line_bydot(sstate, i+1, j, DOWN, new_type);
+ assert(r == TRUE);
+ }
+
+ return r;
+}
+
+/* ----------------------------------------------------------------------
+ * Loop generation and clue removal
+ */
+
+/* We're going to store a list of current candidate squares for lighting.
+ * Each square gets a 'score', which tells us how adding that square right
+ * now would affect the length of the solution loop. We're trying to
+ * maximise that quantity so will bias our random selection of squares to
+ * light towards those with high scores */
+struct square {
+ int score;
+ unsigned long random;
+ int x, y;
+};
+
+static int get_square_cmpfn(void *v1, void *v2)
+{
+ struct square *s1 = v1;
+ struct square *s2 = v2;
+ int r;
+
+ r = s1->x - s2->x;
+ if (r)
+ return r;
+
+ r = s1->y - s2->y;
+ if (r)
+ return r;
+
+ return 0;
+}