chiark / gitweb /
HTML: move 'New game' back out of the drop-down menu.
[sgt-puzzles.git] / net.c
diff --git a/net.c b/net.c
index afce82b9a4ed6d9f561c90781a616f375a149131..57d91d3581c5af92029ad219e505fa7db3f3c22f 100644 (file)
--- a/net.c
+++ b/net.c
@@ -459,6 +459,11 @@ static int todo_get(struct todo *todo) {
     return ret;
 }
 
+/*
+ * Return values: -1 means puzzle was proved inconsistent, 0 means we
+ * failed to narrow down to a unique solution, +1 means we solved it
+ * fully.
+ */
 static int net_solver(int w, int h, unsigned char *tiles,
                      unsigned char *barriers, int wrapping)
 {
@@ -733,7 +738,11 @@ static int net_solver(int w, int h, unsigned char *tiles,
 #endif
            }
 
-           assert(j > 0);             /* we can't lose _all_ possibilities! */
+           if (j == 0) {
+                /* If we've ruled out all possible orientations for a
+                 * tile, then our puzzle has no solution at all. */
+                return -1;
+            }
 
            if (j < i) {
                done_something = TRUE;
@@ -813,14 +822,14 @@ static int net_solver(int w, int h, unsigned char *tiles,
     /*
      * Mark all completely determined tiles as locked.
      */
-    j = TRUE;
+    j = +1;
     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;
+           j = 0;
        }
     }
 
@@ -1334,7 +1343,7 @@ static char *new_game_desc(const game_params *params, random_state *rs,
        /*
         * Run the solver to check unique solubility.
         */
-       while (!net_solver(w, h, tiles, NULL, params->wrapping)) {
+       while (net_solver(w, h, tiles, NULL, params->wrapping) != 1) {
            int n = 0;
 
            /*
@@ -1758,9 +1767,17 @@ static char *solve_game(const game_state *state, const game_state *currstate,
         * Run the internal solver on the provided grid. This might
         * not yield a complete solution.
         */
+        int solver_result;
+
        memcpy(tiles, state->tiles, state->width * state->height);
-       net_solver(state->width, state->height, tiles,
-                  state->barriers, state->wrapping);
+       solver_result = net_solver(state->width, state->height, tiles,
+                                   state->barriers, state->wrapping);
+
+        if (solver_result < 0) {
+            *error = "No solution exists for this puzzle";
+            sfree(tiles);
+            return NULL;
+        }
     } else {
         for (i = 0; i < state->width * state->height; i++) {
             int c = aux[i];
@@ -1909,211 +1926,78 @@ static unsigned char *compute_active(const game_state *state, int cx, int cy)
     return active;
 }
 
-static int *compute_loops_inner(int w, int h, int wrapping,
-                                const unsigned char *tiles,
-                                const unsigned char *barriers)
+struct net_neighbour_ctx {
+    int w, h;
+    const unsigned char *tiles, *barriers;
+    int i, n, neighbours[4];
+};
+static int net_neighbour(int vertex, void *vctx)
 {
-    int *loops, *dsf;
-    int x, y;
+    struct net_neighbour_ctx *ctx = (struct net_neighbour_ctx *)vctx;
 
-    /*
-     * 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.
-     */
+    if (vertex >= 0) {
+        int x = vertex % ctx->w, y = vertex / ctx->w;
+        int tile, dir, x1, y1, v1;
 
-    /* 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);
+        ctx->i = ctx->n = 0;
 
-    /* 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)
+        tile = ctx->tiles[vertex];
+        if (ctx->barriers)
+            tile &= ~ctx->barriers[vertex];
 
-#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));
+        for (dir = 1; dir < 0x10; dir <<= 1) {
+            if (!(tile & dir))
+                continue;
+            OFFSETWH(x1, y1, x, y, dir, ctx->w, ctx->h);
+            v1 = y1 * ctx->w + x1;
+            if (ctx->tiles[v1] & F(dir))
+                ctx->neighbours[ctx->n++] = v1;
+        }
+    }
 
-                if (tile & dir) {
-                    int x1, y1;
+    if (ctx->i < ctx->n)
+        return ctx->neighbours[ctx->i++];
+    else
+        return -1;
+}
 
-                    OFFSETWH(x1, y1, x, y, dir, w, h);
+static int *compute_loops_inner(int w, int h, int wrapping,
+                                const unsigned char *tiles,
+                                const unsigned char *barriers)
+{
+    struct net_neighbour_ctx ctx;
+    struct findloopstate *fls;
+    int *loops;
+    int x, y;
 
-                    /*
-                     * 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));
-                }
-            }
-        }
-    }
+    fls = findloop_new_state(w*h);
+    ctx.w = w;
+    ctx.h = h;
+    ctx.tiles = tiles;
+    ctx.barriers = barriers;
+    findloop_run(fls, w*h, net_neighbour, &ctx);
 
-#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 x1, y1, dir;
             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);
+                if ((tiles[y*w+x] & dir) &&
+                    !(barriers && (barriers[y*w+x] & dir))) {
+                    OFFSETWH(x1, y1, x, y, dir, w, h);
+                    if ((tiles[y1*w+x1] & F(dir)) &&
+                        findloop_is_loop_edge(fls, y*w+x, y1*w+x1))
+                        flags |= LOOP(dir);
                 }
             }
             loops[y*w+x] = flags;
         }
     }
 
-    sfree(dsf);
+    findloop_free_state(fls);
     return loops;
 }
 
@@ -2523,24 +2407,31 @@ static game_state *execute_move(const game_state *from, const char *move)
     /*
      * Check whether the game has been completed.
      * 
-     * For this purpose it doesn't matter where the source square
-     * is, because we can start from anywhere and correctly
-     * determine whether the game is completed.
+     * For this purpose it doesn't matter where the source square is,
+     * because we can start from anywhere (or, at least, any square
+     * that's non-empty!), and correctly determine whether the game is
+     * completed.
      */
     {
-       unsigned char *active = compute_active(ret, 0, 0);
-       int x1, y1;
+       unsigned char *active;
+       int pos;
        int complete = TRUE;
 
-       for (x1 = 0; x1 < ret->width; x1++)
-           for (y1 = 0; y1 < ret->height; y1++)
-               if ((tile(ret, x1, y1) & 0xF) && !index(ret, active, x1, y1)) {
+       for (pos = 0; pos < ret->width * ret->height; pos++)
+            if (ret->tiles[pos] & 0xF)
+                break;
+
+        if (pos < ret->width * ret->height) {
+            active = compute_active(ret, pos % ret->width, pos / ret->width);
+
+            for (pos = 0; pos < ret->width * ret->height; pos++)
+                if ((ret->tiles[pos] & 0xF) && !active[pos]) {
                    complete = FALSE;
-                   goto break_label;  /* break out of two loops at once */
-               }
-       break_label:
+                    break;
+                }
 
-       sfree(active);
+            sfree(active);
+        }
 
        if (complete)
            ret->completed = TRUE;
@@ -3097,20 +2988,43 @@ static void game_redraw(drawing *dr, game_drawstate *ds,
      * Update the status bar.
      */
     {
-       char statusbuf[256];
+       char statusbuf[256], *p;
        int i, n, n2, a;
+        int complete = FALSE;
+
+        p = statusbuf;
+        *p = '\0';     /* ensure even an empty status string is terminated */
 
-       n = state->width * state->height;
-       for (i = a = n2 = 0; i < n; i++) {
-           if (active[i])
-               a++;
-            if (state->tiles[i] & 0xF)
-                n2++;
+        if (state->used_solve) {
+            p += sprintf(p, "Auto-solved. ");
+            complete = TRUE;
+        } else if (state->completed) {
+            p += sprintf(p, "COMPLETED! ");
+            complete = TRUE;
         }
 
-       sprintf(statusbuf, "%sActive: %d/%d",
-               (state->used_solve ? "Auto-solved. " :
-                state->completed ? "COMPLETED! " : ""), a, n2);
+        /*
+         * Omit the 'Active: n/N' counter completely if the source
+         * tile is a completely empty one, because then the active
+         * count can't help but read '1'.
+         */
+        if (tile(state, ui->cx, ui->cy) & 0xF) {
+            n = state->width * state->height;
+            for (i = a = n2 = 0; i < n; i++) {
+                if (active[i])
+                    a++;
+                if (state->tiles[i] & 0xF)
+                    n2++;
+            }
+
+            /*
+             * Also, if we're displaying a completion indicator and
+             * the game is still in its completed state (i.e. every
+             * tile is active), we might as well omit this too.
+             */
+            if (!complete || a < n2)
+                p += sprintf(p, "Active: %d/%d", a, n2);
+        }
 
        status_bar(dr, statusbuf);
     }
@@ -3307,7 +3221,7 @@ static void game_print(drawing *dr, const game_state *state, int tilesize)
 const struct game thegame = {
     "Net", "games.net", "net",
     default_params,
-    game_fetch_preset,
+    game_fetch_preset, NULL,
     decode_params,
     encode_params,
     free_params,