*
* 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
#define PREFERRED_TILE_SIZE 32
#define TILE_SIZE (ds->tilesize)
#define BORDER (TILE_SIZE / 2)
-#define GRIDEXTRA (TILE_SIZE / 32)
+#define GRIDEXTRA max((TILE_SIZE / 32),1)
#define FLASH_TIME 0.4F
{ "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));
/*
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 */
p += 1 + sprintf(p, "(%d,%d)", bx+1, by+1);
}
}
- assert(p - (char *)state->blocks->blocknames < cr*(sizeof(char *)+80));
+ assert(p - (char *)state->blocks->blocknames < (int)(cr*(sizeof(char *)+80)));
for (i = 0; i < cr; i++)
assert(state->blocks->blocknames[i]);
}
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,
struct game_ui {
/*
* These are the coordinates of the currently highlighted
- * square on the grid, or -1,-1 if there isn't one. When there
- * is, pressing a valid number or letter key or Space will
- * enter that number or letter in the grid.
+ * square on the grid, if hshow = 1.
*/
int hx, hy;
/*
* pencil-mark one or a real one.
*/
int hpencil;
+ /*
+ * This indicates whether or not we're showing the highlight
+ * (used to be hx = hy = -1); important so that when we're
+ * using the cursor keys it doesn't keep coming back at a
+ * fixed position. When hshow = 1, pressing a valid number
+ * or letter key or Space will enter that number or letter in the grid.
+ */
+ int hshow;
+ /*
+ * This indicates whether we're using the highlight as a cursor;
+ * it means that it doesn't vanish on a keypress, and that it is
+ * allowed on immutable squares.
+ */
+ int hcursor;
};
static game_ui *new_ui(game_state *state)
{
game_ui *ui = snew(game_ui);
- ui->hx = ui->hy = -1;
- ui->hpencil = 0;
+ ui->hx = ui->hy = 0;
+ ui->hpencil = ui->hshow = ui->hcursor = 0;
return ui;
}
{
int cr = newstate->cr;
/*
- * We prevent pencil-mode highlighting of a filled square. So
- * if the user has just filled in a square which we had a
- * pencil-mode highlight in (by Undo, or by Redo, or by Solve),
- * then we cancel the highlight.
+ * We prevent pencil-mode highlighting of a filled square, unless
+ * we're using the cursor keys. So if the user has just filled in
+ * a square which we had a pencil-mode highlight in (by Undo, or
+ * by Redo, or by Solve), then we cancel the highlight.
*/
- if (ui->hx >= 0 && ui->hy >= 0 && ui->hpencil &&
+ if (ui->hshow && ui->hpencil && !ui->hcursor &&
newstate->grid[ui->hy * cr + ui->hx] != 0) {
- ui->hx = ui->hy = -1;
+ ui->hshow = 0;
}
}
if (tx >= 0 && tx < cr && ty >= 0 && ty < cr) {
if (button == LEFT_BUTTON) {
if (state->immutable[ty*cr+tx]) {
- ui->hx = ui->hy = -1;
- } else if (tx == ui->hx && ty == ui->hy && ui->hpencil == 0) {
- ui->hx = ui->hy = -1;
+ ui->hshow = 0;
+ } else if (tx == ui->hx && ty == ui->hy &&
+ ui->hshow && ui->hpencil == 0) {
+ ui->hshow = 0;
} else {
ui->hx = tx;
ui->hy = ty;
+ ui->hshow = 1;
ui->hpencil = 0;
}
+ ui->hcursor = 0;
return ""; /* UI activity occurred */
}
if (button == RIGHT_BUTTON) {
* Pencil-mode highlighting for non filled squares.
*/
if (state->grid[ty*cr+tx] == 0) {
- if (tx == ui->hx && ty == ui->hy && ui->hpencil) {
- ui->hx = ui->hy = -1;
+ if (tx == ui->hx && ty == ui->hy &&
+ ui->hshow && ui->hpencil) {
+ ui->hshow = 0;
} else {
ui->hpencil = 1;
ui->hx = tx;
ui->hy = ty;
+ ui->hshow = 1;
}
} else {
- ui->hx = ui->hy = -1;
+ ui->hshow = 0;
}
+ ui->hcursor = 0;
return ""; /* UI activity occurred */
}
}
+ if (IS_CURSOR_MOVE(button)) {
+ move_cursor(button, &ui->hx, &ui->hy, cr, cr, 0);
+ ui->hshow = ui->hcursor = 1;
+ return "";
+ }
+ if (ui->hshow &&
+ (button == CURSOR_SELECT)) {
+ ui->hpencil = 1 - ui->hpencil;
+ ui->hcursor = 1;
+ return "";
+ }
- if (ui->hx != -1 && ui->hy != -1 &&
- ((button >= '1' && button <= '9' && button - '0' <= cr) ||
+ if (ui->hshow &&
+ ((button >= '0' && button <= '9' && button - '0' <= cr) ||
(button >= 'a' && button <= 'z' && button - 'a' + 10 <= cr) ||
(button >= 'A' && button <= 'Z' && button - 'A' + 10 <= cr) ||
- button == ' ' || button == '\010' || button == '\177')) {
+ button == CURSOR_SELECT2 || button == '\010' || button == '\177')) {
int n = button - '0';
if (button >= 'A' && button <= 'Z')
n = button - 'A' + 10;
if (button >= 'a' && button <= 'z')
n = button - 'a' + 10;
- if (button == ' ' || button == '\010' || button == '\177')
+ if (button == CURSOR_SELECT2 || button == '\010' || button == '\177')
n = 0;
/*
- * Can't overwrite this square. In principle this shouldn't
- * happen anyway because we should never have even been
- * able to highlight the square, but it never hurts to be
- * careful.
+ * Can't overwrite this square. This can only happen here
+ * if we're using the cursor keys.
*/
if (state->immutable[ui->hy*cr+ui->hx])
return NULL;
/*
- * Can't make pencil marks in a filled square. In principle
- * this shouldn't happen anyway because we should never
- * have even been able to pencil-highlight the square, but
- * it never hurts to be careful.
+ * Can't make pencil marks in a filled square. Again, this
+ * can only become highlighted if we're using cursor keys.
*/
if (ui->hpencil && state->grid[ui->hy*cr+ui->hx])
return NULL;
sprintf(buf, "%c%d,%d,%d",
(char)(ui->hpencil && n > 0 ? 'P' : 'R'), ui->hx, ui->hy, n);
- ui->hx = ui->hy = -1;
+ if (!ui->hcursor) ui->hshow = 0;
return dupstr(buf);
}
highlight = 1;
/* Highlight active input areas. */
- if (x == ui->hx && y == ui->hy)
+ if (x == ui->hx && y == ui->hy && ui->hshow)
highlight = ui->hpencil ? 2 : 1;
/* Mark obvious errors (ie, numbers which occur more than once
* of pencil marks in the squares.
*/
game_compute_size(params, 900, &pw, &ph);
- *x = pw / 100.0;
- *y = ph / 100.0;
+ *x = pw / 100.0F;
+ *y = ph / 100.0F;
}
static void game_print(drawing *dr, game_state *state, int tilesize)
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,
}
#endif
+
+/* vim: set shiftwidth=4 tabstop=8: */
~mdw / sgt / puzzles / blobdiff