+
+ } 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) {
+ sfree(perimeter);
+ 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;
+ }
+ }
+ if (i < 2)
+ break;
+ }
+ sfree(loop[0]);
+ sfree(loop[1]);
+
+ /*
+ * Finally, we must mark the entire disputed section as locked,
+ * to prevent the perturb function being called on it multiple
+ * times.
+ *
+ * To do this, we _sort_ the perimeter of the area. The
+ * existing xyd_cmp function will arrange things into columns
+ * for us, in such a way that each column has the edges in
+ * vertical order. Then we can work down each column and fill
+ * in all the squares between an up edge and a down edge.
+ */
+ qsort(perimeter, nperim, sizeof(struct xyd), xyd_cmp);
+ x = y = -1;
+ for (i = 0; i <= nperim; i++) {
+ if (i == nperim || perimeter[i].x > x) {
+ /*
+ * Fill in everything from the last Up edge to the
+ * bottom of the grid, if necessary.
+ */
+ if (x != -1) {
+ while (y < h) {
+#ifdef PERTURB_DIAGNOSTICS
+ printf("resolved: locking tile %d,%d\n", x, y);
+#endif
+ tiles[y * w + x] |= LOCKED;
+ y++;
+ }
+ x = y = -1;
+ }
+
+ if (i == nperim)
+ break;
+
+ x = perimeter[i].x;
+ y = 0;
+ }
+
+ if (perimeter[i].direction == U) {
+ x = perimeter[i].x;
+ y = perimeter[i].y;
+ } else if (perimeter[i].direction == D) {
+ /*
+ * Fill in everything from the last Up edge to here.
+ */
+ assert(x == perimeter[i].x && y <= perimeter[i].y);
+ while (y <= perimeter[i].y) {
+#ifdef PERTURB_DIAGNOSTICS
+ printf("resolved: locking tile %d,%d\n", x, y);
+#endif
+ tiles[y * w + x] |= LOCKED;
+ y++;
+ }
+ x = y = -1;
+ }
+ }
+
+ sfree(perimeter);
+}
+
+static char *new_game_desc(game_params *params, random_state *rs,
+ char **aux, int interactive)
+{
+ tree234 *possibilities, *barriertree;
+ int w, h, x, y, cx, cy, nbarriers;
+ unsigned char *tiles, *barriers;
+ char *desc, *p;
+
+ w = params->width;
+ h = params->height;
+
+ cx = w / 2;
+ cy = h / 2;
+
+ tiles = snewn(w * h, unsigned char);
+ barriers = snewn(w * h, unsigned char);
+
+ begin_generation:
+
+ memset(tiles, 0, w * h);
+ memset(barriers, 0, w * h);
+
+ /*
+ * Construct the unshuffled grid.
+ *
+ * To do this, we simply start at the centre point, repeatedly
+ * choose a random possibility out of the available ways to
+ * extend a used square into an unused one, and do it. After
+ * extending the third line out of a square, we remove the
+ * fourth from the possibilities list to avoid any full-cross
+ * squares (which would make the game too easy because they
+ * only have one orientation).
+ *
+ * The slightly worrying thing is the avoidance of full-cross
+ * squares. Can this cause our unsophisticated construction
+ * algorithm to paint itself into a corner, by getting into a
+ * situation where there are some unreached squares and the
+ * only way to reach any of them is to extend a T-piece into a
+ * full cross?
+ *
+ * Answer: no it can't, and here's a proof.
+ *
+ * Any contiguous group of such unreachable squares must be
+ * surrounded on _all_ sides by T-pieces pointing away from the
+ * group. (If not, then there is a square which can be extended
+ * into one of the `unreachable' ones, and so it wasn't
+ * unreachable after all.) In particular, this implies that
+ * each contiguous group of unreachable squares must be
+ * rectangular in shape (any deviation from that yields a
+ * non-T-piece next to an `unreachable' square).
+ *
+ * So we have a rectangle of unreachable squares, with T-pieces
+ * forming a solid border around the rectangle. The corners of
+ * that border must be connected (since every tile connects all
+ * the lines arriving in it), and therefore the border must
+ * form a closed loop around the rectangle.
+ *
+ * But this can't have happened in the first place, since we
+ * _know_ we've avoided creating closed loops! Hence, no such
+ * situation can ever arise, and the naive grid construction
+ * algorithm will guaranteeably result in a complete grid
+ * containing no unreached squares, no full crosses _and_ no
+ * closed loops. []
+ */
+ possibilities = newtree234(xyd_cmp_nc);
+
+ if (cx+1 < w)
+ add234(possibilities, new_xyd(cx, cy, R));
+ if (cy-1 >= 0)
+ add234(possibilities, new_xyd(cx, cy, U));
+ if (cx-1 >= 0)
+ add234(possibilities, new_xyd(cx, cy, L));
+ if (cy+1 < h)
+ add234(possibilities, new_xyd(cx, cy, D));
+
+ while (count234(possibilities) > 0) {
+ int i;
+ struct xyd *xyd;
+ int x1, y1, d1, x2, y2, d2, d;
+
+ /*
+ * Extract a randomly chosen possibility from the list.
+ */
+ i = random_upto(rs, count234(possibilities));
+ xyd = delpos234(possibilities, i);
+ x1 = xyd->x;
+ y1 = xyd->y;
+ d1 = xyd->direction;
+ sfree(xyd);
+
+ OFFSET(x2, y2, x1, y1, d1, params);
+ d2 = F(d1);
+#ifdef GENERATION_DIAGNOSTICS
+ printf("picked (%d,%d,%c) <-> (%d,%d,%c)\n",
+ x1, y1, "0RU3L567D9abcdef"[d1], x2, y2, "0RU3L567D9abcdef"[d2]);
+#endif
+
+ /*
+ * Make the connection. (We should be moving to an as yet
+ * unused tile.)
+ */
+ index(params, tiles, x1, y1) |= d1;
+ assert(index(params, tiles, x2, y2) == 0);
+ index(params, tiles, x2, y2) |= d2;
+
+ /*
+ * If we have created a T-piece, remove its last
+ * possibility.
+ */
+ if (COUNT(index(params, tiles, x1, y1)) == 3) {
+ struct xyd xyd1, *xydp;
+
+ xyd1.x = x1;
+ xyd1.y = y1;
+ xyd1.direction = 0x0F ^ index(params, tiles, x1, y1);
+
+ xydp = find234(possibilities, &xyd1, NULL);
+
+ if (xydp) {
+#ifdef GENERATION_DIAGNOSTICS
+ printf("T-piece; removing (%d,%d,%c)\n",
+ xydp->x, xydp->y, "0RU3L567D9abcdef"[xydp->direction]);
+#endif
+ del234(possibilities, xydp);
+ sfree(xydp);
+ }
+ }
+
+ /*
+ * Remove all other possibilities that were pointing at the
+ * tile we've just moved into.
+ */
+ for (d = 1; d < 0x10; d <<= 1) {
+ int x3, y3, d3;
+ struct xyd xyd1, *xydp;
+
+ OFFSET(x3, y3, x2, y2, d, params);
+ d3 = F(d);
+
+ xyd1.x = x3;
+ xyd1.y = y3;
+ xyd1.direction = d3;
+
+ xydp = find234(possibilities, &xyd1, NULL);
+
+ if (xydp) {
+#ifdef GENERATION_DIAGNOSTICS
+ printf("Loop avoidance; removing (%d,%d,%c)\n",
+ xydp->x, xydp->y, "0RU3L567D9abcdef"[xydp->direction]);
+#endif
+ del234(possibilities, xydp);
+ sfree(xydp);
+ }
+ }
+
+ /*
+ * Add new possibilities to the list for moving _out_ of
+ * the tile we have just moved into.
+ */
+ for (d = 1; d < 0x10; d <<= 1) {
+ int x3, y3;
+
+ if (d == d2)
+ continue; /* we've got this one already */
+
+ if (!params->wrapping) {
+ if (d == U && y2 == 0)
+ continue;
+ if (d == D && y2 == h-1)
+ continue;
+ if (d == L && x2 == 0)
+ continue;
+ if (d == R && x2 == w-1)
+ continue;
+ }
+
+ OFFSET(x3, y3, x2, y2, d, params);
+
+ if (index(params, tiles, x3, y3))
+ continue; /* this would create a loop */
+
+#ifdef GENERATION_DIAGNOSTICS
+ printf("New frontier; adding (%d,%d,%c)\n",
+ x2, y2, "0RU3L567D9abcdef"[d]);
+#endif
+ add234(possibilities, new_xyd(x2, y2, d));
+ }
+ }
+ /* Having done that, we should have no possibilities remaining. */
+ assert(count234(possibilities) == 0);
+ freetree234(possibilities);
+
+ if (params->unique) {
+ int prevn = -1;
+
+ /*
+ * Run the solver to check unique solubility.
+ */
+ while (!net_solver(w, h, tiles, NULL, params->wrapping)) {
+ int n = 0;
+
+ /*
+ * We expect (in most cases) that most of the grid will
+ * be uniquely specified already, and the remaining
+ * ambiguous sections will be small and separate. So
+ * our strategy is to find each individual such
+ * section, and perform a perturbation on the network
+ * in that area.
+ */
+ for (y = 0; y < h; y++) for (x = 0; x < w; x++) {
+ if (x+1 < w && ((tiles[y*w+x] ^ tiles[y*w+x+1]) & LOCKED)) {
+ n++;
+ if (tiles[y*w+x] & LOCKED)
+ perturb(w, h, tiles, params->wrapping, rs, x+1, y, L);
+ else
+ perturb(w, h, tiles, params->wrapping, rs, x, y, R);
+ }
+ if (y+1 < h && ((tiles[y*w+x] ^ tiles[(y+1)*w+x]) & LOCKED)) {
+ n++;
+ if (tiles[y*w+x] & LOCKED)
+ perturb(w, h, tiles, params->wrapping, rs, x, y+1, U);
+ else
+ perturb(w, h, tiles, params->wrapping, rs, x, y, D);
+ }
+ }
+
+ /*
+ * Now n counts the number of ambiguous sections we
+ * have fiddled with. If we haven't managed to decrease
+ * it from the last time we ran the solver, give up and
+ * regenerate the entire grid.
+ */
+ if (prevn != -1 && prevn <= n)
+ goto begin_generation; /* (sorry) */
+
+ prevn = n;
+ }
+
+ /*
+ * The solver will have left a lot of LOCKED bits lying
+ * around in the tiles array. Remove them.
+ */
+ for (x = 0; x < w*h; x++)
+ tiles[x] &= ~LOCKED;
+ }
+
+ /*
+ * Now compute a list of the possible barrier locations.
+ */
+ barriertree = newtree234(xyd_cmp_nc);
+ for (y = 0; y < h; y++) {
+ for (x = 0; x < w; x++) {
+
+ if (!(index(params, tiles, x, y) & R) &&
+ (params->wrapping || x < w-1))
+ add234(barriertree, new_xyd(x, y, R));
+ if (!(index(params, tiles, x, y) & D) &&
+ (params->wrapping || y < h-1))
+ add234(barriertree, new_xyd(x, y, D));
+ }
+ }
+
+ /*
+ * Save the unshuffled grid in aux.
+ */
+ {
+ char *solution;
+ int i;
+
+ solution = snewn(w * h + 1, char);
+ for (i = 0; i < w * h; i++)
+ solution[i] = "0123456789abcdef"[tiles[i] & 0xF];
+ solution[w*h] = '\0';
+
+ *aux = solution;
+ }
+
+ /*
+ * Now shuffle the grid.
+ *
+ * In order to avoid accidentally generating an already-solved
+ * grid, we will reshuffle as necessary to ensure that at least
+ * one edge has a mismatched connection.
+ *
+ * This can always be done, since validate_params() enforces a
+ * grid area of at least 2 and our generator never creates
+ * either type of rotationally invariant tile (cross and
+ * blank). Hence there must be at least one edge separating
+ * distinct tiles, and it must be possible to find orientations
+ * of those tiles such that one tile is trying to connect
+ * through that edge and the other is not.
+ *
+ * (We could be more subtle, and allow the shuffle to generate
+ * a grid in which all tiles match up locally and the only
+ * criterion preventing the grid from being already solved is
+ * connectedness. However, that would take more effort, and
+ * it's easier to simply make sure every grid is _obviously_
+ * not solved.)
+ */
+ while (1) {
+ int mismatches;
+
+ for (y = 0; y < h; y++) {
+ for (x = 0; x < w; x++) {
+ int orig = index(params, tiles, x, y);
+ int rot = random_upto(rs, 4);
+ index(params, tiles, x, y) = ROT(orig, rot);
+ }
+ }
+
+ mismatches = 0;
+ /*
+ * I can't even be bothered to check for mismatches across
+ * a wrapping edge, so I'm just going to enforce that there
+ * must be a mismatch across a non-wrapping edge, which is
+ * still always possible.
+ */
+ for (y = 0; y < h; y++) for (x = 0; x < w; x++) {
+ if (x+1 < w && ((ROT(index(params, tiles, x, y), 2) ^
+ index(params, tiles, x+1, y)) & L))
+ mismatches++;
+ if (y+1 < h && ((ROT(index(params, tiles, x, y), 2) ^
+ index(params, tiles, x, y+1)) & U))
+ mismatches++;
+ }
+
+ if (mismatches > 0)
+ break;