+ sc->connected[i] = i; /* initially all distinct */
+
+ /*
+ * Establish a disjoint set forest for tracking which squares
+ * are known to slant in the same direction.
+ */
+ for (i = 0; i < w*h; i++)
+ sc->equiv[i] = i; /* initially all distinct */
+
+ /*
+ * Clear the slashval array.
+ */
+ memset(sc->slashval, 0, w*h);
+
+ /*
+ * Initialise the `exits' and `border' arrays. Theses is used
+ * to do second-order loop avoidance: the dual of the no loops
+ * constraint is that every point must be somehow connected to
+ * the border of the grid (otherwise there would be a solid
+ * loop around it which prevented this).
+ *
+ * I define a `dead end' to be a connected group of points
+ * which contains no border point, and which can form at most
+ * one new connection outside itself. Then I forbid placing an
+ * edge so that it connects together two dead-end groups, since
+ * this would yield a non-border-connected isolated subgraph
+ * with no further scope to extend it.
+ */
+ for (y = 0; y < H; y++)
+ for (x = 0; x < W; x++) {
+ if (y == 0 || y == H-1 || x == 0 || x == W-1)
+ sc->border[y*W+x] = TRUE;
+ else
+ sc->border[y*W+x] = FALSE;
+
+ if (clues[y*W+x] < 0)
+ sc->exits[y*W+x] = 4;
+ else
+ sc->exits[y*W+x] = clues[y*W+x];
+ }
+
+ /*
+ * Make a one-off preliminary pass over the grid looking for
+ * starting-point arrangements. The ones we need to spot are:
+ *
+ * - two adjacent 1s in the centre of the grid imply that each
+ * one's single line points towards the other. (If either 1
+ * were connected on the far side, the two squares shared
+ * between the 1s would both link to the other 1 as a
+ * consequence of neither linking to the first.) Thus, we
+ * can fill in the four squares around them.
+ *
+ * - dually, two adjacent 3s imply that each one's _non_-line
+ * points towards the other.
+ *
+ * - if the pair of 1s and 3s is not _adjacent_ but is
+ * separated by one or more 2s, the reasoning still applies.
+ *
+ * This is more advanced than just spotting obvious starting
+ * squares such as central 4s and edge 2s, so we disable it on
+ * DIFF_EASY.
+ *
+ * (I don't like this loop; it feels grubby to me. My
+ * mathematical intuition feels there ought to be some more
+ * general deductive form which contains this loop as a special
+ * case, but I can't bring it to mind right now.)
+ */
+ if (difficulty > DIFF_EASY) {
+ for (y = 1; y+1 < H; y++)
+ for (x = 1; x+1 < W; x++) {
+ int v = clues[y*W+x], s, x2, y2, dx, dy;
+ if (v != 1 && v != 3)
+ continue;
+ /* Slash value of the square up and left of (x,y). */
+ s = (v == 1 ? +1 : -1);
+
+ /* Look in each direction once. */
+ for (dy = 0; dy < 2; dy++) {
+ dx = 1 - dy;
+ x2 = x+dx;
+ y2 = y+dy;
+ if (x2+1 >= W || y2+1 >= H)
+ continue; /* too close to the border */
+ while (x2+dx+1 < W && y2+dy+1 < H && clues[y2*W+x2] == 2)
+ x2 += dx, y2 += dy;
+ if (clues[y2*W+x2] == v) {
+#ifdef SOLVER_DIAGNOSTICS
+ if (verbose)
+ printf("found adjacent %ds at %d,%d and %d,%d\n",
+ v, x, y, x2, y2);
+#endif
+ fill_square(w, h, x-1, y-1, s, soln,
+ sc->connected, sc);
+ fill_square(w, h, x-1+dy, y-1+dx, -s, soln,
+ sc->connected, sc);
+ fill_square(w, h, x2, y2, s, soln,
+ sc->connected, sc);
+ fill_square(w, h, x2-dy, y2-dx, -s, soln,
+ sc->connected, sc);
+ }
+ }
+ }
+ }