+struct setscratch {
+ int x, y;
+ int n;
+};
+
+#define SCRATCHSZ (state->w+state->h)
+
+/* New solver algorithm: overlapping sets can add IMPOSSIBLE flags.
+ * Algorithm thanks to Simon:
+ *
+ * (a) Any square where you can place a light has a set of squares
+ * which would become non-lights as a result. (This includes
+ * squares lit by the first square, and can also include squares
+ * adjacent to the same clue square if the new light is the last
+ * one around that clue.) Call this MAKESDARK(x,y) with (x,y) being
+ * the square you place a light.
+
+ * (b) Any unlit square has a set of squares on which you could place
+ * a light to illuminate it. (Possibly including itself, of
+ * course.) This set of squares has the property that _at least
+ * one_ of them must contain a light. Sets of this type also arise
+ * from clue squares. Call this MAKESLIGHT(x,y), again with (x,y)
+ * the square you would place a light.
+
+ * (c) If there exists (dx,dy) and (lx,ly) such that MAKESDARK(dx,dy) is
+ * a superset of MAKESLIGHT(lx,ly), this implies that placing a light at
+ * (dx,dy) would either leave no remaining way to illuminate a certain
+ * square, or would leave no remaining way to fulfill a certain clue
+ * (at lx,ly). In either case, a light can be ruled out at that position.
+ *
+ * So, we construct all possible MAKESLIGHT sets, both from unlit squares
+ * and clue squares, and then we look for plausible MAKESDARK sets that include
+ * our (lx,ly) to see if we can find a (dx,dy) to rule out. By the time we have
+ * constructed the MAKESLIGHT set we don't care about (lx,ly), just the set
+ * members.
+ *
+ * Once we have such a set, Simon came up with a Cunning Plan to find
+ * the most sensible MAKESDARK candidate:
+ *
+ * (a) for each square S in your set X, find all the squares which _would_
+ * rule it out. That means any square which would light S, plus
+ * any square adjacent to the same clue square as S (provided
+ * that clue square has only one remaining light to be placed).
+ * It's not hard to make this list. Don't do anything with this
+ * data at the moment except _count_ the squares.
+
+ * (b) Find the square S_min in the original set which has the
+ * _smallest_ number of other squares which would rule it out.
+
+ * (c) Find all the squares that rule out S_min (it's probably
+ * better to recompute this than to have stored it during step
+ * (a), since the CPU requirement is modest but the storage
+ * cost would get ugly.) For each of these squares, see if it
+ * rules out everything else in the set X. Any which does can
+ * be marked as not-a-light.
+ *
+ */
+
+typedef void (*trl_cb)(game_state *state, int dx, int dy,
+ struct setscratch *scratch, int n, void *ctx);
+
+static void try_rule_out(game_state *state, int x, int y,
+ struct setscratch *scratch, int n,
+ trl_cb cb, void *ctx);
+
+static void trl_callback_search(game_state *state, int dx, int dy,
+ struct setscratch *scratch, int n, void *ignored)
+{
+ int i;
+
+#ifdef SOLVER_DIAGNOSTICS
+ if (verbose) debug(("discount cb: light at (%d,%d)\n", dx, dy));
+#endif
+
+ for (i = 0; i < n; i++) {
+ if (dx == scratch[i].x && dy == scratch[i].y) {
+ scratch[i].n = 1;
+ return;
+ }
+ }
+}
+
+static void trl_callback_discount(game_state *state, int dx, int dy,
+ struct setscratch *scratch, int n, void *ctx)
+{
+ int *didsth = (int *)ctx;
+ int i;
+
+ if (GRID(state,flags,dx,dy) & F_IMPOSSIBLE) {
+#ifdef SOLVER_DIAGNOSTICS
+ debug(("Square at (%d,%d) already impossible.\n", dx,dy));
+#endif
+ return;
+ }
+
+ /* Check whether a light at (dx,dy) rules out everything
+ * in scratch, and mark (dx,dy) as IMPOSSIBLE if it does.
+ * We can use try_rule_out for this as well, as the set of
+ * squares which would rule out (x,y) is the same as the
+ * set of squares which (x,y) would rule out. */
+
+#ifdef SOLVER_DIAGNOSTICS
+ if (verbose) debug(("Checking whether light at (%d,%d) rules out everything in scratch.\n", dx, dy));
+#endif
+
+ for (i = 0; i < n; i++)
+ scratch[i].n = 0;
+ try_rule_out(state, dx, dy, scratch, n, trl_callback_search, NULL);
+ for (i = 0; i < n; i++) {
+ if (scratch[i].n == 0) return;
+ }
+ /* The light ruled out everything in scratch. Yay. */
+ GRID(state,flags,dx,dy) |= F_IMPOSSIBLE;
+#ifdef SOLVER_DIAGNOSTICS
+ debug(("Set reduction discounted square at (%d,%d):\n", dx,dy));
+ if (verbose) debug_state(state);
+#endif
+
+ *didsth = 1;
+}
+
+static void trl_callback_incn(game_state *state, int dx, int dy,
+ struct setscratch *scratch, int n, void *ctx)
+{
+ struct setscratch *s = (struct setscratch *)ctx;
+ s->n++;
+}
+
+static void try_rule_out(game_state *state, int x, int y,
+ struct setscratch *scratch, int n,
+ trl_cb cb, void *ctx)
+{
+ /* XXX Find all the squares which would rule out (x,y); anything
+ * that would light it as well as squares adjacent to same clues
+ * as X assuming that clue only has one remaining light.
+ * Call the callback with each square. */
+ ll_data lld;
+ surrounds s, ss;
+ int i, j, curr_lights, tot_lights;
+
+ /* Find all squares that would rule out a light at (x,y) and call trl_cb
+ * with them: anything that would light (x,y)... */
+
+ list_lights(state, x, y, 0, &lld);
+ FOREACHLIT(&lld, { if (could_place_light_xy(state, lx, ly)) { cb(state, lx, ly, scratch, n, ctx); } });
+
+ /* ... as well as any empty space (that isn't x,y) next to any clue square
+ * next to (x,y) that only has one light left to place. */
+
+ get_surrounds(state, x, y, &s);
+ for (i = 0; i < s.npoints; i++) {
+ if (!GRID(state,flags,s.points[i].x,s.points[i].y) & F_NUMBERED)
+ continue;
+ /* we have an adjacent clue square; find /it's/ surrounds
+ * and count the remaining lights it needs. */
+ get_surrounds(state,s.points[i].x,s.points[i].y,&ss);
+ curr_lights = 0;
+ for (j = 0; j < ss.npoints; j++) {
+ if (GRID(state,flags,ss.points[j].x,ss.points[j].y) & F_LIGHT)
+ curr_lights++;
+ }
+ tot_lights = GRID(state, lights, s.points[i].x, s.points[i].y);
+ /* We have a clue with tot_lights to fill, and curr_lights currently
+ * around it. If adding a light at (x,y) fills up the clue (i.e.
+ * curr_lights + 1 = tot_lights) then we need to discount all other
+ * unlit squares around the clue. */
+ if ((curr_lights + 1) == tot_lights) {
+ for (j = 0; j < ss.npoints; j++) {
+ int lx = ss.points[j].x, ly = ss.points[j].y;
+ if (lx == x && ly == y) continue;
+ if (could_place_light_xy(state, lx, ly))
+ cb(state, lx, ly, scratch, n, ctx);
+ }
+ }
+ }
+}
+
+#ifdef SOLVER_DIAGNOSTICS
+static void debug_scratch(const char *msg, struct setscratch *scratch, int n)
+{
+ int i;
+ debug(("%s scratch (%d elements):\n", msg, n));
+ for (i = 0; i < n; i++) {
+ debug((" (%d,%d) n%d\n", scratch[i].x, scratch[i].y, scratch[i].n));
+ }
+}
+#endif
+
+static int discount_set(game_state *state,
+ struct setscratch *scratch, int n)
+{
+ int i, besti, bestn, didsth = 0;
+
+#ifdef SOLVER_DIAGNOSTICS
+ if (verbose > 1) debug_scratch("discount_set", scratch, n);
+#endif
+ if (n == 0) return 0;
+
+ for (i = 0; i < n; i++) {
+ try_rule_out(state, scratch[i].x, scratch[i].y, scratch, n,
+ trl_callback_incn, (void*)&(scratch[i]));
+ }
+#ifdef SOLVER_DIAGNOSTICS
+ if (verbose > 1) debug_scratch("discount_set after count", scratch, n);
+#endif
+
+ besti = -1; bestn = SCRATCHSZ;
+ for (i = 0; i < n; i++) {
+ if (scratch[i].n < bestn) {
+ bestn = scratch[i].n;
+ besti = i;
+ }
+ }
+#ifdef SOLVER_DIAGNOSTICS
+ if (verbose > 1) debug(("best square (%d,%d) with n%d.\n",
+ scratch[besti].x, scratch[besti].y, scratch[besti].n));
+#endif
+ try_rule_out(state, scratch[besti].x, scratch[besti].y, scratch, n,
+ trl_callback_discount, (void*)&didsth);
+#ifdef SOLVER_DIAGNOSTICS
+ if (didsth) debug((" [from square (%d,%d)]\n",
+ scratch[besti].x, scratch[besti].y));
+#endif
+
+ return didsth;
+}
+
+static void discount_clear(game_state *state, struct setscratch *scratch, int *n)
+{
+ *n = 0;
+ memset(scratch, 0, SCRATCHSZ * sizeof(struct setscratch));
+}
+
+static void unlit_cb(game_state *state, int lx, int ly,
+ struct setscratch *scratch, int *n)
+{
+ if (could_place_light_xy(state, lx, ly)) {
+ scratch[*n].x = lx; scratch[*n].y = ly; (*n)++;
+ }
+}
+
+/* Construct a MAKESLIGHT set from an unlit square. */
+static int discount_unlit(game_state *state, int x, int y,
+ struct setscratch *scratch)
+{
+ ll_data lld;
+ int n, didsth;
+
+#ifdef SOLVER_DIAGNOSTICS
+ if (verbose) debug(("Trying to discount for unlit square at (%d,%d).\n", x, y));
+ if (verbose > 1) debug_state(state);
+#endif
+
+ discount_clear(state, scratch, &n);
+
+ list_lights(state, x, y, 1, &lld);
+ FOREACHLIT(&lld, { unlit_cb(state, lx, ly, scratch, &n); });
+ didsth = discount_set(state, scratch, n);
+#ifdef SOLVER_DIAGNOSTICS
+ if (didsth) debug((" [from unlit square at (%d,%d)].\n", x, y));
+#endif
+ return didsth;
+
+}
+
+/* Construct a series of MAKESLIGHT sets from a clue square.
+ * for a clue square with N remaining spaces that must contain M lights, every
+ * subset of size N-M+1 of those N spaces forms such a set.
+ */
+
+static int discount_clue(game_state *state, int x, int y,
+ struct setscratch *scratch)
+{
+ int slen, m = GRID(state, lights, x, y), n, i, didsth = 0, lights;
+ unsigned int flags;
+ surrounds s, sempty;
+ combi_ctx *combi;
+
+ if (m == 0) return 0;
+
+#ifdef SOLVER_DIAGNOSTICS
+ if (verbose) debug(("Trying to discount for sets at clue (%d,%d).\n", x, y));
+ if (verbose > 1) debug_state(state);
+#endif
+
+ /* m is no. of lights still to place; starts off at the clue value
+ * and decreases when we find a light already down.
+ * n is no. of spaces left; starts off at 0 and goes up when we find
+ * a plausible space. */
+
+ get_surrounds(state, x, y, &s);
+ memset(&sempty, 0, sizeof(surrounds));
+ for (i = 0; i < s.npoints; i++) {
+ int lx = s.points[i].x, ly = s.points[i].y;
+ flags = GRID(state,flags,lx,ly);
+ lights = GRID(state,lights,lx,ly);
+
+ if (flags & F_LIGHT) m--;
+
+ if (could_place_light(flags, lights)) {
+ sempty.points[sempty.npoints].x = lx;
+ sempty.points[sempty.npoints].y = ly;
+ sempty.npoints++;
+ }
+ }
+ n = sempty.npoints; /* sempty is now a surrounds of only blank squares. */
+ if (n == 0) return 0; /* clue is full already. */
+
+ if (m < 0 || m > n) return 0; /* become impossible. */
+
+ combi = new_combi(n - m + 1, n);
+ while (next_combi(combi)) {
+ discount_clear(state, scratch, &slen);
+ for (i = 0; i < combi->r; i++) {
+ scratch[slen].x = sempty.points[combi->a[i]].x;
+ scratch[slen].y = sempty.points[combi->a[i]].y;
+ slen++;
+ }
+ if (discount_set(state, scratch, slen)) didsth = 1;
+ }
+ free_combi(combi);
+#ifdef SOLVER_DIAGNOSTICS
+ if (didsth) debug((" [from clue at (%d,%d)].\n", x, y));
+#endif
+ return didsth;
+}
+
+#define F_SOLVE_FORCEUNIQUE 1
+#define F_SOLVE_DISCOUNTSETS 2
+#define F_SOLVE_ALLOWRECURSE 4
+
+static unsigned int flags_from_difficulty(int difficulty)
+{
+ unsigned int sflags = F_SOLVE_FORCEUNIQUE;
+ assert(difficulty <= DIFFCOUNT);
+ if (difficulty >= 1) sflags |= F_SOLVE_DISCOUNTSETS;
+ if (difficulty >= 2) sflags |= F_SOLVE_ALLOWRECURSE;
+ return sflags;
+}
+
+#define MAXRECURSE 5
+