+ if (squares > area)
+ return "Too much data to fit in grid";
+
+ if (params->r == 1) {
+ int pos;
+
+ /*
+ * Now we expect a suffix giving the jigsaw block
+ * structure. Parse it and validate that it divides the
+ * grid into the right number of regions which are the
+ * right size.
+ */
+ if (*desc != ',')
+ return "Expected jigsaw block structure in game description";
+ pos = 0;
+
+ dsf = snew_dsf(area);
+ desc++;
+
+ while (*desc) {
+ int c, adv;
+
+ if (*desc == '_')
+ c = 0;
+ else if (*desc >= 'a' && *desc <= 'z')
+ c = *desc - 'a' + 1;
+ else {
+ sfree(dsf);
+ return "Invalid character in game description";
+ }
+ desc++;
+
+ adv = (c != 25); /* 'z' is a special case */
+
+ while (c-- > 0) {
+ int p0, p1;
+
+ /*
+ * Non-edge; merge the two dsf classes on either
+ * side of it.
+ */
+ if (pos >= 2*cr*(cr-1)) {
+ sfree(dsf);
+ return "Too much data in block structure specification";
+ } else if (pos < cr*(cr-1)) {
+ int y = pos/(cr-1);
+ int x = pos%(cr-1);
+ p0 = y*cr+x;
+ p1 = y*cr+x+1;
+ } else {
+ int x = pos/(cr-1) - cr;
+ int y = pos%(cr-1);
+ p0 = y*cr+x;
+ p1 = (y+1)*cr+x;
+ }
+ dsf_merge(dsf, p0, p1);
+
+ pos++;
+ }
+ if (adv)
+ pos++;
+ }
+
+ /*
+ * When desc is exhausted, we expect to have gone exactly
+ * one space _past_ the end of the grid, due to the dummy
+ * edge at the end.
+ */
+ if (pos != 2*cr*(cr-1)+1) {
+ sfree(dsf);
+ return "Not enough data in block structure specification";
+ }
+
+ /*
+ * Now we've got our dsf. Verify that it matches
+ * expectations.
+ */
+ {
+ int *canons, *counts;
+ int i, j, c, ncanons = 0;
+
+ canons = snewn(cr, int);
+ counts = snewn(cr, int);
+
+ for (i = 0; i < area; i++) {
+ j = dsf_canonify(dsf, i);
+
+ for (c = 0; c < ncanons; c++)
+ if (canons[c] == j) {
+ counts[c]++;
+ if (counts[c] > cr) {
+ sfree(dsf);
+ sfree(canons);
+ sfree(counts);
+ return "A jigsaw block is too big";
+ }
+ break;
+ }
+
+ if (c == ncanons) {
+ if (ncanons >= cr) {
+ sfree(dsf);
+ sfree(canons);
+ sfree(counts);
+ return "Too many distinct jigsaw blocks";
+ }
+ canons[ncanons] = j;
+ counts[ncanons] = 1;
+ ncanons++;
+ }
+ }
+
+ /*
+ * If we've managed to get through that loop without
+ * tripping either of the error conditions, then we
+ * must have partitioned the entire grid into at most
+ * cr blocks of at most cr squares each; therefore we
+ * must have _exactly_ cr blocks of _exactly_ cr
+ * squares each. I'll verify that by assertion just in
+ * case something has gone horribly wrong, but it
+ * shouldn't have been able to happen by duff input,
+ * only by a bug in the above code.
+ */
+ assert(ncanons == cr);
+ for (c = 0; c < ncanons; c++)
+ assert(counts[c] == cr);
+
+ sfree(canons);
+ sfree(counts);
+ }
+
+ sfree(dsf);
+ } else {
+ if (*desc)
+ return "Unexpected jigsaw block structure in game description";
+ }
+
+ return NULL;
+}
+
+static game_state *new_game(midend *me, game_params *params, char *desc)
+{
+ game_state *state = snew(game_state);
+ int c = params->c, r = params->r, cr = c*r, area = cr * cr;
+ int i;
+
+ state->cr = cr;
+ state->xtype = params->xtype;
+
+ state->grid = snewn(area, digit);
+ state->pencil = snewn(area * cr, unsigned char);
+ memset(state->pencil, 0, area * cr);
+ state->immutable = snewn(area, unsigned char);
+ memset(state->immutable, FALSE, area);
+
+ state->blocks = snew(struct block_structure);
+ state->blocks->c = c; state->blocks->r = r;
+ state->blocks->refcount = 1;
+ state->blocks->whichblock = snewn(area*2, int);
+ state->blocks->blocks = snewn(cr, int *);
+ for (i = 0; i < cr; i++)
+ state->blocks->blocks[i] = state->blocks->whichblock + area + i*cr;
+#ifdef STANDALONE_SOLVER
+ state->blocks->blocknames = (char **)smalloc(cr*(sizeof(char *)+80));
+#endif
+
+ state->completed = state->cheated = FALSE;
+
+ i = 0;
+ while (*desc && *desc != ',') {
+ int n = *desc++;
+ if (n >= 'a' && n <= 'z') {
+ int run = n - 'a' + 1;
+ assert(i + run <= area);
+ while (run-- > 0)
+ state->grid[i++] = 0;
+ } else if (n == '_') {
+ /* do nothing */;
+ } else if (n > '0' && n <= '9') {
+ assert(i < area);
+ state->immutable[i] = TRUE;
+ state->grid[i++] = atoi(desc-1);
+ while (*desc >= '0' && *desc <= '9')
+ desc++;
+ } else {
+ assert(!"We can't get here");
+ }
+ }
+ assert(i == area);
+
+ if (r == 1) {
+ int pos = 0;
+ int *dsf;
+ int nb;
+
+ assert(*desc == ',');
+
+ dsf = snew_dsf(area);
+ desc++;
+
+ while (*desc) {
+ int c, adv;
+
+ if (*desc == '_')
+ c = 0;
+ else {
+ assert(*desc >= 'a' && *desc <= 'z');
+ c = *desc - 'a' + 1;
+ }
+ desc++;
+
+ adv = (c != 25); /* 'z' is a special case */
+
+ while (c-- > 0) {
+ int p0, p1;
+
+ /*
+ * Non-edge; merge the two dsf classes on either
+ * side of it.
+ */
+ assert(pos < 2*cr*(cr-1));
+ if (pos < cr*(cr-1)) {
+ int y = pos/(cr-1);
+ int x = pos%(cr-1);
+ p0 = y*cr+x;
+ p1 = y*cr+x+1;
+ } else {
+ int x = pos/(cr-1) - cr;
+ int y = pos%(cr-1);
+ p0 = y*cr+x;
+ p1 = (y+1)*cr+x;
+ }
+ dsf_merge(dsf, p0, p1);
+
+ pos++;
+ }
+ if (adv)
+ pos++;
+ }
+
+ /*
+ * When desc is exhausted, we expect to have gone exactly
+ * one space _past_ the end of the grid, due to the dummy
+ * edge at the end.
+ */
+ assert(pos == 2*cr*(cr-1)+1);
+
+ /*
+ * Now we've got our dsf. Translate it into a block
+ * structure.
+ */
+ nb = 0;
+ for (i = 0; i < area; i++)
+ state->blocks->whichblock[i] = -1;
+ for (i = 0; i < area; i++) {
+ int j = dsf_canonify(dsf, i);
+ if (state->blocks->whichblock[j] < 0)
+ state->blocks->whichblock[j] = nb++;
+ state->blocks->whichblock[i] = state->blocks->whichblock[j];
+ }
+ assert(nb == cr);
+
+ sfree(dsf);
+ } else {
+ int x, y;
+
+ assert(!*desc);
+
+ for (y = 0; y < cr; y++)
+ for (x = 0; x < cr; x++)
+ state->blocks->whichblock[y*cr+x] = (y/c) * c + (x/r);
+ }
+
+ /*
+ * Having sorted out whichblock[], set up the block index arrays.
+ */
+ for (i = 0; i < cr; i++)
+ state->blocks->blocks[i][cr-1] = 0;
+ for (i = 0; i < area; i++) {
+ int b = state->blocks->whichblock[i];
+ int j = state->blocks->blocks[b][cr-1]++;
+ assert(j < cr);
+ state->blocks->blocks[b][j] = i;
+ }
+
+#ifdef STANDALONE_SOLVER
+ /*
+ * Set up the block names for solver diagnostic output.
+ */
+ {
+ char *p = (char *)(state->blocks->blocknames + cr);
+
+ if (r == 1) {
+ for (i = 0; i < cr; i++)
+ state->blocks->blocknames[i] = NULL;
+
+ for (i = 0; i < area; i++) {
+ int j = state->blocks->whichblock[i];
+ if (!state->blocks->blocknames[j]) {
+ state->blocks->blocknames[j] = p;
+ p += 1 + sprintf(p, "starting at (%d,%d)",
+ 1 + i%cr, 1 + i/cr);
+ }
+ }
+ } else {
+ int bx, by;
+ for (by = 0; by < r; by++)
+ for (bx = 0; bx < c; bx++) {
+ state->blocks->blocknames[by*c+bx] = p;
+ p += 1 + sprintf(p, "(%d,%d)", bx+1, by+1);
+ }
+ }
+ assert(p - (char *)state->blocks->blocknames < (int)(cr*(sizeof(char *)+80)));
+ for (i = 0; i < cr; i++)
+ assert(state->blocks->blocknames[i]);
+ }
+#endif
+
+ return state;
+}
+
+static game_state *dup_game(game_state *state)
+{
+ game_state *ret = snew(game_state);
+ int cr = state->cr, area = cr * cr;
+
+ ret->cr = state->cr;
+ ret->xtype = state->xtype;
+
+ ret->blocks = state->blocks;
+ ret->blocks->refcount++;
+
+ ret->grid = snewn(area, digit);
+ memcpy(ret->grid, state->grid, area);
+
+ ret->pencil = snewn(area * cr, unsigned char);
+ memcpy(ret->pencil, state->pencil, area * cr);
+
+ ret->immutable = snewn(area, unsigned char);
+ memcpy(ret->immutable, state->immutable, area);
+
+ ret->completed = state->completed;
+ ret->cheated = state->cheated;
+
+ return ret;
+}
+
+static void free_game(game_state *state)
+{
+ if (--state->blocks->refcount == 0) {
+ sfree(state->blocks->whichblock);
+ sfree(state->blocks->blocks);
+#ifdef STANDALONE_SOLVER
+ sfree(state->blocks->blocknames);
+#endif
+ sfree(state->blocks);
+ }
+ sfree(state->immutable);
+ sfree(state->pencil);
+ sfree(state->grid);
+ sfree(state);
+}
+
+static char *solve_game(game_state *state, game_state *currstate,
+ char *ai, char **error)
+{
+ int cr = state->cr;
+ char *ret;
+ digit *grid;
+ int solve_ret;
+
+ /*
+ * If we already have the solution in ai, save ourselves some
+ * time.
+ */
+ if (ai)
+ return dupstr(ai);
+
+ grid = snewn(cr*cr, digit);
+ memcpy(grid, state->grid, cr*cr);
+ solve_ret = solver(cr, state->blocks, state->xtype, grid, DIFF_RECURSIVE);
+
+ *error = NULL;
+
+ if (solve_ret == DIFF_IMPOSSIBLE)
+ *error = "No solution exists for this puzzle";
+ else if (solve_ret == DIFF_AMBIGUOUS)
+ *error = "Multiple solutions exist for this puzzle";
+
+ if (*error) {
+ sfree(grid);
+ return NULL;
+ }
+
+ ret = encode_solve_move(cr, grid);
+
+ sfree(grid);
+
+ return ret;
+}
+
+static char *grid_text_format(int cr, struct block_structure *blocks,
+ int xtype, digit *grid)
+{
+ int vmod, hmod;
+ int x, y;
+ int totallen, linelen, nlines;
+ char *ret, *p, ch;
+
+ /*
+ * For non-jigsaw Sudoku, we format in the way we always have,
+ * by having the digits unevenly spaced so that the dividing
+ * lines can fit in:
+ *
+ * . . | . .
+ * . . | . .
+ * ----+----
+ * . . | . .
+ * . . | . .
+ *
+ * For jigsaw puzzles, however, we must leave space between
+ * _all_ pairs of digits for an optional dividing line, so we
+ * have to move to the rather ugly
+ *
+ * . . . .
+ * ------+------
+ * . . | . .
+ * +---+
+ * . . | . | .
+ * ------+ |
+ * . . . | .
+ *
+ * We deal with both cases using the same formatting code; we
+ * simply invent a vmod value such that there's a vertical
+ * dividing line before column i iff i is divisible by vmod
+ * (so it's r in the first case and 1 in the second), and hmod
+ * likewise for horizontal dividing lines.
+ */
+
+ if (blocks->r != 1) {
+ vmod = blocks->r;
+ hmod = blocks->c;
+ } else {
+ vmod = hmod = 1;
+ }
+
+ /*
+ * Line length: we have cr digits, each with a space after it,
+ * and (cr-1)/vmod dividing lines, each with a space after it.
+ * The final space is replaced by a newline, but that doesn't
+ * affect the length.
+ */
+ linelen = 2*(cr + (cr-1)/vmod);
+
+ /*
+ * Number of lines: we have cr rows of digits, and (cr-1)/hmod
+ * dividing rows.
+ */
+ nlines = cr + (cr-1)/hmod;
+
+ /*
+ * Allocate the space.
+ */
+ totallen = linelen * nlines;
+ ret = snewn(totallen+1, char); /* leave room for terminating NUL */
+
+ /*
+ * Write the text.
+ */
+ p = ret;
+ for (y = 0; y < cr; y++) {
+ /*
+ * Row of digits.
+ */
+ for (x = 0; x < cr; x++) {
+ /*
+ * Digit.
+ */
+ digit d = grid[y*cr+x];
+
+ if (d == 0) {
+ /*
+ * Empty space: we usually write a dot, but we'll
+ * highlight spaces on the X-diagonals (in X mode)
+ * by using underscores instead.
+ */
+ if (xtype && (ondiag0(y*cr+x) || ondiag1(y*cr+x)))
+ ch = '_';
+ else
+ ch = '.';
+ } else if (d <= 9) {
+ ch = '0' + d;
+ } else {
+ ch = 'a' + d-10;
+ }
+
+ *p++ = ch;
+ if (x == cr-1) {
+ *p++ = '\n';
+ continue;
+ }
+ *p++ = ' ';