X-Git-Url: http://www.chiark.greenend.org.uk/ucgi/~ian/git?a=blobdiff_plain;f=lightup.c;h=bfc6980600c5bb6ad189cbfa3aed0ef4ddcda329;hb=3234912f921916a1b8da164fd61dc75579358577;hp=5b97b2b0704d45cfada22938b9ff86c5e3f7bd96;hpb=980880be1f2801b2a69fcc67abc0f5827fd106f2;p=sgt-puzzles.git diff --git a/lightup.c b/lightup.c index 5b97b2b..bfc6980 100644 --- a/lightup.c +++ b/lightup.c @@ -1,5 +1,45 @@ /* * 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 @@ -117,7 +157,8 @@ typedef struct { /* 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; @@ -189,7 +230,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 */ @@ -215,6 +256,11 @@ static void decode_params(game_params *params, char const *string) 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 */ @@ -228,7 +274,7 @@ static void decode_params(game_params *params, char const *string) } } -static char *encode_params(game_params *params, int full) +static char *encode_params(const game_params *params, int full) { char buf[80]; @@ -243,7 +289,7 @@ static char *encode_params(game_params *params, int full) 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]; @@ -288,7 +334,7 @@ static config_item *game_configure(game_params *params) 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); @@ -301,7 +347,7 @@ static game_params *custom_params(config_item *cfg) 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"; @@ -322,7 +368,7 @@ static char *validate_params(game_params *params, int full) /* --- 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); @@ -337,7 +383,7 @@ static game_state *new_state(game_params *params) 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); @@ -434,7 +480,7 @@ static int grid_overlap(game_state *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); @@ -523,7 +569,8 @@ static void clean_board(game_state *state, int leave_blacks) 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; @@ -612,7 +659,6 @@ static void list_lights(game_state *state, int ox, int oy, int origin, { 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; @@ -1402,6 +1448,7 @@ static int strip_unused_nums(game_state *state) } } } + debug(("Stripped %d unused numbers.\n", n)); return n; } @@ -1471,11 +1518,13 @@ static int puzzle_is_good(game_state *state, int difficulty) #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; @@ -1499,8 +1548,7 @@ static char *new_game_desc(game_params *params, random_state *rs, /* 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); @@ -1581,7 +1629,7 @@ goodpuzzle: 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++) { @@ -1603,7 +1651,8 @@ 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) { game_state *ret = new_state(params); int x,y; @@ -1650,8 +1699,8 @@ static game_state *new_game(midend *me, game_params *params, char *desc) 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]; @@ -1672,7 +1721,7 @@ static char *solve_game(game_state *state, game_state *currstate, /* 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: @@ -1706,7 +1755,7 @@ done: 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; } @@ -1715,7 +1764,7 @@ static int game_can_format_as_text_now(game_params *params) * 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; @@ -1770,7 +1819,7 @@ struct game_ui { 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; @@ -1782,19 +1831,19 @@ static void free_ui(game_ui *ui) 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; @@ -1826,8 +1875,9 @@ struct game_drawstate { (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; @@ -1895,7 +1945,7 @@ static char *interpret_move(game_state *state, game_ui *ui, game_drawstate *ds, 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; @@ -1945,8 +1995,8 @@ badmove: */ /* 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; @@ -1957,7 +2007,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; ds->crad = 3*(tilesize-1)/8; @@ -1990,7 +2040,7 @@ static float *game_colours(frontend *fe, int *ncolours) 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; @@ -2020,8 +2070,8 @@ static void game_free_drawstate(drawing *dr, game_drawstate *ds) #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); @@ -2055,8 +2105,8 @@ static unsigned int tile_flags(game_drawstate *ds, game_state *state, game_ui *u 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); @@ -2109,9 +2159,10 @@ static void tile_redraw(drawing *dr, game_drawstate *ds, game_state *state, 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; @@ -2145,14 +2196,14 @@ static void game_redraw(drawing *dr, game_drawstate *ds, game_state *oldstate, } } -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) @@ -2160,17 +2211,17 @@ 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) { 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; @@ -2182,7 +2233,7 @@ static void game_print_size(game_params *params, float *x, float *y) *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); @@ -2267,7 +2318,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,