+static char *solve_game(const game_state *state, const game_state *currstate,
+ const char *aux, char **error)
+{
+ unsigned char *tiles;
+ char *ret;
+ int retlen, retsize;
+ int i;
+
+ tiles = snewn(state->width * state->height, unsigned char);
+
+ if (!aux) {
+ /*
+ * Run the internal solver on the provided grid. This might
+ * not yield a complete solution.
+ */
+ memcpy(tiles, state->tiles, state->width * state->height);
+ net_solver(state->width, state->height, tiles,
+ state->barriers, state->wrapping);
+ } else {
+ for (i = 0; i < state->width * state->height; i++) {
+ int c = aux[i];
+
+ if (c >= '0' && c <= '9')
+ tiles[i] = c - '0';
+ else if (c >= 'a' && c <= 'f')
+ tiles[i] = c - 'a' + 10;
+ else if (c >= 'A' && c <= 'F')
+ tiles[i] = c - 'A' + 10;
+
+ tiles[i] |= LOCKED;
+ }
+ }
+
+ /*
+ * Now construct a string which can be passed to execute_move()
+ * to transform the current grid into the solved one.
+ */
+ retsize = 256;
+ ret = snewn(retsize, char);
+ retlen = 0;
+ ret[retlen++] = 'S';
+
+ for (i = 0; i < state->width * state->height; i++) {
+ int from = currstate->tiles[i], to = tiles[i];
+ int ft = from & (R|L|U|D), tt = to & (R|L|U|D);
+ int x = i % state->width, y = i / state->width;
+ int chr = '\0';
+ char buf[80], *p = buf;
+
+ if (from == to)
+ continue; /* nothing needs doing at all */
+
+ /*
+ * To transform this tile into the desired tile: first
+ * unlock the tile if it's locked, then rotate it if
+ * necessary, then lock it if necessary.
+ */
+ if (from & LOCKED)
+ p += sprintf(p, ";L%d,%d", x, y);
+
+ if (tt == A(ft))
+ chr = 'A';
+ else if (tt == C(ft))
+ chr = 'C';
+ else if (tt == F(ft))
+ chr = 'F';
+ else {
+ assert(tt == ft);
+ chr = '\0';
+ }
+ if (chr)
+ p += sprintf(p, ";%c%d,%d", chr, x, y);
+
+ if (to & LOCKED)
+ p += sprintf(p, ";L%d,%d", x, y);
+
+ if (p > buf) {
+ if (retlen + (p - buf) >= retsize) {
+ retsize = retlen + (p - buf) + 512;
+ ret = sresize(ret, retsize, char);
+ }
+ memcpy(ret+retlen, buf, p - buf);
+ retlen += p - buf;
+ }
+ }
+
+ assert(retlen < retsize);
+ ret[retlen] = '\0';
+ ret = sresize(ret, retlen+1, char);
+
+ sfree(tiles);
+
+ return ret;
+}
+
+static int game_can_format_as_text_now(const game_params *params)
+{
+ return TRUE;
+}
+
+static char *game_text_format(const game_state *state)
+{
+ return NULL;
+}
+
+/* ----------------------------------------------------------------------
+ * Utility routine.
+ */
+
+/*
+ * Compute which squares are reachable from the centre square, as a
+ * quick visual aid to determining how close the game is to
+ * completion. This is also a simple way to tell if the game _is_
+ * completed - just call this function and see whether every square
+ * is marked active.
+ */
+static unsigned char *compute_active(const game_state *state, int cx, int cy)
+{
+ unsigned char *active;
+ tree234 *todo;
+ struct xyd *xyd;
+
+ active = snewn(state->width * state->height, unsigned char);
+ memset(active, 0, state->width * state->height);
+
+ /*
+ * We only store (x,y) pairs in todo, but it's easier to reuse
+ * xyd_cmp and just store direction 0 every time.
+ */
+ todo = newtree234(xyd_cmp_nc);
+ index(state, active, cx, cy) = ACTIVE;
+ add234(todo, new_xyd(cx, cy, 0));
+
+ while ( (xyd = delpos234(todo, 0)) != NULL) {
+ int x1, y1, d1, x2, y2, d2;
+
+ x1 = xyd->x;
+ y1 = xyd->y;
+ sfree(xyd);
+
+ for (d1 = 1; d1 < 0x10; d1 <<= 1) {
+ OFFSET(x2, y2, x1, y1, d1, state);
+ d2 = F(d1);
+
+ /*
+ * If the next tile in this direction is connected to
+ * us, and there isn't a barrier in the way, and it
+ * isn't already marked active, then mark it active and
+ * add it to the to-examine list.
+ */
+ if ((tile(state, x1, y1) & d1) &&
+ (tile(state, x2, y2) & d2) &&
+ !(barrier(state, x1, y1) & d1) &&
+ !index(state, active, x2, y2)) {
+ index(state, active, x2, y2) = ACTIVE;
+ add234(todo, new_xyd(x2, y2, 0));
+ }
+ }
+ }
+ /* Now we expect the todo list to have shrunk to zero size. */
+ assert(count234(todo) == 0);
+ freetree234(todo);
+
+ return active;
+}
+
+static int *compute_loops_inner(int w, int h, int wrapping,
+ const unsigned char *tiles,
+ const unsigned char *barriers)
+{
+ int *loops, *dsf;
+ int x, y;
+
+ /*
+ * The loop-detecting algorithm I use here is not quite the same
+ * one as I've used in Slant and Loopy. Those two puzzles use a
+ * very similar algorithm which works by finding connected
+ * components, not of the graph _vertices_, but of the pieces of
+ * space in between them. You divide the plane into maximal areas
+ * that can't be intersected by a grid edge (faces in Loopy,
+ * diamond shapes centred on a grid edge in Slant); you form a dsf
+ * over those areas, and unify any pair _not_ separated by a graph
+ * edge; then you've identified the connected components of the
+ * space, and can now immediately tell whether an edge is part of
+ * a loop or not by checking whether the pieces of space on either
+ * side of it are in the same component.
+ *
+ * In Net, this doesn't work reliably, because of the toroidal
+ * wrapping mode. A torus has non-trivial homology, which is to
+ * say, there can exist a closed loop on its surface which is not
+ * the boundary of any proper subset of the torus's area. For
+ * example, consider the 'loop' consisting of a straight vertical
+ * line going off the top of the grid and coming back on the
+ * bottom to join up with itself. This certainly wants to be
+ * marked as a loop, but it won't be detected as one by the above
+ * algorithm, because all the area of the grid is still connected
+ * via the left- and right-hand edges, so the two sides of the
+ * loop _are_ in the same equivalence class.
+ *
+ * The replacement algorithm I use here is also dsf-based, but the
+ * dsf is now over _sides of edges_. That is to say, on a general
+ * graph, you would have two dsf elements per edge of the graph.
+ * The unification rule is: for each vertex, iterate round the
+ * edges leaving that vertex in cyclic order, and dsf-unify the
+ * _near sides_ of each pair of adjacent edges. The effect of this
+ * is to trace round the outside edge of each connected component
+ * of the graph (this time of the actual graph, not the space
+ * between), so that the outline of each component becomes its own
+ * equivalence class. And now, just as before, an edge is part of
+ * a loop iff its two sides are not in the same component.
+ *
+ * This correctly detects even homologically nontrivial loops on a
+ * torus, because a torus is still _orientable_ - there's no way
+ * that a loop can join back up with itself with the two sides
+ * swapped. It would stop working, however, on a Mobius strip or a
+ * Klein bottle - so if I ever implement either of those modes for
+ * Net, I'll have to revisit this algorithm yet again and probably
+ * replace it with a completely general and much more fiddly
+ * approach such as Tarjan's bridge-finding algorithm (which is
+ * linear-time, but looks to me as if it's going to take more
+ * effort to get it working, especially when the graph is
+ * represented so unlike an ordinary graph).
+ *
+ * In Net, the algorithm as I describe it above has to be fiddled
+ * with just a little, to deal with the fact that there are two
+ * kinds of 'vertex' in the graph - one set at face-centres, and
+ * another set at edge-midpoints where two wires either do or do
+ * not join. Since those two vertex classes have very different
+ * representations in the Net data structure, separate code is
+ * needed for them.
+ */
+
+ /* Four potential edges per grid cell; one dsf node for each side
+ * of each one makes 8 per cell. */
+ dsf = snew_dsf(w*h*8);
+
+ /* Encode the dsf nodes. We imagine going round anticlockwise, so
+ * BEFORE(dir) indicates the clockwise side of an edge, e.g. the
+ * underside of R or the right-hand side of U. AFTER is the other
+ * side. */
+#define BEFORE(dir) ((dir)==R?7:(dir)==U?1:(dir)==L?3:5)
+#define AFTER(dir) ((dir)==R?0:(dir)==U?2:(dir)==L?4:6)
+
+#if 0
+ printf("--- begin\n");
+#endif
+ for (y = 0; y < h; y++) {
+ for (x = 0; x < w; x++) {
+ int tile = tiles[y*w+x];
+ int dir;
+ for (dir = 1; dir < 0x10; dir <<= 1) {
+ /*
+ * To unify dsf nodes around a face-centre vertex,
+ * it's easiest to do it _unconditionally_ - e.g. just
+ * unify the top side of R with the right side of U
+ * regardless of whether there's an edge in either
+ * place. Later we'll also unify the top and bottom
+ * sides of any nonexistent edge, which will e.g.
+ * complete a connection BEFORE(U) - AFTER(R) -
+ * BEFORE(R) - AFTER(D) in the absence of an R edge.
+ *
+ * This is a safe optimisation because these extra dsf
+ * nodes unified into our equivalence class can't get
+ * out of control - they are never unified with
+ * anything _else_ elsewhere in the algorithm.
+ */
+#if 0
+ printf("tile centre %d,%d: merge %d,%d\n",
+ x, y,
+ (y*w+x)*8+AFTER(C(dir)),
+ (y*w+x)*8+BEFORE(dir));
+#endif
+ dsf_merge(dsf,
+ (y*w+x)*8+AFTER(C(dir)),
+ (y*w+x)*8+BEFORE(dir));
+
+ if (tile & dir) {
+ int x1, y1;
+
+ OFFSETWH(x1, y1, x, y, dir, w, h);
+
+ /*
+ * If the tile does have an edge going out in this
+ * direction, we must check whether it joins up
+ * (without being blocked by a barrier) to an edge
+ * in the next cell along. If so, we unify around
+ * the edge-centre vertex by joining each side of
+ * this edge to the appropriate side of the next
+ * cell's edge; otherwise, the edge is a stub (the
+ * only one reaching the edge-centre vertex) and
+ * so we join its own two sides together.
+ */
+ if ((barriers && barriers[y*w+x] & dir) ||
+ !(tiles[y1*w+x1] & F(dir))) {
+#if 0
+ printf("tile edge stub %d,%d -> %c: merge %d,%d\n",
+ x, y, (dir==L?'L':dir==U?'U':dir==R?'R':'D'),
+ (y*w+x)*8+BEFORE(dir),
+ (y*w+x)*8+AFTER(dir));
+#endif
+ dsf_merge(dsf,
+ (y*w+x)*8+BEFORE(dir),
+ (y*w+x)*8+AFTER(dir));
+ } else {
+#if 0
+ printf("tile edge conn %d,%d -> %c: merge %d,%d\n",
+ x, y, (dir==L?'L':dir==U?'U':dir==R?'R':'D'),
+ (y*w+x)*8+BEFORE(dir),
+ (y*w+x)*8+AFTER(F(dir)));
+#endif
+ dsf_merge(dsf,
+ (y*w+x)*8+BEFORE(dir),
+ (y1*w+x1)*8+AFTER(F(dir)));
+#if 0
+ printf("tile edge conn %d,%d -> %c: merge %d,%d\n",
+ x, y, (dir==L?'L':dir==U?'U':dir==R?'R':'D'),
+ (y*w+x)*8+AFTER(dir),
+ (y*w+x)*8+BEFORE(F(dir)));
+#endif
+ dsf_merge(dsf,
+ (y*w+x)*8+AFTER(dir),
+ (y1*w+x1)*8+BEFORE(F(dir)));
+ }
+ } else {
+ /*
+ * As discussed above, if this edge doesn't even
+ * exist, we unify its two sides anyway to
+ * complete the unification of whatever edges do
+ * exist in this cell.
+ */
+#if 0
+ printf("tile edge missing %d,%d -> %c: merge %d,%d\n",
+ x, y, (dir==L?'L':dir==U?'U':dir==R?'R':'D'),
+ (y*w+x)*8+BEFORE(dir),
+ (y*w+x)*8+AFTER(dir));
+#endif
+ dsf_merge(dsf,
+ (y*w+x)*8+BEFORE(dir),
+ (y*w+x)*8+AFTER(dir));
+ }
+ }
+ }
+ }
+
+#if 0
+ printf("--- end\n");
+#endif
+ loops = snewn(w*h, int);
+
+ /*
+ * Now we've done the loop detection and can read off the output
+ * flags trivially: any piece of connection whose two sides are
+ * not in the same dsf class is part of a loop.
+ */
+ for (y = 0; y < h; y++) {
+ for (x = 0; x < w; x++) {
+ int dir;
+ int tile = tiles[y*w+x];
+ int flags = 0;
+ for (dir = 1; dir < 0x10; dir <<= 1) {
+ if ((tile & dir) &&
+ (dsf_canonify(dsf, (y*w+x)*8+BEFORE(dir)) !=
+ dsf_canonify(dsf, (y*w+x)*8+AFTER(dir)))) {
+ flags |= LOOP(dir);
+ }
+ }
+ loops[y*w+x] = flags;
+ }
+ }
+
+ sfree(dsf);
+ return loops;
+}
+
+static int *compute_loops(const game_state *state)
+{
+ return compute_loops_inner(state->width, state->height, state->wrapping,
+ state->tiles, state->barriers);
+}
+
+struct game_ui {
+ int org_x, org_y; /* origin */
+ int cx, cy; /* source tile (game coordinates) */
+ int cur_x, cur_y;
+ int cur_visible;
+ random_state *rs; /* used for jumbling */
+#ifdef USE_DRAGGING
+ int dragtilex, dragtiley, dragstartx, dragstarty, dragged;
+#endif
+};