ref: 3cd83d05e899e62232b68ea95cf7f07505ebd79f
parent: 4bb9232bcb2a8d5c7e43e54136f839df142e6204
author: Simon Tatham <[email protected]>
date: Thu Apr 30 13:56:56 EDT 2009
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]
--- a/solo.c
+++ b/solo.c
@@ -3340,33 +3340,71 @@
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;
for (i = 0; i < b->nr_squares[n1]; i++)
@@ -3377,9 +3415,16 @@
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 @@
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 @@
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 @@
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)