+static void dsf_to_blocks(int *dsf, struct block_structure *blocks,
+ int min_expected, int max_expected)
+{
+ int cr = blocks->c * blocks->r, area = cr * cr;
+ int i, nb = 0;
+
+ for (i = 0; i < area; i++)
+ blocks->whichblock[i] = -1;
+ for (i = 0; i < area; i++) {
+ int j = dsf_canonify(dsf, i);
+ if (blocks->whichblock[j] < 0)
+ blocks->whichblock[j] = nb++;
+ blocks->whichblock[i] = blocks->whichblock[j];
+ }
+ assert(nb >= min_expected && nb <= max_expected);
+ blocks->nr_blocks = nb;
+}
+
+static void make_blocks_from_whichblock(struct block_structure *blocks)
+{
+ int i;
+
+ for (i = 0; i < blocks->nr_blocks; i++) {
+ blocks->blocks[i][blocks->max_nr_squares-1] = 0;
+ blocks->nr_squares[i] = 0;
+ }
+ for (i = 0; i < blocks->area; i++) {
+ int b = blocks->whichblock[i];
+ int j = blocks->blocks[b][blocks->max_nr_squares-1]++;
+ assert(j < blocks->max_nr_squares);
+ blocks->blocks[b][j] = i;
+ blocks->nr_squares[b]++;
+ }
+}
+
+static char *encode_block_structure_desc(char *p, struct block_structure *blocks)
+{
+ int i, currrun = 0;
+ int c = blocks->c, r = blocks->r, cr = c * r;
+
+ /*
+ * Encode the block structure. We do this by encoding
+ * the pattern of dividing lines: first we iterate
+ * over the cr*(cr-1) internal vertical grid lines in
+ * ordinary reading order, then over the cr*(cr-1)
+ * internal horizontal ones in transposed reading
+ * order.
+ *
+ * We encode the number of non-lines between the
+ * lines; _ means zero (two adjacent divisions), a
+ * means 1, ..., y means 25, and z means 25 non-lines
+ * _and no following line_ (so that za means 26, zb 27
+ * etc).
+ */
+ for (i = 0; i <= 2*cr*(cr-1); i++) {
+ int x, y, p0, p1, edge;
+
+ if (i == 2*cr*(cr-1)) {
+ edge = TRUE; /* terminating virtual edge */
+ } else {
+ if (i < cr*(cr-1)) {
+ y = i/(cr-1);
+ x = i%(cr-1);
+ p0 = y*cr+x;
+ p1 = y*cr+x+1;
+ } else {
+ x = i/(cr-1) - cr;
+ y = i%(cr-1);
+ p0 = y*cr+x;
+ p1 = (y+1)*cr+x;
+ }
+ edge = (blocks->whichblock[p0] != blocks->whichblock[p1]);
+ }
+
+ if (edge) {
+ while (currrun > 25)
+ *p++ = 'z', currrun -= 25;
+ if (currrun)
+ *p++ = 'a'-1 + currrun;
+ else
+ *p++ = '_';
+ currrun = 0;
+ } else
+ currrun++;
+ }
+ return p;
+}
+
+static char *encode_grid(char *desc, digit *grid, int area)
+{
+ int run, i;
+ char *p = desc;
+
+ run = 0;
+ for (i = 0; i <= area; i++) {
+ int n = (i < area ? grid[i] : -1);
+
+ if (!n)
+ run++;
+ else {
+ if (run) {
+ while (run > 0) {
+ int c = 'a' - 1 + run;
+ if (run > 26)
+ c = 'z';
+ *p++ = c;
+ run -= c - ('a' - 1);
+ }
+ } else {
+ /*
+ * If there's a number in the very top left or
+ * bottom right, there's no point putting an
+ * unnecessary _ before or after it.
+ */
+ if (p > desc && n > 0)
+ *p++ = '_';
+ }
+ if (n > 0)
+ p += sprintf(p, "%d", n);
+ run = 0;
+ }
+ }
+ return p;
+}
+
+/*
+ * Conservatively stimate the number of characters required for
+ * encoding a grid of a certain area.
+ */
+static int grid_encode_space (int area)
+{
+ int t, count;
+ for (count = 1, t = area; t > 26; t -= 26)
+ count++;
+ return count * area;
+}
+
+/*
+ * Conservatively stimate the number of characters required for
+ * encoding a given blocks structure.
+ */
+static int blocks_encode_space(struct block_structure *blocks)
+{
+ int cr = blocks->c * blocks->r, area = cr * cr;
+ return grid_encode_space(area);
+}
+
+static char *encode_puzzle_desc(const game_params *params, digit *grid,
+ struct block_structure *blocks,
+ digit *kgrid,
+ struct block_structure *kblocks)
+{
+ int c = params->c, r = params->r, cr = c*r;
+ int area = cr*cr;
+ char *p, *desc;
+ int space;
+
+ space = grid_encode_space(area) + 1;
+ if (r == 1)
+ space += blocks_encode_space(blocks) + 1;
+ if (params->killer) {
+ space += blocks_encode_space(kblocks) + 1;
+ space += grid_encode_space(area) + 1;
+ }
+ desc = snewn(space, char);
+ p = encode_grid(desc, grid, area);
+
+ if (r == 1) {
+ *p++ = ',';
+ p = encode_block_structure_desc(p, blocks);
+ }
+ if (params->killer) {
+ *p++ = ',';
+ p = encode_block_structure_desc(p, kblocks);
+ *p++ = ',';
+ p = encode_grid(p, kgrid, area);
+ }
+ assert(p - desc < space);
+ *p++ = '\0';
+ desc = sresize(desc, p - desc, char);
+
+ return desc;
+}
+
+static void merge_blocks(struct block_structure *b, int n1, int n2)
+{
+ int i;
+ /* Move data towards the lower block number. */
+ if (n2 < n1) {
+ int t = n2;
+ n2 = n1;
+ n1 = t;
+ }
+
+ /* Merge n2 into n1, and move the last block into n2's position. */
+ for (i = 0; i < b->nr_squares[n2]; i++)
+ b->whichblock[b->blocks[n2][i]] = n1;
+ memcpy(b->blocks[n1] + b->nr_squares[n1], b->blocks[n2],
+ b->nr_squares[n2] * sizeof **b->blocks);
+ b->nr_squares[n1] += b->nr_squares[n2];
+
+ n1 = b->nr_blocks - 1;
+ if (n2 != n1) {
+ memcpy(b->blocks[n2], b->blocks[n1],
+ b->nr_squares[n1] * sizeof **b->blocks);
+ for (i = 0; i < b->nr_squares[n1]; i++)
+ b->whichblock[b->blocks[n1][i]] = n2;
+ b->nr_squares[n2] = b->nr_squares[n1];
+ }
+ b->nr_blocks = n1;
+}
+
+static int merge_some_cages(struct block_structure *b, int cr, int area,
+ digit *grid, random_state *rs)
+{
+ /*
+ * Make a list of all the pairs of adjacent blocks.
+ */
+ int i, j, k;
+ struct pair {
+ int b1, b2;
+ } *pairs;
+ int npairs;
+
+ pairs = snewn(b->nr_blocks * b->nr_blocks, struct pair);
+ npairs = 0;
+
+ for (i = 0; i < b->nr_blocks; i++) {
+ for (j = i+1; j < b->nr_blocks; j++) {
+
+ /*
+ * 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++)
+ digits_found |= 1 << grid[b->blocks[n1][i]];
+ for (i = 0; i < b->nr_squares[n2]; i++)
+ if (digits_found & (1 << grid[b->blocks[n2][i]]))
+ break;
+ if (i != b->nr_squares[n2])
+ continue;
+
+ /*
+ * Got one! Do the merge.
+ */
+ merge_blocks(b, n1, n2);
+ sfree(pairs);
+ return TRUE;
+ }
+
+ sfree(pairs);
+ return FALSE;
+}
+
+static void compute_kclues(struct block_structure *cages, digit *kclues,
+ digit *grid, int area)
+{
+ int i;
+ memset(kclues, 0, area * sizeof *kclues);
+ for (i = 0; i < cages->nr_blocks; i++) {
+ int j, sum = 0;
+ for (j = 0; j < area; j++)
+ if (cages->whichblock[j] == i)
+ sum += grid[j];
+ for (j = 0; j < area; j++)
+ if (cages->whichblock[j] == i)
+ break;
+ assert (j != area);
+ kclues[j] = sum;
+ }
+}
+
+static struct block_structure *gen_killer_cages(int cr, random_state *rs,
+ int remove_singletons)
+{
+ int nr;
+ int x, y, area = cr * cr;
+ int n_singletons = 0;
+ struct block_structure *b = alloc_block_structure (1, cr, area, cr, area);
+
+ for (x = 0; x < area; x++)
+ b->whichblock[x] = -1;
+ nr = 0;
+ for (y = 0; y < cr; y++)
+ for (x = 0; x < cr; x++) {
+ int rnd;
+ int xy = y*cr+x;
+ if (b->whichblock[xy] != -1)
+ continue;
+ b->whichblock[xy] = nr;
+
+ rnd = random_bits(rs, 4);
+ if (xy + 1 < area && (rnd >= 4 || (!remove_singletons && rnd >= 1))) {
+ int xy2 = xy + 1;
+ if (x + 1 == cr || b->whichblock[xy2] != -1 ||
+ (xy + cr < area && random_bits(rs, 1) == 0))
+ xy2 = xy + cr;
+ if (xy2 >= area)
+ n_singletons++;
+ else
+ b->whichblock[xy2] = nr;
+ } else
+ n_singletons++;
+ nr++;
+ }
+
+ b->nr_blocks = nr;
+ make_blocks_from_whichblock(b);
+
+ for (x = y = 0; x < b->nr_blocks; x++)
+ if (b->nr_squares[x] == 1)
+ y++;
+ assert(y == n_singletons);
+
+ if (n_singletons > 0 && remove_singletons) {
+ int n;
+ for (n = 0; n < b->nr_blocks;) {
+ int xy, x, y, xy2, other;
+ if (b->nr_squares[n] > 1) {
+ n++;
+ continue;
+ }
+ xy = b->blocks[n][0];
+ x = xy % cr;
+ y = xy / cr;
+ if (xy + 1 == area)
+ xy2 = xy - 1;
+ else if (x + 1 < cr && (y + 1 == cr || random_bits(rs, 1) == 0))
+ xy2 = xy + 1;
+ else
+ xy2 = xy + cr;
+ other = b->whichblock[xy2];
+
+ if (b->nr_squares[other] == 1)
+ n_singletons--;
+ n_singletons--;
+ merge_blocks(b, n, other);
+ if (n < other)
+ n++;
+ }
+ assert(n_singletons == 0);
+ }
+ return b;
+}
+
+static char *new_game_desc(const game_params *params, random_state *rs,