X-Git-Url: https://git.distorted.org.uk/~mdw/sgt/puzzles/blobdiff_plain/351c6261eaca09572ad01a318fb33d0bdb5c8bd7..6e8e5c5141cf8f754a1b468eb53ea91e494f97f7:/solo.c diff --git a/solo.c b/solo.c index 480bb2b..f074a9c 100644 --- a/solo.c +++ b/solo.c @@ -3,25 +3,12 @@ * * TODO: * - * - can we do anything about nasty centring of text in GTK? It - * seems to be taking ascenders/descenders into account when - * centring. Ick. - * - * - implement stronger modes of reasoning in nsolve, thus - * enabling harder puzzles - * + and having done that, supply configurable difficulty - * levels - * * - it might still be nice to do some prioritisation on the * removal of numbers from the grid * + one possibility is to try to minimise the maximum number * of filled squares in any block, which in particular ought * to enforce never leaving a completely filled block in the * puzzle as presented. - * + be careful of being too clever here, though, until after - * I've tried implementing difficulty levels. It's not - * impossible that those might impose much more important - * constraints on this process. * * - alternative interface modes * + sudoku.com's Windows program has a palette of possible @@ -34,8 +21,7 @@ * one thing is ever highlighted at a time, so there's no way * to confuse the two. * + `pencil marks' might be useful for more subtle forms of - * deduction, once we implement creation of puzzles that - * require it. + * deduction, now we can create puzzles that require them. */ /* @@ -74,8 +60,15 @@ #include #include +#ifdef STANDALONE_SOLVER +#include +int solver_show_working; +#endif + #include "puzzles.h" +#define max(x,y) ((x)>(y)?(x):(y)) + /* * To save space, I store digits internally as unsigned char. This * imposes a hard limit of 255 on the order of the puzzle. Since @@ -94,6 +87,9 @@ typedef unsigned char digit; enum { SYMM_NONE, SYMM_ROT2, SYMM_ROT4, SYMM_REF4 }; +enum { DIFF_BLOCK, DIFF_SIMPLE, DIFF_INTERSECT, + DIFF_SET, DIFF_RECURSIVE, DIFF_AMBIGUOUS, DIFF_IMPOSSIBLE }; + enum { COL_BACKGROUND, COL_GRID, @@ -104,14 +100,14 @@ enum { }; struct game_params { - int c, r, symm; + int c, r, symm, diff; }; struct game_state { int c, r; digit *grid; unsigned char *immutable; /* marks which digits are clues */ - int completed; + int completed, cheated; }; static game_params *default_params(void) @@ -120,35 +116,11 @@ static game_params *default_params(void) ret->c = ret->r = 3; ret->symm = SYMM_ROT2; /* a plausible default */ + ret->diff = DIFF_BLOCK; /* so is this */ return ret; } -static int game_fetch_preset(int i, char **name, game_params **params) -{ - game_params *ret; - int c, r; - char buf[80]; - - switch (i) { - case 0: c = 2, r = 2; break; - case 1: c = 2, r = 3; break; - case 2: c = 3, r = 3; break; - case 3: c = 3, r = 4; break; - case 4: c = 4, r = 4; break; - default: return FALSE; - } - - sprintf(buf, "%dx%d", c, r); - *name = dupstr(buf); - *params = ret = snew(game_params); - ret->c = c; - ret->r = r; - ret->symm = SYMM_ROT2; - /* FIXME: difficulty presets? */ - return TRUE; -} - static void free_params(game_params *params) { sfree(params); @@ -161,47 +133,92 @@ static game_params *dup_params(game_params *params) return ret; } -static game_params *decode_params(char const *string) +static int game_fetch_preset(int i, char **name, game_params **params) { - game_params *ret = default_params(); + static struct { + char *title; + game_params params; + } presets[] = { + { "2x2 Trivial", { 2, 2, SYMM_ROT2, DIFF_BLOCK } }, + { "2x3 Basic", { 2, 3, SYMM_ROT2, DIFF_SIMPLE } }, + { "3x3 Trivial", { 3, 3, SYMM_ROT2, DIFF_BLOCK } }, + { "3x3 Basic", { 3, 3, SYMM_ROT2, DIFF_SIMPLE } }, + { "3x3 Intermediate", { 3, 3, SYMM_ROT2, DIFF_INTERSECT } }, + { "3x3 Advanced", { 3, 3, SYMM_ROT2, DIFF_SET } }, + { "3x3 Unreasonable", { 3, 3, SYMM_ROT2, DIFF_RECURSIVE } }, + { "3x4 Basic", { 3, 4, SYMM_ROT2, DIFF_SIMPLE } }, + { "4x4 Basic", { 4, 4, SYMM_ROT2, DIFF_SIMPLE } }, + }; + + if (i < 0 || i >= lenof(presets)) + return FALSE; + + *name = dupstr(presets[i].title); + *params = dup_params(&presets[i].params); + + return TRUE; +} +static void decode_params(game_params *ret, char const *string) +{ ret->c = ret->r = atoi(string); - ret->symm = SYMM_ROT2; while (*string && isdigit((unsigned char)*string)) string++; if (*string == 'x') { string++; ret->r = atoi(string); while (*string && isdigit((unsigned char)*string)) string++; } - if (*string == 'r' || *string == 'm' || *string == 'a') { - int sn, sc; - sc = *string++; - sn = atoi(string); - while (*string && isdigit((unsigned char)*string)) string++; - if (sc == 'm' && sn == 4) - ret->symm = SYMM_REF4; - if (sc == 'r' && sn == 4) - ret->symm = SYMM_ROT4; - if (sc == 'r' && sn == 2) - ret->symm = SYMM_ROT2; - if (sc == 'a') - ret->symm = SYMM_NONE; + while (*string) { + if (*string == 'r' || *string == 'm' || *string == 'a') { + int sn, sc; + sc = *string++; + sn = atoi(string); + while (*string && isdigit((unsigned char)*string)) string++; + if (sc == 'm' && sn == 4) + ret->symm = SYMM_REF4; + if (sc == 'r' && sn == 4) + ret->symm = SYMM_ROT4; + if (sc == 'r' && sn == 2) + ret->symm = SYMM_ROT2; + if (sc == 'a') + ret->symm = SYMM_NONE; + } else if (*string == 'd') { + string++; + if (*string == 't') /* trivial */ + string++, ret->diff = DIFF_BLOCK; + else if (*string == 'b') /* basic */ + string++, ret->diff = DIFF_SIMPLE; + else if (*string == 'i') /* intermediate */ + string++, ret->diff = DIFF_INTERSECT; + else if (*string == 'a') /* advanced */ + string++, ret->diff = DIFF_SET; + else if (*string == 'u') /* unreasonable */ + string++, ret->diff = DIFF_RECURSIVE; + } else + string++; /* eat unknown character */ } - /* FIXME: difficulty levels */ - - return ret; } -static char *encode_params(game_params *params) +static char *encode_params(game_params *params, int full) { char str[80]; - /* - * Symmetry is a game generation preference and hence is left - * out of the encoding. Users can add it back in as they see - * fit. - */ sprintf(str, "%dx%d", params->c, params->r); + if (full) { + switch (params->symm) { + case SYMM_REF4: strcat(str, "m4"); break; + case SYMM_ROT4: strcat(str, "r4"); break; + /* case SYMM_ROT2: strcat(str, "r2"); break; [default] */ + case SYMM_NONE: strcat(str, "a"); break; + } + switch (params->diff) { + /* case DIFF_BLOCK: strcat(str, "dt"); break; [default] */ + case DIFF_SIMPLE: strcat(str, "db"); break; + case DIFF_INTERSECT: strcat(str, "di"); break; + case DIFF_SET: strcat(str, "da"); break; + case DIFF_RECURSIVE: strcat(str, "du"); break; + } + } return dupstr(str); } @@ -229,14 +246,15 @@ static config_item *game_configure(game_params *params) ret[2].sval = ":None:2-way rotation:4-way rotation:4-way mirror"; ret[2].ival = params->symm; - /* - * FIXME: difficulty level. - */ + ret[3].name = "Difficulty"; + ret[3].type = C_CHOICES; + ret[3].sval = ":Trivial:Basic:Intermediate:Advanced:Unreasonable"; + ret[3].ival = params->diff; - ret[3].name = NULL; - ret[3].type = C_END; - ret[3].sval = NULL; - ret[3].ival = 0; + ret[4].name = NULL; + ret[4].type = C_END; + ret[4].sval = NULL; + ret[4].ival = 0; return ret; } @@ -248,6 +266,7 @@ static game_params *custom_params(config_item *cfg) ret->c = atoi(cfg[0].sval); ret->r = atoi(cfg[1].sval); ret->symm = cfg[2].ival; + ret->diff = cfg[3].ival; return ret; } @@ -548,31 +567,35 @@ static int rsolve(int c, int r, digit *grid, random_state *rs, int max) * in because all the other numbers that could go in it are * ruled out. * - * More advanced modes of reasoning I'd like to support in future: - * - * - Intersectional elimination: given two domains which overlap + * - Intersectional analysis: given two domains which overlap * (hence one must be a block, and the other can be a row or * col), if the possible locations for a particular number in * one of the domains can be narrowed down to the overlap, then * that number can be ruled out everywhere but the overlap in * the other domain too. * - * - Setwise numeric elimination: if there is a subset of the - * empty squares within a domain such that the union of the - * possible numbers in that subset has the same size as the - * subset itself, then those numbers can be ruled out everywhere - * else in the domain. (For example, if there are five empty - * squares and the possible numbers in each are 12, 23, 13, 134 - * and 1345, then the first three empty squares form such a - * subset: the numbers 1, 2 and 3 _must_ be in those three - * squares in some permutation, and hence we can deduce none of - * them can be in the fourth or fifth squares.) - * - * - Setwise positional elimination: if there is a subset of the - * unplaced numbers within a domain such that the union of all - * their possible positions has the same size as the subset - * itself, then all other numbers can be ruled out for those - * positions. + * - Set elimination: if there is a subset of the empty squares + * within a domain such that the union of the possible numbers + * in that subset has the same size as the subset itself, then + * those numbers can be ruled out everywhere else in the domain. + * (For example, if there are five empty squares and the + * possible numbers in each are 12, 23, 13, 134 and 1345, then + * the first three empty squares form such a subset: the numbers + * 1, 2 and 3 _must_ be in those three squares in some + * permutation, and hence we can deduce none of them can be in + * the fourth or fifth squares.) + * + You can also see this the other way round, concentrating + * on numbers rather than squares: if there is a subset of + * the unplaced numbers within a domain such that the union + * of all their possible positions has the same size as the + * subset itself, then all other numbers can be ruled out for + * those positions. However, it turns out that this is + * exactly equivalent to the first formulation at all times: + * there is a 1-1 correspondence between suitable subsets of + * the unplaced numbers and suitable subsets of the unfilled + * places, found by taking the _complement_ of the union of + * the numbers' possible positions (or the spaces' possible + * contents). */ /* @@ -675,10 +698,14 @@ static void nsolve_place(struct nsolve_usage *usage, int x, int y, int n) * in its row, its column and its block. */ usage->row[y*cr+n-1] = usage->col[x*cr+n-1] = - usage->blk[((y/c)*c+(x/r))*cr+n-1] = TRUE; + usage->blk[((y%r)*c+(x/r))*cr+n-1] = TRUE; } -static int nsolve_elim(struct nsolve_usage *usage, int start, int step) +static int nsolve_elim(struct nsolve_usage *usage, int start, int step +#ifdef STANDALONE_SOLVER + , char *fmt, ... +#endif + ) { int c = usage->c, r = usage->r, cr = c*r; int fpos, m, i; @@ -705,6 +732,16 @@ static int nsolve_elim(struct nsolve_usage *usage, int start, int step) y %= cr; if (!usage->grid[YUNTRANS(y)*cr+x]) { +#ifdef STANDALONE_SOLVER + if (solver_show_working) { + va_list ap; + va_start(ap, fmt); + vprintf(fmt, ap); + va_end(ap); + printf(":\n placing %d at (%d,%d)\n", + n, 1+x, 1+YUNTRANS(y)); + } +#endif nsolve_place(usage, x, y, n); return TRUE; } @@ -713,11 +750,260 @@ static int nsolve_elim(struct nsolve_usage *usage, int start, int step) return FALSE; } +static int nsolve_intersect(struct nsolve_usage *usage, + int start1, int step1, int start2, int step2 +#ifdef STANDALONE_SOLVER + , char *fmt, ... +#endif + ) +{ + int c = usage->c, r = usage->r, cr = c*r; + int ret, i; + + /* + * Loop over the first domain and see if there's any set bit + * not also in the second. + */ + for (i = 0; i < cr; i++) { + int p = start1+i*step1; + if (usage->cube[p] && + !(p >= start2 && p < start2+cr*step2 && + (p - start2) % step2 == 0)) + return FALSE; /* there is, so we can't deduce */ + } + + /* + * We have determined that all set bits in the first domain are + * within its overlap with the second. So loop over the second + * domain and remove all set bits that aren't also in that + * overlap; return TRUE iff we actually _did_ anything. + */ + ret = FALSE; + for (i = 0; i < cr; i++) { + int p = start2+i*step2; + if (usage->cube[p] && + !(p >= start1 && p < start1+cr*step1 && (p - start1) % step1 == 0)) + { +#ifdef STANDALONE_SOLVER + if (solver_show_working) { + int px, py, pn; + + if (!ret) { + va_list ap; + va_start(ap, fmt); + vprintf(fmt, ap); + va_end(ap); + printf(":\n"); + } + + pn = 1 + p % cr; + py = p / cr; + px = py / cr; + py %= cr; + + printf(" ruling out %d at (%d,%d)\n", + pn, 1+px, 1+YUNTRANS(py)); + } +#endif + ret = TRUE; /* we did something */ + usage->cube[p] = 0; + } + } + + return ret; +} + +static int nsolve_set(struct nsolve_usage *usage, + int start, int step1, int step2 +#ifdef STANDALONE_SOLVER + , char *fmt, ... +#endif + ) +{ + int c = usage->c, r = usage->r, cr = c*r; + int i, j, n, count; + unsigned char *grid = snewn(cr*cr, unsigned char); + unsigned char *rowidx = snewn(cr, unsigned char); + unsigned char *colidx = snewn(cr, unsigned char); + unsigned char *set = snewn(cr, unsigned char); + + /* + * We are passed a cr-by-cr matrix of booleans. Our first job + * is to winnow it by finding any definite placements - i.e. + * any row with a solitary 1 - and discarding that row and the + * column containing the 1. + */ + memset(rowidx, TRUE, cr); + memset(colidx, TRUE, cr); + for (i = 0; i < cr; i++) { + int count = 0, first = -1; + for (j = 0; j < cr; j++) + if (usage->cube[start+i*step1+j*step2]) + first = j, count++; + if (count == 0) { + /* + * This condition actually marks a completely insoluble + * (i.e. internally inconsistent) puzzle. We return and + * report no progress made. + */ + return FALSE; + } + if (count == 1) + rowidx[i] = colidx[first] = FALSE; + } + + /* + * Convert each of rowidx/colidx from a list of 0s and 1s to a + * list of the indices of the 1s. + */ + for (i = j = 0; i < cr; i++) + if (rowidx[i]) + rowidx[j++] = i; + n = j; + for (i = j = 0; i < cr; i++) + if (colidx[i]) + colidx[j++] = i; + assert(n == j); + + /* + * And create the smaller matrix. + */ + for (i = 0; i < n; i++) + for (j = 0; j < n; j++) + grid[i*cr+j] = usage->cube[start+rowidx[i]*step1+colidx[j]*step2]; + + /* + * Having done that, we now have a matrix in which every row + * has at least two 1s in. Now we search to see if we can find + * a rectangle of zeroes (in the set-theoretic sense of + * `rectangle', i.e. a subset of rows crossed with a subset of + * columns) whose width and height add up to n. + */ + + memset(set, 0, n); + count = 0; + while (1) { + /* + * We have a candidate set. If its size is <=1 or >=n-1 + * then we move on immediately. + */ + if (count > 1 && count < n-1) { + /* + * The number of rows we need is n-count. See if we can + * find that many rows which each have a zero in all + * the positions listed in `set'. + */ + int rows = 0; + for (i = 0; i < n; i++) { + int ok = TRUE; + for (j = 0; j < n; j++) + if (set[j] && grid[i*cr+j]) { + ok = FALSE; + break; + } + if (ok) + rows++; + } + + /* + * We expect never to be able to get _more_ than + * n-count suitable rows: this would imply that (for + * example) there are four numbers which between them + * have at most three possible positions, and hence it + * indicates a faulty deduction before this point or + * even a bogus clue. + */ + assert(rows <= n - count); + if (rows >= n - count) { + int progress = FALSE; + + /* + * We've got one! Now, for each row which _doesn't_ + * satisfy the criterion, eliminate all its set + * bits in the positions _not_ listed in `set'. + * Return TRUE (meaning progress has been made) if + * we successfully eliminated anything at all. + * + * This involves referring back through + * rowidx/colidx in order to work out which actual + * positions in the cube to meddle with. + */ + for (i = 0; i < n; i++) { + int ok = TRUE; + for (j = 0; j < n; j++) + if (set[j] && grid[i*cr+j]) { + ok = FALSE; + break; + } + if (!ok) { + for (j = 0; j < n; j++) + if (!set[j] && grid[i*cr+j]) { + int fpos = (start+rowidx[i]*step1+ + colidx[j]*step2); +#ifdef STANDALONE_SOLVER + if (solver_show_working) { + int px, py, pn; + + if (!progress) { + va_list ap; + va_start(ap, fmt); + vprintf(fmt, ap); + va_end(ap); + printf(":\n"); + } + + pn = 1 + fpos % cr; + py = fpos / cr; + px = py / cr; + py %= cr; + + printf(" ruling out %d at (%d,%d)\n", + pn, 1+px, 1+YUNTRANS(py)); + } +#endif + progress = TRUE; + usage->cube[fpos] = FALSE; + } + } + } + + if (progress) { + sfree(set); + sfree(colidx); + sfree(rowidx); + sfree(grid); + return TRUE; + } + } + } + + /* + * Binary increment: change the rightmost 0 to a 1, and + * change all 1s to the right of it to 0s. + */ + i = n; + while (i > 0 && set[i-1]) + set[--i] = 0, count--; + if (i > 0) + set[--i] = 1, count++; + else + break; /* done */ + } + + sfree(set); + sfree(colidx); + sfree(rowidx); + sfree(grid); + + return FALSE; +} + static int nsolve(int c, int r, digit *grid) { struct nsolve_usage *usage; int cr = c*r; int x, y, n; + int diff = DIFF_BLOCK; /* * Set up a usage structure as a clean slate (everything @@ -754,6 +1040,13 @@ static int nsolve(int c, int r, digit *grid) * 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: /* @@ -763,8 +1056,15 @@ static int nsolve(int c, int r, digit *grid) for (y = 0; y < r; y++) for (n = 1; n <= cr; n++) if (!usage->blk[(y*c+(x/r))*cr+n-1] && - nsolve_elim(usage, cubepos(x,y,n), r*cr)) + nsolve_elim(usage, cubepos(x,y,n), r*cr +#ifdef STANDALONE_SOLVER + , "positional elimination," + " block (%d,%d)", 1+x/r, 1+y +#endif + )) { + diff = max(diff, DIFF_BLOCK); goto cont; + } /* * Row-wise positional elimination. @@ -772,16 +1072,29 @@ static int nsolve(int c, int r, digit *grid) for (y = 0; y < cr; y++) for (n = 1; n <= cr; n++) if (!usage->row[y*cr+n-1] && - nsolve_elim(usage, cubepos(0,y,n), cr*cr)) + nsolve_elim(usage, cubepos(0,y,n), cr*cr +#ifdef STANDALONE_SOLVER + , "positional elimination," + " row %d", 1+YUNTRANS(y) +#endif + )) { + 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] && - nsolve_elim(usage, cubepos(x,0,n), cr)) + nsolve_elim(usage, cubepos(x,0,n), cr +#ifdef STANDALONE_SOLVER + , "positional elimination," " column %d", 1+x +#endif + )) { + diff = max(diff, DIFF_SIMPLE); goto cont; + } /* * Numeric elimination. @@ -789,8 +1102,111 @@ static int nsolve(int c, int r, digit *grid) for (x = 0; x < cr; x++) for (y = 0; y < cr; y++) if (!usage->grid[YUNTRANS(y)*cr+x] && - nsolve_elim(usage, cubepos(x,y,1), 1)) - goto cont; + nsolve_elim(usage, cubepos(x,y,1), 1 +#ifdef STANDALONE_SOLVER + , "numeric elimination at (%d,%d)", 1+x, + 1+YUNTRANS(y) +#endif + )) { + diff = max(diff, DIFF_SIMPLE); + goto cont; + } + + /* + * Intersectional analysis, rows vs blocks. + */ + for (y = 0; y < cr; y++) + for (x = 0; x < cr; x += r) + for (n = 1; n <= cr; n++) + if (!usage->row[y*cr+n-1] && + !usage->blk[((y%r)*c+(x/r))*cr+n-1] && + (nsolve_intersect(usage, cubepos(0,y,n), cr*cr, + cubepos(x,y%r,n), r*cr +#ifdef STANDALONE_SOLVER + , "intersectional analysis," + " row %d vs block (%d,%d)", + 1+YUNTRANS(y), 1+x/r, 1+y%r +#endif + ) || + nsolve_intersect(usage, cubepos(x,y%r,n), r*cr, + cubepos(0,y,n), cr*cr +#ifdef STANDALONE_SOLVER + , "intersectional analysis," + " block (%d,%d) vs row %d", + 1+x/r, 1+y%r, 1+YUNTRANS(y) +#endif + ))) { + diff = max(diff, DIFF_INTERSECT); + goto cont; + } + + /* + * Intersectional analysis, columns vs blocks. + */ + for (x = 0; x < cr; x++) + for (y = 0; y < r; y++) + for (n = 1; n <= cr; n++) + if (!usage->col[x*cr+n-1] && + !usage->blk[(y*c+(x/r))*cr+n-1] && + (nsolve_intersect(usage, cubepos(x,0,n), cr, + cubepos((x/r)*r,y,n), r*cr +#ifdef STANDALONE_SOLVER + , "intersectional analysis," + " column %d vs block (%d,%d)", + 1+x, 1+x/r, 1+y +#endif + ) || + nsolve_intersect(usage, cubepos((x/r)*r,y,n), r*cr, + cubepos(x,0,n), cr +#ifdef STANDALONE_SOLVER + , "intersectional analysis," + " block (%d,%d) vs column %d", + 1+x/r, 1+y, 1+x +#endif + ))) { + diff = max(diff, DIFF_INTERSECT); + goto cont; + } + + /* + * Blockwise set elimination. + */ + for (x = 0; x < cr; x += r) + for (y = 0; y < r; y++) + if (nsolve_set(usage, cubepos(x,y,1), r*cr, 1 +#ifdef STANDALONE_SOLVER + , "set elimination, block (%d,%d)", 1+x/r, 1+y +#endif + )) { + diff = max(diff, DIFF_SET); + goto cont; + } + + /* + * Row-wise set elimination. + */ + for (y = 0; y < cr; y++) + if (nsolve_set(usage, cubepos(0,y,1), cr*cr, 1 +#ifdef STANDALONE_SOLVER + , "set elimination, row %d", 1+YUNTRANS(y) +#endif + )) { + diff = max(diff, DIFF_SET); + goto cont; + } + + /* + * Column-wise set elimination. + */ + for (x = 0; x < cr; x++) + if (nsolve_set(usage, cubepos(x,0,1), cr, 1 +#ifdef STANDALONE_SOLVER + , "set elimination, column %d", 1+x +#endif + )) { + diff = max(diff, DIFF_SET); + goto cont; + } /* * If we reach here, we have made no deductions in this @@ -808,8 +1224,8 @@ static int nsolve(int c, int r, digit *grid) for (x = 0; x < cr; x++) for (y = 0; y < cr; y++) if (!grid[y*cr+x]) - return FALSE; - return TRUE; + return DIFF_IMPOSSIBLE; + return diff; } /* ---------------------------------------------------------------------- @@ -944,7 +1360,13 @@ static int symmetries(game_params *params, int x, int y, int *output, int s) return i; } -static char *new_game_seed(game_params *params, random_state *rs) +struct game_aux_info { + int c, r; + digit *grid; +}; + +static char *new_game_desc(game_params *params, random_state *rs, + game_aux_info **aux) { int c = params->c, r = params->r, cr = c*r; int area = cr*cr; @@ -952,150 +1374,148 @@ static char *new_game_seed(game_params *params, random_state *rs) struct xy { int x, y; } *locs; int nlocs; int ret; - char *seed; + char *desc; int coords[16], ncoords; int xlim, ylim; + int maxdiff, recursing; /* - * Start the recursive solver with an empty grid to generate a - * random solved state. + * Adjust the maximum difficulty level to be consistent with + * the puzzle size: all 2x2 puzzles appear to be Trivial + * (DIFF_BLOCK) so we cannot hold out for even a Basic + * (DIFF_SIMPLE) one. */ - grid = snewn(area, digit); - memset(grid, 0, area); - ret = rsolve(c, r, grid, rs, 1); - assert(ret == 1); - assert(check_valid(c, r, grid)); - -#ifdef DEBUG - memcpy(grid, - "\x0\x1\x0\x0\x6\x0\x0\x0\x0" - "\x5\x0\x0\x7\x0\x4\x0\x2\x0" - "\x0\x0\x6\x1\x0\x0\x0\x0\x0" - "\x8\x9\x7\x0\x0\x0\x0\x0\x0" - "\x0\x0\x3\x0\x4\x0\x9\x0\x0" - "\x0\x0\x0\x0\x0\x0\x8\x7\x6" - "\x0\x0\x0\x0\x0\x9\x1\x0\x0" - "\x0\x3\x0\x6\x0\x5\x0\x0\x7" - "\x0\x0\x0\x0\x8\x0\x0\x5\x0" - , area); - - { - int y, x; - for (y = 0; y < cr; y++) { - for (x = 0; x < cr; x++) { - printf("%2.0d", grid[y*cr+x]); - } - printf("\n"); - } - printf("\n"); - } - - nsolve(c, r, grid); - - { - int y, x; - for (y = 0; y < cr; y++) { - for (x = 0; x < cr; x++) { - printf("%2.0d", grid[y*cr+x]); - } - printf("\n"); - } - printf("\n"); - } -#endif + maxdiff = params->diff; + if (c == 2 && r == 2) + maxdiff = DIFF_BLOCK; - /* - * Now we have a solved grid, start removing things from it - * while preserving solubility. - */ + grid = snewn(area, digit); locs = snewn(area, struct xy); grid2 = snewn(area, digit); - symmetry_limit(params, &xlim, &ylim, params->symm); - while (1) { - int x, y, i, j; - /* - * Iterate over the grid and enumerate all the filled - * squares we could empty. - */ - nlocs = 0; - - for (x = 0; x < xlim; x++) - for (y = 0; y < ylim; y++) - if (grid[y*cr+x]) { - locs[nlocs].x = x; - locs[nlocs].y = y; - nlocs++; - } + /* + * Loop until we get a grid of the required difficulty. This is + * nasty, but it seems to be unpleasantly hard to generate + * difficult grids otherwise. + */ + do { + /* + * Start the recursive solver with an empty grid to generate a + * random solved state. + */ + memset(grid, 0, area); + ret = rsolve(c, r, grid, rs, 1); + assert(ret == 1); + assert(check_valid(c, r, grid)); /* - * Now shuffle that list. + * Save the solved grid in the aux_info. */ - for (i = nlocs; i > 1; i--) { - int p = random_upto(rs, i); - if (p != i-1) { - struct xy t = locs[p]; - locs[p] = locs[i-1]; - locs[i-1] = t; - } + { + game_aux_info *ai = snew(game_aux_info); + ai->c = c; + ai->r = r; + ai->grid = snewn(cr * cr, digit); + memcpy(ai->grid, grid, cr * cr * sizeof(digit)); + *aux = ai; } - /* - * Now loop over the shuffled list and, for each element, - * see whether removing that element (and its reflections) - * from the grid will still leave the grid soluble by - * nsolve. - */ - for (i = 0; i < nlocs; i++) { - x = locs[i].x; - y = locs[i].y; - - memcpy(grid2, grid, area); - ncoords = symmetries(params, x, y, coords, params->symm); - for (j = 0; j < ncoords; j++) - grid2[coords[2*j+1]*cr+coords[2*j]] = 0; - - if (nsolve(c, r, grid2)) { - for (j = 0; j < ncoords; j++) - grid[coords[2*j+1]*cr+coords[2*j]] = 0; - break; - } - } + /* + * Now we have a solved grid, start removing things from it + * while preserving solubility. + */ + symmetry_limit(params, &xlim, &ylim, params->symm); + recursing = FALSE; + while (1) { + int x, y, i, j; + + /* + * Iterate over the grid and enumerate all the filled + * squares we could empty. + */ + nlocs = 0; + + for (x = 0; x < xlim; x++) + for (y = 0; y < ylim; y++) + if (grid[y*cr+x]) { + locs[nlocs].x = x; + locs[nlocs].y = y; + nlocs++; + } + + /* + * Now shuffle that list. + */ + for (i = nlocs; i > 1; i--) { + int p = random_upto(rs, i); + if (p != i-1) { + struct xy t = locs[p]; + locs[p] = locs[i-1]; + locs[i-1] = t; + } + } + + /* + * Now loop over the shuffled list and, for each element, + * see whether removing that element (and its reflections) + * from the grid will still leave the grid soluble by + * nsolve. + */ + for (i = 0; i < nlocs; i++) { + int ret; + + x = locs[i].x; + y = locs[i].y; + + memcpy(grid2, grid, area); + ncoords = symmetries(params, x, y, coords, params->symm); + for (j = 0; j < ncoords; j++) + grid2[coords[2*j+1]*cr+coords[2*j]] = 0; + + if (recursing) + ret = (rsolve(c, r, grid2, NULL, 2) == 1); + else + ret = (nsolve(c, r, grid2) <= maxdiff); + + if (ret) { + for (j = 0; j < ncoords; j++) + grid[coords[2*j+1]*cr+coords[2*j]] = 0; + break; + } + } + + if (i == nlocs) { + /* + * There was nothing we could remove without + * destroying solvability. If we're trying to + * generate a recursion-only grid and haven't + * switched over to rsolve yet, we now do; + * otherwise we give up. + */ + if (maxdiff == DIFF_RECURSIVE && !recursing) { + recursing = TRUE; + } else { + break; + } + } + } + + memcpy(grid2, grid, area); + } while (nsolve(c, r, grid2) < maxdiff); - if (i == nlocs) { - /* - * There was nothing we could remove without destroying - * solvability. - */ - break; - } - } sfree(grid2); sfree(locs); -#ifdef DEBUG - { - int y, x; - for (y = 0; y < cr; y++) { - for (x = 0; x < cr; x++) { - printf("%2.0d", grid[y*cr+x]); - } - printf("\n"); - } - printf("\n"); - } -#endif - /* * Now we have the grid as it will be presented to the user. - * Encode it in a game seed. + * Encode it in a game desc. */ { char *p; int run, i; - seed = snewn(5 * area, char); - p = seed; + desc = snewn(5 * area, char); + p = desc; run = 0; for (i = 0; i <= area; i++) { int n = (i < area ? grid[i] : -1); @@ -1117,7 +1537,7 @@ static char *new_game_seed(game_params *params, random_state *rs) * bottom right, there's no point putting an * unnecessary _ before or after it. */ - if (p > seed && n > 0) + if (p > desc && n > 0) *p++ = '_'; } if (n > 0) @@ -1125,33 +1545,39 @@ static char *new_game_seed(game_params *params, random_state *rs) run = 0; } } - assert(p - seed < 5 * area); + assert(p - desc < 5 * area); *p++ = '\0'; - seed = sresize(seed, p - seed, char); + desc = sresize(desc, p - desc, char); } sfree(grid); - return seed; + return desc; } -static char *validate_seed(game_params *params, char *seed) +static void game_free_aux_info(game_aux_info *aux) +{ + sfree(aux->grid); + sfree(aux); +} + +static char *validate_desc(game_params *params, char *desc) { int area = params->r * params->r * params->c * params->c; int squares = 0; - while (*seed) { - int n = *seed++; + while (*desc) { + int n = *desc++; if (n >= 'a' && n <= 'z') { squares += n - 'a' + 1; } else if (n == '_') { /* do nothing */; } else if (n > '0' && n <= '9') { squares++; - while (*seed >= '0' && *seed <= '9') - seed++; + while (*desc >= '0' && *desc <= '9') + desc++; } else - return "Invalid character in game specification"; + return "Invalid character in game description"; } if (squares < area) @@ -1163,7 +1589,7 @@ static char *validate_seed(game_params *params, char *seed) return NULL; } -static game_state *new_game(game_params *params, char *seed) +static game_state *new_game(game_params *params, char *desc) { game_state *state = snew(game_state); int c = params->c, r = params->r, cr = c*r, area = cr * cr; @@ -1176,11 +1602,11 @@ static game_state *new_game(game_params *params, char *seed) state->immutable = snewn(area, unsigned char); memset(state->immutable, FALSE, area); - state->completed = FALSE; + state->completed = state->cheated = FALSE; i = 0; - while (*seed) { - int n = *seed++; + while (*desc) { + int n = *desc++; if (n >= 'a' && n <= 'z') { int run = n - 'a' + 1; assert(i + run <= area); @@ -1191,9 +1617,9 @@ static game_state *new_game(game_params *params, char *seed) } else if (n > '0' && n <= '9') { assert(i < area); state->immutable[i] = TRUE; - state->grid[i++] = atoi(seed-1); - while (*seed >= '0' && *seed <= '9') - seed++; + state->grid[i++] = atoi(desc-1); + while (*desc >= '0' && *desc <= '9') + desc++; } else { assert(!"We can't get here"); } @@ -1218,6 +1644,7 @@ static game_state *dup_game(game_state *state) memcpy(ret->immutable, state->immutable, area); ret->completed = state->completed; + ret->cheated = state->cheated; return ret; } @@ -1229,6 +1656,104 @@ static void free_game(game_state *state) sfree(state); } +static game_state *solve_game(game_state *state, game_aux_info *ai, + char **error) +{ + game_state *ret; + int c = state->c, r = state->r, cr = c*r; + int rsolve_ret; + + ret = dup_game(state); + ret->completed = ret->cheated = TRUE; + + /* + * If we already have the solution in the aux_info, save + * ourselves some time. + */ + if (ai) { + + assert(c == ai->c); + assert(r == ai->r); + memcpy(ret->grid, ai->grid, cr * cr * sizeof(digit)); + + } else { + rsolve_ret = rsolve(c, r, ret->grid, NULL, 2); + + if (rsolve_ret != 1) { + free_game(ret); + if (rsolve_ret == 0) + *error = "No solution exists for this puzzle"; + else + *error = "Multiple solutions exist for this puzzle"; + return NULL; + } + } + + return ret; +} + +static char *grid_text_format(int c, int r, digit *grid) +{ + int cr = c*r; + int x, y; + int maxlen; + char *ret, *p; + + /* + * There are cr lines of digits, plus r-1 lines of block + * separators. Each line contains cr digits, cr-1 separating + * spaces, and c-1 two-character block separators. Thus, the + * total length of a line is 2*cr+2*c-3 (not counting the + * newline), and there are cr+r-1 of them. + */ + maxlen = (cr+r-1) * (2*cr+2*c-2); + ret = snewn(maxlen+1, char); + p = ret; + + for (y = 0; y < cr; y++) { + for (x = 0; x < cr; x++) { + int ch = grid[y * cr + x]; + if (ch == 0) + ch = ' '; + else if (ch <= 9) + ch = '0' + ch; + else + ch = 'a' + ch-10; + *p++ = ch; + if (x+1 < cr) { + *p++ = ' '; + if ((x+1) % r == 0) { + *p++ = '|'; + *p++ = ' '; + } + } + } + *p++ = '\n'; + if (y+1 < cr && (y+1) % c == 0) { + for (x = 0; x < cr; x++) { + *p++ = '-'; + if (x+1 < cr) { + *p++ = '-'; + if ((x+1) % r == 0) { + *p++ = '+'; + *p++ = '-'; + } + } + } + *p++ = '\n'; + } + } + + assert(p - ret == maxlen); + *p = '\0'; + return ret; +} + +static char *game_text_format(game_state *state) +{ + return grid_text_format(state->c, state->r, state->grid); +} + struct game_ui { /* * These are the coordinates of the currently highlighted @@ -1260,8 +1785,10 @@ static game_state *make_move(game_state *from, game_ui *ui, int x, int y, int tx, ty; game_state *ret; - tx = (x - BORDER) / TILE_SIZE; - ty = (y - BORDER) / TILE_SIZE; + button &= ~MOD_NUM_KEYPAD; /* we treat this the same as normal */ + + tx = (x + TILE_SIZE - BORDER) / TILE_SIZE - 1; + ty = (y + TILE_SIZE - BORDER) / TILE_SIZE - 1; if (tx >= 0 && tx < cr && ty >= 0 && ty < cr && button == LEFT_BUTTON) { if (tx == ui->hx && ty == ui->hy) { @@ -1494,7 +2021,8 @@ static float game_anim_length(game_state *oldstate, game_state *newstate, static float game_flash_length(game_state *oldstate, game_state *newstate, int dir) { - if (!oldstate->completed && newstate->completed) + if (!oldstate->completed && newstate->completed && + !oldstate->cheated && !newstate->cheated) return FLASH_TIME; return 0.0F; } @@ -1509,21 +2037,23 @@ static int game_wants_statusbar(void) #endif const struct game thegame = { - "Solo", "games.solo", TRUE, + "Solo", "games.solo", default_params, game_fetch_preset, decode_params, encode_params, free_params, dup_params, - game_configure, - custom_params, + TRUE, game_configure, custom_params, validate_params, - new_game_seed, - validate_seed, + new_game_desc, + game_free_aux_info, + validate_desc, new_game, dup_game, free_game, + TRUE, solve_game, + TRUE, game_text_format, new_ui, free_ui, make_move, @@ -1539,6 +2069,10 @@ const struct game thegame = { #ifdef STANDALONE_SOLVER +/* + * gcc -DSTANDALONE_SOLVER -o solosolver solo.c malloc.c + */ + void frontend_default_colour(frontend *fe, float *output) {} void draw_text(frontend *fe, int x, int y, int fonttype, int fontsize, int align, int colour, char *text) {} @@ -1551,8 +2085,10 @@ void unclip(frontend *fe) {} void start_draw(frontend *fe) {} void draw_update(frontend *fe, int x, int y, int w, int h) {} void end_draw(frontend *fe) {} - -#include +unsigned long random_bits(random_state *state, int bits) +{ assert(!"Shouldn't get randomness"); return 0; } +unsigned long random_upto(random_state *state, unsigned long limit) +{ assert(!"Shouldn't get randomness"); return 0; } void fatal(char *fmt, ...) { @@ -1572,9 +2108,10 @@ int main(int argc, char **argv) { game_params *p; game_state *s; - int recurse = FALSE; - char *id = NULL, *seed, *err; + int recurse = TRUE; + char *id = NULL, *desc, *err; int y, x; + int grade = FALSE; while (--argc > 0) { char *p = *++argv; @@ -1582,6 +2119,12 @@ int main(int argc, char **argv) recurse = TRUE; } else if (!strcmp(p, "-n")) { recurse = FALSE; + } else if (!strcmp(p, "-v")) { + solver_show_working = TRUE; + recurse = FALSE; + } else if (!strcmp(p, "-g")) { + grade = TRUE; + recurse = FALSE; } else if (*p == '-') { fprintf(stderr, "%s: unrecognised option `%s'\n", argv[0]); return 1; @@ -1591,41 +2134,61 @@ int main(int argc, char **argv) } if (!id) { - fprintf(stderr, "usage: %s [-n | -r] \n", argv[0]); + fprintf(stderr, "usage: %s [-n | -r | -g | -v] \n", argv[0]); return 1; } - seed = strchr(id, ':'); - if (!seed) { + desc = strchr(id, ':'); + if (!desc) { fprintf(stderr, "%s: game id expects a colon in it\n", argv[0]); return 1; } - *seed++ = '\0'; + *desc++ = '\0'; - p = decode_params(id); - err = validate_seed(p, seed); + p = default_params(); + decode_params(p, id); + err = validate_desc(p, desc); if (err) { fprintf(stderr, "%s: %s\n", argv[0], err); return 1; } - s = new_game(p, seed); + s = new_game(p, desc); if (recurse) { int ret = rsolve(p->c, p->r, s->grid, NULL, 2); if (ret > 1) { - printf("multiple solutions detected; only first one output\n"); + fprintf(stderr, "%s: rsolve: multiple solutions detected\n", + argv[0]); } } else { - nsolve(p->c, p->r, s->grid); - } - - for (y = 0; y < p->c * p->r; y++) { - for (x = 0; x < p->c * p->r; x++) { - printf("%2.0d", s->grid[y * p->c * p->r + x]); + int ret = nsolve(p->c, p->r, s->grid); + if (grade) { + if (ret == DIFF_IMPOSSIBLE) { + /* + * Now resort to rsolve to determine whether it's + * really soluble. + */ + ret = rsolve(p->c, p->r, s->grid, NULL, 2); + if (ret == 0) + ret = DIFF_IMPOSSIBLE; + else if (ret == 1) + ret = DIFF_RECURSIVE; + else + ret = DIFF_AMBIGUOUS; + } + printf("Difficulty rating: %s\n", + ret==DIFF_BLOCK ? "Trivial (blockwise positional elimination only)": + ret==DIFF_SIMPLE ? "Basic (row/column/number elimination required)": + ret==DIFF_INTERSECT ? "Intermediate (intersectional analysis required)": + ret==DIFF_SET ? "Advanced (set elimination required)": + ret==DIFF_RECURSIVE ? "Unreasonable (guesswork and backtracking required)": + ret==DIFF_AMBIGUOUS ? "Ambiguous (multiple solutions exist)": + ret==DIFF_IMPOSSIBLE ? "Impossible (no solution exists)": + "INTERNAL ERROR: unrecognised difficulty code"); } - printf("\n"); } - printf("\n"); + + printf("%s\n", grid_text_format(p->c, p->r, s->grid)); return 0; }