X-Git-Url: https://git.distorted.org.uk/~mdw/sgt/puzzles/blobdiff_plain/3ddae0ff1ac0a8e6b42fb647cfe73b62e16b740d..a1d5acfff9de3df31ef5575b2350a6c8973fb2d1:/solo.c diff --git a/solo.c b/solo.c index b09d8e2..f3afb02 100644 --- a/solo.c +++ b/solo.c @@ -3,25 +3,36 @@ * * 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 - * + * - reports from users are that `Trivial'-mode puzzles are still + * rather hard compared to newspapers' easy ones, so some better + * low-end difficulty grading would be nice + * + it's possible that really easy puzzles always have + * _several_ things you can do, so don't make you hunt too + * hard for the one deduction you can currently make + * + it's also possible that easy puzzles require fewer + * cross-eliminations: perhaps there's a higher incidence of + * things you can deduce by looking only at (say) rows, + * rather than things you have to check both rows and columns + * for + * + but really, what I need to do is find some really easy + * puzzles and _play_ them, to see what's actually easy about + * them + * + while I'm revamping this area, filling in the _last_ + * number in a nearly-full row or column should certainly be + * permitted even at the lowest difficulty level. + * + also Owen noticed that `Basic' grids requiring numeric + * elimination are actually very hard, so I wonder if a + * difficulty gradation between that and positional- + * elimination-only might be in order + * + but it's not good to have _too_ many difficulty levels, or + * it'll take too long to randomly generate a given level. + * * - 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 @@ -33,9 +44,13 @@ * click, _or_ you highlight a square and then type. At most * 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. + * + then again, I don't actually like sudoku.com's interface; + * it's too much like a paint package whereas I prefer to + * think of Solo as a text editor. + * + another PDA-friendly possibility is a drag interface: + * _drag_ numbers from the palette into the grid squares. + * Thought experiments suggest I'd prefer that to the + * sudoku.com approach, but I haven't actually tried it. */ /* @@ -74,8 +89,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,24 +116,29 @@ 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, COL_CLUE, COL_USER, COL_HIGHLIGHT, + COL_PENCIL, NCOLOURS }; struct game_params { - int c, r, symm; + int c, r, symm, diff; }; struct game_state { int c, r; digit *grid; + unsigned char *pencil; /* c*r*c*r elements */ unsigned char *immutable; /* marks which digits are clues */ - int completed; + int completed, cheated; }; static game_params *default_params(void) @@ -120,35 +147,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 +164,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 +277,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 +297,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,25 +598,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.) + * - 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). */ /* @@ -669,10 +729,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; @@ -699,6 +763,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; } @@ -707,11 +781,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 @@ -748,6 +1071,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: /* @@ -757,8 +1087,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. @@ -766,16 +1103,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. @@ -783,8 +1133,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 @@ -802,8 +1255,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; } /* ---------------------------------------------------------------------- @@ -938,7 +1391,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 interactive) { int c = params->c, r = params->r, cr = c*r; int area = cr*cr; @@ -946,150 +1405,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); @@ -1111,7 +1568,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) @@ -1119,33 +1576,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 void game_free_aux_info(game_aux_info *aux) +{ + sfree(aux->grid); + sfree(aux); } -static char *validate_seed(game_params *params, char *seed) +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) @@ -1157,7 +1620,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(midend_data *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; @@ -1167,14 +1630,16 @@ static game_state *new_game(game_params *params, char *seed) state->r = params->r; 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->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); @@ -1185,9 +1650,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"); } @@ -1208,10 +1673,14 @@ static game_state *dup_game(game_state *state) 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; } @@ -1219,10 +1688,109 @@ static game_state *dup_game(game_state *state) static void free_game(game_state *state) { sfree(state->immutable); + sfree(state->pencil); sfree(state->grid); 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 @@ -1231,6 +1799,11 @@ struct game_ui { * enter that number or letter in the grid. */ int hx, hy; + /* + * This indicates whether the current highlight is a + * pencil-mark one or a real one. + */ + int hpencil; }; static game_ui *new_ui(game_state *state) @@ -1238,6 +1811,7 @@ static game_ui *new_ui(game_state *state) game_ui *ui = snew(game_ui); ui->hx = ui->hy = -1; + ui->hpencil = 0; return ui; } @@ -1247,23 +1821,33 @@ static void free_ui(game_ui *ui) sfree(ui); } -static game_state *make_move(game_state *from, game_ui *ui, int x, int y, - int button) +static game_state *make_move(game_state *from, game_ui *ui, game_drawstate *ds, + int x, int y, int button) { int c = from->c, r = from->r, cr = c*r; int tx, ty; game_state *ret; - tx = (x - BORDER) / TILE_SIZE; - ty = (y - BORDER) / TILE_SIZE; + button &= ~MOD_MASK; + + 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 || button == RIGHT_BUTTON)) { + /* + * Prevent pencil-mode highlighting of a filled square. + */ + if (button == RIGHT_BUTTON && from->grid[ty*cr+tx]) + return NULL; - if (tx >= 0 && tx < cr && ty >= 0 && ty < cr && button == LEFT_BUTTON) { if (tx == ui->hx && ty == ui->hy) { ui->hx = ui->hy = -1; } else { ui->hx = tx; ui->hy = ty; } + ui->hpencil = (button == RIGHT_BUTTON); return from; /* UI activity occurred */ } @@ -1283,18 +1867,33 @@ static game_state *make_move(game_state *from, game_ui *ui, int x, int y, if (from->immutable[ui->hy*cr+ui->hx]) return NULL; /* can't overwrite this square */ + /* + * Can't make pencil marks in a filled square. In principle + * this shouldn't happen anyway because we should never + * have even been able to pencil-highlight the square, but + * it never hurts to be careful. + */ + if (ui->hpencil && from->grid[ui->hy*cr+ui->hx]) + return NULL; + ret = dup_game(from); - ret->grid[ui->hy*cr+ui->hx] = n; + if (ui->hpencil && n > 0) { + int index = (ui->hy*cr+ui->hx) * cr + (n-1); + ret->pencil[index] = !ret->pencil[index]; + } else { + ret->grid[ui->hy*cr+ui->hx] = n; + memset(ret->pencil + (ui->hy*cr+ui->hx)*cr, 0, cr); + + /* + * We've made a real change to the grid. Check to see + * if the game has been completed. + */ + if (!ret->completed && check_valid(c, r, ret->grid)) { + ret->completed = TRUE; + } + } ui->hx = ui->hy = -1; - /* - * We've made a real change to the grid. Check to see - * if the game has been completed. - */ - if (!ret->completed && check_valid(c, r, ret->grid)) { - ret->completed = TRUE; - } - return ret; /* made a valid move */ } @@ -1309,6 +1908,7 @@ struct game_drawstate { int started; int c, r, cr; digit *grid; + unsigned char *pencil; unsigned char *hl; }; @@ -1345,6 +1945,10 @@ static float *game_colours(frontend *fe, game_state *state, int *ncolours) ret[COL_HIGHLIGHT * 3 + 1] = 0.85F * ret[COL_BACKGROUND * 3 + 1]; ret[COL_HIGHLIGHT * 3 + 2] = 0.85F * ret[COL_BACKGROUND * 3 + 2]; + ret[COL_PENCIL * 3 + 0] = 0.5F * ret[COL_BACKGROUND * 3 + 0]; + ret[COL_PENCIL * 3 + 1] = 0.5F * ret[COL_BACKGROUND * 3 + 1]; + ret[COL_PENCIL * 3 + 2] = ret[COL_BACKGROUND * 3 + 2]; + *ncolours = NCOLOURS; return ret; } @@ -1360,6 +1964,8 @@ static game_drawstate *game_new_drawstate(game_state *state) ds->cr = cr; ds->grid = snewn(cr*cr, digit); memset(ds->grid, 0, cr*cr); + ds->pencil = snewn(cr*cr*cr, digit); + memset(ds->pencil, 0, cr*cr*cr); ds->hl = snewn(cr*cr, unsigned char); memset(ds->hl, 0, cr*cr); @@ -1369,6 +1975,7 @@ static game_drawstate *game_new_drawstate(game_state *state) static void game_free_drawstate(game_drawstate *ds) { sfree(ds->hl); + sfree(ds->pencil); sfree(ds->grid); sfree(ds); } @@ -1381,7 +1988,9 @@ static void draw_number(frontend *fe, game_drawstate *ds, game_state *state, int cx, cy, cw, ch; char str[2]; - if (ds->grid[y*cr+x] == state->grid[y*cr+x] && ds->hl[y*cr+x] == hl) + if (ds->grid[y*cr+x] == state->grid[y*cr+x] && + ds->hl[y*cr+x] == hl && + !memcmp(ds->pencil+(y*cr+x)*cr, state->pencil+(y*cr+x)*cr, cr)) return; /* no change required */ tx = BORDER + x * TILE_SIZE + 2; @@ -1403,9 +2012,20 @@ static void draw_number(frontend *fe, game_drawstate *ds, game_state *state, clip(fe, cx, cy, cw, ch); - /* background needs erasing? */ - if (ds->grid[y*cr+x] || ds->hl[y*cr+x] != hl) - draw_rect(fe, cx, cy, cw, ch, hl ? COL_HIGHLIGHT : COL_BACKGROUND); + /* background needs erasing */ + draw_rect(fe, cx, cy, cw, ch, hl == 1 ? COL_HIGHLIGHT : COL_BACKGROUND); + + /* pencil-mode highlight */ + if (hl == 2) { + int coords[6]; + coords[0] = cx; + coords[1] = cy; + coords[2] = cx+cw/2; + coords[3] = cy; + coords[4] = cx; + coords[5] = cy+ch/2; + draw_polygon(fe, coords, 3, TRUE, COL_HIGHLIGHT); + } /* new number needs drawing? */ if (state->grid[y*cr+x]) { @@ -1416,6 +2036,23 @@ static void draw_number(frontend *fe, game_drawstate *ds, game_state *state, draw_text(fe, tx + TILE_SIZE/2, ty + TILE_SIZE/2, FONT_VARIABLE, TILE_SIZE/2, ALIGN_VCENTRE | ALIGN_HCENTRE, state->immutable[y*cr+x] ? COL_CLUE : COL_USER, str); + } else { + /* pencil marks required? */ + int i, j; + + for (i = j = 0; i < cr; i++) + if (state->pencil[(y*cr+x)*cr+i]) { + int dx = j % r, dy = j / r, crm = max(c, r); + str[1] = '\0'; + str[0] = i + '1'; + if (str[0] > '9') + str[0] += 'a' - ('9'+1); + draw_text(fe, tx + (4*dx+3) * TILE_SIZE / (4*r+2), + ty + (4*dy+3) * TILE_SIZE / (4*c+2), + FONT_VARIABLE, TILE_SIZE/(crm*5/4), + ALIGN_VCENTRE | ALIGN_HCENTRE, COL_PENCIL, str); + j++; + } } unclip(fe); @@ -1423,6 +2060,7 @@ static void draw_number(frontend *fe, game_drawstate *ds, game_state *state, draw_update(fe, cx, cy, cw, ch); ds->grid[y*cr+x] = state->grid[y*cr+x]; + memcpy(ds->pencil+(y*cr+x)*cr, state->pencil+(y*cr+x)*cr, cr); ds->hl[y*cr+x] = hl; } @@ -1462,11 +2100,14 @@ static void game_redraw(frontend *fe, game_drawstate *ds, game_state *oldstate, */ for (x = 0; x < cr; x++) { for (y = 0; y < cr; y++) { - draw_number(fe, ds, state, x, y, - (x == ui->hx && y == ui->hy) || - (flashtime > 0 && - (flashtime <= FLASH_TIME/3 || - flashtime >= FLASH_TIME*2/3))); + int highlight = 0; + if (flashtime > 0 && + (flashtime <= FLASH_TIME/3 || + flashtime >= FLASH_TIME*2/3)) + highlight = 1; + if (x == ui->hx && y == ui->hy) + highlight = ui->hpencil ? 2 : 1; + draw_number(fe, ds, state, x, y, highlight); } } @@ -1480,15 +2121,16 @@ static void game_redraw(frontend *fe, game_drawstate *ds, game_state *oldstate, } static float game_anim_length(game_state *oldstate, game_state *newstate, - int dir) + int dir, game_ui *ui) { return 0.0F; } static float game_flash_length(game_state *oldstate, game_state *newstate, - int dir) + int dir, game_ui *ui) { - if (!oldstate->completed && newstate->completed) + if (!oldstate->completed && newstate->completed && + !oldstate->cheated && !newstate->cheated) return FLASH_TIME; return 0.0F; } @@ -1498,26 +2140,33 @@ static int game_wants_statusbar(void) return FALSE; } +static int game_timing_state(game_state *state) +{ + return TRUE; +} + #ifdef COMBINED #define thegame solo #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, @@ -1529,10 +2178,15 @@ const struct game thegame = { game_anim_length, game_flash_length, game_wants_statusbar, + FALSE, game_timing_state, }; #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) {} @@ -1545,8 +2199,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, ...) { @@ -1566,9 +2222,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; @@ -1576,6 +2233,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; @@ -1585,41 +2248,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; }