nb->blocks[i] = nb->blocks_data + i*nb->max_nr_squares;
#ifdef STANDALONE_SOLVER
- nb->blocknames = (char **)smalloc(b->c * b->r *(sizeof(char *)+80));
memcpy(nb->blocknames, b->blocknames, b->c * b->r *(sizeof(char *)+80));
{
int i;
usage->cube = snewn(cr*cr*cr, unsigned char);
usage->grid = grid; /* write straight back to the input */
if (kgrid) {
- int nclues = kblocks->nr_blocks;
+ int nclues;
+
+ assert(kblocks);
+ nclues = kblocks->nr_blocks;
/*
* Allow for expansion of the killer regions, the absolute
* limit is obviously one region per square.
"one solution");
#endif
+ sfree(usage->sq2region);
+ sfree(usage->regions);
sfree(usage->cube);
sfree(usage->row);
sfree(usage->col);
free_block_structure(usage->extra_cages);
sfree(usage->extra_clues);
}
+ if (usage->kclues) sfree(usage->kclues);
sfree(usage);
solver_free_scratch(scratch);
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;
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,
blocks = alloc_block_structure (c, r, area, cr, cr);
- if (params->killer) {
- kblocks = alloc_block_structure (c, r, area, cr, area);
- kgrid = snewn(area, digit);
- } else {
- kblocks = NULL;
- kgrid = NULL;
- }
+ kblocks = NULL;
+ kgrid = (params->killer) ? snewn(area, digit) : NULL;
#ifdef STANDALONE_SOLVER
assert(!"This should never happen, so we don't need to create blocknames");
make_blocks_from_whichblock(blocks);
if (params->killer) {
+ if (kblocks) free_block_structure(kblocks);
kblocks = gen_killer_cages(cr, rs, params->kdiff > DIFF_KSINGLE);
}
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
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;
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)
desc = encode_puzzle_desc(params, grid, blocks, kgrid, kblocks);
sfree(grid);
+ free_block_structure(blocks);
+ if (params->killer) {
+ free_block_structure(kblocks);
+ sfree(kgrid);
+ }
return desc;
}
sfree(state->immutable);
sfree(state->pencil);
sfree(state->grid);
+ if (state->kgrid) sfree(state->kgrid);
sfree(state);
}