*
* 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
#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 {
game_params *ret = snew(game_params);
ret->c = ret->r = 3;
+ ret->symm = SYMM_ROT2; /* a plausible default */
return ret;
}
*params = ret = snew(game_params);
ret->c = c;
ret->r = r;
+ ret->symm = SYMM_ROT2;
/* FIXME: difficulty presets? */
return TRUE;
}
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;
{
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);
}
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;
}
ret->c = atoi(cfg[0].sval);
ret->r = atoi(cfg[1].sval);
+ ret->symm = cfg[2].ival;
return ret;
}
* 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;
/*
* 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;
/*
/* 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)
{
* 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
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;
}
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
/*
* 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;
/*
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.
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;
/*
*/
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;
/*
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;
int nlocs;
int ret;
char *seed;
+ int coords[16], ncoords;
+ int xlim, ylim;
/*
* Start the recursive solver with an empty grid to generate a
* 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;
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;
}
}
~mdw / sgt / puzzles / blobdiff