Bridges solver enhancement. In the stage 3 solver, we were considering

the possibility that an island might form an isolated subgraph by
connecting to one of its neighbours (and, if so, reducing the maximum
bridge count in that direction so that some bridge would have to go
elsewhere), but we were not also considering the possibility that it
might form an isolated subgraph by connecting to _more_ than one of
its neighbours. For instance, if you have a 3 adjacent to a 1, a 2 and
something else, then at least one bridge must go to the something-else.

Previously insoluble test case:
10x10m2:a2b4a5a2a2a1ga2d3b33a3a4c2aa3e1a22b2a4b4aa3b1a2b33a1e3aa2a1a2c23a3a3a4a2a

[originally from svn r9543]

diff --git a/bridges.c b/bridges.c
index 794908da89612301a92e13dd67507da4e1b70b7e..8f8ff7579c76bb3a18c5e5af6c33a40497c06565 100644 (file)
--- a/bridges.c
+++ b/bridges.c
@@ -77,7 +77,8 @@ struct game_params {
 typedef unsigned int grid_type; /* change me later if we invent > 16 bits of flags. */
 
 struct solver_state {
-    int *dsf, *tmpdsf;
+    int *dsf, *comptspaces;
+    int *tmpdsf, *tmpcompspaces;
     int refcount;
 };
 
@@ -1414,15 +1415,18 @@ static int solve_island_subgroup(struct island *is, int direction, int n)
         return 0;
     }
 
-    is_join = INDEX(state, gridi,
-                    ISLAND_ORTHX(is, direction),
-                    ISLAND_ORTHY(is, direction));
-    assert(is_join);
+    if (direction >= 0) {
+        is_join = INDEX(state, gridi,
+                        ISLAND_ORTHX(is, direction),
+                        ISLAND_ORTHY(is, direction));
+        assert(is_join);
 
-    /* if is_join isn't full, return 0. */
-    if (island_countbridges(is_join) < is_join->count) {
-        debug(("...dest island (%d,%d) not full.\n", is_join->x, is_join->y));
-        return 0;
+        /* if is_join isn't full, return 0. */
+        if (island_countbridges(is_join) < is_join->count) {
+            debug(("...dest island (%d,%d) not full.\n",
+                   is_join->x, is_join->y));
+            return 0;
+        }
     }
 
     /* Check group membership for is->dsf; if it's full return 1. */
@@ -1521,6 +1525,88 @@ static int solve_island_stage3(struct island *is, int *didsth_r)
         }
         map_update_possibles(is->state);
     }
+
+    for (i = 0; i < is->adj.npoints; i++) {
+        /*
+         * Now check to see if any currently empty direction must have
+         * at least one bridge in order to avoid forming an isolated
+         * subgraph. This differs from the check above in that it
+         * considers multiple target islands. For example:
+         *
+         *   2   2    4
+         *                                  1     3     2
+         *       3
+         *                                        4
+         *
+         * The example on the left can be handled by the above loop:
+         * it will observe that connecting the central 2 twice to the
+         * left would form an isolated subgraph, and hence it will
+         * restrict that 2 to at most one bridge in that direction.
+         * But the example on the right won't be handled by that loop,
+         * because the deduction requires us to imagine connecting the
+         * 3 to _both_ the 1 and 2 at once to form an isolated
+         * subgraph.
+         *
+         * This pass is necessary _as well_ as the above one, because
+         * neither can do the other's job. In the left one,
+         * restricting the direction which _would_ cause trouble can
+         * be done even if it's not yet clear which of the remaining
+         * directions has to have a compensatory bridge; whereas the
+         * pass below that can handle the right-hand example does need
+         * to know what direction to point the necessary bridge in.
+         *
+         * Neither pass can handle the most general case, in which we
+         * observe that an arbitrary subset of an island's neighbours
+         * would form an isolated subgraph with it if it connected
+         * maximally to them, and hence that at least one bridge must
+         * point to some neighbour outside that subset but we don't
+         * know which neighbour. To handle that, we'd have to have a
+         * richer data format for the solver, which could cope with
+         * recording the idea that at least one of two edges must have
+         * a bridge.
+         */
+        int got = 0;
+        int before[4];
+        int j;
+
+        spc = island_adjspace(is, 1, missing, i);
+        if (spc == 0) continue;
+
+        for (j = 0; j < is->adj.npoints; j++)
+            before[j] = GRIDCOUNT(is->state,
+                                  is->adj.points[j].x,
+                                  is->adj.points[j].y,
+                                  is->adj.points[j].dx ? G_LINEH : G_LINEV);
+        if (before[i] != 0) continue;  /* this idea is pointless otherwise */
+
+        memcpy(ss->tmpdsf, ss->dsf, wh*sizeof(int));
+
+        for (j = 0; j < is->adj.npoints; j++) {
+            spc = island_adjspace(is, 1, missing, j);
+            if (spc == 0) continue;
+            if (j == i) continue;
+            solve_join(is, j, before[j] + spc, 0);
+        }
+        map_update_possibles(is->state);
+
+        if (solve_island_subgroup(is, -1, n))
+            got = 1;
+
+        for (j = 0; j < is->adj.npoints; j++)
+            solve_join(is, j, before[j], 0);
+        memcpy(ss->dsf, ss->tmpdsf, wh*sizeof(int));
+
+        if (got) {
+            debug(("island at (%d,%d) must connect in direction (%d,%d) to"
+                   " avoid full subgroup.\n",
+                   is->x, is->y, is->adj.points[i].dx, is->adj.points[i].dy));
+            solve_join(is, i, 1, 0);
+            didsth = 1;
+        }
+
+        map_update_possibles(is->state);
+    }
+
     if (didsth) *didsth_r = didsth;
     return 1;
 }