X-Git-Url: https://git.distorted.org.uk/~mdw/sgt/puzzles/blobdiff_plain/fb86a8e006a25ad515f2a506528edb617f136cec..95568cbba202f550265c42840fd47401736fb442:/bridges.c

diff --git a/bridges.c b/bridges.c
index 8f8ff75..a5eef25 100644
--- a/bridges.c
+++ b/bridges.c
@@ -3,7 +3,68 @@
  *
  * Things still to do:
  *
- * * write a recursive solver?
+ *  - The solver's algorithmic design is not really ideal. It makes
+ *    use of the same data representation as gameplay uses, which
+ *    often looks like a tempting reuse of code but isn't always a
+ *    good idea. In this case, it's unpleasant that each edge of the
+ *    graph ends up represented as multiple squares on a grid, with
+ *    flags indicating when edges and non-edges cross; that's useful
+ *    when the result can be directly translated into positions of
+ *    graphics on the display, but in purely internal work it makes
+ *    even simple manipulations during solving more painful than they
+ *    should be, and complex ones have no choice but to modify the
+ *    data structures temporarily, test things, and put them back. I
+ *    envisage a complete solver rewrite along the following lines:
+ *     + We have a collection of vertices (islands) and edges
+ *       (potential bridge locations, i.e. pairs of horizontal or
+ *       vertical islands with no other island in between).
+ *     + Each edge has an associated list of edges that cross it, and
+ *       hence with which it is mutually exclusive.
+ *     + For each edge, we track the min and max number of bridges we
+ *       currently think possible.
+ *     + For each vertex, we track the number of _liberties_ it has,
+ *       i.e. its clue number minus the min bridge count for each edge
+ *       out of it.
+ *     + We also maintain a dsf that identifies sets of vertices which
+ *       are connected components of the puzzle so far, and for each
+ *       equivalence class we track the total number of liberties for
+ *       that component. (The dsf mechanism will also already track
+ *       the size of each component, i.e. number of islands.)
+ *     + So incrementing the min for an edge requires processing along
+ *       the lines of:
+ *        - set the max for all edges crossing that one to zero
+ *        - decrement the liberty count for the vertex at each end,
+ *          and also for each vertex's equivalence class (NB they may
+ *          be the same class)
+ *        - unify the two equivalence classes if they're not already,
+ *          and if so, set the liberty count for the new class to be
+ *          the sum of the previous two.
+ *     + Decrementing the max is much easier, however.
+ *     + With this data structure the really fiddly stuff in stage3()
+ *       becomes more or less trivial, because it's now a quick job to
+ *       find out whether an island would form an isolated subgraph if
+ *       connected to a given subset of its neighbours:
+ *        - identify the connected components containing the test
+ *          vertex and its putative new neighbours (but be careful not
+ *          to count a component more than once if two or more of the
+ *          vertices involved are already in the same one)
+ *        - find the sum of those components' liberty counts, and also
+ *          the total number of islands involved
+ *        - if the total liberty count of the connected components is
+ *          exactly equal to twice the number of edges we'd be adding
+ *          (of course each edge destroys two liberties, one at each
+ *          end) then these components would become a subgraph with
+ *          zero liberties if connected together.
+ *        - therefore, if that subgraph also contains fewer than the
+ *          total number of islands, it's disallowed.
+ *        - As mentioned in stage3(), once we've identified such a
+ *          disallowed pattern, we have two choices for what to do
+ *          with it: if the candidate set of neighbours has size 1 we
+ *          can reduce the max for the edge to that one neighbour,
+ *          whereas if its complement has size 1 we can increase the
+ *          min for the edge to the _omitted_ neighbour.
+ *
+ *  - write a recursive solver?
  */
 
 #include <stdio.h>
@@ -879,6 +940,7 @@ static void map_update_possibles(game_state *state)
         idx = x;
         s = e = -1;
         bl = 0;
+        maxb = state->params.maxb;     /* placate optimiser */
         /* Unset possible flags until we find an island. */
         for (y = 0; y < state->h; y++) {
             is_s = IDX(state, gridi, idx);
@@ -924,6 +986,7 @@ static void map_update_possibles(game_state *state)
         idx = y*w;
         s = e = -1;
         bl = 0;
+        maxb = state->params.maxb;     /* placate optimiser */
         for (x = 0; x < state->w; x++) {
             is_s = IDX(state, gridi, idx);
             if (is_s) {
@@ -1401,7 +1464,7 @@ static int solve_island_stage2(struct island *is, int *didsth_r)
     return 1;
 }
 
-static int solve_island_subgroup(struct island *is, int direction, int n)
+static int solve_island_subgroup(struct island *is, int direction)
 {
     struct island *is_join;
     int nislands, *dsf = is->state->solver->dsf;
@@ -1410,7 +1473,7 @@ static int solve_island_subgroup(struct island *is, int direction, int n)
     debug(("..checking subgroups.\n"));
 
     /* if is isn't full, return 0. */
-    if (n < is->count) {
+    if (island_countbridges(is) < is->count) {
         debug(("...orig island (%d,%d) not full.\n", is->x, is->y));
         return 0;
     }
@@ -1436,7 +1499,7 @@ static int solve_island_subgroup(struct island *is, int direction, int n)
             /* we have a full subgroup that isn't the whole set.
              * This isn't allowed. */
             debug(("island at (%d,%d) makes full subgroup, disallowing.\n",
-                   is->x, is->y, n));
+                   is->x, is->y));
             return 1;
         } else {
             debug(("...has finished puzzle.\n"));
@@ -1475,10 +1538,6 @@ static int solve_island_stage3(struct island *is, int *didsth_r)
     if (missing <= 0) return 1;
 
     for (i = 0; i < is->adj.npoints; i++) {
-        /* We only do right- or down-pointing bridges. */
-        if (is->adj.points[i].dx == -1 ||
-            is->adj.points[i].dy == -1) continue;
-
         x = is->adj.points[i].x;
         y = is->adj.points[i].y;
         spc = island_adjspace(is, 1, missing, i);
@@ -1499,7 +1558,7 @@ static int solve_island_stage3(struct island *is, int *didsth_r)
             solve_join(is, i, n, 0);
             map_update_possibles(is->state);
 
-            if (solve_island_subgroup(is, i, n) ||
+            if (solve_island_subgroup(is, i) ||
                 solve_island_impossible(is->state)) {
                 maxb = n-1;
                 debug(("island at (%d,%d) d(%d,%d) new max of %d bridges:\n",
@@ -1589,7 +1648,7 @@ static int solve_island_stage3(struct island *is, int *didsth_r)
         }
         map_update_possibles(is->state);
 
-        if (solve_island_subgroup(is, -1, n))
+        if (solve_island_subgroup(is, -1))
             got = 1;
 
         for (j = 0; j < is->adj.npoints; j++)
@@ -2098,8 +2157,8 @@ struct game_drawstate {
     int show_hints;
 };
 
-static char *update_drag_dst(game_state *state, game_ui *ui, game_drawstate *ds,
-                            int nx, int ny)
+static char *update_drag_dst(game_state *state, game_ui *ui,
+                             const game_drawstate *ds, int nx, int ny)
 {
     int ox, oy, dx, dy, i, currl, maxb;
     struct island *is;
@@ -2194,7 +2253,7 @@ static char *finish_drag(game_state *state, game_ui *ui)
     return dupstr(buf);
 }
 
-static char *interpret_move(game_state *state, game_ui *ui, game_drawstate *ds,
+static char *interpret_move(game_state *state, game_ui *ui, const game_drawstate *ds,
 			    int x, int y, int button)
 {
     int gx = FROMCOORD(x), gy = FROMCOORD(y);