X-Git-Url: https://git.distorted.org.uk/~mdw/sgt/puzzles/blobdiff_plain/1d8e8ad877a2eb931659f6d5b531684a42ba28f1..4b24f58222c549b383d23ed86a958c9656218c48:/solo.c diff --git a/solo.c b/solo.c index dfeeca5..eb35e00 100644 --- a/solo.c +++ b/solo.c @@ -3,30 +3,12 @@ * * TODO: * - * - finalise game name - * - * - 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 - * - * - configurable difficulty levels - * - * - vary the symmetry (rotational or none)? - * - * - try for cleverer ways of reducing the solved grid; they seem - * to be coming out a bit full for the most part, and in - * particular it's inexcusable to leave a grid with an entire - * block (or presumably row or column) filled! I _hope_ we can - * do this simply by better prioritising (somehow) the possible - * removals. - * + one simple option might be to work the other way: start - * with an empty grid and gradually _add_ numbers until it - * becomes solvable? Perhaps there might be some heuristic - * which enables us to pinpoint the most critical clues and - * thus add as few as possible. + * - 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. * * - alternative interface modes * + sudoku.com's Windows program has a palette of possible @@ -39,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. */ /* @@ -79,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 @@ -97,24 +85,29 @@ typedef unsigned char digit; #define FLASH_TIME 0.4F +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, - NCOLOURS + COL_GRID, + COL_CLUE, + COL_USER, + COL_HIGHLIGHT, + NCOLOURS }; struct game_params { - int c, r; + 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) @@ -122,34 +115,12 @@ static game_params *default_params(void) game_params *ret = snew(game_params); ret->c = ret->r = 3; + ret->symm = SYMM_ROT2; /* a plausible default */ + ret->diff = DIFF_SIMPLE; /* 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; - /* FIXME: difficulty presets? */ - return TRUE; -} - static void free_params(game_params *params) { sfree(params); @@ -162,18 +133,69 @@ static game_params *dup_params(game_params *params) return ret; } +static int game_fetch_preset(int i, char **name, game_params **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 Basic", { 3, 3, SYMM_ROT2, DIFF_SIMPLE } }, + { "3x3 Intermediate", { 3, 3, SYMM_ROT2, DIFF_INTERSECT } }, + { "3x3 Advanced", { 3, 3, SYMM_ROT2, DIFF_SET } }, + { "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 game_params *decode_params(char const *string) { game_params *ret = default_params(); 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++; } - /* FIXME: difficulty levels */ + 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 + string++; /* eat unknown character */ + } return ret; } @@ -182,6 +204,11 @@ static char *encode_params(game_params *params) { 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); return dupstr(str); } @@ -205,14 +232,20 @@ static config_item *game_configure(game_params *params) ret[1].sval = dupstr(buf); ret[1].ival = 0; - /* - * FIXME: difficulty level. - */ + ret[2].name = "Symmetry"; + ret[2].type = C_CHOICES; + ret[2].sval = ":None:2-way rotation:4-way rotation:4-way mirror"; + ret[2].ival = params->symm; - ret[2].name = NULL; - ret[2].type = C_END; - ret[2].sval = NULL; - ret[2].ival = 0; + ret[3].name = "Difficulty"; + ret[3].type = C_CHOICES; + ret[3].sval = ":Trivial:Basic:Intermediate:Advanced"; + ret[3].ival = params->diff; + + ret[4].name = NULL; + ret[4].type = C_END; + ret[4].sval = NULL; + ret[4].ival = 0; return ret; } @@ -221,8 +254,10 @@ static game_params *custom_params(config_item *cfg) { game_params *ret = snew(game_params); - ret->c = atof(cfg[0].sval); - ret->r = atof(cfg[1].sval); + ret->c = atoi(cfg[0].sval); + ret->r = atoi(cfg[1].sval); + ret->symm = cfg[2].ival; + ret->diff = cfg[3].ival; return ret; } @@ -523,27 +558,53 @@ 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). */ +/* + * Within this solver, I'm going to transform all y-coordinates by + * inverting the significance of the block number and the position + * within the block. That is, we will start with the top row of + * each block in order, then the second row of each block in order, + * etc. + * + * This transformation has the enormous advantage that it means + * every row, column _and_ block is described by an arithmetic + * progression of coordinates within the cubic array, so that I can + * use the same very simple function to do blockwise, row-wise and + * column-wise elimination. + */ +#define YTRANS(y) (((y)%c)*r+(y)/c) +#define YUNTRANS(y) (((y)%r)*c+(y)/r) + struct nsolve_usage { int c, r, cr; /* @@ -552,11 +613,12 @@ struct nsolve_usage { * or not that digit _could_ in principle go in that position. * * The way to index this array is cube[(x*cr+y)*cr+n-1]. + * y-coordinates in here are transformed. */ unsigned char *cube; /* * This is the grid in which we write down our final - * deductions. + * deductions. y-coordinates in here are _not_ transformed. */ digit *grid; /* @@ -571,11 +633,13 @@ struct nsolve_usage { /* blk[(y*c+x)*cr+n-1] TRUE if digit n has been placed in block (x,y) */ unsigned char *blk; }; -#define cube(x,y,n) (usage->cube[((x)*usage->cr+(y))*usage->cr+(n)-1]) +#define cubepos(x,y,n) (((x)*usage->cr+(y))*usage->cr+(n)-1) +#define cube(x,y,n) (usage->cube[cubepos(x,y,n)]) /* * Function called when we are certain that a particular square has - * a particular number in it. + * a particular number in it. The y-coordinate passed in here is + * transformed. */ static void nsolve_place(struct nsolve_usage *usage, int x, int y, int n) { @@ -609,134 +673,319 @@ static void nsolve_place(struct nsolve_usage *usage, int x, int y, int n) * Rule out this number in all other positions in the block. */ bx = (x/r)*r; - by = (y/c)*c; + by = y % r; for (i = 0; i < r; i++) for (j = 0; j < c; j++) - if (bx+i != x || by+j != y) - cube(bx+i,by+j,n) = FALSE; + if (bx+i != x || by+j*r != y) + cube(bx+i,by+j*r,n) = FALSE; /* * Enter the number in the result grid. */ - usage->grid[y*cr+x] = n; + usage->grid[YUNTRANS(y)*cr+x] = n; /* * Cross out this number from the list of numbers left to place * 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_blk_pos_elim(struct nsolve_usage *usage, - int x, int y, int n) +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; - int i, j, fx, fy, m; - - x *= r; - y *= c; + int c = usage->c, r = usage->r, cr = c*r; + int fpos, m, i; /* - * Count the possible positions within this block where this - * number could appear. + * Count the number of set bits within this section of the + * cube. */ m = 0; - fx = fy = -1; - for (i = 0; i < r; i++) - for (j = 0; j < c; j++) - if (cube(x+i,y+j,n)) { - fx = x+i; - fy = y+j; - m++; - } + fpos = -1; + for (i = 0; i < cr; i++) + if (usage->cube[start+i*step]) { + fpos = start+i*step; + m++; + } if (m == 1) { - assert(fx >= 0 && fy >= 0); - nsolve_place(usage, fx, fy, n); - return TRUE; + int x, y, n; + assert(fpos >= 0); + + n = 1 + fpos % cr; + y = fpos / cr; + x = y / cr; + 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; + } } return FALSE; } -static int nsolve_row_pos_elim(struct nsolve_usage *usage, - int y, int n) +static int nsolve_intersect(struct nsolve_usage *usage, + int start1, int step1, int start2, int step2 +#ifdef STANDALONE_SOLVER + , char *fmt, ... +#endif + ) { - int cr = usage->cr; - int x, fx, m; + int c = usage->c, r = usage->r, cr = c*r; + int ret, i; /* - * Count the possible positions within this row where this - * number could appear. + * Loop over the first domain and see if there's any set bit + * not also in the second. */ - m = 0; - fx = -1; - for (x = 0; x < cr; x++) - if (cube(x,y,n)) { - fx = x; - m++; - } + 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 */ + } - if (m == 1) { - assert(fx >= 0); - nsolve_place(usage, fx, y, n); - return TRUE; + /* + * 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 FALSE; + return ret; } -static int nsolve_col_pos_elim(struct nsolve_usage *usage, - int x, int n) +static int nsolve_set(struct nsolve_usage *usage, + int start, int step1, int step2 +#ifdef STANDALONE_SOLVER + , char *fmt, ... +#endif + ) { - int cr = usage->cr; - int y, fy, m; + 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); /* - * Count the possible positions within this column where this - * number could appear. + * 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. */ - m = 0; - fy = -1; - for (y = 0; y < cr; y++) - if (cube(x,y,n)) { - fy = y; - m++; - } - - if (m == 1) { - assert(fy >= 0); - nsolve_place(usage, x, fy, n); - return TRUE; + 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; } - return 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); -static int nsolve_num_elim(struct nsolve_usage *usage, - int x, int y) -{ - int cr = usage->cr; - int n, fn, m; + /* + * 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]; /* - * Count the possible numbers that could appear in this square. + * 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. */ - m = 0; - fn = -1; - for (n = 1; n <= cr; n++) - if (cube(x,y,n)) { - fn = n; - m++; - } - if (m == 1) { - assert(fn > 0); - nsolve_place(usage, x, y, fn); - return TRUE; + 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; } @@ -745,6 +994,7 @@ 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 @@ -771,7 +1021,7 @@ 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]) - nsolve_place(usage, x, y, grid[y*cr+x]); + nsolve_place(usage, x, YTRANS(y), grid[y*cr+x]); /* * Now loop over the grid repeatedly trying all permitted modes @@ -781,15 +1031,31 @@ 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: + /* * Blockwise positional elimination. */ - for (x = 0; x < c; x++) + for (x = 0; x < cr; x += r) for (y = 0; y < r; y++) for (n = 1; n <= cr; n++) - if (!usage->blk[((y/c)*c+(x/r))*cr+n-1] && - nsolve_blk_pos_elim(usage, x, y, n)) - continue; + if (!usage->blk[(y*c+(x/r))*cr+n-1] && + 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. @@ -797,25 +1063,141 @@ 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_row_pos_elim(usage, y, n)) - continue; + 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_col_pos_elim(usage, x, n)) - continue; + 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. */ for (x = 0; x < cr; x++) for (y = 0; y < cr; y++) - if (!usage->grid[y*cr+x] && - nsolve_num_elim(usage, x, y)) - continue; + if (!usage->grid[YUNTRANS(y)*cr+x] && + 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 @@ -833,8 +1215,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; } /* ---------------------------------------------------------------------- @@ -905,7 +1287,77 @@ static int check_valid(int c, int r, digit *grid) return TRUE; } -static char *new_game_seed(game_params *params, random_state *rs) +static void symmetry_limit(game_params *params, int *xlim, int *ylim, int s) +{ + int c = params->c, r = params->r, cr = c*r; + + switch (s) { + case SYMM_NONE: + *xlim = *ylim = cr; + break; + case SYMM_ROT2: + *xlim = (cr+1) / 2; + *ylim = cr; + break; + case SYMM_REF4: + case SYMM_ROT4: + *xlim = *ylim = (cr+1) / 2; + break; + } +} + +static int symmetries(game_params *params, int x, int y, int *output, int s) +{ + int c = params->c, r = params->r, cr = c*r; + int i = 0; + + *output++ = x; + *output++ = y; + i++; + + switch (s) { + case SYMM_NONE: + break; /* just x,y is all we need */ + case SYMM_REF4: + case SYMM_ROT4: + switch (s) { + case SYMM_REF4: + *output++ = cr - 1 - x; + *output++ = y; + i++; + + *output++ = x; + *output++ = cr - 1 - y; + i++; + break; + case SYMM_ROT4: + *output++ = cr - 1 - y; + *output++ = x; + i++; + + *output++ = y; + *output++ = cr - 1 - x; + i++; + break; + } + /* fall through */ + case SYMM_ROT2: + *output++ = cr - 1 - x; + *output++ = cr - 1 - y; + i++; + break; + } + + return i; +} + +struct game_aux_info { + int c, r; + digit *grid; +}; + +static char *new_game_seed(game_params *params, random_state *rs, + game_aux_info **aux) { int c = params->c, r = params->r, cr = c*r; int area = cr*cr; @@ -914,139 +1366,122 @@ static char *new_game_seed(game_params *params, random_state *rs) int nlocs; int ret; char *seed; + int coords[16], ncoords; + int xlim, ylim; + int maxdiff; /* - * 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); + maxdiff = params->diff; + if (c == 2 && r == 2) + maxdiff = DIFF_BLOCK; - { - 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 + grid = snewn(area, digit); + locs = snewn(area, struct xy); + grid2 = snewn(area, digit); /* - * Now we have a solved grid, start removing things from it - * while preserving solubility. + * 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. */ - locs = snewn((cr+1)/2 * (cr+1)/2, struct xy); - grid2 = snewn(area, digit); - while (1) { - int x, y, i; + 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)); /* - * Iterate over the top left corner of the grid and - * enumerate all the filled squares we could empty. + * Save the solved grid in the aux_info. */ - nlocs = 0; - - for (x = 0; 2*x < cr; x++) - for (y = 0; 2*y < cr; 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; - } + { + 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); - grid2[y*cr+x] = 0; - grid2[y*cr+cr-1-x] = 0; - grid2[(cr-1-y)*cr+x] = 0; - grid2[(cr-1-y)*cr+cr-1-x] = 0; - - if (nsolve(c, r, grid2)) { - grid[y*cr+x] = 0; - grid[y*cr+cr-1-x] = 0; - grid[(cr-1-y)*cr+x] = 0; - grid[(cr-1-y)*cr+cr-1-x] = 0; - break; - } - } + /* + * Now we have a solved grid, start removing things from it + * while preserving solubility. + */ + 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++; + } + + /* + * 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++) { + 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) <= maxdiff) { + 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. + */ + 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. @@ -1096,6 +1531,12 @@ static char *new_game_seed(game_params *params, random_state *rs) return seed; } +static void game_free_aux_info(game_aux_info *aux) +{ + sfree(aux->grid); + sfree(aux); +} + static char *validate_seed(game_params *params, char *seed) { int area = params->r * params->r * params->c * params->c; @@ -1137,7 +1578,7 @@ 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) { @@ -1179,6 +1620,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; } @@ -1190,6 +1632,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 @@ -1221,8 +1761,8 @@ 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; + 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) { @@ -1455,7 +1995,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; } @@ -1470,21 +2011,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, + game_free_aux_info, validate_seed, new_game, dup_game, free_game, + TRUE, solve_game, + TRUE, game_text_format, new_ui, free_ui, make_move, @@ -1497,3 +2040,130 @@ const struct game thegame = { game_flash_length, game_wants_statusbar, }; + +#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) {} +void draw_rect(frontend *fe, int x, int y, int w, int h, int colour) {} +void draw_line(frontend *fe, int x1, int y1, int x2, int y2, int colour) {} +void draw_polygon(frontend *fe, int *coords, int npoints, + int fill, int colour) {} +void clip(frontend *fe, int x, int y, int w, int h) {} +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) {} +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, ...) +{ + va_list ap; + + fprintf(stderr, "fatal error: "); + + va_start(ap, fmt); + vfprintf(stderr, fmt, ap); + va_end(ap); + + fprintf(stderr, "\n"); + exit(1); +} + +int main(int argc, char **argv) +{ + game_params *p; + game_state *s; + int recurse = TRUE; + char *id = NULL, *seed, *err; + int y, x; + int grade = FALSE; + + while (--argc > 0) { + char *p = *++argv; + if (!strcmp(p, "-r")) { + 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; + } else { + id = p; + } + } + + if (!id) { + fprintf(stderr, "usage: %s [-n | -r | -g | -v] \n", argv[0]); + return 1; + } + + seed = strchr(id, ':'); + if (!seed) { + fprintf(stderr, "%s: game id expects a colon in it\n", argv[0]); + return 1; + } + *seed++ = '\0'; + + p = decode_params(id); + err = validate_seed(p, seed); + if (err) { + fprintf(stderr, "%s: %s\n", argv[0], err); + return 1; + } + s = new_game(p, seed); + + if (recurse) { + int ret = rsolve(p->c, p->r, s->grid, NULL, 2); + if (ret > 1) { + fprintf(stderr, "%s: rsolve: multiple solutions detected\n", + argv[0]); + } + } else { + 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("%s\n", grid_text_format(p->c, p->r, s->grid)); + + return 0; +} + +#endif