*
* TODO:
*
- * - Jigsaw Sudoku is currently an undocumented feature enabled
- * by setting r (`Rows of sub-blocks' in the GUI configurer) to
- * 1. The reason it's undocumented is because they're rather
- * erratic to generate, because gridgen tends to hang up for
- * ages. I think this is because some jigsaw block layouts
- * simply do not admit very many valid filled grids (and
- * perhaps some have none at all).
- * + To fix this, I think probably the solution is a change in
- * grid generation policy: gridgen needs to have less of an
- * all-or-nothing attitude and instead make only a limited
- * amount of effort to construct a filled grid before giving
- * up and trying a new layout. (Come to think of it, this
- * same change might also make 5x5 standard Sudoku more
- * practical to generate, if correctly tuned.)
- * + If I get this fixed, other work needed on jigsaw mode is:
- * * introduce a GUI config checkbox. game_configure()
- * ticks this box iff r==1; if it's ticked in a call to
- * custom_params(), we replace (c, r) with (c*r, 1).
- * * document it.
- *
* - reports from users are that `Trivial'-mode puzzles are still
* rather hard compared to newspapers' easy ones, so some better
* low-end difficulty grading would be nice
{ "3x3 Advanced X", { 3, 3, SYMM_ROT2, DIFF_SET, TRUE } },
{ "3x3 Extreme", { 3, 3, SYMM_ROT2, DIFF_EXTREME, FALSE } },
{ "3x3 Unreasonable", { 3, 3, SYMM_ROT2, DIFF_RECURSIVE, FALSE } },
+ { "9 Jigsaw Basic", { 9, 1, SYMM_ROT2, DIFF_SIMPLE, FALSE } },
+ { "9 Jigsaw Basic X", { 9, 1, SYMM_ROT2, DIFF_SIMPLE, TRUE } },
+ { "9 Jigsaw Advanced", { 9, 1, SYMM_ROT2, DIFF_SET, FALSE } },
#ifndef SLOW_SYSTEM
{ "3x4 Basic", { 3, 4, SYMM_ROT2, DIFF_SIMPLE, FALSE } },
{ "4x4 Basic", { 4, 4, SYMM_ROT2, DIFF_SIMPLE, FALSE } },
config_item *ret;
char buf[80];
- ret = snewn(6, config_item);
+ ret = snewn(7, config_item);
ret[0].name = "Columns of sub-blocks";
ret[0].type = C_STRING;
ret[2].sval = NULL;
ret[2].ival = params->xtype;
- ret[3].name = "Symmetry";
- ret[3].type = C_CHOICES;
- ret[3].sval = ":None:2-way rotation:4-way rotation:2-way mirror:"
+ ret[3].name = "Jigsaw (irregularly shaped sub-blocks)";
+ ret[3].type = C_BOOLEAN;
+ ret[3].sval = NULL;
+ ret[3].ival = (params->r == 1);
+
+ ret[4].name = "Symmetry";
+ ret[4].type = C_CHOICES;
+ ret[4].sval = ":None:2-way rotation:4-way rotation:2-way mirror:"
"2-way diagonal mirror:4-way mirror:4-way diagonal mirror:"
"8-way mirror";
- ret[3].ival = params->symm;
+ ret[4].ival = params->symm;
- ret[4].name = "Difficulty";
- ret[4].type = C_CHOICES;
- ret[4].sval = ":Trivial:Basic:Intermediate:Advanced:Extreme:Unreasonable";
- ret[4].ival = params->diff;
+ ret[5].name = "Difficulty";
+ ret[5].type = C_CHOICES;
+ ret[5].sval = ":Trivial:Basic:Intermediate:Advanced:Extreme:Unreasonable";
+ ret[5].ival = params->diff;
- ret[5].name = NULL;
- ret[5].type = C_END;
- ret[5].sval = NULL;
- ret[5].ival = 0;
+ ret[6].name = NULL;
+ ret[6].type = C_END;
+ ret[6].sval = NULL;
+ ret[6].ival = 0;
return ret;
}
ret->c = atoi(cfg[0].sval);
ret->r = atoi(cfg[1].sval);
ret->xtype = cfg[2].ival;
- ret->symm = cfg[3].ival;
- ret->diff = cfg[4].ival;
+ if (cfg[3].ival) {
+ ret->c *= ret->r;
+ ret->r = 1;
+ }
+ ret->symm = cfg[4].ival;
+ ret->diff = cfg[5].ival;
return ret;
}
random_state *rs;
};
+static void gridgen_place(struct gridgen_usage *usage, int x, int y, digit n,
+ int placing)
+{
+ int cr = usage->cr;
+ usage->row[y*cr+n-1] = usage->col[x*cr+n-1] =
+ usage->blk[usage->blocks->whichblock[y*cr+x]*cr+n-1] = placing;
+ if (usage->diag) {
+ if (ondiag0(y*cr+x))
+ usage->diag[n-1] = placing;
+ if (ondiag1(y*cr+x))
+ usage->diag[cr+n-1] = placing;
+ }
+ usage->grid[y*cr+x] = placing ? n : 0;
+}
+
/*
* The real recursive step in the generating function.
*
* Return values: 1 means solution found, 0 means no solution
* found on this branch.
*/
-static int gridgen_real(struct gridgen_usage *usage, digit *grid)
+static int gridgen_real(struct gridgen_usage *usage, digit *grid, int *steps)
{
int cr = usage->cr;
int i, j, n, sx, sy, bestm, bestr, ret;
* Firstly, check for completion! If there are no spaces left
* in the grid, we have a solution.
*/
- if (usage->nspaces == 0) {
- memcpy(grid, usage->grid, cr * cr);
+ if (usage->nspaces == 0)
return TRUE;
- }
+
+ /*
+ * Next, abandon generation if we went over our steps limit.
+ */
+ if (*steps <= 0)
+ return FALSE;
+ (*steps)--;
/*
* Otherwise, there must be at least one space. Find the most
n = digits[i];
/* Update the usage structure to reflect the placing of this digit. */
- usage->row[sy*cr+n-1] = usage->col[sx*cr+n-1] =
- usage->blk[usage->blocks->whichblock[sy*cr+sx]*cr+n-1] = TRUE;
- if (usage->diag) {
- if (ondiag0(sy*cr+sx))
- usage->diag[n-1] = TRUE;
- if (ondiag1(sy*cr+sx))
- usage->diag[cr+n-1] = TRUE;
- }
- usage->grid[sy*cr+sx] = n;
+ gridgen_place(usage, sx, sy, n, TRUE);
usage->nspaces--;
/* Call the solver recursively. Stop when we find a solution. */
- if (gridgen_real(usage, grid))
+ if (gridgen_real(usage, grid, steps)) {
ret = TRUE;
+ break;
+ }
/* Revert the usage structure. */
- usage->row[sy*cr+n-1] = usage->col[sx*cr+n-1] =
- usage->blk[usage->blocks->whichblock[sy*cr+sx]*cr+n-1] = FALSE;
- if (usage->diag) {
- if (ondiag0(sy*cr+sx))
- usage->diag[n-1] = FALSE;
- if (ondiag1(sy*cr+sx))
- usage->diag[cr+n-1] = FALSE;
- }
- usage->grid[sy*cr+sx] = 0;
+ gridgen_place(usage, sx, sy, n, FALSE);
usage->nspaces++;
-
- if (ret)
- break;
}
sfree(digits);
* grid, which is simply an array of cr*cr digits.
*/
static int gridgen(int cr, struct block_structure *blocks, int xtype,
- digit *grid, random_state *rs)
+ digit *grid, random_state *rs, int maxsteps)
{
struct gridgen_usage *usage;
int x, y, ret;
usage->cr = cr;
usage->blocks = blocks;
- usage->grid = snewn(cr * cr, digit);
- memcpy(usage->grid, grid, cr * cr);
+ usage->grid = grid;
usage->row = snewn(cr * cr, unsigned char);
usage->col = snewn(cr * cr, unsigned char);
usage->diag = NULL;
}
+ /*
+ * Begin by filling in the whole top row with randomly chosen
+ * numbers. This cannot introduce any bias or restriction on
+ * the available grids, since we already know those numbers
+ * are all distinct so all we're doing is choosing their
+ * labels.
+ */
+ for (x = 0; x < cr; x++)
+ grid[x] = x+1;
+ shuffle(grid, cr, sizeof(*grid), rs);
+ for (x = 0; x < cr; x++)
+ gridgen_place(usage, x, 0, grid[x], TRUE);
+
usage->spaces = snewn(cr * cr, struct gridgen_coord);
usage->nspaces = 0;
usage->rs = rs;
/*
- * Initialise the list of grid spaces.
+ * Initialise the list of grid spaces, taking care to leave
+ * out the row I've already filled in above.
*/
- for (y = 0; y < cr; y++) {
+ for (y = 1; y < cr; y++) {
for (x = 0; x < cr; x++) {
usage->spaces[usage->nspaces].x = x;
usage->spaces[usage->nspaces].y = y;
/*
* Run the real generator function.
*/
- ret = gridgen_real(usage, grid);
+ ret = gridgen_real(usage, grid, &maxsteps);
/*
* Clean up the usage structure now we have our answer.
sfree(usage->blk);
sfree(usage->col);
sfree(usage->row);
- sfree(usage->grid);
sfree(usage);
return ret;
blocks->blocks[b][j] = i;
}
- if (!gridgen(cr, blocks, params->xtype, grid, rs))
- continue; /* this might happen if the jigsaw is unsuitable */
+ if (!gridgen(cr, blocks, params->xtype, grid, rs, area*area))
+ continue;
assert(check_valid(cr, blocks, params->xtype, grid));
/*
return "Too much data to fit in grid";
if (params->r == 1) {
+ int pos;
+
/*
* Now we expect a suffix giving the jigsaw block
* structure. Parse it and validate that it divides the
*/
if (*desc != ',')
return "Expected jigsaw block structure in game description";
- int pos = 0;
+ pos = 0;
dsf = snew_dsf(area);
desc++;
if (*desc == '_')
c = 0;
- else if (*desc >= 'a' && *desc <= 'z')
+ else {
+ assert(*desc >= 'a' && *desc <= 'z');
c = *desc - 'a' + 1;
- else
- assert(!"Shouldn't get here");
+ }
desc++;
adv = (c != 25); /* 'z' is a special case */
return ret;
}
+static int game_can_format_as_text_now(game_params *params)
+{
+ return TRUE;
+}
+
static char *game_text_format(game_state *state)
{
return grid_text_format(state->cr, state->blocks, state->xtype,
*/
if (state->xtype) {
int i;
- int xhighlight = print_grey_colour(dr, HATCH_SLASH, 0.90F);
+ int xhighlight = print_grey_colour(dr, 0.90F);
for (i = 0; i < cr; i++)
draw_rect(dr, BORDER + i*TILE_SIZE, BORDER + i*TILE_SIZE,
dup_game,
free_game,
TRUE, solve_game,
- TRUE, game_text_format,
+ TRUE, game_can_format_as_text_now, game_text_format,
new_ui,
free_ui,
encode_ui,
~mdw / sgt / puzzles / blobdiff