/*
* 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(("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(game_params *params)
+static int game_can_format_as_text_now(const game_params *params)
{
return TRUE;
}
* 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;
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;
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_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_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)
{
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;
*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);
const struct game thegame = {
"Light Up", "games.lightup", "lightup",
default_params,
- game_fetch_preset,
+ game_fetch_preset, NULL,
decode_params,
encode_params,
free_params,
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