From ef57b17d968689e10ea3b2b6a75d360365645556 Mon Sep 17 00:00:00 2001 From: simon Date: Sun, 24 Apr 2005 09:21:57 +0000 Subject: [PATCH] Introduce configurable symmetry type in generated puzzles, and drop the default symmetry from order-4 down to order-2, which seems to mitigate the excessively-full-grid problem by permitting more freedom to remove stuff. git-svn-id: svn://svn.tartarus.org/sgt/puzzles@5666 cda61777-01e9-0310-a592-d414129be87e --- puzzles.but | 38 ++++++++++++++ solo.c | 171 +++++++++++++++++++++++++++++++++++++++++++++--------------- 2 files changed, 168 insertions(+), 41 deletions(-) diff --git a/puzzles.but b/puzzles.but index cb6a9c1..8e99a31 100644 --- a/puzzles.but +++ b/puzzles.but @@ -583,6 +583,44 @@ rows, into which the main grid is divided. (The size of a block is the inverse of this: for example, if you select 2 columns and 3 rows, each actual block will have 3 columns and 2 rows.) +You can also configure the type of symmetry shown in the generated +puzzles. More symmetry makes the puzzles look prettier but may also +make them easier, since the symmetry constraints can force more +clues than necessary to be present. Completely asymmetric puzzles +have the freedom to contain as few clues as possible. + +\H{solo-cmdline} \I{command line, for Solo}Additional command-line +configuration + +The symmetry parameter, described in \k{solo-parameters}, is not +mentioned by default in the game ID (see \k{common-id}). So if you +set your symmetry to (say) 4-way rotational, and then you generate a +3\by\.4 grid, then the game ID will simply say \c{3x4:}\e{numbers}. +This means that if you send the game ID to another player and they +paste it into their copy of Solo, their game will not be +automatically configured to use the same symmetry in any subsequent +grids it generates. (I don't think the average person examining a +single grid sent to them by another player would want their +configuration modified to that extent.) + +If you are specifying a game ID or game parameters on the command +line (see \k{common-cmdline}) and you do want to configure the +symmetry, you can do it by suffixing additional text to the +parameters: + +\b \cq{m4} for 4-way mirror symmetry + +\b \cq{r4} for 4-way rotational symmetry + +\b \cq{r2} for 2-way rotational symmetry + +\b \cq{a} for no symmetry at all (stands for \q{asymmetric}) + +So, for example, you can make Solo generate asymmetric 3x4 grids by +running \cq{solo 3x4a}, or 4-way rotationally symmetric 2x3 grids by +running \cq{solo 2x3r4}. + + \A{licence} \I{MIT licence}\ii{Licence} This software is \i{copyright} 2004-2005 Simon Tatham. diff --git a/solo.c b/solo.c index 35a081f..24562eb 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; } @@ -223,6 +247,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; return ret; } @@ -905,6 +930,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 +1003,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 +1058,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 +1101,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; } } -- 2.11.0