/*
- * 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";
for (box = 0; box < ctx->nboxes; box++) {
int *sq = ctx->boxlist + ctx->boxes[box];
int n = ctx->boxes[box+1] - ctx->boxes[box];
- int value = ctx->clues[box] & ~CMASK;
- int op = ctx->clues[box] & CMASK;
+ long value = ctx->clues[box] & ~CMASK;
+ long op = ctx->clues[box] & CMASK;
if (diff == DIFF_HARD) {
for (i = 0; i < n; i++)
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 > 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
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] & good) {
+ if (singletons[j] & bad) {
clues[j] = clue;
singletons[j] = 0;
break;
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);
- char *err;
const char *p = desc;
int i;
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++;
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;
break;
case C_DIV:
{
- int d1 = cluevals[j], d2 = state->grid[i];
- if (d1 == 0 || d2 == 0)
+ int d1 = min(cluevals[j], state->grid[i]);
+ int d2 = max(cluevals[j], state->grid[i]);
+ if (d1 == 0 || d2 % d1 != 0)
cluevals[j] = 0;
else
- cluevals[j] = d2/d1 + d1/d2;/* one of them is 0 :-) */
+ cluevals[j] = d2 / d1;
}
break;
}
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 :
/* Count the pencil marks required. */
for (i = 1, npencil = 0; i <= w; i++)
- if (tile & (1 << (i + DF_PENCIL_SHIFT)))
+ if (tile & (1L << (i + DF_PENCIL_SHIFT)))
npencil++;
if (npencil) {
pr = pl + TILESIZE - GRIDEXTRA;
pt = ty + GRIDEXTRA;
pb = pt + TILESIZE - GRIDEXTRA;
+ if (dsf_canonify(clues->dsf, y*w+x) == y*w+x) {
+ /*
+ * Make space for the clue text.
+ */
+ pt += TILESIZE/4;
+ /* minph--; */
+ }
/*
* We arrange our pencil marks in a grid layout, with
* Now actually draw the pencil marks.
*/
for (i = 1, j = 0; i <= w; i++)
- if (tile & (1 << (i + DF_PENCIL_SHIFT))) {
+ if (tile & (1L << (i + DF_PENCIL_SHIFT))) {
int dx = j % pw, dy = j / pw;
str[1] = '\0';
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_timing_state(game_state *state, game_ui *ui)
+static int game_status(const game_state *state)
+{
+ return state->completed ? +1 : 0;
+}
+
+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);
FONT_VARIABLE, TILESIZE/2,
ALIGN_VCENTRE | ALIGN_HCENTRE, ink, str);
}
+
+ sfree(minus_sign);
+ sfree(times_sign);
+ sfree(divide_sign);
}
#ifdef COMBINED
game_redraw,
game_anim_length,
game_flash_length,
+ game_status,
TRUE, FALSE, game_print_size, game_print,
FALSE, /* wants_statusbar */
FALSE, game_timing_state,