+ 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;
+}
+
+static int square_sort_cmpfn(void *v1, void *v2)
+{
+ struct square *s1 = v1;
+ struct square *s2 = v2;
+ int r;
+
+ r = s2->score - s1->score;
+ if (r) {
+ return r;
+ }
+
+ if (s1->random < s2->random)
+ return -1;
+ else if (s1->random > s2->random)
+ return 1;
+
+ /*
+ * It's _just_ possible that two squares might have been given
+ * the same random value. In that situation, fall back to
+ * comparing based on the coordinates. This introduces a tiny
+ * directional bias, but not a significant one.
+ */
+ return get_square_cmpfn(v1, v2);
+}
+
+enum { SQUARE_LIT, SQUARE_UNLIT };
+
+#define SQUARE_STATE(i, j) \
+ ( LEGAL_SQUARE(state, i, j) ? \
+ LV_SQUARE_STATE(i,j) : \
+ SQUARE_UNLIT )
+
+#define LV_SQUARE_STATE(i, j) board[SQUARE_INDEX(state, i, j)]
+
+/* Generate a new complete set of clues for the given game_state (respecting
+ * the dimensions provided by said game_state) */
+static void add_full_clues(game_state *state, random_state *rs)
+{
+ char *clues;
+ char *board;
+ int i, j, a, b, c;
+ int board_area = SQUARE_COUNT(state);
+ int t;
+
+ struct square *square, *tmpsquare, *sq;
+ struct square square_pos;
+
+ /* These will contain exactly the same information, sorted into different
+ * orders */
+ tree234 *lightable_squares_sorted, *lightable_squares_gettable;
+
+#define SQUARE_REACHABLE(i,j) \
+ (t = (SQUARE_STATE(i-1, j) == SQUARE_LIT || \
+ SQUARE_STATE(i+1, j) == SQUARE_LIT || \
+ SQUARE_STATE(i, j-1) == SQUARE_LIT || \
+ SQUARE_STATE(i, j+1) == SQUARE_LIT), \
+ t)
+
+ /* One situation in which we may not light a square is if that'll leave one
+ * square above/below and one left/right of us unlit, separated by a lit
+ * square diagnonal from us */
+#define SQUARE_DIAGONAL_VIOLATION(i, j, h, v) \
+ (t = (SQUARE_STATE((i)+(h), (j)) == SQUARE_UNLIT && \
+ SQUARE_STATE((i), (j)+(v)) == SQUARE_UNLIT && \
+ SQUARE_STATE((i)+(h), (j)+(v)) == SQUARE_LIT), \
+ t)
+
+ /* We also may not light a square if it will form a loop of lit squares
+ * around some unlit squares, as then the game soln won't have a single
+ * loop */
+#define SQUARE_LOOP_VIOLATION(i, j, lit1, lit2) \
+ (SQUARE_STATE((i)+1, (j)) == lit1 && \
+ SQUARE_STATE((i)-1, (j)) == lit1 && \
+ SQUARE_STATE((i), (j)+1) == lit2 && \
+ SQUARE_STATE((i), (j)-1) == lit2)
+
+#define CAN_LIGHT_SQUARE(i, j) \
+ (SQUARE_REACHABLE(i, j) && \
+ !SQUARE_DIAGONAL_VIOLATION(i, j, -1, -1) && \
+ !SQUARE_DIAGONAL_VIOLATION(i, j, +1, -1) && \
+ !SQUARE_DIAGONAL_VIOLATION(i, j, -1, +1) && \
+ !SQUARE_DIAGONAL_VIOLATION(i, j, +1, +1) && \
+ !SQUARE_LOOP_VIOLATION(i, j, SQUARE_LIT, SQUARE_UNLIT) && \
+ !SQUARE_LOOP_VIOLATION(i, j, SQUARE_UNLIT, SQUARE_LIT))
+
+#define IS_LIGHTING_CANDIDATE(i, j) \
+ (SQUARE_STATE(i, j) == SQUARE_UNLIT && \
+ CAN_LIGHT_SQUARE(i,j))
+
+ /* The 'score' of a square reflects its current desirability for selection
+ * as the next square to light. We want to encourage moving into uncharted
+ * areas so we give scores according to how many of the square's neighbours
+ * are currently unlit. */
+
+ /* UNLIT SCORE