/*
- * 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 <stdio.h>
#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,
};
struct game_params {
- int w, diff;
+ int w, diff, multiplication_only;
};
struct clues {
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)
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;
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 */
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;
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";
* 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;
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++)
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];
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;
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.
*
* 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. */
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 > 2)
+ 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
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++) {
}
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] & bad) {
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.
* 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;
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);
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);
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;
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;
}
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);
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;
/*
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;
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;
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;
#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;
}
static void game_set_size(drawing *dr, game_drawstate *ds,
- game_params *params, int tilesize)
+ const game_params *params, int tilesize)
{
ds->tilesize = tilesize;
}
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);
}
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;
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.
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];
* 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 :
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;
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)
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;
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);
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,
~ian / sgt-puzzles.git / blobdiff