+ for (x = 0; x < cr; x++) {
+ int count, t, n;
+
+ /*
+ * If this square doesn't have exactly two candidate
+ * numbers, don't try it.
+ *
+ * In this loop we also sum the candidate numbers,
+ * which is a nasty hack to allow us to quickly find
+ * `the other one' (since we will shortly know there
+ * are exactly two).
+ */
+ for (count = t = 0, n = 1; n <= cr; n++)
+ if (cube(x, y, n))
+ count++, t += n;
+ if (count != 2)
+ continue;
+
+ /*
+ * Now attempt a bfs for each candidate.
+ */
+ for (n = 1; n <= cr; n++)
+ if (cube(x, y, n)) {
+ int orign, currn, head, tail;
+
+ /*
+ * Begin a bfs.
+ */
+ orign = n;
+
+ memset(number, cr+1, cr*cr);
+ head = tail = 0;
+ bfsqueue[tail++] = y*cr+x;
+#ifdef STANDALONE_SOLVER
+ bfsprev[y*cr+x] = -1;
+#endif
+ number[y*cr+x] = t - n;
+
+ while (head < tail) {
+ int xx, yy, nneighbours, xt, yt, i;
+
+ xx = bfsqueue[head++];
+ yy = xx / cr;
+ xx %= cr;
+
+ currn = number[yy*cr+xx];
+
+ /*
+ * Find neighbours of yy,xx.
+ */
+ nneighbours = 0;
+ for (yt = 0; yt < cr; yt++)
+ neighbours[nneighbours++] = yt*cr+xx;
+ for (xt = 0; xt < cr; xt++)
+ neighbours[nneighbours++] = yy*cr+xt;
+ xt = usage->blocks->whichblock[yy*cr+xx];
+ for (yt = 0; yt < cr; yt++)
+ neighbours[nneighbours++] = usage->blocks->blocks[xt][yt];
+ if (usage->diag) {
+ int sqindex = yy*cr+xx;
+ if (ondiag0(sqindex)) {
+ for (i = 0; i < cr; i++)
+ neighbours[nneighbours++] = diag0(i);
+ }
+ if (ondiag1(sqindex)) {
+ for (i = 0; i < cr; i++)
+ neighbours[nneighbours++] = diag1(i);
+ }
+ }
+
+ /*
+ * Try visiting each of those neighbours.
+ */
+ for (i = 0; i < nneighbours; i++) {
+ int cc, tt, nn;
+
+ xt = neighbours[i] % cr;
+ yt = neighbours[i] / cr;
+
+ /*
+ * We need this square to not be
+ * already visited, and to include
+ * currn as a possible number.
+ */
+ if (number[yt*cr+xt] <= cr)
+ continue;
+ if (!cube(xt, yt, currn))
+ continue;
+
+ /*
+ * Don't visit _this_ square a second
+ * time!
+ */
+ if (xt == xx && yt == yy)
+ continue;
+
+ /*
+ * To continue with the bfs, we need
+ * this square to have exactly two
+ * possible numbers.
+ */
+ for (cc = tt = 0, nn = 1; nn <= cr; nn++)
+ if (cube(xt, yt, nn))
+ cc++, tt += nn;
+ if (cc == 2) {
+ bfsqueue[tail++] = yt*cr+xt;
+#ifdef STANDALONE_SOLVER
+ bfsprev[yt*cr+xt] = yy*cr+xx;
+#endif
+ number[yt*cr+xt] = tt - currn;
+ }
+
+ /*
+ * One other possibility is that this
+ * might be the square in which we can
+ * make a real deduction: if it's
+ * adjacent to x,y, and currn is equal
+ * to the original number we ruled out.
+ */
+ if (currn == orign &&
+ (xt == x || yt == y ||
+ (usage->blocks->whichblock[yt*cr+xt] == usage->blocks->whichblock[y*cr+x]) ||
+ (usage->diag && ((ondiag0(yt*cr+xt) && ondiag0(y*cr+x)) ||
+ (ondiag1(yt*cr+xt) && ondiag1(y*cr+x)))))) {
+#ifdef STANDALONE_SOLVER
+ if (solver_show_working) {
+ char *sep = "";
+ int xl, yl;
+ printf("%*sforcing chain, %d at ends of ",
+ solver_recurse_depth*4, "", orign);
+ xl = xx;
+ yl = yy;
+ while (1) {
+ printf("%s(%d,%d)", sep, 1+xl,
+ 1+yl);
+ xl = bfsprev[yl*cr+xl];
+ if (xl < 0)
+ break;
+ yl = xl / cr;
+ xl %= cr;
+ sep = "-";
+ }
+ printf("\n%*s ruling out %d at (%d,%d)\n",
+ solver_recurse_depth*4, "",
+ orign, 1+xt, 1+yt);
+ }
+#endif
+ cube(xt, yt, orign) = FALSE;
+ return 1;
+ }
+ }
+ }
+ }
+ }
+
+ return 0;
+}
+
+static struct solver_scratch *solver_new_scratch(struct solver_usage *usage)
+{
+ struct solver_scratch *scratch = snew(struct solver_scratch);
+ int cr = usage->cr;
+ scratch->grid = snewn(cr*cr, unsigned char);
+ scratch->rowidx = snewn(cr, unsigned char);
+ scratch->colidx = snewn(cr, unsigned char);
+ scratch->set = snewn(cr, unsigned char);
+ scratch->neighbours = snewn(5*cr, int);
+ scratch->bfsqueue = snewn(cr*cr, int);
+#ifdef STANDALONE_SOLVER
+ scratch->bfsprev = snewn(cr*cr, int);
+#endif
+ scratch->indexlist = snewn(cr*cr, int); /* used for set elimination */
+ scratch->indexlist2 = snewn(cr, int); /* only used for intersect() */
+ return scratch;
+}
+
+static void solver_free_scratch(struct solver_scratch *scratch)
+{
+#ifdef STANDALONE_SOLVER
+ sfree(scratch->bfsprev);
+#endif
+ sfree(scratch->bfsqueue);
+ sfree(scratch->neighbours);
+ sfree(scratch->set);
+ sfree(scratch->colidx);
+ sfree(scratch->rowidx);
+ sfree(scratch->grid);
+ sfree(scratch->indexlist);
+ sfree(scratch->indexlist2);
+ sfree(scratch);
+}
+
+static int solver(int cr, struct block_structure *blocks, int xtype,
+ digit *grid, int maxdiff)
+{
+ struct solver_usage *usage;
+ struct solver_scratch *scratch;
+ int x, y, b, i, n, ret;
+ int diff = DIFF_BLOCK;
+
+ /*
+ * Set up a usage structure as a clean slate (everything
+ * possible).
+ */
+ usage = snew(struct solver_usage);
+ usage->cr = cr;
+ usage->blocks = blocks;
+ usage->cube = snewn(cr*cr*cr, unsigned char);
+ usage->grid = grid; /* write straight back to the input */
+ memset(usage->cube, TRUE, cr*cr*cr);
+
+ usage->row = snewn(cr * cr, unsigned char);
+ usage->col = snewn(cr * cr, unsigned char);
+ usage->blk = snewn(cr * cr, unsigned char);
+ memset(usage->row, FALSE, cr * cr);
+ memset(usage->col, FALSE, cr * cr);
+ memset(usage->blk, FALSE, cr * cr);
+
+ if (xtype) {
+ usage->diag = snewn(cr * 2, unsigned char);
+ memset(usage->diag, FALSE, cr * 2);
+ } else
+ usage->diag = NULL;
+
+ scratch = solver_new_scratch(usage);
+
+ /*
+ * Place all the clue numbers we are given.
+ */
+ for (x = 0; x < cr; x++)
+ for (y = 0; y < cr; y++)
+ if (grid[y*cr+x])
+ solver_place(usage, x, y, grid[y*cr+x]);
+
+ /*
+ * Now loop over the grid repeatedly trying all permitted modes
+ * of reasoning. The loop terminates if we complete an
+ * iteration without making any progress; we then return
+ * failure or success depending on whether the grid is full or
+ * not.
+ */
+ while (1) {
+ /*
+ * I'd like to write `continue;' inside each of the
+ * following loops, so that the solver returns here after
+ * making some progress. However, I can't specify that I
+ * want to continue an outer loop rather than the innermost
+ * one, so I'm apologetically resorting to a goto.
+ */
+ cont:
+
+ /*
+ * Blockwise positional elimination.
+ */
+ for (b = 0; b < cr; b++)
+ for (n = 1; n <= cr; n++)
+ if (!usage->blk[b*cr+n-1]) {
+ for (i = 0; i < cr; i++)
+ scratch->indexlist[i] = cubepos2(usage->blocks->blocks[b][i],n);
+ ret = solver_elim(usage, scratch->indexlist
+#ifdef STANDALONE_SOLVER
+ , "positional elimination,"
+ " %d in block %s", n,
+ usage->blocks->blocknames[b]
+#endif
+ );
+ if (ret < 0) {
+ diff = DIFF_IMPOSSIBLE;
+ goto got_result;
+ } else if (ret > 0) {
+ diff = max(diff, DIFF_BLOCK);
+ goto cont;
+ }
+ }
+
+ if (maxdiff <= DIFF_BLOCK)
+ break;
+
+ /*
+ * Row-wise positional elimination.
+ */
+ for (y = 0; y < cr; y++)
+ for (n = 1; n <= cr; n++)
+ if (!usage->row[y*cr+n-1]) {
+ for (x = 0; x < cr; x++)
+ scratch->indexlist[x] = cubepos(x, y, n);
+ ret = solver_elim(usage, scratch->indexlist
+#ifdef STANDALONE_SOLVER
+ , "positional elimination,"
+ " %d in row %d", n, 1+y
+#endif
+ );
+ if (ret < 0) {
+ diff = DIFF_IMPOSSIBLE;
+ goto got_result;
+ } else if (ret > 0) {
+ diff = max(diff, DIFF_SIMPLE);
+ goto cont;
+ }
+ }
+ /*
+ * Column-wise positional elimination.
+ */
+ for (x = 0; x < cr; x++)
+ for (n = 1; n <= cr; n++)
+ if (!usage->col[x*cr+n-1]) {
+ for (y = 0; y < cr; y++)
+ scratch->indexlist[y] = cubepos(x, y, n);
+ ret = solver_elim(usage, scratch->indexlist
+#ifdef STANDALONE_SOLVER
+ , "positional elimination,"
+ " %d in column %d", n, 1+x
+#endif
+ );
+ if (ret < 0) {
+ diff = DIFF_IMPOSSIBLE;
+ goto got_result;
+ } else if (ret > 0) {
+ diff = max(diff, DIFF_SIMPLE);
+ goto cont;
+ }
+ }
+
+ /*
+ * X-diagonal positional elimination.
+ */
+ if (usage->diag) {
+ for (n = 1; n <= cr; n++)
+ if (!usage->diag[n-1]) {
+ for (i = 0; i < cr; i++)
+ scratch->indexlist[i] = cubepos2(diag0(i), n);
+ ret = solver_elim(usage, scratch->indexlist
+#ifdef STANDALONE_SOLVER
+ , "positional elimination,"
+ " %d in \\-diagonal", n
+#endif
+ );
+ if (ret < 0) {
+ diff = DIFF_IMPOSSIBLE;
+ goto got_result;
+ } else if (ret > 0) {
+ diff = max(diff, DIFF_SIMPLE);
+ goto cont;
+ }
+ }
+ for (n = 1; n <= cr; n++)
+ if (!usage->diag[cr+n-1]) {
+ for (i = 0; i < cr; i++)
+ scratch->indexlist[i] = cubepos2(diag1(i), n);
+ ret = solver_elim(usage, scratch->indexlist
+#ifdef STANDALONE_SOLVER
+ , "positional elimination,"
+ " %d in /-diagonal", n
+#endif
+ );
+ if (ret < 0) {
+ diff = DIFF_IMPOSSIBLE;
+ goto got_result;
+ } else if (ret > 0) {
+ diff = max(diff, DIFF_SIMPLE);
+ goto cont;
+ }
+ }