X-Git-Url: http://www.chiark.greenend.org.uk/ucgi/~ian/git?a=blobdiff_plain;f=lightup.c;h=bfc6980600c5bb6ad189cbfa3aed0ef4ddcda329;hb=3ce69e84cad15844282d691fa03e711c5353c05e;hp=d9fa07964ed556ff9806c63c42d1d1d6b99175c7;hpb=466aa6e532f6956e8398d21ed7b5f6a4b22fcac4;p=sgt-puzzles.git diff --git a/lightup.c b/lightup.c index d9fa079..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; @@ -727,6 +773,7 @@ static void place_lights(game_state *state, random_state *rs) debug_state(state); assert(!"place_lights failed to resolve overlapping lights!"); } + sfree(numindices); } /* Fills in all black squares with numbers of adjacent lights. */ @@ -1016,9 +1063,9 @@ static void try_rule_out(game_state *state, int x, int y, 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; @@ -1401,6 +1448,7 @@ static int strip_unused_nums(game_state *state) } } } + debug(("Stripped %d unused numbers.\n", n)); return n; } @@ -1470,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; @@ -1498,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); @@ -1580,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++) { @@ -1602,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; @@ -1649,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]; @@ -1671,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: @@ -1705,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; } @@ -1714,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; @@ -1769,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; @@ -1781,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; @@ -1825,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; @@ -1840,27 +1891,20 @@ static char *interpret_move(game_state *state, game_ui *ui, game_drawstate *ds, cx = FROMCOORD(x); cy = FROMCOORD(y); action = (button == LEFT_BUTTON) ? FLIP_LIGHT : FLIP_IMPOSSIBLE; - } else if (button == CURSOR_SELECT || button == CURSOR_SELECT2 || + } 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' || button == CURSOR_SELECT2) ? - 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 @@ -1875,11 +1919,19 @@ static char *interpret_move(game_state *state, game_ui *ui, game_drawstate *ds, 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; @@ -1893,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; @@ -1943,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; @@ -1955,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; @@ -1988,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; @@ -2018,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); @@ -2053,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); @@ -2064,7 +2116,7 @@ static void tile_redraw(drawing *dr, game_drawstate *ds, game_state *state, 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 @@ -2107,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; @@ -2143,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) @@ -2158,12 +2211,17 @@ static float game_flash_length(game_state *oldstate, game_state *newstate, 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) { 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; @@ -2175,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); @@ -2212,7 +2270,7 @@ static void game_print(drawing *dr, game_state *state, int tilesize) 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, @@ -2260,6 +2318,7 @@ const struct game thegame = { game_redraw, game_anim_length, game_flash_length, + game_status, TRUE, FALSE, game_print_size, game_print, FALSE, /* wants_statusbar */ FALSE, game_timing_state,