X-Git-Url: https://git.distorted.org.uk/~mdw/sgt/puzzles/blobdiff_plain/1d8e8ad877a2eb931659f6d5b531684a42ba28f1..4846f788f861e4c7d895831ba77c497f6875d998:/solo.c diff --git a/solo.c b/solo.c index dfeeca5..70eaa99 100644 --- a/solo.c +++ b/solo.c @@ -3,30 +3,25 @@ * * 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 + * + and having done that, supply configurable difficulty + * levels * - * - 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. + * + 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 @@ -97,17 +92,19 @@ typedef unsigned char digit; #define FLASH_TIME 0.4F +enum { SYMM_NONE, SYMM_ROT2, SYMM_ROT4, SYMM_REF4 }; + 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; }; struct game_state { @@ -122,6 +119,7 @@ static game_params *default_params(void) game_params *ret = snew(game_params); ret->c = ret->r = 3; + ret->symm = SYMM_ROT2; /* a plausible default */ return ret; } @@ -146,6 +144,7 @@ static int game_fetch_preset(int i, char **name, game_params **params) *params = ret = snew(game_params); ret->c = c; ret->r = r; + ret->symm = SYMM_ROT2; /* FIXME: difficulty presets? */ return TRUE; } @@ -167,12 +166,27 @@ 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++; } + 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; + } /* FIXME: difficulty levels */ return ret; @@ -182,6 +196,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 +224,19 @@ static config_item *game_configure(game_params *params) ret[1].sval = dupstr(buf); ret[1].ival = 0; + 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; + /* * FIXME: difficulty level. */ - ret[2].name = NULL; - ret[2].type = C_END; - ret[2].sval = NULL; - ret[2].ival = 0; + ret[3].name = NULL; + ret[3].type = C_END; + ret[3].sval = NULL; + ret[3].ival = 0; return ret; } @@ -221,8 +245,9 @@ 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; return ret; } @@ -544,6 +569,22 @@ static int rsolve(int c, int r, digit *grid, random_state *rs, int max) * them can be in the fourth or fifth squares.) */ +/* + * 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 +593,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 +613,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,16 +653,16 @@ 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 @@ -628,112 +672,33 @@ static void nsolve_place(struct nsolve_usage *usage, int x, int y, int n) usage->blk[((y/c)*c+(x/r))*cr+n-1] = TRUE; } -static int nsolve_blk_pos_elim(struct nsolve_usage *usage, - int x, int y, int n) -{ - int c = usage->c, r = usage->r; - int i, j, fx, fy, m; - - x *= r; - y *= c; - - /* - * Count the possible positions within this block where this - * number could appear. - */ - 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++; - } - - if (m == 1) { - assert(fx >= 0 && fy >= 0); - nsolve_place(usage, fx, fy, n); - return TRUE; - } - - return FALSE; -} - -static int nsolve_row_pos_elim(struct nsolve_usage *usage, - int y, int n) -{ - int cr = usage->cr; - int x, fx, m; - - /* - * Count the possible positions within this row where this - * number could appear. - */ - m = 0; - fx = -1; - for (x = 0; x < cr; x++) - if (cube(x,y,n)) { - fx = x; - m++; - } - - if (m == 1) { - assert(fx >= 0); - nsolve_place(usage, fx, y, n); - return TRUE; - } - - return FALSE; -} - -static int nsolve_col_pos_elim(struct nsolve_usage *usage, - int x, int n) +static int nsolve_elim(struct nsolve_usage *usage, int start, int step) { - int cr = usage->cr; - int y, fy, m; + int c = usage->c, r = usage->r, cr = c*r; + int fpos, m, i; /* - * Count the possible positions within this column where this - * number could appear. + * Count the number of set bits within this section of the + * cube. */ m = 0; - fy = -1; - for (y = 0; y < cr; y++) - if (cube(x,y,n)) { - fy = y; + fpos = -1; + for (i = 0; i < cr; i++) + if (usage->cube[start+i*step]) { + fpos = start+i*step; m++; } if (m == 1) { - assert(fy >= 0); - nsolve_place(usage, x, fy, n); - return TRUE; - } + int x, y, n; + assert(fpos >= 0); - return FALSE; -} - -static int nsolve_num_elim(struct nsolve_usage *usage, - int x, int y) -{ - int cr = usage->cr; - int n, fn, m; - - /* - * Count the possible numbers that could appear in this square. - */ - m = 0; - fn = -1; - for (n = 1; n <= cr; n++) - if (cube(x,y,n)) { - fn = n; - m++; - } + n = 1 + fpos % cr; + y = fpos / cr; + x = y / cr; + y %= cr; - if (m == 1) { - assert(fn > 0); - nsolve_place(usage, x, y, fn); + nsolve_place(usage, x, y, n); return TRUE; } @@ -771,7 +736,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 @@ -784,11 +749,11 @@ static int nsolve(int c, int r, digit *grid) /* * 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)) + if (!usage->blk[(y*c+(x/r))*cr+n-1] && + nsolve_elim(usage, cubepos(x,y,n), r*cr)) continue; /* @@ -797,7 +762,7 @@ 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)) + nsolve_elim(usage, cubepos(0,y,n), cr*cr)) continue; /* * Column-wise positional elimination. @@ -805,7 +770,7 @@ static int nsolve(int c, int r, digit *grid) 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)) + nsolve_elim(usage, cubepos(x,0,n), cr)) continue; /* @@ -813,8 +778,8 @@ static int nsolve(int c, int r, digit *grid) */ for (x = 0; x < cr; x++) for (y = 0; y < cr; y++) - if (!usage->grid[y*cr+x] && - nsolve_num_elim(usage, x, y)) + if (!usage->grid[YUNTRANS(y)*cr+x] && + nsolve_elim(usage, cubepos(x,y,1), 1)) continue; /* @@ -905,6 +870,70 @@ static int check_valid(int c, int r, digit *grid) return TRUE; } +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; +} + static char *new_game_seed(game_params *params, random_state *rs) { int c = params->c, r = params->r, cr = c*r; @@ -914,6 +943,8 @@ static char *new_game_seed(game_params *params, random_state *rs) int nlocs; int ret; char *seed; + int coords[16], ncoords; + int xlim, ylim; /* * Start the recursive solver with an empty grid to generate a @@ -967,19 +998,20 @@ static char *new_game_seed(game_params *params, random_state *rs) * Now we have a solved grid, start removing things from it * while preserving solubility. */ - locs = snewn((cr+1)/2 * (cr+1)/2, struct xy); + locs = snewn(area, struct xy); grid2 = snewn(area, digit); + symmetry_limit(params, &xlim, &ylim, params->symm); while (1) { - int x, y, i; + int x, y, i, j; /* - * Iterate over the top left corner of the grid and - * enumerate all the filled squares we could empty. + * Iterate over the grid and enumerate all the filled + * squares we could empty. */ nlocs = 0; - for (x = 0; 2*x < cr; x++) - for (y = 0; 2*y < cr; y++) + 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; @@ -1009,16 +1041,13 @@ static char *new_game_seed(game_params *params, random_state *rs) 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; + 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)) { - 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; + for (j = 0; j < ncoords; j++) + grid[coords[2*j+1]*cr+coords[2*j]] = 0; break; } }