+ for (i = 0; i < h; i++) {
+ edgestate[(i * w + w-1) * 5 + 1] = edgestate[(i * w) * 5 + 4] = 2;
+ }
+ }
+
+ /*
+ * If we have barriers available, we can mark those edges as
+ * closed too.
+ */
+ if (barriers) {
+ for (y = 0; y < h; y++) for (x = 0; x < w; x++) {
+ int d;
+ for (d = 1; d <= 8; d += d) {
+ if (barriers[y*w+x] & d) {
+ int x2, y2;
+ /*
+ * In principle the barrier list should already
+ * contain each barrier from each side, but
+ * let's not take chances with our internal
+ * consistency.
+ */
+ OFFSETWH(x2, y2, x, y, d, w, h);
+ edgestate[(y*w+x) * 5 + d] = 2;
+ edgestate[(y2*w+x2) * 5 + F(d)] = 2;
+ }
+ }
+ }
+ }
+
+ /*
+ * Since most deductions made by this solver are local (the
+ * exception is loop avoidance, where joining two tiles
+ * together on one side of the grid can theoretically permit a
+ * fresh deduction on the other), we can address the scaling
+ * problem inherent in iterating repeatedly over the entire
+ * grid by instead working with a to-do list.
+ */
+ todo = todo_new(w * h);
+
+ /*
+ * Main deductive loop.
+ */
+ done_something = TRUE; /* prevent instant termination! */
+ while (1) {
+ int index;
+
+ /*
+ * Take a tile index off the todo list and process it.
+ */
+ index = todo_get(todo);
+ if (index == -1) {
+ /*
+ * If we have run out of immediate things to do, we
+ * have no choice but to scan the whole grid for
+ * longer-range things we've missed. Hence, I now add
+ * every square on the grid back on to the to-do list.
+ * I also set `done_something' to FALSE at this point;
+ * if we later come back here and find it still FALSE,
+ * we will know we've scanned the entire grid without
+ * finding anything new to do, and we can terminate.
+ */
+ if (!done_something)
+ break;
+ for (i = 0; i < w*h; i++)
+ todo_add(todo, i);
+ done_something = FALSE;
+
+ index = todo_get(todo);
+ }
+
+ y = index / w;
+ x = index % w;
+ {
+ int d, ourclass = dsf_canonify(equivalence, y*w+x);
+ int deadendmax[9];
+
+ deadendmax[1] = deadendmax[2] = deadendmax[4] = deadendmax[8] = 0;
+
+ for (i = j = 0; i < 4 && tilestate[(y*w+x) * 4 + i] != 255; i++) {
+ int valid;
+ int nnondeadends, nondeadends[4], deadendtotal;
+ int nequiv, equiv[5];
+ int val = tilestate[(y*w+x) * 4 + i];
+
+ valid = TRUE;
+ nnondeadends = deadendtotal = 0;
+ equiv[0] = ourclass;
+ nequiv = 1;
+ for (d = 1; d <= 8; d += d) {
+ /*
+ * Immediately rule out this orientation if it
+ * conflicts with any known edge.
+ */
+ if ((edgestate[(y*w+x) * 5 + d] == 1 && !(val & d)) ||
+ (edgestate[(y*w+x) * 5 + d] == 2 && (val & d)))
+ valid = FALSE;
+
+ if (val & d) {
+ /*
+ * Count up the dead-end statistics.
+ */
+ if (deadends[(y*w+x) * 5 + d] <= area) {
+ deadendtotal += deadends[(y*w+x) * 5 + d];
+ } else {
+ nondeadends[nnondeadends++] = d;
+ }
+
+ /*
+ * Ensure we aren't linking to any tiles,
+ * through edges not already known to be
+ * open, which create a loop.
+ */
+ if (edgestate[(y*w+x) * 5 + d] == 0) {
+ int c, k, x2, y2;
+
+ OFFSETWH(x2, y2, x, y, d, w, h);
+ c = dsf_canonify(equivalence, y2*w+x2);
+ for (k = 0; k < nequiv; k++)
+ if (c == equiv[k])
+ break;
+ if (k == nequiv)
+ equiv[nequiv++] = c;
+ else
+ valid = FALSE;
+ }
+ }
+ }
+
+ if (nnondeadends == 0) {
+ /*
+ * If this orientation links together dead-ends
+ * with a total area of less than the entire
+ * grid, it is invalid.
+ *
+ * (We add 1 to deadendtotal because of the
+ * tile itself, of course; one tile linking
+ * dead ends of size 2 and 3 forms a subnetwork
+ * with a total area of 6, not 5.)
+ */
+ if (deadendtotal > 0 && deadendtotal+1 < area)
+ valid = FALSE;
+ } else if (nnondeadends == 1) {
+ /*
+ * If this orientation links together one or
+ * more dead-ends with precisely one
+ * non-dead-end, then we may have to mark that
+ * non-dead-end as a dead end going the other
+ * way. However, it depends on whether all
+ * other orientations share the same property.
+ */
+ deadendtotal++;
+ if (deadendmax[nondeadends[0]] < deadendtotal)
+ deadendmax[nondeadends[0]] = deadendtotal;
+ } else {
+ /*
+ * If this orientation links together two or
+ * more non-dead-ends, then we can rule out the
+ * possibility of putting in new dead-end
+ * markings in those directions.
+ */
+ int k;
+ for (k = 0; k < nnondeadends; k++)
+ deadendmax[nondeadends[k]] = area+1;
+ }
+
+ if (valid)
+ tilestate[(y*w+x) * 4 + j++] = val;
+#ifdef SOLVER_DIAGNOSTICS
+ else
+ printf("ruling out orientation %x at %d,%d\n", val, x, y);
+#endif
+ }
+
+ assert(j > 0); /* we can't lose _all_ possibilities! */
+
+ if (j < i) {
+ done_something = TRUE;
+
+ /*
+ * We have ruled out at least one tile orientation.
+ * Make sure the rest are blanked.
+ */
+ while (j < 4)
+ tilestate[(y*w+x) * 4 + j++] = 255;
+ }
+
+ /*
+ * Now go through the tile orientations again and see
+ * if we've deduced anything new about any edges.
+ */
+ {
+ int a, o;
+ a = 0xF; o = 0;
+
+ for (i = 0; i < 4 && tilestate[(y*w+x) * 4 + i] != 255; i++) {
+ a &= tilestate[(y*w+x) * 4 + i];
+ o |= tilestate[(y*w+x) * 4 + i];
+ }
+ for (d = 1; d <= 8; d += d)
+ if (edgestate[(y*w+x) * 5 + d] == 0) {
+ int x2, y2, d2;
+ OFFSETWH(x2, y2, x, y, d, w, h);
+ d2 = F(d);
+ if (a & d) {
+ /* This edge is open in all orientations. */
+#ifdef SOLVER_DIAGNOSTICS
+ printf("marking edge %d,%d:%d open\n", x, y, d);
+#endif
+ edgestate[(y*w+x) * 5 + d] = 1;
+ edgestate[(y2*w+x2) * 5 + d2] = 1;
+ dsf_merge(equivalence, y*w+x, y2*w+x2);
+ done_something = TRUE;
+ todo_add(todo, y2*w+x2);
+ } else if (!(o & d)) {
+ /* This edge is closed in all orientations. */
+#ifdef SOLVER_DIAGNOSTICS
+ printf("marking edge %d,%d:%d closed\n", x, y, d);
+#endif
+ edgestate[(y*w+x) * 5 + d] = 2;
+ edgestate[(y2*w+x2) * 5 + d2] = 2;
+ done_something = TRUE;
+ todo_add(todo, y2*w+x2);
+ }
+ }
+
+ }
+
+ /*
+ * Now check the dead-end markers and see if any of
+ * them has lowered from the real ones.
+ */
+ for (d = 1; d <= 8; d += d) {
+ int x2, y2, d2;
+ OFFSETWH(x2, y2, x, y, d, w, h);
+ d2 = F(d);
+ if (deadendmax[d] > 0 &&
+ deadends[(y2*w+x2) * 5 + d2] > deadendmax[d]) {
+#ifdef SOLVER_DIAGNOSTICS
+ printf("setting dead end value %d,%d:%d to %d\n",
+ x2, y2, d2, deadendmax[d]);
+#endif
+ deadends[(y2*w+x2) * 5 + d2] = deadendmax[d];
+ done_something = TRUE;
+ todo_add(todo, y2*w+x2);
+ }
+ }
+
+ }
+ }
+
+ /*
+ * Mark all completely determined tiles as locked.
+ */
+ j = TRUE;
+ for (i = 0; i < w*h; i++) {
+ if (tilestate[i * 4 + 1] == 255) {
+ assert(tilestate[i * 4 + 0] != 255);
+ tiles[i] = tilestate[i * 4] | LOCKED;
+ } else {
+ tiles[i] &= ~LOCKED;
+ j = FALSE;
+ }
+ }
+
+ /*
+ * Free up working space.
+ */
+ todo_free(todo);
+ sfree(tilestate);
+ sfree(edgestate);
+ sfree(deadends);
+ sfree(equivalence);
+
+ return j;
+}
+
+/* ----------------------------------------------------------------------
+ * Randomly select a new game description.
+ */
+
+/*
+ * Function to randomly perturb an ambiguous section in a grid, to
+ * attempt to ensure unique solvability.
+ */
+static void perturb(int w, int h, unsigned char *tiles, int wrapping,
+ random_state *rs, int startx, int starty, int startd)
+{
+ struct xyd *perimeter, *perim2, *loop[2], looppos[2];
+ int nperim, perimsize, nloop[2], loopsize[2];
+ int x, y, d, i;
+
+ /*
+ * We know that the tile at (startx,starty) is part of an
+ * ambiguous section, and we also know that its neighbour in
+ * direction startd is fully specified. We begin by tracing all
+ * the way round the ambiguous area.
+ */
+ nperim = perimsize = 0;
+ perimeter = NULL;
+ x = startx;
+ y = starty;
+ d = startd;
+#ifdef PERTURB_DIAGNOSTICS
+ printf("perturb %d,%d:%d\n", x, y, d);
+#endif
+ do {
+ int x2, y2, d2;
+
+ if (nperim >= perimsize) {
+ perimsize = perimsize * 3 / 2 + 32;
+ perimeter = sresize(perimeter, perimsize, struct xyd);
+ }
+ perimeter[nperim].x = x;
+ perimeter[nperim].y = y;
+ perimeter[nperim].direction = d;
+ nperim++;
+#ifdef PERTURB_DIAGNOSTICS
+ printf("perimeter: %d,%d:%d\n", x, y, d);
+#endif
+
+ /*
+ * First, see if we can simply turn left from where we are
+ * and find another locked square.
+ */
+ d2 = A(d);
+ OFFSETWH(x2, y2, x, y, d2, w, h);
+ if ((!wrapping && (abs(x2-x) > 1 || abs(y2-y) > 1)) ||
+ (tiles[y2*w+x2] & LOCKED)) {
+ d = d2;
+ } else {
+ /*
+ * Failing that, step left into the new square and look
+ * in front of us.
+ */
+ x = x2;
+ y = y2;
+ OFFSETWH(x2, y2, x, y, d, w, h);
+ if ((wrapping || (abs(x2-x) <= 1 && abs(y2-y) <= 1)) &&
+ !(tiles[y2*w+x2] & LOCKED)) {
+ /*
+ * And failing _that_, we're going to have to step
+ * forward into _that_ square and look right at the
+ * same locked square as we started with.
+ */
+ x = x2;
+ y = y2;
+ d = C(d);
+ }
+ }
+
+ } while (x != startx || y != starty || d != startd);
+
+ /*
+ * Our technique for perturbing this ambiguous area is to
+ * search round its edge for a join we can make: that is, an
+ * edge on the perimeter which is (a) not currently connected,
+ * and (b) connecting it would not yield a full cross on either
+ * side. Then we make that join, search round the network to
+ * find the loop thus constructed, and sever the loop at a
+ * randomly selected other point.
+ */
+ perim2 = snewn(nperim, struct xyd);
+ memcpy(perim2, perimeter, nperim * sizeof(struct xyd));
+ /* Shuffle the perimeter, so as to search it without directional bias. */
+ shuffle(perim2, nperim, sizeof(*perim2), rs);
+ for (i = 0; i < nperim; i++) {
+ int x2, y2;
+
+ x = perim2[i].x;
+ y = perim2[i].y;
+ d = perim2[i].direction;
+
+ OFFSETWH(x2, y2, x, y, d, w, h);
+ if (!wrapping && (abs(x2-x) > 1 || abs(y2-y) > 1))
+ continue; /* can't link across non-wrapping border */
+ if (tiles[y*w+x] & d)
+ continue; /* already linked in this direction! */
+ if (((tiles[y*w+x] | d) & 15) == 15)
+ continue; /* can't turn this tile into a cross */
+ if (((tiles[y2*w+x2] | F(d)) & 15) == 15)
+ continue; /* can't turn other tile into a cross */
+
+ /*
+ * We've found the point at which we're going to make a new
+ * link.
+ */
+#ifdef PERTURB_DIAGNOSTICS
+ printf("linking %d,%d:%d\n", x, y, d);
+#endif
+ tiles[y*w+x] |= d;
+ tiles[y2*w+x2] |= F(d);
+
+ break;
+ }
+ sfree(perim2);
+
+ if (i == nperim)
+ return; /* nothing we can do! */
+
+ /*
+ * Now we've constructed a new link, we need to find the entire
+ * loop of which it is a part.
+ *
+ * In principle, this involves doing a complete search round
+ * the network. However, I anticipate that in the vast majority
+ * of cases the loop will be quite small, so what I'm going to
+ * do is make _two_ searches round the network in parallel, one
+ * keeping its metaphorical hand on the left-hand wall while
+ * the other keeps its hand on the right. As soon as one of
+ * them gets back to its starting point, I abandon the other.
+ */
+ for (i = 0; i < 2; i++) {
+ loopsize[i] = nloop[i] = 0;
+ loop[i] = NULL;
+ looppos[i].x = x;
+ looppos[i].y = y;
+ looppos[i].direction = d;
+ }
+ while (1) {
+ for (i = 0; i < 2; i++) {
+ int x2, y2, j;
+
+ x = looppos[i].x;
+ y = looppos[i].y;
+ d = looppos[i].direction;
+
+ OFFSETWH(x2, y2, x, y, d, w, h);
+
+ /*
+ * Add this path segment to the loop, unless it exactly
+ * reverses the previous one on the loop in which case
+ * we take it away again.
+ */
+#ifdef PERTURB_DIAGNOSTICS
+ printf("looppos[%d] = %d,%d:%d\n", i, x, y, d);
+#endif
+ if (nloop[i] > 0 &&
+ loop[i][nloop[i]-1].x == x2 &&
+ loop[i][nloop[i]-1].y == y2 &&
+ loop[i][nloop[i]-1].direction == F(d)) {
+#ifdef PERTURB_DIAGNOSTICS
+ printf("removing path segment %d,%d:%d from loop[%d]\n",
+ x2, y2, F(d), i);
+#endif
+ nloop[i]--;
+ } else {
+ if (nloop[i] >= loopsize[i]) {
+ loopsize[i] = loopsize[i] * 3 / 2 + 32;
+ loop[i] = sresize(loop[i], loopsize[i], struct xyd);
+ }
+#ifdef PERTURB_DIAGNOSTICS
+ printf("adding path segment %d,%d:%d to loop[%d]\n",
+ x, y, d, i);
+#endif
+ loop[i][nloop[i]++] = looppos[i];
+ }
+
+#ifdef PERTURB_DIAGNOSTICS
+ printf("tile at new location is %x\n", tiles[y2*w+x2] & 0xF);
+#endif
+ d = F(d);
+ for (j = 0; j < 4; j++) {
+ if (i == 0)
+ d = A(d);
+ else
+ d = C(d);
+#ifdef PERTURB_DIAGNOSTICS
+ printf("trying dir %d\n", d);
+#endif
+ if (tiles[y2*w+x2] & d) {
+ looppos[i].x = x2;
+ looppos[i].y = y2;
+ looppos[i].direction = d;
+ break;
+ }
+ }
+
+ assert(j < 4);
+ assert(nloop[i] > 0);
+
+ if (looppos[i].x == loop[i][0].x &&
+ looppos[i].y == loop[i][0].y &&
+ looppos[i].direction == loop[i][0].direction) {
+#ifdef PERTURB_DIAGNOSTICS
+ printf("loop %d finished tracking\n", i);
+#endif
+
+ /*
+ * Having found our loop, we now sever it at a
+ * randomly chosen point - absolutely any will do -
+ * which is not the one we joined it at to begin
+ * with. Conveniently, the one we joined it at is
+ * loop[i][0], so we just avoid that one.
+ */
+ j = random_upto(rs, nloop[i]-1) + 1;
+ x = loop[i][j].x;
+ y = loop[i][j].y;
+ d = loop[i][j].direction;
+ OFFSETWH(x2, y2, x, y, d, w, h);
+ tiles[y*w+x] &= ~d;
+ tiles[y2*w+x2] &= ~F(d);
+
+ break;
+ }