Fix a misdesign I must have missed when I reviewed the Killer patch:

merge_some_cages() was written in the assumption that it would
always be able to do something, in that it returned void on success
and if it couldn't find anything to do it would just loop round
forever trying the same things over and over again.

Now it makes a methodical list of the pairs of cages which are merge
candidates, goes through them in a random order until it finds a
viable one, and returns a boolean indicating whether it succeeded or
ran out of candidates.

A test case which previously hung and now does not is "solo
--generate 1 7jxkdt#12345-10".

[originally from svn r8541]

diff --git a/solo.c b/solo.c
index a298d156e6ef90265e3534fad8bb0d88659d72ce..fc2ac0410f565876dfe2b1de3174a493351cdeb9 100644 (file)
--- a/solo.c
+++ b/solo.c
@@ -3340,32 +3340,70 @@ static void merge_blocks(struct block_structure *b, int n1, int n2)
     b->nr_blocks = n1;
 }
 
-static void merge_some_cages(struct block_structure *b, int cr, int area,
+static int merge_some_cages(struct block_structure *b, int cr, int area,
                             digit *grid, random_state *rs)
 {
-    do {
-       /* Find two candidates for merging.  */
-       int i, n1, n2;
-       int x = 1 + random_bits(rs, 20) % (cr - 2);
-       int y = 1 + random_bits(rs, 20) % (cr - 2);
-       int xy = y*cr + x;
-       int off = random_bits(rs, 1) == 0 ? -1 : 1;
-       int other = xy;
-       unsigned int digits_found;
+    /*
+     * Make a list of all the pairs of adjacent blocks.
+     */
+    int i, j, k;
+    struct pair {
+       int b1, b2;
+    } *pairs;
+    int npairs;
 
-       if (random_bits(rs, 1) == 0)
-           other = xy + off;
-       else
-           other = xy + off * cr;
-       n1 = b->whichblock[xy];
-       n2 = b->whichblock[other];
-       if (n1 == n2)
-           continue;
+    pairs = snewn(b->nr_blocks * b->nr_blocks, struct pair);
+    npairs = 0;
 
-       assert(n1 >= 0 && n2 >= 0 && n1 < b->nr_blocks && n2 < b->nr_blocks);
+    for (i = 0; i < b->nr_blocks; i++) {
+       for (j = i+1; j < b->nr_blocks; j++) {
 
-       if (b->nr_squares[n1] + b->nr_squares[n2] > b->max_nr_squares)
-           continue;
+           /*
+            * Rule the merger out of consideration if it's
+            * obviously not viable.
+            */
+           if (b->nr_squares[i] + b->nr_squares[j] > b->max_nr_squares)
+               continue;              /* we couldn't merge these anyway */
+
+           /*
+            * See if these two blocks have a pair of squares
+            * adjacent to each other.
+            */
+           for (k = 0; k < b->nr_squares[i]; k++) {
+               int xy = b->blocks[i][k];
+               int y = xy / cr, x = xy % cr;
+               if ((y   > 0  && b->whichblock[xy - cr] == j) ||
+                   (y+1 < cr && b->whichblock[xy + cr] == j) ||
+                   (x   > 0  && b->whichblock[xy -  1] == j) ||
+                   (x+1 < cr && b->whichblock[xy +  1] == j)) {
+                   /*
+                    * Yes! Add this pair to our list.
+                    */
+                   pairs[npairs].b1 = i;
+                   pairs[npairs].b2 = j;
+                   break;
+               }
+           }
+       }
+    }
+
+    /*
+     * Now go through that list in random order until we find a pair
+     * of blocks we can merge.
+     */
+    while (npairs > 0) {
+       int n1, n2;
+       unsigned int digits_found;
+
+       /*
+        * Pick a random pair, and remove it from the list.
+        */
+       i = random_upto(rs, npairs);
+       n1 = pairs[i].b1;
+       n2 = pairs[i].b2;
+       if (i != npairs-1)
+           pairs[i] = pairs[npairs-1];
+       npairs--;
 
        /* Guarantee that the merged cage would still be a region.  */
        digits_found = 0;
@@ -3377,9 +3415,16 @@ static void merge_some_cages(struct block_structure *b, int cr, int area,
        if (i != b->nr_squares[n2])
            continue;
 
+       /*
+        * Got one! Do the merge.
+        */
        merge_blocks(b, n1, n2);
-       break;
-    } while (1);
+       sfree(pairs);
+       return TRUE;
+    }
+
+    sfree(pairs);
+    return FALSE;
 }
 
 static void compute_kclues(struct block_structure *cages, digit *kclues,
@@ -3593,7 +3638,8 @@ static char *new_game_desc(game_params *params, random_state *rs,
                        free_block_structure(good_cages);
                    ntries = 0;
                    good_cages = dup_block_structure(kblocks);
-                   merge_some_cages(kblocks, cr, area, grid2, rs);
+                   if (!merge_some_cages(kblocks, cr, area, grid2, rs))
+                       break;
                } else if (dlev.diff > dlev.maxdiff || dlev.kdiff > dlev.maxkdiff) {
                    /*
                     * Give up after too many tries and either use the good one we
@@ -3610,7 +3656,8 @@ static char *new_game_desc(game_params *params, random_state *rs,
                    if (good_cages != NULL) {
                        free_block_structure(kblocks);
                        kblocks = dup_block_structure(good_cages);
-                       merge_some_cages(kblocks, cr, area, grid2, rs);
+                       if (!merge_some_cages(kblocks, cr, area, grid2, rs))
+                           break;
                    } else {
                        if (last_cages == NULL)
                            break;
@@ -3622,7 +3669,8 @@ static char *new_game_desc(game_params *params, random_state *rs,
                    if (last_cages)
                        free_block_structure(last_cages);
                    last_cages = dup_block_structure(kblocks);
-                   merge_some_cages(kblocks, cr, area, grid2, rs);
+                   if (!merge_some_cages(kblocks, cr, area, grid2, rs))
+                       break;
                }
            }
            if (last_cages)