ref: f5138782b18c7445c5a42fc4d3161413686865f0
parent: 3346ae2e54c05590434165718888973a4cc4477e
author: Simon Tatham <anakin@pobox.com>
date: Sun Apr 24 05:21:57 EDT 2005
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. [originally from svn r5666]
--- a/puzzles.but
+++ b/puzzles.but
@@ -583,6 +583,44 @@
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.--- a/solo.c
+++ b/solo.c
@@ -3,8 +3,6 @@
*
* 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.
@@ -11,23 +9,20 @@
*
* - implement stronger modes of reasoning in nsolve, thus
* enabling harder puzzles
+ * + and having done that, supply configurable difficulty
+ * levels
*
- * - configurable difficulty levels
+ * - it might still be nice to do some prioritisation on the
+ * removal of numbers from the grid
+ * + one possibility is to try to minimise the maximum number
+ * of filled squares in any block, which in particular ought
+ * to enforce never leaving a completely filled block in the
+ * puzzle as presented.
+ * + be careful of being too clever here, though, until after
+ * I've tried implementing difficulty levels. It's not
+ * impossible that those might impose much more important
+ * constraints on this process.
*
- * - 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.
- *
* - alternative interface modes
* + sudoku.com's Windows program has a palette of possible
* entries; you select a palette entry first and then click
@@ -97,17 +92,19 @@
#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 @@
game_params *ret = snew(game_params);
ret->c = ret->r = 3;
+ ret->symm = SYMM_ROT2; /* a plausible default */
return ret;
}
@@ -146,6 +144,7 @@
*params = ret = snew(game_params);
ret->c = c;
ret->r = r;
+ ret->symm = SYMM_ROT2;
/* FIXME: difficulty presets? */
return TRUE;
}
@@ -167,6 +166,7 @@
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++;
@@ -173,6 +173,20 @@
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 @@
{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 @@
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 @@
ret->c = atoi(cfg[0].sval);
ret->r = atoi(cfg[1].sval);
+ ret->symm = cfg[2].ival;
return ret;
}
@@ -905,6 +930,70 @@
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 @@
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 @@
* 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 @@
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;
}
}