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

git-svn-id: svn://svn.tartarus.org/sgt/puzzles@9543 cda61777-01e9-0310-a592-d414129be87e

diff --git a/bridges.c b/bridges.c
index 794908d..8f8ff75 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;
 }