- * Full recursive Solo solver.
- *
- * The algorithm for this solver is shamelessly copied from a
- * Python solver written by Andrew Wilkinson (which is GPLed, but
- * I've reused only ideas and no code). It mostly just does the
- * obvious recursive thing: pick an empty square, put one of the
- * possible digits in it, recurse until all squares are filled,
- * backtrack and change some choices if necessary.
- *
- * The clever bit is that every time it chooses which square to
- * fill in next, it does so by counting the number of _possible_
- * numbers that can go in each square, and it prioritises so that
- * it picks a square with the _lowest_ number of possibilities. The
- * idea is that filling in lots of the obvious bits (particularly
- * any squares with only one possibility) will cut down on the list
- * of possibilities for other squares and hence reduce the enormous
- * search space as much as possible as early as possible.
- *
- * In practice the algorithm appeared to work very well; run on
- * sample problems from the Times it completed in well under a
- * second on my G5 even when written in Python, and given an empty
- * grid (so that in principle it would enumerate _all_ solved
- * grids!) it found the first valid solution just as quickly. So
- * with a bit more randomisation I see no reason not to use this as
- * my grid generator.
- */
-
-/*
- * Internal data structure used in solver to keep track of
- * progress.
- */
-struct rsolve_coord { int x, y, r; };
-struct rsolve_usage {
- int c, r, cr; /* cr == c*r */
- /* grid is a copy of the input grid, modified as we go along */
- digit *grid;
- /* row[y*cr+n-1] TRUE if digit n has been placed in row y */
- unsigned char *row;
- /* col[x*cr+n-1] TRUE if digit n has been placed in row x */
- unsigned char *col;
- /* blk[(y*c+x)*cr+n-1] TRUE if digit n has been placed in block (x,y) */
- unsigned char *blk;
- /* This lists all the empty spaces remaining in the grid. */
- struct rsolve_coord *spaces;
- int nspaces;
- /* If we need randomisation in the solve, this is our random state. */
- random_state *rs;
- /* Number of solutions so far found, and maximum number we care about. */
- int solns, maxsolns;
-};
-
-/*
- * The real recursive step in the solving function.
- */
-static void rsolve_real(struct rsolve_usage *usage, digit *grid)
-{
- int c = usage->c, r = usage->r, cr = usage->cr;
- int i, j, n, sx, sy, bestm, bestr;
- int *digits;
-
- /*
- * Firstly, check for completion! If there are no spaces left
- * in the grid, we have a solution.
- */
- if (usage->nspaces == 0) {
- if (!usage->solns) {
- /*
- * This is our first solution, so fill in the output grid.
- */
- memcpy(grid, usage->grid, cr * cr);
- }
- usage->solns++;
- return;
- }
-
- /*
- * Otherwise, there must be at least one space. Find the most
- * constrained space, using the `r' field as a tie-breaker.
- */
- bestm = cr+1; /* so that any space will beat it */
- bestr = 0;
- i = sx = sy = -1;
- for (j = 0; j < usage->nspaces; j++) {
- int x = usage->spaces[j].x, y = usage->spaces[j].y;
- int m;
-
- /*
- * Find the number of digits that could go in this space.
- */
- m = 0;
- for (n = 0; n < cr; n++)
- if (!usage->row[y*cr+n] && !usage->col[x*cr+n] &&
- !usage->blk[((y/c)*c+(x/r))*cr+n])
- m++;
-
- if (m < bestm || (m == bestm && usage->spaces[j].r < bestr)) {
- bestm = m;
- bestr = usage->spaces[j].r;
- sx = x;
- sy = y;
- i = j;
- }
- }
-
- /*
- * Swap that square into the final place in the spaces array,
- * so that decrementing nspaces will remove it from the list.
- */
- if (i != usage->nspaces-1) {
- struct rsolve_coord t;
- t = usage->spaces[usage->nspaces-1];
- usage->spaces[usage->nspaces-1] = usage->spaces[i];
- usage->spaces[i] = t;
- }
-
- /*
- * Now we've decided which square to start our recursion at,
- * simply go through all possible values, shuffling them
- * randomly first if necessary.
- */
- digits = snewn(bestm, int);
- j = 0;
- for (n = 0; n < cr; n++)
- if (!usage->row[sy*cr+n] && !usage->col[sx*cr+n] &&
- !usage->blk[((sy/c)*c+(sx/r))*cr+n]) {
- digits[j++] = n+1;
- }
-
- if (usage->rs) {
- /* shuffle */
- for (i = j; i > 1; i--) {
- int p = random_upto(usage->rs, i);
- if (p != i-1) {
- int t = digits[p];
- digits[p] = digits[i-1];
- digits[i-1] = t;
- }
- }
- }
-
- /* And finally, go through the digit list and actually recurse. */
- for (i = 0; i < j; i++) {
- n = digits[i];
-
- /* Update the usage structure to reflect the placing of this digit. */
- usage->row[sy*cr+n-1] = usage->col[sx*cr+n-1] =
- usage->blk[((sy/c)*c+(sx/r))*cr+n-1] = TRUE;
- usage->grid[sy*cr+sx] = n;
- usage->nspaces--;
-
- /* Call the solver recursively. */
- rsolve_real(usage, grid);
-
- /*
- * If we have seen as many solutions as we need, terminate
- * all processing immediately.
- */
- if (usage->solns >= usage->maxsolns)
- break;
-
- /* Revert the usage structure. */
- usage->row[sy*cr+n-1] = usage->col[sx*cr+n-1] =
- usage->blk[((sy/c)*c+(sx/r))*cr+n-1] = FALSE;
- usage->grid[sy*cr+sx] = 0;
- usage->nspaces++;
- }
-
- sfree(digits);
-}
-
-/*
- * Entry point to solver. You give it dimensions and a starting
- * grid, which is simply an array of N^4 digits. In that array, 0
- * means an empty square, and 1..N mean a clue square.
- *
- * Return value is the number of solutions found; searching will
- * stop after the provided `max'. (Thus, you can pass max==1 to
- * indicate that you only care about finding _one_ solution, or
- * max==2 to indicate that you want to know the difference between
- * a unique and non-unique solution.) The input parameter `grid' is
- * also filled in with the _first_ (or only) solution found by the
- * solver.
- */
-static int rsolve(int c, int r, digit *grid, random_state *rs, int max)
-{
- struct rsolve_usage *usage;
- int x, y, cr = c*r;
- int ret;
-
- /*
- * Create an rsolve_usage structure.
- */
- usage = snew(struct rsolve_usage);
-
- usage->c = c;
- usage->r = r;
- usage->cr = cr;
-
- usage->grid = snewn(cr * cr, digit);
- memcpy(usage->grid, grid, 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);
-
- usage->spaces = snewn(cr * cr, struct rsolve_coord);
- usage->nspaces = 0;
-
- usage->solns = 0;
- usage->maxsolns = max;
-
- usage->rs = rs;
-
- /*
- * Now fill it in with data from the input grid.
- */
- for (y = 0; y < cr; y++) {
- for (x = 0; x < cr; x++) {
- int v = grid[y*cr+x];
- if (v == 0) {
- usage->spaces[usage->nspaces].x = x;
- usage->spaces[usage->nspaces].y = y;
- if (rs)
- usage->spaces[usage->nspaces].r = random_bits(rs, 31);
- else
- usage->spaces[usage->nspaces].r = usage->nspaces;
- usage->nspaces++;
- } else {
- usage->row[y*cr+v-1] = TRUE;
- usage->col[x*cr+v-1] = TRUE;
- usage->blk[((y/c)*c+(x/r))*cr+v-1] = TRUE;
- }
- }
- }
-
- /*
- * Run the real recursive solving function.
- */
- rsolve_real(usage, grid);
- ret = usage->solns;
-
- /*
- * Clean up the usage structure now we have our answer.
- */
- sfree(usage->spaces);
- sfree(usage->blk);
- sfree(usage->col);
- sfree(usage->row);
- sfree(usage->grid);
- sfree(usage);
-
- /*
- * And return.
- */
- return ret;
-}
-
-/* ----------------------------------------------------------------------
- * End of recursive solver code.
- */
-
-/* ----------------------------------------------------------------------
- * Less capable non-recursive solver. This one is used to check
- * solubility of a grid as we gradually remove numbers from it: by
- * verifying a grid using this solver we can ensure it isn't _too_
- * hard (e.g. does not actually require guessing and backtracking).
- *