X-Git-Url: http://www.chiark.greenend.org.uk/ucgi/~ian/git?p=sgt-puzzles.git;a=blobdiff_plain;f=keen.c;h=b91e95bc9e1f095bfb7918296025b4e45d5e818f;hp=da55fb2084503b4c9a546c6fe3205c6e1ece6d67;hb=3ce69e84cad15844282d691fa03e711c5353c05e;hpb=980880be1f2801b2a69fcc67abc0f5827fd106f2 diff --git a/keen.c b/keen.c index da55fb2..b91e95b 100644 --- a/keen.c +++ b/keen.c @@ -1,5 +1,6 @@ /* - * keen.c: an implementation of the Times's 'KenKen' puzzle. + * keen.c: an implementation of the Times's 'KenKen' puzzle, and + * also of Nikoli's very similar 'Inshi No Heya' puzzle. */ #include @@ -42,6 +43,14 @@ static char const keen_diffchars[] = DIFFLIST(ENCODE); #define CMASK 0x60000000L #define CUNIT 0x20000000L +/* + * Maximum size of any clue block. Very large ones are annoying in UI + * terms (if they're multiplicative you end up with too many digits to + * fit in the square) and also in solver terms (too many possibilities + * to iterate over). + */ +#define MAXBLK 6 + enum { COL_BACKGROUND, COL_GRID, @@ -53,7 +62,7 @@ enum { }; struct game_params { - int w, diff; + int w, diff, multiplication_only; }; struct clues { @@ -77,19 +86,22 @@ static game_params *default_params(void) ret->w = 6; ret->diff = DIFF_NORMAL; + ret->multiplication_only = FALSE; return ret; } const static struct game_params keen_presets[] = { - { 4, DIFF_EASY }, - { 5, DIFF_EASY }, - { 6, DIFF_EASY }, - { 6, DIFF_NORMAL }, - { 6, DIFF_HARD }, - { 6, DIFF_EXTREME }, - { 6, DIFF_UNREASONABLE }, - { 9, DIFF_NORMAL }, + { 4, DIFF_EASY, FALSE }, + { 5, DIFF_EASY, FALSE }, + { 5, DIFF_EASY, TRUE }, + { 6, DIFF_EASY, FALSE }, + { 6, DIFF_NORMAL, FALSE }, + { 6, DIFF_NORMAL, TRUE }, + { 6, DIFF_HARD, FALSE }, + { 6, DIFF_EXTREME, FALSE }, + { 6, DIFF_UNREASONABLE, FALSE }, + { 9, DIFF_NORMAL, FALSE }, }; static int game_fetch_preset(int i, char **name, game_params **params) @@ -103,7 +115,8 @@ static int game_fetch_preset(int i, char **name, game_params **params) ret = snew(game_params); *ret = keen_presets[i]; /* structure copy */ - sprintf(buf, "%dx%d %s", ret->w, ret->w, keen_diffnames[ret->diff]); + sprintf(buf, "%dx%d %s%s", ret->w, ret->w, keen_diffnames[ret->diff], + ret->multiplication_only ? ", multiplication only" : ""); *name = dupstr(buf); *params = ret; @@ -115,7 +128,7 @@ static void free_params(game_params *params) sfree(params); } -static game_params *dup_params(game_params *params) +static game_params *dup_params(const game_params *params) { game_params *ret = snew(game_params); *ret = *params; /* structure copy */ @@ -141,25 +154,31 @@ static void decode_params(game_params *params, char const *string) p++; } } + + if (*p == 'm') { + p++; + params->multiplication_only = TRUE; + } } -static char *encode_params(game_params *params, int full) +static char *encode_params(const game_params *params, int full) { char ret[80]; sprintf(ret, "%d", params->w); if (full) - sprintf(ret + strlen(ret), "d%c", keen_diffchars[params->diff]); + sprintf(ret + strlen(ret), "d%c%s", keen_diffchars[params->diff], + params->multiplication_only ? "m" : ""); return dupstr(ret); } -static config_item *game_configure(game_params *params) +static config_item *game_configure(const game_params *params) { config_item *ret; char buf[80]; - ret = snewn(3, config_item); + ret = snewn(4, config_item); ret[0].name = "Grid size"; ret[0].type = C_STRING; @@ -172,25 +191,31 @@ static config_item *game_configure(game_params *params) ret[1].sval = DIFFCONFIG; ret[1].ival = params->diff; - ret[2].name = NULL; - ret[2].type = C_END; + ret[2].name = "Multiplication only"; + ret[2].type = C_BOOLEAN; ret[2].sval = NULL; - ret[2].ival = 0; + ret[2].ival = params->multiplication_only; + + ret[3].name = NULL; + ret[3].type = C_END; + ret[3].sval = NULL; + ret[3].ival = 0; return ret; } -static game_params *custom_params(config_item *cfg) +static game_params *custom_params(const config_item *cfg) { game_params *ret = snew(game_params); ret->w = atoi(cfg[0].sval); ret->diff = cfg[1].ival; + ret->multiplication_only = cfg[2].ival; return ret; } -static char *validate_params(game_params *params, int full) +static char *validate_params(const game_params *params, int full) { if (params->w < 3 || params->w > 9) return "Grid size must be between 3 and 9"; @@ -226,6 +251,36 @@ static void solver_clue_candidate(struct solver_ctx *ctx, int diff, int box) * digit constraints in that box. We expect to find the digits * of the candidate layout in ctx->dscratch, and we update * ctx->iscratch as appropriate. + * + * The contents of ctx->iscratch are completely different + * depending on whether diff == DIFF_HARD or not. This function + * uses iscratch completely differently between the two cases, and + * the code in solver_common() which consumes the result must + * likewise have an if statement with completely different + * branches for the two cases. + * + * In DIFF_EASY and DIFF_NORMAL modes, the valid entries in + * ctx->iscratch are 0,...,n-1, and each of those entries + * ctx->iscratch[i] gives a bitmap of the possible digits in the + * ith square of the clue box currently under consideration. So + * each entry of iscratch starts off as an empty bitmap, and we + * set bits in it as possible layouts for the clue box are + * considered (and the difference between DIFF_EASY and + * DIFF_NORMAL is just that in DIFF_EASY mode we deliberately set + * more bits than absolutely necessary, hence restricting our own + * knowledge). + * + * But in DIFF_HARD mode, the valid entries are 0,...,2*w-1 (at + * least outside *this* function - inside this function, we also + * use 2*w,...,4*w-1 as scratch space in the loop below); the + * first w of those give the possible digits in the intersection + * of the current clue box with each column of the puzzle, and the + * next w do the same for each row. In this mode, each iscratch + * entry starts off as a _full_ bitmap, and in this function we + * _clear_ bits for digits that are absent from a given row or + * column in each candidate layout, so that the only bits which + * remain set are those for digits which have to appear in a given + * row/column no matter how the clue box is laid out. */ if (diff == DIFF_EASY) { unsigned mask = 0; @@ -284,8 +339,14 @@ static int solver_common(struct latin_solver *solver, void *vctx, int diff) long value = ctx->clues[box] & ~CMASK; long op = ctx->clues[box] & CMASK; + /* + * Initialise ctx->iscratch for this clue box. At different + * difficulty levels we must initialise a different amount of + * it to different things; see the comments in + * solver_clue_candidate explaining what each version does. + */ if (diff == DIFF_HARD) { - for (i = 0; i < n; i++) + for (i = 0; i < 2*w; i++) ctx->iscratch[i] = (1 << (w+1)) - (1 << 1); } else { for (i = 0; i < n; i++) @@ -399,6 +460,13 @@ static int solver_common(struct latin_solver *solver, void *vctx, int diff) break; } + /* + * Do deductions based on the information we've now + * accumulated in ctx->iscratch. See the comments above in + * solver_clue_candidate explaining what data is left in here, + * and how it differs between DIFF_HARD and lower difficulty + * levels (hence the big if statement here). + */ if (diff < DIFF_HARD) { #ifdef STANDALONE_SOLVER char prefix[256]; @@ -732,7 +800,7 @@ static char *parse_block_structure(const char **p, int w, int *dsf) return NULL; } -static char *new_game_desc(game_params *params, random_state *rs, +static char *new_game_desc(const game_params *params, random_state *rs, char **aux, int interactive) { int w = params->w, a = w*w; @@ -847,26 +915,34 @@ done x = i % w; y = i / w; - if (x > 0 && + if (x > 0 && dsf_size(dsf, i-1) < MAXBLK && (best == -1 || revorder[i-1] < revorder[best])) best = i-1; - if (x+1 < w && + if (x+1 < w && dsf_size(dsf, i+1) < MAXBLK && (best == -1 || revorder[i+1] < revorder[best])) best = i+1; - if (y > 0 && + if (y > 0 && dsf_size(dsf, i-w) < MAXBLK && (best == -1 || revorder[i-w] < revorder[best])) best = i-w; - if (y+1 < w && + if (y+1 < w && dsf_size(dsf, i+w) < MAXBLK && (best == -1 || revorder[i+w] < revorder[best])) best = i+w; if (best >= 0) { - singletons[i] = FALSE; + singletons[i] = singletons[best] = FALSE; dsf_merge(dsf, i, best); } } } + /* Quit and start again if we have any singletons left over + * which we weren't able to do anything at all with. */ + for (i = 0; i < a; i++) + if (singletons[i]) + break; + if (i < a) + continue; + /* * Decide what would be acceptable clues for each block. * @@ -887,18 +963,18 @@ done * suitable for what. */ #define F_ADD 0x01 -#define F_ADD_BAD 0x02 -#define F_SUB 0x04 -#define F_SUB_BAD 0x08 -#define F_MUL 0x10 -#define F_MUL_BAD 0x20 -#define F_DIV 0x40 -#define F_DIV_BAD 0x80 +#define F_SUB 0x02 +#define F_MUL 0x04 +#define F_DIV 0x08 +#define BAD_SHIFT 4 + for (i = 0; i < a; i++) { singletons[i] = 0; j = dsf_canonify(dsf, i); k = dsf_size(dsf, j); - if (j == i && k > 2) { + if (params->multiplication_only) + singletons[j] = F_MUL; + else if (j == i && k > 2) { singletons[j] |= F_ADD | F_MUL; } else if (j != i && k == 2) { /* Fetch the two numbers and sort them into order. */ @@ -916,25 +992,23 @@ done v = p + q; if (v > 4 && v < 2*w-2) singletons[j] |= F_ADD; - else - singletons[j] |= F_ADD_BAD; + else + singletons[j] |= F_ADD << BAD_SHIFT; /* - * Multiplication clues: similarly, we prefer clues - * of this type which leave multiple options open. - * We can't rule out all the others, though, because - * there are very very few 2-square multiplication - * clues that _don't_ leave only one option. + * Multiplication clues: above Normal difficulty, we + * prefer (but don't absolutely insist on) clues of + * this type which leave multiple options open. */ v = p * q; n = 0; for (k = 1; k <= w; k++) if (v % k == 0 && v / k <= w && v / k != k) n++; - if (n > 1) + if (n <= 2 && diff > DIFF_NORMAL) + singletons[j] |= F_MUL << BAD_SHIFT; + else singletons[j] |= F_MUL; - else - singletons[j] |= F_MUL_BAD; /* * Subtraction: we completely avoid a difference of @@ -976,11 +1050,10 @@ done long clue; int good, bad; switch (k) { - case 0: clue = C_DIV; good = F_DIV; bad = F_DIV_BAD; break; - case 1: clue = C_SUB; good = F_SUB; bad = F_SUB_BAD; break; - case 2: clue = C_MUL; good = F_MUL; bad = F_MUL_BAD; break; - default /* case 3 */ : - clue = C_ADD; good = F_ADD; bad = F_ADD_BAD; break; + case 0: clue = C_DIV; good = F_DIV; break; + case 1: clue = C_SUB; good = F_SUB; break; + case 2: clue = C_MUL; good = F_MUL; break; + default /* case 3 */ : clue = C_ADD; good = F_ADD; break; } for (i = 0; i < a; i++) { @@ -993,9 +1066,10 @@ done } if (i == a) { /* didn't find a nice one, use a nasty one */ + bad = good << BAD_SHIFT; for (i = 0; i < a; i++) { j = order[i]; - if (singletons[j] & good) { + if (singletons[j] & bad) { clues[j] = clue; singletons[j] = 0; break; @@ -1010,13 +1084,10 @@ done break; } #undef F_ADD -#undef F_ADD_BAD #undef F_SUB -#undef F_SUB_BAD #undef F_MUL -#undef F_MUL_BAD #undef F_DIV -#undef F_DIV_BAD +#undef BAD_SHIFT /* * Having chosen the clue types, calculate the clue values. @@ -1136,7 +1207,7 @@ done * Gameplay. */ -static char *validate_desc(game_params *params, char *desc) +static char *validate_desc(const game_params *params, const char *desc) { int w = params->w, a = w*w; int *dsf; @@ -1184,11 +1255,11 @@ static char *validate_desc(game_params *params, char *desc) return NULL; } -static game_state *new_game(midend *me, game_params *params, char *desc) +static game_state *new_game(midend *me, const game_params *params, + const char *desc) { int w = params->w, a = w*w; game_state *state = snew(game_state); - char *err; const char *p = desc; int i; @@ -1197,7 +1268,7 @@ static game_state *new_game(midend *me, game_params *params, char *desc) state->clues->refcount = 1; state->clues->w = w; state->clues->dsf = snew_dsf(a); - err = parse_block_structure(&p, w, state->clues->dsf); + parse_block_structure(&p, w, state->clues->dsf); assert(*p == ','); p++; @@ -1244,7 +1315,7 @@ static game_state *new_game(midend *me, game_params *params, char *desc) return state; } -static game_state *dup_game(game_state *state) +static game_state *dup_game(const game_state *state) { int w = state->par.w, a = w*w; game_state *ret = snew(game_state); @@ -1277,8 +1348,8 @@ static void free_game(game_state *state) sfree(state); } -static char *solve_game(game_state *state, game_state *currstate, - char *aux, char **error) +static char *solve_game(const game_state *state, const game_state *currstate, + const char *aux, char **error) { int w = state->par.w, a = w*w; int i, ret; @@ -1312,12 +1383,12 @@ static char *solve_game(game_state *state, game_state *currstate, return out; } -static int game_can_format_as_text_now(game_params *params) +static int game_can_format_as_text_now(const game_params *params) { return TRUE; } -static char *game_text_format(game_state *state) +static char *game_text_format(const game_state *state) { return NULL; } @@ -1349,7 +1420,7 @@ struct game_ui { int hcursor; }; -static game_ui *new_ui(game_state *state) +static game_ui *new_ui(const game_state *state) { game_ui *ui = snew(game_ui); @@ -1364,17 +1435,17 @@ static void free_ui(game_ui *ui) sfree(ui); } -static char *encode_ui(game_ui *ui) +static char *encode_ui(const game_ui *ui) { return NULL; } -static void decode_ui(game_ui *ui, char *encoding) +static void decode_ui(game_ui *ui, const char *encoding) { } -static void game_changed_state(game_ui *ui, game_state *oldstate, - game_state *newstate) +static void game_changed_state(game_ui *ui, const game_state *oldstate, + const game_state *newstate) { int w = newstate->par.w; /* @@ -1413,7 +1484,7 @@ struct game_drawstate { char *minus_sign, *times_sign, *divide_sign; }; -static int check_errors(game_state *state, long *errors) +static int check_errors(const game_state *state, long *errors) { int w = state->par.w, a = w*w; int i, j, x, y, errs = FALSE; @@ -1520,8 +1591,9 @@ static int check_errors(game_state *state, long *errors) return errs; } -static char *interpret_move(game_state *state, game_ui *ui, game_drawstate *ds, - int x, int y, int button) +static char *interpret_move(const game_state *state, game_ui *ui, + const game_drawstate *ds, + int x, int y, int button) { int w = state->par.w; int tx, ty; @@ -1607,7 +1679,7 @@ static char *interpret_move(game_state *state, game_ui *ui, game_drawstate *ds, return NULL; } -static game_state *execute_move(game_state *from, char *move) +static game_state *execute_move(const game_state *from, const char *move) { int w = from->par.w, a = w*w; game_state *ret; @@ -1670,8 +1742,8 @@ static game_state *execute_move(game_state *from, char *move) #define SIZE(w) ((w) * TILESIZE + 2*BORDER) -static void game_compute_size(game_params *params, int tilesize, - int *x, int *y) +static void game_compute_size(const game_params *params, int tilesize, + int *x, int *y) { /* Ick: fake up `ds->tilesize' for macro expansion purposes */ struct { int tilesize; } ads, *ds = &ads; @@ -1681,7 +1753,7 @@ static void game_compute_size(game_params *params, int tilesize, } static void game_set_size(drawing *dr, game_drawstate *ds, - game_params *params, int tilesize) + const game_params *params, int tilesize) { ds->tilesize = tilesize; } @@ -1720,7 +1792,7 @@ static const char *const minus_signs[] = { "\xE2\x88\x92", "-" }; static const char *const times_signs[] = { "\xC3\x97", "*" }; static const char *const divide_signs[] = { "\xC3\xB7", "/" }; -static game_drawstate *game_new_drawstate(drawing *dr, game_state *state) +static game_drawstate *game_new_drawstate(drawing *dr, const game_state *state) { int w = state->par.w, a = w*w; struct game_drawstate *ds = snew(struct game_drawstate); @@ -1750,7 +1822,7 @@ static void game_free_drawstate(drawing *dr, game_drawstate *ds) } static void draw_tile(drawing *dr, game_drawstate *ds, struct clues *clues, - int x, int y, long tile) + int x, int y, long tile, int only_one_op) { int w = clues->w /* , a = w*w */; int tx, ty, tw, th; @@ -1780,6 +1852,18 @@ static void draw_tile(drawing *dr, game_drawstate *ds, struct clues *clues, draw_rect(dr, cx, cy, cw, ch, (tile & DF_HIGHLIGHT) ? COL_HIGHLIGHT : COL_BACKGROUND); + /* pencil-mode highlight */ + if (tile & DF_HIGHLIGHT_PENCIL) { + int coords[6]; + coords[0] = cx; + coords[1] = cy; + coords[2] = cx+cw/2; + coords[3] = cy; + coords[4] = cx; + coords[5] = cy+ch/2; + draw_polygon(dr, coords, 3, COL_HIGHLIGHT, COL_HIGHLIGHT); + } + /* * Draw the corners of thick lines in corner-adjacent squares, * which jut into this square by one pixel. @@ -1793,18 +1877,6 @@ static void draw_tile(drawing *dr, game_drawstate *ds, struct clues *clues, if (x+1 < w && y+1 < w && dsf_canonify(clues->dsf, y*w+x) != dsf_canonify(clues->dsf, (y+1)*w+x+1)) draw_rect(dr, tx+TILESIZE-1-2*GRIDEXTRA, ty+TILESIZE-1-2*GRIDEXTRA, GRIDEXTRA, GRIDEXTRA, COL_GRID); - /* pencil-mode highlight */ - if (tile & DF_HIGHLIGHT_PENCIL) { - int coords[6]; - coords[0] = cx; - coords[1] = cy; - coords[2] = cx+cw/2; - coords[3] = cy; - coords[4] = cx; - coords[5] = cy+ch/2; - draw_polygon(dr, coords, 3, COL_HIGHLIGHT, COL_HIGHLIGHT); - } - /* Draw the box clue. */ if (dsf_canonify(clues->dsf, y*w+x) == y*w+x) { long clue = clues->clues[y*w+x]; @@ -1820,7 +1892,7 @@ static void draw_tile(drawing *dr, game_drawstate *ds, struct clues *clues, * want to display them right if so. */ sprintf (str, "%ld%s", clueval, - (size == 1 ? "" : + (size == 1 || only_one_op ? "" : cluetype == C_ADD ? "+" : cluetype == C_SUB ? ds->minus_sign : cluetype == C_MUL ? ds->times_sign : @@ -1941,9 +2013,10 @@ static void draw_tile(drawing *dr, game_drawstate *ds, struct clues *clues, draw_update(dr, cx, cy, cw, ch); } -static void game_redraw(drawing *dr, game_drawstate *ds, game_state *oldstate, - game_state *state, int dir, game_ui *ui, - float animtime, float flashtime) +static void game_redraw(drawing *dr, game_drawstate *ds, + const game_state *oldstate, const game_state *state, + int dir, const game_ui *ui, + float animtime, float flashtime) { int w = state->par.w /*, a = w*w */; int x, y; @@ -1992,20 +2065,21 @@ static void game_redraw(drawing *dr, game_drawstate *ds, game_state *oldstate, if (ds->tiles[y*w+x] != tile) { ds->tiles[y*w+x] = tile; - draw_tile(dr, ds, state->clues, x, y, tile); + draw_tile(dr, ds, state->clues, x, y, tile, + state->par.multiplication_only); } } } } -static float game_anim_length(game_state *oldstate, game_state *newstate, - int dir, game_ui *ui) +static float game_anim_length(const game_state *oldstate, + const game_state *newstate, int dir, game_ui *ui) { return 0.0F; } -static float game_flash_length(game_state *oldstate, game_state *newstate, - int dir, game_ui *ui) +static float game_flash_length(const game_state *oldstate, + const game_state *newstate, int dir, game_ui *ui) { if (!oldstate->completed && newstate->completed && !oldstate->cheated && !newstate->cheated) @@ -2013,19 +2087,19 @@ static float game_flash_length(game_state *oldstate, game_state *newstate, return 0.0F; } -static int game_is_solved(game_state *state) +static int game_status(const game_state *state) { - return state->completed; + return state->completed ? +1 : 0; } -static int game_timing_state(game_state *state, game_ui *ui) +static int game_timing_state(const game_state *state, game_ui *ui) { if (state->completed) return FALSE; return TRUE; } -static void game_print_size(game_params *params, float *x, float *y) +static void game_print_size(const game_params *params, float *x, float *y) { int pw, ph; @@ -2168,7 +2242,7 @@ static void outline_block_structure(drawing *dr, game_drawstate *ds, sfree(coords); } -static void game_print(drawing *dr, game_state *state, int tilesize) +static void game_print(drawing *dr, const game_state *state, int tilesize) { int w = state->par.w; int ink = print_mono_colour(dr, 0); @@ -2294,7 +2368,7 @@ const struct game thegame = { game_redraw, game_anim_length, game_flash_length, - game_is_solved, + game_status, TRUE, FALSE, game_print_size, game_print, FALSE, /* wants_statusbar */ FALSE, game_timing_state,