From: simon <simon@cda61777-01e9-0310-a592-d414129be87e>
Date: Mon, 16 Nov 2009 21:21:00 +0000 (+0000)
Subject: Fix for the grid generation in the presence of particularly strange
X-Git-Url: https://git.distorted.org.uk/~mdw/sgt/puzzles/commitdiff_plain/24575af26cacdd5c37afd07e0b99a7c234cf7f43

Fix for the grid generation in the presence of particularly strange
grid types.


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

diff --git a/loopy.c b/loopy.c
index de4d6a4..34b97a2 100644
--- a/loopy.c
+++ b/loopy.c
@@ -1309,6 +1309,7 @@ static int can_colour_face(grid *g, char* board, int face_index,
     int i, j;
     grid_face *test_face = g->faces + face_index;
     grid_face *starting_face, *current_face;
+    grid_dot *starting_dot;
     int transitions;
     int current_state, s; /* booleans: equal or not-equal to 'colour' */
     int found_same_coloured_neighbour = FALSE;
@@ -1353,17 +1354,39 @@ static int can_colour_face(grid *g, char* board, int face_index,
      *     test_face->dots[i]->faces[j]
      * We assume dots go clockwise around the test face,
      * and faces go clockwise around dots. */
+
+    /*
+     * The end condition is slightly fiddly. In sufficiently strange
+     * degenerate grids, our test face may be adjacent to the same
+     * other face multiple times (typically if it's the exterior
+     * face). Consider this, in particular:
+     * 
+     *   +--+
+     *   |  |
+     *   +--+--+
+     *   |  |  |
+     *   +--+--+
+     * 
+     * The bottom left face there is adjacent to the exterior face
+     * twice, so we can't just terminate our iteration when we reach
+     * the same _face_ we started at. Furthermore, we can't
+     * condition on having the same (i,j) pair either, because
+     * several (i,j) pairs identify the bottom left contiguity with
+     * the exterior face! We canonicalise the (i,j) pair by taking
+     * one step around before we set the termination tracking.
+     */
+
     i = j = 0;
-    starting_face = test_face->dots[0]->faces[0];
-    if (starting_face == test_face) {
+    current_face = test_face->dots[0]->faces[0];
+    if (current_face == test_face) {
         j = 1;
-        starting_face = test_face->dots[0]->faces[1];
+        current_face = test_face->dots[0]->faces[1];
     }
-    current_face = starting_face;
     transitions = 0;
     current_state = (FACE_COLOUR(current_face) == colour);
-
-    do {
+    starting_dot = NULL;
+    starting_face = NULL;
+    while (TRUE) {
         /* Advance to next face.
          * Need to loop here because it might take several goes to
          * find it. */
@@ -1394,13 +1417,22 @@ static int can_colour_face(grid *g, char* board, int face_index,
         /* (i,j) are now advanced to next face */
         current_face = test_face->dots[i]->faces[j];
         s = (FACE_COLOUR(current_face) == colour);
-        if (s != current_state) {
-            ++transitions;
-            current_state = s;
-            if (transitions > 2)
-                return FALSE; /* no point in continuing */
+	if (!starting_dot) {
+	    starting_dot = test_face->dots[i];
+	    starting_face = current_face;
+	    current_state = s;
+	} else {
+	    if (s != current_state) {
+		++transitions;
+		current_state = s;
+		if (transitions > 2)
+		    break;
+	    }
+	    if (test_face->dots[i] == starting_dot &&
+		current_face == starting_face)
+		break;
         }
-    } while (current_face != starting_face);
+    }
 
     return (transitions == 2) ? TRUE : FALSE;
 }
@@ -1565,12 +1597,11 @@ static void add_full_clues(game_state *state, random_state *rs)
         struct face_score *fs_white, *fs_black;
         int c_lightable = count234(lightable_faces_sorted);
         int c_darkable = count234(darkable_faces_sorted);
-        if (c_lightable == 0) {
-            /* No more lightable faces.  Because of how the algorithm
-             * works, there should be no more darkable faces either. */
-            assert(c_darkable == 0);
+        if (c_lightable == 0 && c_darkable == 0) {
+            /* No more faces we can use at all. */
             break;
         }
+	assert(c_lightable != 0 && c_darkable != 0);
 
         fs_white = (struct face_score *)index234(lightable_faces_sorted, 0);
         fs_black = (struct face_score *)index234(darkable_faces_sorted, 0);