/*
* lightup.c: Implementation of the Nikoli game 'Light Up'.
+ *
+ * Possible future solver enhancements:
+ *
+ * - In a situation where two clues are diagonally adjacent, you can
+ * deduce bounds on the number of lights shared between them. For
+ * instance, suppose a 3 clue is diagonally adjacent to a 1 clue:
+ * of the two squares adjacent to both clues, at least one must be
+ * a light (or the 3 would be unsatisfiable) and yet at most one
+ * must be a light (or the 1 would be overcommitted), so in fact
+ * _exactly_ one must be a light, and hence the other two squares
+ * adjacent to the 3 must also be lights and the other two adjacent
+ * to the 1 must not. Likewise if the 3 is replaced with a 2 but
+ * one of its other two squares is known not to be a light, and so
+ * on.
+ *
+ * - In a situation where two clues are orthogonally separated (not
+ * necessarily directly adjacent), you may be able to deduce
+ * something about the squares that align with each other. For
+ * instance, suppose two clues are vertically adjacent. Consider
+ * the pair of squares A,B horizontally adjacent to the top clue,
+ * and the pair C,D horizontally adjacent to the bottom clue.
+ * Assuming no intervening obstacles, A and C align with each other
+ * and hence at most one of them can be a light, and B and D
+ * likewise, so we must have at most two lights between the four
+ * squares. So if the clues indicate that there are at _least_ two
+ * lights in those four squares because the top clue requires at
+ * least one of AB to be a light and the bottom one requires at
+ * least one of CD, then we can in fact deduce that there are
+ * _exactly_ two lights between the four squares, and fill in the
+ * other squares adjacent to each clue accordingly. For instance,
+ * if both clues are 3s, then we instantly deduce that all four of
+ * the squares _vertically_ adjacent to the two clues must be
+ * lights. (For that to happen, of course, there'd also have to be
+ * a black square in between the clues, so the two inner lights
+ * don't light each other.)
+ *
+ * - I haven't thought it through carefully, but there's always the
+ * possibility that both of the above deductions are special cases
+ * of some more general pattern which can be made computationally
+ * feasible...
*/
#include <stdio.h>
/* Fills in (doesn't allocate) a surrounds structure with the grid locations
* around a given square, taking account of the edges. */
-static void get_surrounds(game_state *state, int ox, int oy, surrounds *s)
+static void get_surrounds(const game_state *state, int ox, int oy,
+ surrounds *s)
{
assert(ox >= 0 && ox < state->w && oy >= 0 && oy < state->h);
s->npoints = 0;
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 */
if (*string == 's') {
string++;
EATNUM(params->symm);
+ } else {
+ /* cope with user input such as '18x10' by ensuring symmetry
+ * is not selected by default to be incompatible with dimensions */
+ if (params->symm == SYMM_ROT4 && params->w != params->h)
+ params->symm = SYMM_ROT2;
}
params->difficulty = 0;
/* cope with old params */
}
}
-static char *encode_params(game_params *params, int full)
+static char *encode_params(const game_params *params, int full)
{
char buf[80];
return dupstr(buf);
}
-static config_item *game_configure(game_params *params)
+static config_item *game_configure(const game_params *params)
{
config_item *ret;
char buf[80];
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);
return ret;
}
-static char *validate_params(game_params *params, int full)
+static char *validate_params(const game_params *params, int full)
{
if (params->w < 2 || params->h < 2)
return "Width and height must be at least 2";
/* --- Game state construction/freeing helper functions --- */
-static game_state *new_state(game_params *params)
+static game_state *new_state(const game_params *params)
{
game_state *ret = snew(game_state);
return ret;
}
-static game_state *dup_game(game_state *state)
+static game_state *dup_game(const game_state *state)
{
game_state *ret = snew(game_state);
return 0;
}
-static int number_wrong(game_state *state, int x, int y)
+static int number_wrong(const game_state *state, int x, int y)
{
surrounds s;
int i, n, empty, lights = GRID(state, lights, x, y);
state->nlights = 0;
}
-static void set_blacks(game_state *state, game_params *params, random_state *rs)
+static void set_blacks(game_state *state, const game_params *params,
+ random_state *rs)
{
int x, y, degree = 0, rotate = 0, nblack;
int rh, rw, i;
{
int x,y;
- memset(lld, 0, sizeof(lld));
lld->ox = lld->minx = lld->maxx = ox;
lld->oy = lld->miny = lld->maxy = oy;
lld->include_origin = origin;
debug_state(state);
assert(!"place_lights failed to resolve overlapping lights!");
}
+ sfree(numindices);
}
/* Fills in all black squares with numbers of adjacent lights. */
unsigned int flags, int lights)
{
ll_data lld;
- int sx,sy,n = 0;
+ int sx = 0, sy = 0, n = 0;
if (lights > 0) return 0;
if (flags & F_BLACK) return 0;
get_surrounds(state, x, y, &s);
for (i = 0; i < s.npoints; i++) {
- if (!GRID(state,flags,s.points[i].x,s.points[i].y) & F_NUMBERED)
+ if (!(GRID(state,flags,s.points[i].x,s.points[i].y) & F_NUMBERED))
continue;
- /* we have an adjacent clue square; find /it's/ surrounds
+ /* we have an adjacent clue square; find /its/ surrounds
* and count the remaining lights it needs. */
get_surrounds(state,s.points[i].x,s.points[i].y,&ss);
curr_lights = 0;
}
}
}
+ debug(("Stripped %d unused numbers.\n", n));
return n;
}
#define MAX_GRIDGEN_TRIES 20
-static char *new_game_desc(game_params *params, random_state *rs,
+static char *new_game_desc(const game_params *params_in, random_state *rs,
char **aux, int interactive)
{
+ game_params params_copy = *params_in; /* structure copy */
+ game_params *params = ¶ms_copy;
game_state *news = new_state(params), *copys;
- int nsol, i, j, run, x, y, wh = params->w*params->h, num;
+ int i, j, run, x, y, wh = params->w*params->h, num;
char *ret, *p;
int *numindices;
/* Take a copy, remove numbers we didn't use and check there's
* still a unique solution; if so, use the copy subsequently. */
copys = dup_game(news);
- nsol = strip_unused_nums(copys);
- debug(("Stripped %d unused numbers.\n", nsol));
+ strip_unused_nums(copys);
if (!puzzle_is_good(copys, params->difficulty)) {
debug(("Stripped grid is not good, reverting.\n"));
free_game(copys);
return ret;
}
-static char *validate_desc(game_params *params, char *desc)
+static char *validate_desc(const game_params *params, const char *desc)
{
int i;
for (i = 0; i < params->w*params->h; i++) {
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)
{
game_state *ret = new_state(params);
int x,y;
return ret;
}
-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)
{
game_state *solved;
char *move = NULL, buf[80];
/* That didn't work; try solving from the clean puzzle. */
solved = dup_game(state);
if (dosolve(solved, sflags, NULL) > 0) goto solved;
- *error = "Puzzle is not self-consistent.";
+ *error = "Unable to find a solution to this puzzle.";
goto done;
solved:
return move;
}
+static int game_can_format_as_text_now(const game_params *params)
+{
+ return TRUE;
+}
+
/* 'borrowed' from slant.c, mainly. I could have printed it one
* character per cell (like debug_state) but that comes out tiny.
* 'L' is used for 'light here' because 'O' looks too much like '0'
* (black square with no surrounding lights). */
-static char *game_text_format(game_state *state)
+static char *game_text_format(const game_state *state)
{
int w = state->w, h = state->h, W = w+1, H = h+1;
int x, y, len, lights;
int cur_x, cur_y, cur_visible;
};
-static game_ui *new_ui(game_state *state)
+static game_ui *new_ui(const game_state *state)
{
game_ui *ui = snew(game_ui);
ui->cur_x = ui->cur_y = ui->cur_visible = 0;
sfree(ui);
}
-static char *encode_ui(game_ui *ui)
+static char *encode_ui(const game_ui *ui)
{
/* nothing to encode. */
return NULL;
}
-static void decode_ui(game_ui *ui, char *encoding)
+static void decode_ui(game_ui *ui, const char *encoding)
{
/* nothing to decode. */
}
-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)
{
if (newstate->completed)
ui->cur_visible = 0;
(pc)) -1 (nil)
(nil))
*/
-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)
{
enum { NONE, FLIP_LIGHT, FLIP_IMPOSSIBLE } action = NONE;
int cx = -1, cy = -1;
cx = FROMCOORD(x);
cy = FROMCOORD(y);
action = (button == LEFT_BUTTON) ? FLIP_LIGHT : FLIP_IMPOSSIBLE;
- } else if (button == CURSOR_SELECT ||
+ } else if (IS_CURSOR_SELECT(button) ||
button == 'i' || button == 'I' ||
button == ' ' || button == '\r' || button == '\n') {
- ui->cur_visible = 1;
- cx = ui->cur_x;
- cy = ui->cur_y;
- action = (button == 'i' || button == 'I') ?
- FLIP_IMPOSSIBLE : FLIP_LIGHT;
- } else if (button == CURSOR_UP || button == CURSOR_DOWN ||
- button == CURSOR_RIGHT || button == CURSOR_LEFT) {
- int dx = 0, dy = 0;
- switch (button) {
- case CURSOR_UP: dy = -1; break;
- case CURSOR_DOWN: dy = 1; break;
- case CURSOR_RIGHT: dx = 1; break;
- case CURSOR_LEFT: dx = -1; break;
- default: assert(!"shouldn't get here");
+ if (ui->cur_visible) {
+ /* Only allow cursor-effect operations if the cursor is visible
+ * (otherwise you have no idea which square it might be affecting) */
+ cx = ui->cur_x;
+ cy = ui->cur_y;
+ action = (button == 'i' || button == 'I' || button == CURSOR_SELECT2) ?
+ FLIP_IMPOSSIBLE : FLIP_LIGHT;
}
- ui->cur_x += dx; ui->cur_y += dy;
- ui->cur_x = min(max(ui->cur_x, 0), state->w - 1);
- ui->cur_y = min(max(ui->cur_y, 0), state->h - 1);
+ ui->cur_visible = 1;
+ } else if (IS_CURSOR_MOVE(button)) {
+ move_cursor(button, &ui->cur_x, &ui->cur_y, state->w, state->h, 0);
ui->cur_visible = 1;
nullret = empty;
} else
if (flags & F_BLACK)
return nullret;
if (action == FLIP_LIGHT) {
+#ifdef STYLUS_BASED
+ if (flags & F_IMPOSSIBLE || flags & F_LIGHT) c = 'I'; else c = 'L';
+#else
if (flags & F_IMPOSSIBLE) return nullret;
c = 'L';
+#endif
} else {
+#ifdef STYLUS_BASED
+ if (flags & F_IMPOSSIBLE || flags & F_LIGHT) c = 'L'; else c = 'I';
+#else
if (flags & F_LIGHT) return nullret;
c = 'I';
+#endif
}
sprintf(buf, "%c%d,%d", (int)c, cx, cy);
break;
return dupstr(buf);
}
-static game_state *execute_move(game_state *state, char *move)
+static game_state *execute_move(const game_state *state, const char *move)
{
game_state *ret = dup_game(state);
int x, y, n, flags;
*/
/* XXX entirely cloned from fifteen.c; separate out? */
-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;
ds->crad = 3*(tilesize-1)/8;
}
-static float *game_colours(frontend *fe, game_state *state, int *ncolours)
+static float *game_colours(frontend *fe, int *ncolours)
{
float *ret = snewn(3 * NCOLOURS, float);
int i;
return ret;
}
-static game_drawstate *game_new_drawstate(drawing *dr, game_state *state)
+static game_drawstate *game_new_drawstate(drawing *dr, const game_state *state)
{
struct game_drawstate *ds = snew(struct game_drawstate);
int i;
#define HINT_OVERLAPS
#define HINT_NUMBERS
-static unsigned int tile_flags(game_drawstate *ds, game_state *state, game_ui *ui,
- int x, int y, int flashing)
+static unsigned int tile_flags(game_drawstate *ds, const game_state *state,
+ const game_ui *ui, int x, int y, int flashing)
{
unsigned int flags = GRID(state, flags, x, y);
int lights = GRID(state, lights, x, y);
return ret;
}
-static void tile_redraw(drawing *dr, game_drawstate *ds, game_state *state,
- int x, int y)
+static void tile_redraw(drawing *dr, game_drawstate *ds,
+ const game_state *state, int x, int y)
{
unsigned int ds_flags = GRID(ds, flags, x, y);
int dx = COORD(x), dy = COORD(y);
draw_rect(dr, dx, dy, TILE_SIZE, TILE_SIZE, COL_BLACK);
if (ds_flags & DF_NUMBERED) {
int ccol = (ds_flags & DF_NUMBERWRONG) ? COL_ERROR : COL_LIGHT;
- char str[10];
+ char str[32];
/* We know that this won't change over the course of the game
* so it's OK to ignore this when calculating whether or not
int lcol = (ds_flags & DF_OVERLAP) ? COL_ERROR : COL_LIGHT;
draw_circle(dr, dx + TILE_SIZE/2, dy + TILE_SIZE/2, TILE_RADIUS,
lcol, COL_BLACK);
- } else if (ds_flags & DF_IMPOSSIBLE) {
- int rlen = TILE_SIZE / 4;
- draw_rect(dr, dx + TILE_SIZE/2 - rlen/2, dy + TILE_SIZE/2 - rlen/2,
- rlen, rlen, COL_BLACK);
+ } else if ((ds_flags & DF_IMPOSSIBLE)) {
+ static int draw_blobs_when_lit = -1;
+ if (draw_blobs_when_lit < 0) {
+ char *env = getenv("LIGHTUP_LIT_BLOBS");
+ draw_blobs_when_lit = (!env || (env[0] == 'y' ||
+ env[0] == 'Y'));
+ }
+ if (!(ds_flags & DF_LIT) || draw_blobs_when_lit) {
+ int rlen = TILE_SIZE / 4;
+ draw_rect(dr, dx + TILE_SIZE/2 - rlen/2,
+ dy + TILE_SIZE/2 - rlen/2,
+ rlen, rlen, COL_BLACK);
+ }
}
}
draw_update(dr, dx, dy, TILE_SIZE, TILE_SIZE);
}
-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 flashing = FALSE;
int x,y;
}
}
-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->used_solve && !newstate->used_solve)
return 0.0F;
}
-static int game_wants_statusbar(void)
+static int game_status(const game_state *state)
{
- return FALSE;
+ 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)
{
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;
* I'll use 6mm squares by default.
*/
game_compute_size(params, 600, &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)
+static void game_print(drawing *dr, const game_state *state, int tilesize)
{
int w = state->w, h = state->h;
int ink = print_mono_colour(dr, 0);
/* Ick: fake up `ds->tilesize' for macro expansion purposes */
game_drawstate ads, *ds = &ads;
- ads.tilesize = tilesize;
- ds->crad = 3*(tilesize-1)/8;
+ game_set_size(dr, ds, NULL, tilesize);
/*
* Border.
if (ds_flags & DF_BLACK) {
draw_rect(dr, dx, dy, TILE_SIZE, TILE_SIZE, ink);
if (ds_flags & DF_NUMBERED) {
- char str[10];
+ char str[32];
sprintf(str, "%d", GRID(state, lights, x, y));
draw_text(dr, dx + TILE_SIZE/2, dy + TILE_SIZE/2,
FONT_VARIABLE, TILE_SIZE*3/5,
#endif
const struct game thegame = {
- "Light Up", "games.lightup",
+ "Light Up", "games.lightup", "lightup",
default_params,
game_fetch_preset,
decode_params,
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,
game_redraw,
game_anim_length,
game_flash_length,
+ game_status,
TRUE, FALSE, game_print_size, game_print,
- game_wants_statusbar,
+ FALSE, /* wants_statusbar */
FALSE, game_timing_state,
- 0, /* mouse_priorities */
+ 0, /* flags */
};
#ifdef STANDALONE_SOLVER