X-Git-Url: http://www.chiark.greenend.org.uk/ucgi/~ian/git?a=blobdiff_plain;f=palisade.c;h=984e616789059741be81aeaaaf0807da4145be0e;hb=fa64ed3e875e005452e5ecd639bd1d6099387bd7;hp=8776cc15c18119a44f8dbb9d2ca5712bc492ec93;hpb=6860c65bb3807dd83830e047d35d8f0fe4e89a86;p=sgt-puzzles.git

diff --git a/palisade.c b/palisade.c
index 8776cc1..984e616 100644
--- a/palisade.c
+++ b/palisade.c
@@ -511,10 +511,20 @@ static void dfs_dsf(int i, int w, borderflag *border, int *dsf, int black)
 static int is_solved(const game_params *params, clue *clues,
                      borderflag *border)
 {
-    int wh = params->w * params->h, k = params->k, *dsf = snew_dsf(wh), i;
+    int w = params->w, h = params->h, wh = w*h, k = params->k;
+    int i, x, y;
+    int *dsf = snew_dsf(wh);
 
     assert (dsf[0] == UNVISITED); /* check: UNVISITED and dsf.c match up */
 
+    /*
+     * A game is solved if:
+     *
+     *  - the borders drawn on the grid divide it into connected
+     *    components such that every square is in a component of the
+     *    correct size
+     *  - the borders also satisfy the clue set
+     */
     for (i = 0; i < wh; ++i) {
         if (dsf[i] == UNVISITED) dfs_dsf(i, params->w, border, dsf, TRUE);
         if (dsf_size(dsf, i) != k) goto error;
@@ -522,6 +532,26 @@ static int is_solved(const game_params *params, clue *clues,
         if (clues[i] != bitcount[border[i] & BORDER_MASK]) goto error;
     }
 
+    /*
+     * ... and thirdly:
+     *
+     *  - there are no *stray* borders, in that every border is
+     *    actually part of the division between two components.
+     *    Otherwise you could cheat by finding a subdivision which did
+     *    not *exceed* any clue square's counter, and then adding a
+     *    few extra edges.
+     */
+    for (y = 0; y < h; y++) {
+        for (x = 0; x < w; x++) {
+            if (x+1 < w && (border[y*w+x] & BORDER_R) &&
+                dsf_canonify(dsf, y*w+x) == dsf_canonify(dsf, y*w+(x+1)))
+                goto error;
+            if (y+1 < h && (border[y*w+x] & BORDER_D) &&
+                dsf_canonify(dsf, y*w+x) == dsf_canonify(dsf, (y+1)*w+x))
+                goto error;
+        }
+    }
+
     sfree(dsf);
     return TRUE;
 
@@ -755,8 +785,12 @@ static char *solve_game(const game_state *state, const game_state *currstate,
     init_borders(w, h, move + 1);
     move[wh + 1] = '\0';
 
-    if (solver(&state->shared->params, state->shared->clues, move + 1))
+    if (solver(&state->shared->params, state->shared->clues, move + 1)) {
+        int i;
+        for (i = 0; i < wh; i++)
+            move[i+1] |= '@';          /* turn into sensible ASCII */
         return (char *) move;
+    }
 
     *error = "Sorry, I can't solve this puzzle";
     sfree(move);