From 881746789a489fad85aae8317555f73dbe261556 Mon Sep 17 00:00:00 2001 From: Franklin Wei Date: Sat, 29 Apr 2017 18:21:56 -0400 Subject: puzzles: refactor and resync with upstream This brings puzzles up-to-date with upstream revision 2d333750272c3967cfd5cd3677572cddeaad5932, though certain changes made by me, including cursor-only Untangle and some compilation fixes remain. Upstream code has been moved to its separate subdirectory and future syncs can be done by simply copying over the new sources. Change-Id: Ia6506ca5f78c3627165ea6791d38db414ace0804 --- apps/plugins/puzzles/src/lightup.c | 2405 ++++++++++++++++++++++++++++++++++++ 1 file changed, 2405 insertions(+) create mode 100644 apps/plugins/puzzles/src/lightup.c (limited to 'apps/plugins/puzzles/src/lightup.c') diff --git a/apps/plugins/puzzles/src/lightup.c b/apps/plugins/puzzles/src/lightup.c new file mode 100644 index 0000000000..4dd46c8392 --- /dev/null +++ b/apps/plugins/puzzles/src/lightup.c @@ -0,0 +1,2405 @@ +/* + * 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 +#include +#include +#include +#include +#include + +#include "puzzles.h" + +/* + * In standalone solver mode, `verbose' is a variable which can be + * set by command-line option; in debugging mode it's simply always + * true. + */ +#if defined STANDALONE_SOLVER +#define SOLVER_DIAGNOSTICS +int verbose = 0; +#undef debug +#define debug(x) printf x +#elif defined SOLVER_DIAGNOSTICS +#define verbose 2 +#endif + +/* --- Constants, structure definitions, etc. --- */ + +#define PREFERRED_TILE_SIZE 32 +#define TILE_SIZE (ds->tilesize) +#define BORDER (TILE_SIZE / 2) +#define TILE_RADIUS (ds->crad) + +#define COORD(x) ( (x) * TILE_SIZE + BORDER ) +#define FROMCOORD(x) ( ((x) - BORDER + TILE_SIZE) / TILE_SIZE - 1 ) + +#define FLASH_TIME 0.30F + +enum { + COL_BACKGROUND, + COL_GRID, + COL_BLACK, /* black */ + COL_LIGHT, /* white */ + COL_LIT, /* yellow */ + COL_ERROR, /* red */ + COL_CURSOR, + NCOLOURS +}; + +enum { SYMM_NONE, SYMM_REF2, SYMM_ROT2, SYMM_REF4, SYMM_ROT4, SYMM_MAX }; + +#define DIFFCOUNT 2 + +struct game_params { + int w, h; + int blackpc; /* %age of black squares */ + int symm; + int difficulty; /* 0 to DIFFCOUNT */ +}; + +#define F_BLACK 1 + +/* flags for black squares */ +#define F_NUMBERED 2 /* it has a number attached */ +#define F_NUMBERUSED 4 /* this number was useful for solving */ + +/* flags for non-black squares */ +#define F_IMPOSSIBLE 8 /* can't put a light here */ +#define F_LIGHT 16 + +#define F_MARK 32 + +struct game_state { + int w, h, nlights; + int *lights; /* For black squares, (optionally) the number + of surrounding lights. For non-black squares, + the number of times it's lit. size h*w*/ + unsigned int *flags; /* size h*w */ + int completed, used_solve; +}; + +#define GRID(gs,grid,x,y) (gs->grid[(y)*((gs)->w) + (x)]) + +/* A ll_data holds information about which lights would be lit by + * a particular grid location's light (or conversely, which locations + * could light a specific other location). */ +/* most things should consider this struct opaque. */ +typedef struct { + int ox,oy; + int minx, maxx, miny, maxy; + int include_origin; +} ll_data; + +/* Macro that executes 'block' once per light in lld, including + * the origin if include_origin is specified. 'block' can use + * lx and ly as the coords. */ +#define FOREACHLIT(lld,block) do { \ + int lx,ly; \ + ly = (lld)->oy; \ + for (lx = (lld)->minx; lx <= (lld)->maxx; lx++) { \ + if (lx == (lld)->ox) continue; \ + block \ + } \ + lx = (lld)->ox; \ + for (ly = (lld)->miny; ly <= (lld)->maxy; ly++) { \ + if (!(lld)->include_origin && ly == (lld)->oy) continue; \ + block \ + } \ +} while(0) + + +typedef struct { + struct { int x, y; unsigned int f; } points[4]; + int npoints; +} surrounds; + +/* 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(const game_state *state, int ox, int oy, + surrounds *s) +{ + assert(ox >= 0 && ox < state->w && oy >= 0 && oy < state->h); + s->npoints = 0; +#define ADDPOINT(cond,nx,ny) do {\ + if (cond) { \ + s->points[s->npoints].x = (nx); \ + s->points[s->npoints].y = (ny); \ + s->points[s->npoints].f = 0; \ + s->npoints++; \ + } } while(0) + ADDPOINT(ox > 0, ox-1, oy); + ADDPOINT(ox < (state->w-1), ox+1, oy); + ADDPOINT(oy > 0, ox, oy-1); + ADDPOINT(oy < (state->h-1), ox, oy+1); +} + +/* --- Game parameter functions --- */ + +#define DEFAULT_PRESET 0 + +const struct game_params lightup_presets[] = { + { 7, 7, 20, SYMM_ROT4, 0 }, + { 7, 7, 20, SYMM_ROT4, 1 }, + { 7, 7, 20, SYMM_ROT4, 2 }, + { 10, 10, 20, SYMM_ROT2, 0 }, + { 10, 10, 20, SYMM_ROT2, 1 }, +#ifdef SLOW_SYSTEM + { 12, 12, 20, SYMM_ROT2, 0 }, + { 12, 12, 20, SYMM_ROT2, 1 }, +#else + { 10, 10, 20, SYMM_ROT2, 2 }, + { 14, 14, 20, SYMM_ROT2, 0 }, + { 14, 14, 20, SYMM_ROT2, 1 }, + { 14, 14, 20, SYMM_ROT2, 2 } +#endif +}; + +static game_params *default_params(void) +{ + game_params *ret = snew(game_params); + *ret = lightup_presets[DEFAULT_PRESET]; + + return ret; +} + +static int game_fetch_preset(int i, char **name, game_params **params) +{ + game_params *ret; + char buf[80]; + + if (i < 0 || i >= lenof(lightup_presets)) + return FALSE; + + ret = default_params(); + *ret = lightup_presets[i]; + *params = ret; + + sprintf(buf, "%dx%d %s", + ret->w, ret->h, + ret->difficulty == 2 ? "hard" : + ret->difficulty == 1 ? "tricky" : "easy"); + *name = dupstr(buf); + + return TRUE; +} + +static void free_params(game_params *params) +{ + sfree(params); +} + +static game_params *dup_params(const game_params *params) +{ + game_params *ret = snew(game_params); + *ret = *params; /* structure copy */ + return ret; +} + +#define EATNUM(x) do { \ + (x) = atoi(string); \ + while (*string && isdigit((unsigned char)*string)) string++; \ +} while(0) + +static void decode_params(game_params *params, char const *string) +{ + EATNUM(params->w); + if (*string == 'x') { + string++; + EATNUM(params->h); + } + if (*string == 'b') { + string++; + EATNUM(params->blackpc); + } + 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 */ + if (*string == 'r') { + params->difficulty = 2; + string++; + } + if (*string == 'd') { + string++; + EATNUM(params->difficulty); + } +} + +static char *encode_params(const game_params *params, int full) +{ + char buf[80]; + + if (full) { + sprintf(buf, "%dx%db%ds%dd%d", + params->w, params->h, params->blackpc, + params->symm, + params->difficulty); + } else { + sprintf(buf, "%dx%d", params->w, params->h); + } + return dupstr(buf); +} + +static config_item *game_configure(const game_params *params) +{ + config_item *ret; + char buf[80]; + + ret = snewn(6, config_item); + + ret[0].name = "Width"; + ret[0].type = C_STRING; + sprintf(buf, "%d", params->w); + ret[0].sval = dupstr(buf); + ret[0].ival = 0; + + ret[1].name = "Height"; + ret[1].type = C_STRING; + sprintf(buf, "%d", params->h); + ret[1].sval = dupstr(buf); + ret[1].ival = 0; + + ret[2].name = "%age of black squares"; + ret[2].type = C_STRING; + sprintf(buf, "%d", params->blackpc); + ret[2].sval = dupstr(buf); + ret[2].ival = 0; + + ret[3].name = "Symmetry"; + ret[3].type = C_CHOICES; + ret[3].sval = ":None" + ":2-way mirror:2-way rotational" + ":4-way mirror:4-way rotational"; + ret[3].ival = params->symm; + + ret[4].name = "Difficulty"; + ret[4].type = C_CHOICES; + ret[4].sval = ":Easy:Tricky:Hard"; + ret[4].ival = params->difficulty; + + ret[5].name = NULL; + ret[5].type = C_END; + ret[5].sval = NULL; + ret[5].ival = 0; + + return ret; +} + +static game_params *custom_params(const config_item *cfg) +{ + game_params *ret = snew(game_params); + + ret->w = atoi(cfg[0].sval); + ret->h = atoi(cfg[1].sval); + ret->blackpc = atoi(cfg[2].sval); + ret->symm = cfg[3].ival; + ret->difficulty = cfg[4].ival; + + return ret; +} + +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"; + if (full) { + if (params->blackpc < 5 || params->blackpc > 100) + return "Percentage of black squares must be between 5% and 100%"; + if (params->w != params->h) { + if (params->symm == SYMM_ROT4) + return "4-fold symmetry is only available with square grids"; + } + if (params->symm < 0 || params->symm >= SYMM_MAX) + return "Unknown symmetry type"; + if (params->difficulty < 0 || params->difficulty > DIFFCOUNT) + return "Unknown difficulty level"; + } + return NULL; +} + +/* --- Game state construction/freeing helper functions --- */ + +static game_state *new_state(const game_params *params) +{ + game_state *ret = snew(game_state); + + ret->w = params->w; + ret->h = params->h; + ret->lights = snewn(ret->w * ret->h, int); + ret->nlights = 0; + memset(ret->lights, 0, ret->w * ret->h * sizeof(int)); + ret->flags = snewn(ret->w * ret->h, unsigned int); + memset(ret->flags, 0, ret->w * ret->h * sizeof(unsigned int)); + ret->completed = ret->used_solve = 0; + return ret; +} + +static game_state *dup_game(const game_state *state) +{ + game_state *ret = snew(game_state); + + ret->w = state->w; + ret->h = state->h; + + ret->lights = snewn(ret->w * ret->h, int); + memcpy(ret->lights, state->lights, ret->w * ret->h * sizeof(int)); + ret->nlights = state->nlights; + + ret->flags = snewn(ret->w * ret->h, unsigned int); + memcpy(ret->flags, state->flags, ret->w * ret->h * sizeof(unsigned int)); + + ret->completed = state->completed; + ret->used_solve = state->used_solve; + + return ret; +} + +static void free_game(game_state *state) +{ + sfree(state->lights); + sfree(state->flags); + sfree(state); +} + +static void debug_state(game_state *state) +{ + int x, y; + char c = '?'; + + for (y = 0; y < state->h; y++) { + for (x = 0; x < state->w; x++) { + c = '.'; + if (GRID(state, flags, x, y) & F_BLACK) { + if (GRID(state, flags, x, y) & F_NUMBERED) + c = GRID(state, lights, x, y) + '0'; + else + c = '#'; + } else { + if (GRID(state, flags, x, y) & F_LIGHT) + c = 'O'; + else if (GRID(state, flags, x, y) & F_IMPOSSIBLE) + c = 'X'; + } + debug(("%c", (int)c)); + } + debug((" ")); + for (x = 0; x < state->w; x++) { + if (GRID(state, flags, x, y) & F_BLACK) + c = '#'; + else { + c = (GRID(state, flags, x, y) & F_LIGHT) ? 'A' : 'a'; + c += GRID(state, lights, x, y); + } + debug(("%c", (int)c)); + } + debug(("\n")); + } +} + +/* --- Game completion test routines. --- */ + +/* These are split up because occasionally functions are only + * interested in one particular aspect. */ + +/* Returns non-zero if all grid spaces are lit. */ +static int grid_lit(game_state *state) +{ + int x, y; + + for (x = 0; x < state->w; x++) { + for (y = 0; y < state->h; y++) { + if (GRID(state,flags,x,y) & F_BLACK) continue; + if (GRID(state,lights,x,y) == 0) + return 0; + } + } + return 1; +} + +/* Returns non-zero if any lights are lit by other lights. */ +static int grid_overlap(game_state *state) +{ + int x, y; + + for (x = 0; x < state->w; x++) { + for (y = 0; y < state->h; y++) { + if (!(GRID(state, flags, x, y) & F_LIGHT)) continue; + if (GRID(state, lights, x, y) > 1) + return 1; + } + } + return 0; +} + +static int number_wrong(const game_state *state, int x, int y) +{ + surrounds s; + int i, n, empty, lights = GRID(state, lights, x, y); + + /* + * This function computes the display hint for a number: we + * turn the number red if it is definitely wrong. This means + * that either + * + * (a) it has too many lights around it, or + * (b) it would have too few lights around it even if all the + * plausible squares (not black, lit or F_IMPOSSIBLE) were + * filled with lights. + */ + + assert(GRID(state, flags, x, y) & F_NUMBERED); + get_surrounds(state, x, y, &s); + + empty = n = 0; + for (i = 0; i < s.npoints; i++) { + if (GRID(state,flags,s.points[i].x,s.points[i].y) & F_LIGHT) { + n++; + continue; + } + if (GRID(state,flags,s.points[i].x,s.points[i].y) & F_BLACK) + continue; + if (GRID(state,flags,s.points[i].x,s.points[i].y) & F_IMPOSSIBLE) + continue; + if (GRID(state,lights,s.points[i].x,s.points[i].y)) + continue; + empty++; + } + return (n > lights || (n + empty < lights)); +} + +static int number_correct(game_state *state, int x, int y) +{ + surrounds s; + int n = 0, i, lights = GRID(state, lights, x, y); + + assert(GRID(state, flags, x, y) & F_NUMBERED); + 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_LIGHT) + n++; + } + return (n == lights) ? 1 : 0; +} + +/* Returns non-zero if any numbers add up incorrectly. */ +static int grid_addsup(game_state *state) +{ + int x, y; + + for (x = 0; x < state->w; x++) { + for (y = 0; y < state->h; y++) { + if (!(GRID(state, flags, x, y) & F_NUMBERED)) continue; + if (!number_correct(state, x, y)) return 0; + } + } + return 1; +} + +static int grid_correct(game_state *state) +{ + if (grid_lit(state) && + !grid_overlap(state) && + grid_addsup(state)) return 1; + return 0; +} + +/* --- Board initial setup (blacks, lights, numbers) --- */ + +static void clean_board(game_state *state, int leave_blacks) +{ + int x,y; + for (x = 0; x < state->w; x++) { + for (y = 0; y < state->h; y++) { + if (leave_blacks) + GRID(state, flags, x, y) &= F_BLACK; + else + GRID(state, flags, x, y) = 0; + GRID(state, lights, x, y) = 0; + } + } + state->nlights = 0; +} + +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 wodd = (state->w % 2) ? 1 : 0; + int hodd = (state->h % 2) ? 1 : 0; + int xs[4], ys[4]; + + switch (params->symm) { + case SYMM_NONE: degree = 1; rotate = 0; break; + case SYMM_ROT2: degree = 2; rotate = 1; break; + case SYMM_REF2: degree = 2; rotate = 0; break; + case SYMM_ROT4: degree = 4; rotate = 1; break; + case SYMM_REF4: degree = 4; rotate = 0; break; + default: assert(!"Unknown symmetry type"); + } + if (params->symm == SYMM_ROT4 && (state->h != state->w)) + assert(!"4-fold symmetry unavailable without square grid"); + + if (degree == 4) { + rw = state->w/2; + rh = state->h/2; + if (!rotate) rw += wodd; /* ... but see below. */ + rh += hodd; + } else if (degree == 2) { + rw = state->w; + rh = state->h/2; + rh += hodd; + } else { + rw = state->w; + rh = state->h; + } + + /* clear, then randomise, required region. */ + clean_board(state, 0); + nblack = (rw * rh * params->blackpc) / 100; + for (i = 0; i < nblack; i++) { + do { + x = random_upto(rs,rw); + y = random_upto(rs,rh); + } while (GRID(state,flags,x,y) & F_BLACK); + GRID(state, flags, x, y) |= F_BLACK; + } + + /* Copy required region. */ + if (params->symm == SYMM_NONE) return; + + for (x = 0; x < rw; x++) { + for (y = 0; y < rh; y++) { + if (degree == 4) { + xs[0] = x; + ys[0] = y; + xs[1] = state->w - 1 - (rotate ? y : x); + ys[1] = rotate ? x : y; + xs[2] = rotate ? (state->w - 1 - x) : x; + ys[2] = state->h - 1 - y; + xs[3] = rotate ? y : (state->w - 1 - x); + ys[3] = state->h - 1 - (rotate ? x : y); + } else { + xs[0] = x; + ys[0] = y; + xs[1] = rotate ? (state->w - 1 - x) : x; + ys[1] = state->h - 1 - y; + } + for (i = 1; i < degree; i++) { + GRID(state, flags, xs[i], ys[i]) = + GRID(state, flags, xs[0], ys[0]); + } + } + } + /* SYMM_ROT4 misses the middle square above; fix that here. */ + if (degree == 4 && rotate && wodd && + (random_upto(rs,100) <= (unsigned int)params->blackpc)) + GRID(state,flags, + state->w/2 + wodd - 1, state->h/2 + hodd - 1) |= F_BLACK; + +#ifdef SOLVER_DIAGNOSTICS + if (verbose) debug_state(state); +#endif +} + +/* Fills in (does not allocate) a ll_data with all the tiles that would + * be illuminated by a light at point (ox,oy). If origin=1 then the + * origin is included in this list. */ +static void list_lights(game_state *state, int ox, int oy, int origin, + ll_data *lld) +{ + int x,y; + + lld->ox = lld->minx = lld->maxx = ox; + lld->oy = lld->miny = lld->maxy = oy; + lld->include_origin = origin; + + y = oy; + for (x = ox-1; x >= 0; x--) { + if (GRID(state, flags, x, y) & F_BLACK) break; + if (x < lld->minx) lld->minx = x; + } + for (x = ox+1; x < state->w; x++) { + if (GRID(state, flags, x, y) & F_BLACK) break; + if (x > lld->maxx) lld->maxx = x; + } + + x = ox; + for (y = oy-1; y >= 0; y--) { + if (GRID(state, flags, x, y) & F_BLACK) break; + if (y < lld->miny) lld->miny = y; + } + for (y = oy+1; y < state->h; y++) { + if (GRID(state, flags, x, y) & F_BLACK) break; + if (y > lld->maxy) lld->maxy = y; + } +} + +/* Makes sure a light is the given state, editing the lights table to suit the + * new state if necessary. */ +static void set_light(game_state *state, int ox, int oy, int on) +{ + ll_data lld; + int diff = 0; + + assert(!(GRID(state,flags,ox,oy) & F_BLACK)); + + if (!on && GRID(state,flags,ox,oy) & F_LIGHT) { + diff = -1; + GRID(state,flags,ox,oy) &= ~F_LIGHT; + state->nlights--; + } else if (on && !(GRID(state,flags,ox,oy) & F_LIGHT)) { + diff = 1; + GRID(state,flags,ox,oy) |= F_LIGHT; + state->nlights++; + } + + if (diff != 0) { + list_lights(state,ox,oy,1,&lld); + FOREACHLIT(&lld, GRID(state,lights,lx,ly) += diff; ); + } +} + +/* Returns 1 if removing a light at (x,y) would cause a square to go dark. */ +static int check_dark(game_state *state, int x, int y) +{ + ll_data lld; + + list_lights(state, x, y, 1, &lld); + FOREACHLIT(&lld, if (GRID(state,lights,lx,ly) == 1) { return 1; } ); + return 0; +} + +/* Sets up an initial random correct position (i.e. every + * space lit, and no lights lit by other lights) by filling the + * grid with lights and then removing lights one by one at random. */ +static void place_lights(game_state *state, random_state *rs) +{ + int i, x, y, n, *numindices, wh = state->w*state->h; + ll_data lld; + + numindices = snewn(wh, int); + for (i = 0; i < wh; i++) numindices[i] = i; + shuffle(numindices, wh, sizeof(*numindices), rs); + + /* Place a light on all grid squares without lights. */ + for (x = 0; x < state->w; x++) { + for (y = 0; y < state->h; y++) { + GRID(state, flags, x, y) &= ~F_MARK; /* we use this later. */ + if (GRID(state, flags, x, y) & F_BLACK) continue; + set_light(state, x, y, 1); + } + } + + for (i = 0; i < wh; i++) { + y = numindices[i] / state->w; + x = numindices[i] % state->w; + if (!(GRID(state, flags, x, y) & F_LIGHT)) continue; + if (GRID(state, flags, x, y) & F_MARK) continue; + list_lights(state, x, y, 0, &lld); + + /* If we're not lighting any lights ourself, don't remove anything. */ + n = 0; + FOREACHLIT(&lld, if (GRID(state,flags,lx,ly) & F_LIGHT) { n += 1; } ); + if (n == 0) continue; /* [1] */ + + /* Check whether removing lights we're lighting would cause anything + * to go dark. */ + n = 0; + FOREACHLIT(&lld, if (GRID(state,flags,lx,ly) & F_LIGHT) { n += check_dark(state,lx,ly); } ); + if (n == 0) { + /* No, it wouldn't, so we can remove them all. */ + FOREACHLIT(&lld, set_light(state,lx,ly, 0); ); + GRID(state,flags,x,y) |= F_MARK; + } + + if (!grid_overlap(state)) { + sfree(numindices); + return; /* we're done. */ + } + assert(grid_lit(state)); + } + /* could get here if the line at [1] continue'd out of the loop. */ + if (grid_overlap(state)) { + debug_state(state); + assert(!"place_lights failed to resolve overlapping lights!"); + } + sfree(numindices); +} + +/* Fills in all black squares with numbers of adjacent lights. */ +static void place_numbers(game_state *state) +{ + int x, y, i, n; + surrounds s; + + for (x = 0; x < state->w; x++) { + for (y = 0; y < state->h; y++) { + if (!(GRID(state,flags,x,y) & F_BLACK)) continue; + get_surrounds(state, x, y, &s); + n = 0; + for (i = 0; i < s.npoints; i++) { + if (GRID(state,flags,s.points[i].x, s.points[i].y) & F_LIGHT) + n++; + } + GRID(state,flags,x,y) |= F_NUMBERED; + GRID(state,lights,x,y) = n; + } + } +} + +/* --- Actual solver, with helper subroutines. --- */ + +static void tsl_callback(game_state *state, + int lx, int ly, int *x, int *y, int *n) +{ + if (GRID(state,flags,lx,ly) & F_IMPOSSIBLE) return; + if (GRID(state,lights,lx,ly) > 0) return; + *x = lx; *y = ly; (*n)++; +} + +static int try_solve_light(game_state *state, int ox, int oy, + unsigned int flags, int lights) +{ + ll_data lld; + int sx = 0, sy = 0, n = 0; + + if (lights > 0) return 0; + if (flags & F_BLACK) return 0; + + /* We have an unlit square; count how many ways there are left to + * place a light that lights us (including this square); if only + * one, we must put a light there. Squares that could light us + * are, of course, the same as the squares we would light... */ + list_lights(state, ox, oy, 1, &lld); + FOREACHLIT(&lld, { tsl_callback(state, lx, ly, &sx, &sy, &n); }); + if (n == 1) { + set_light(state, sx, sy, 1); +#ifdef SOLVER_DIAGNOSTICS + debug(("(%d,%d) can only be lit from (%d,%d); setting to LIGHT\n", + ox,oy,sx,sy)); + if (verbose) debug_state(state); +#endif + return 1; + } + + return 0; +} + +static int could_place_light(unsigned int flags, int lights) +{ + if (flags & (F_BLACK | F_IMPOSSIBLE)) return 0; + return (lights > 0) ? 0 : 1; +} + +static int could_place_light_xy(game_state *state, int x, int y) +{ + int lights = GRID(state,lights,x,y); + unsigned int flags = GRID(state,flags,x,y); + return (could_place_light(flags, lights)) ? 1 : 0; +} + +/* For a given number square, determine whether we have enough info + * to unambiguously place its lights. */ +static int try_solve_number(game_state *state, int nx, int ny, + unsigned int nflags, int nlights) +{ + surrounds s; + int x, y, nl, ns, i, ret = 0, lights; + unsigned int flags; + + if (!(nflags & F_NUMBERED)) return 0; + nl = nlights; + get_surrounds(state,nx,ny,&s); + ns = s.npoints; + + /* nl is no. of lights we need to place, ns is no. of spaces we + * have to place them in. Try and narrow these down, and mark + * points we can ignore later. */ + for (i = 0; i < s.npoints; i++) { + x = s.points[i].x; y = s.points[i].y; + flags = GRID(state,flags,x,y); + lights = GRID(state,lights,x,y); + if (flags & F_LIGHT) { + /* light here already; one less light for one less place. */ + nl--; ns--; + s.points[i].f |= F_MARK; + } else if (!could_place_light(flags, lights)) { + ns--; + s.points[i].f |= F_MARK; + } + } + if (ns == 0) return 0; /* nowhere to put anything. */ + if (nl == 0) { + /* we have placed all lights we need to around here; all remaining + * surrounds are therefore IMPOSSIBLE. */ + GRID(state,flags,nx,ny) |= F_NUMBERUSED; + for (i = 0; i < s.npoints; i++) { + if (!(s.points[i].f & F_MARK)) { + GRID(state,flags,s.points[i].x,s.points[i].y) |= F_IMPOSSIBLE; + ret = 1; + } + } +#ifdef SOLVER_DIAGNOSTICS + printf("Clue at (%d,%d) full; setting unlit to IMPOSSIBLE.\n", + nx,ny); + if (verbose) debug_state(state); +#endif + } else if (nl == ns) { + /* we have as many lights to place as spaces; fill them all. */ + GRID(state,flags,nx,ny) |= F_NUMBERUSED; + for (i = 0; i < s.npoints; i++) { + if (!(s.points[i].f & F_MARK)) { + set_light(state, s.points[i].x,s.points[i].y, 1); + ret = 1; + } + } +#ifdef SOLVER_DIAGNOSTICS + printf("Clue at (%d,%d) trivial; setting unlit to LIGHT.\n", + nx,ny); + if (verbose) debug_state(state); +#endif + } + return ret; +} + +struct setscratch { + int x, y; + int n; +}; + +#define SCRATCHSZ (state->w+state->h) + +/* New solver algorithm: overlapping sets can add IMPOSSIBLE flags. + * Algorithm thanks to Simon: + * + * (a) Any square where you can place a light has a set of squares + * which would become non-lights as a result. (This includes + * squares lit by the first square, and can also include squares + * adjacent to the same clue square if the new light is the last + * one around that clue.) Call this MAKESDARK(x,y) with (x,y) being + * the square you place a light. + + * (b) Any unlit square has a set of squares on which you could place + * a light to illuminate it. (Possibly including itself, of + * course.) This set of squares has the property that _at least + * one_ of them must contain a light. Sets of this type also arise + * from clue squares. Call this MAKESLIGHT(x,y), again with (x,y) + * the square you would place a light. + + * (c) If there exists (dx,dy) and (lx,ly) such that MAKESDARK(dx,dy) is + * a superset of MAKESLIGHT(lx,ly), this implies that placing a light at + * (dx,dy) would either leave no remaining way to illuminate a certain + * square, or would leave no remaining way to fulfill a certain clue + * (at lx,ly). In either case, a light can be ruled out at that position. + * + * So, we construct all possible MAKESLIGHT sets, both from unlit squares + * and clue squares, and then we look for plausible MAKESDARK sets that include + * our (lx,ly) to see if we can find a (dx,dy) to rule out. By the time we have + * constructed the MAKESLIGHT set we don't care about (lx,ly), just the set + * members. + * + * Once we have such a set, Simon came up with a Cunning Plan to find + * the most sensible MAKESDARK candidate: + * + * (a) for each square S in your set X, find all the squares which _would_ + * rule it out. That means any square which would light S, plus + * any square adjacent to the same clue square as S (provided + * that clue square has only one remaining light to be placed). + * It's not hard to make this list. Don't do anything with this + * data at the moment except _count_ the squares. + + * (b) Find the square S_min in the original set which has the + * _smallest_ number of other squares which would rule it out. + + * (c) Find all the squares that rule out S_min (it's probably + * better to recompute this than to have stored it during step + * (a), since the CPU requirement is modest but the storage + * cost would get ugly.) For each of these squares, see if it + * rules out everything else in the set X. Any which does can + * be marked as not-a-light. + * + */ + +typedef void (*trl_cb)(game_state *state, int dx, int dy, + struct setscratch *scratch, int n, void *ctx); + +static void try_rule_out(game_state *state, int x, int y, + struct setscratch *scratch, int n, + trl_cb cb, void *ctx); + +static void trl_callback_search(game_state *state, int dx, int dy, + struct setscratch *scratch, int n, void *ignored) +{ + int i; + +#ifdef SOLVER_DIAGNOSTICS + if (verbose) debug(("discount cb: light at (%d,%d)\n", dx, dy)); +#endif + + for (i = 0; i < n; i++) { + if (dx == scratch[i].x && dy == scratch[i].y) { + scratch[i].n = 1; + return; + } + } +} + +static void trl_callback_discount(game_state *state, int dx, int dy, + struct setscratch *scratch, int n, void *ctx) +{ + int *didsth = (int *)ctx; + int i; + + if (GRID(state,flags,dx,dy) & F_IMPOSSIBLE) { +#ifdef SOLVER_DIAGNOSTICS + debug(("Square at (%d,%d) already impossible.\n", dx,dy)); +#endif + return; + } + + /* Check whether a light at (dx,dy) rules out everything + * in scratch, and mark (dx,dy) as IMPOSSIBLE if it does. + * We can use try_rule_out for this as well, as the set of + * squares which would rule out (x,y) is the same as the + * set of squares which (x,y) would rule out. */ + +#ifdef SOLVER_DIAGNOSTICS + if (verbose) debug(("Checking whether light at (%d,%d) rules out everything in scratch.\n", dx, dy)); +#endif + + for (i = 0; i < n; i++) + scratch[i].n = 0; + try_rule_out(state, dx, dy, scratch, n, trl_callback_search, NULL); + for (i = 0; i < n; i++) { + if (scratch[i].n == 0) return; + } + /* The light ruled out everything in scratch. Yay. */ + GRID(state,flags,dx,dy) |= F_IMPOSSIBLE; +#ifdef SOLVER_DIAGNOSTICS + debug(("Set reduction discounted square at (%d,%d):\n", dx,dy)); + if (verbose) debug_state(state); +#endif + + *didsth = 1; +} + +static void trl_callback_incn(game_state *state, int dx, int dy, + struct setscratch *scratch, int n, void *ctx) +{ + struct setscratch *s = (struct setscratch *)ctx; + s->n++; +} + +static void try_rule_out(game_state *state, int x, int y, + struct setscratch *scratch, int n, + trl_cb cb, void *ctx) +{ + /* XXX Find all the squares which would rule out (x,y); anything + * that would light it as well as squares adjacent to same clues + * as X assuming that clue only has one remaining light. + * Call the callback with each square. */ + ll_data lld; + surrounds s, ss; + int i, j, curr_lights, tot_lights; + + /* Find all squares that would rule out a light at (x,y) and call trl_cb + * with them: anything that would light (x,y)... */ + + list_lights(state, x, y, 0, &lld); + FOREACHLIT(&lld, { if (could_place_light_xy(state, lx, ly)) { cb(state, lx, ly, scratch, n, ctx); } }); + + /* ... as well as any empty space (that isn't x,y) next to any clue square + * next to (x,y) that only has one light left to place. */ + + 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)) + continue; + /* 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; + for (j = 0; j < ss.npoints; j++) { + if (GRID(state,flags,ss.points[j].x,ss.points[j].y) & F_LIGHT) + curr_lights++; + } + tot_lights = GRID(state, lights, s.points[i].x, s.points[i].y); + /* We have a clue with tot_lights to fill, and curr_lights currently + * around it. If adding a light at (x,y) fills up the clue (i.e. + * curr_lights + 1 = tot_lights) then we need to discount all other + * unlit squares around the clue. */ + if ((curr_lights + 1) == tot_lights) { + for (j = 0; j < ss.npoints; j++) { + int lx = ss.points[j].x, ly = ss.points[j].y; + if (lx == x && ly == y) continue; + if (could_place_light_xy(state, lx, ly)) + cb(state, lx, ly, scratch, n, ctx); + } + } + } +} + +#ifdef SOLVER_DIAGNOSTICS +static void debug_scratch(const char *msg, struct setscratch *scratch, int n) +{ + int i; + debug(("%s scratch (%d elements):\n", msg, n)); + for (i = 0; i < n; i++) { + debug((" (%d,%d) n%d\n", scratch[i].x, scratch[i].y, scratch[i].n)); + } +} +#endif + +static int discount_set(game_state *state, + struct setscratch *scratch, int n) +{ + int i, besti, bestn, didsth = 0; + +#ifdef SOLVER_DIAGNOSTICS + if (verbose > 1) debug_scratch("discount_set", scratch, n); +#endif + if (n == 0) return 0; + + for (i = 0; i < n; i++) { + try_rule_out(state, scratch[i].x, scratch[i].y, scratch, n, + trl_callback_incn, (void*)&(scratch[i])); + } +#ifdef SOLVER_DIAGNOSTICS + if (verbose > 1) debug_scratch("discount_set after count", scratch, n); +#endif + + besti = -1; bestn = SCRATCHSZ; + for (i = 0; i < n; i++) { + if (scratch[i].n < bestn) { + bestn = scratch[i].n; + besti = i; + } + } +#ifdef SOLVER_DIAGNOSTICS + if (verbose > 1) debug(("best square (%d,%d) with n%d.\n", + scratch[besti].x, scratch[besti].y, scratch[besti].n)); +#endif + try_rule_out(state, scratch[besti].x, scratch[besti].y, scratch, n, + trl_callback_discount, (void*)&didsth); +#ifdef SOLVER_DIAGNOSTICS + if (didsth) debug((" [from square (%d,%d)]\n", + scratch[besti].x, scratch[besti].y)); +#endif + + return didsth; +} + +static void discount_clear(game_state *state, struct setscratch *scratch, int *n) +{ + *n = 0; + memset(scratch, 0, SCRATCHSZ * sizeof(struct setscratch)); +} + +static void unlit_cb(game_state *state, int lx, int ly, + struct setscratch *scratch, int *n) +{ + if (could_place_light_xy(state, lx, ly)) { + scratch[*n].x = lx; scratch[*n].y = ly; (*n)++; + } +} + +/* Construct a MAKESLIGHT set from an unlit square. */ +static int discount_unlit(game_state *state, int x, int y, + struct setscratch *scratch) +{ + ll_data lld; + int n, didsth; + +#ifdef SOLVER_DIAGNOSTICS + if (verbose) debug(("Trying to discount for unlit square at (%d,%d).\n", x, y)); + if (verbose > 1) debug_state(state); +#endif + + discount_clear(state, scratch, &n); + + list_lights(state, x, y, 1, &lld); + FOREACHLIT(&lld, { unlit_cb(state, lx, ly, scratch, &n); }); + didsth = discount_set(state, scratch, n); +#ifdef SOLVER_DIAGNOSTICS + if (didsth) debug((" [from unlit square at (%d,%d)].\n", x, y)); +#endif + return didsth; + +} + +/* Construct a series of MAKESLIGHT sets from a clue square. + * for a clue square with N remaining spaces that must contain M lights, every + * subset of size N-M+1 of those N spaces forms such a set. + */ + +static int discount_clue(game_state *state, int x, int y, + struct setscratch *scratch) +{ + int slen, m = GRID(state, lights, x, y), n, i, didsth = 0, lights; + unsigned int flags; + surrounds s, sempty; + combi_ctx *combi; + + if (m == 0) return 0; + +#ifdef SOLVER_DIAGNOSTICS + if (verbose) debug(("Trying to discount for sets at clue (%d,%d).\n", x, y)); + if (verbose > 1) debug_state(state); +#endif + + /* m is no. of lights still to place; starts off at the clue value + * and decreases when we find a light already down. + * n is no. of spaces left; starts off at 0 and goes up when we find + * a plausible space. */ + + get_surrounds(state, x, y, &s); + memset(&sempty, 0, sizeof(surrounds)); + for (i = 0; i < s.npoints; i++) { + int lx = s.points[i].x, ly = s.points[i].y; + flags = GRID(state,flags,lx,ly); + lights = GRID(state,lights,lx,ly); + + if (flags & F_LIGHT) m--; + + if (could_place_light(flags, lights)) { + sempty.points[sempty.npoints].x = lx; + sempty.points[sempty.npoints].y = ly; + sempty.npoints++; + } + } + n = sempty.npoints; /* sempty is now a surrounds of only blank squares. */ + if (n == 0) return 0; /* clue is full already. */ + + if (m < 0 || m > n) return 0; /* become impossible. */ + + combi = new_combi(n - m + 1, n); + while (next_combi(combi)) { + discount_clear(state, scratch, &slen); + for (i = 0; i < combi->r; i++) { + scratch[slen].x = sempty.points[combi->a[i]].x; + scratch[slen].y = sempty.points[combi->a[i]].y; + slen++; + } + if (discount_set(state, scratch, slen)) didsth = 1; + } + free_combi(combi); +#ifdef SOLVER_DIAGNOSTICS + if (didsth) debug((" [from clue at (%d,%d)].\n", x, y)); +#endif + return didsth; +} + +#define F_SOLVE_FORCEUNIQUE 1 +#define F_SOLVE_DISCOUNTSETS 2 +#define F_SOLVE_ALLOWRECURSE 4 + +static unsigned int flags_from_difficulty(int difficulty) +{ + unsigned int sflags = F_SOLVE_FORCEUNIQUE; + assert(difficulty <= DIFFCOUNT); + if (difficulty >= 1) sflags |= F_SOLVE_DISCOUNTSETS; + if (difficulty >= 2) sflags |= F_SOLVE_ALLOWRECURSE; + return sflags; +} + +#define MAXRECURSE 5 + +static int solve_sub(game_state *state, + unsigned int solve_flags, int depth, + int *maxdepth) +{ + unsigned int flags; + int x, y, didstuff, ncanplace, lights; + int bestx, besty, n, bestn, copy_soluble, self_soluble, ret, maxrecurse = 0; + game_state *scopy; + ll_data lld; + struct setscratch *sscratch = NULL; + +#ifdef SOLVER_DIAGNOSTICS + printf("solve_sub: depth = %d\n", depth); +#endif + if (maxdepth && *maxdepth < depth) *maxdepth = depth; + if (solve_flags & F_SOLVE_ALLOWRECURSE) maxrecurse = MAXRECURSE; + + while (1) { + if (grid_overlap(state)) { + /* Our own solver, from scratch, should never cause this to happen + * (assuming a soluble grid). However, if we're trying to solve + * from a half-completed *incorrect* grid this might occur; we + * just return the 'no solutions' code in this case. */ + ret = 0; goto done; + } + + if (grid_correct(state)) { ret = 1; goto done; } + + ncanplace = 0; + didstuff = 0; + /* These 2 loops, and the functions they call, are the critical loops + * for timing; any optimisations should look here first. */ + for (x = 0; x < state->w; x++) { + for (y = 0; y < state->h; y++) { + flags = GRID(state,flags,x,y); + lights = GRID(state,lights,x,y); + ncanplace += could_place_light(flags, lights); + + if (try_solve_light(state, x, y, flags, lights)) didstuff = 1; + if (try_solve_number(state, x, y, flags, lights)) didstuff = 1; + } + } + if (didstuff) continue; + if (!ncanplace) { + /* nowhere to put a light, puzzle is unsoluble. */ + ret = 0; goto done; + } + + if (solve_flags & F_SOLVE_DISCOUNTSETS) { + if (!sscratch) sscratch = snewn(SCRATCHSZ, struct setscratch); + /* Try a more cunning (and more involved) way... more details above. */ + for (x = 0; x < state->w; x++) { + for (y = 0; y < state->h; y++) { + flags = GRID(state,flags,x,y); + lights = GRID(state,lights,x,y); + + if (!(flags & F_BLACK) && lights == 0) { + if (discount_unlit(state, x, y, sscratch)) { + didstuff = 1; + goto reduction_success; + } + } else if (flags & F_NUMBERED) { + if (discount_clue(state, x, y, sscratch)) { + didstuff = 1; + goto reduction_success; + } + } + } + } + } +reduction_success: + if (didstuff) continue; + + /* We now have to make a guess; we have places to put lights but + * no definite idea about where they can go. */ + if (depth >= maxrecurse) { + /* mustn't delve any deeper. */ + ret = -1; goto done; + } + /* Of all the squares that we could place a light, pick the one + * that would light the most currently unlit squares. */ + /* This heuristic was just plucked from the air; there may well be + * a more efficient way of choosing a square to flip to minimise + * recursion. */ + bestn = 0; + bestx = besty = -1; /* suyb */ + for (x = 0; x < state->w; x++) { + for (y = 0; y < state->h; y++) { + flags = GRID(state,flags,x,y); + lights = GRID(state,lights,x,y); + if (!could_place_light(flags, lights)) continue; + + n = 0; + list_lights(state, x, y, 1, &lld); + FOREACHLIT(&lld, { if (GRID(state,lights,lx,ly) == 0) n++; }); + if (n > bestn) { + bestn = n; bestx = x; besty = y; + } + } + } + assert(bestn > 0); + assert(bestx >= 0 && besty >= 0); + + /* Now we've chosen a plausible (x,y), try to solve it once as 'lit' + * and once as 'impossible'; we need to make one copy to do this. */ + + scopy = dup_game(state); +#ifdef SOLVER_DIAGNOSTICS + debug(("Recursing #1: trying (%d,%d) as IMPOSSIBLE\n", bestx, besty)); +#endif + GRID(state,flags,bestx,besty) |= F_IMPOSSIBLE; + self_soluble = solve_sub(state, solve_flags, depth+1, maxdepth); + + if (!(solve_flags & F_SOLVE_FORCEUNIQUE) && self_soluble > 0) { + /* we didn't care about finding all solutions, and we just + * found one; return with it immediately. */ + free_game(scopy); + ret = self_soluble; + goto done; + } + +#ifdef SOLVER_DIAGNOSTICS + debug(("Recursing #2: trying (%d,%d) as LIGHT\n", bestx, besty)); +#endif + set_light(scopy, bestx, besty, 1); + copy_soluble = solve_sub(scopy, solve_flags, depth+1, maxdepth); + + /* If we wanted a unique solution but we hit our recursion limit + * (on either branch) then we have to assume we didn't find possible + * extra solutions, and return 'not soluble'. */ + if ((solve_flags & F_SOLVE_FORCEUNIQUE) && + ((copy_soluble < 0) || (self_soluble < 0))) { + ret = -1; + /* Make sure that whether or not it was self or copy (or both) that + * were soluble, that we return a solved state in self. */ + } else if (copy_soluble <= 0) { + /* copy wasn't soluble; keep self state and return that result. */ + ret = self_soluble; + } else if (self_soluble <= 0) { + /* copy solved and we didn't, so copy in copy's (now solved) + * flags and light state. */ + memcpy(state->lights, scopy->lights, + scopy->w * scopy->h * sizeof(int)); + memcpy(state->flags, scopy->flags, + scopy->w * scopy->h * sizeof(unsigned int)); + ret = copy_soluble; + } else { + ret = copy_soluble + self_soluble; + } + free_game(scopy); + goto done; + } +done: + if (sscratch) sfree(sscratch); +#ifdef SOLVER_DIAGNOSTICS + if (ret < 0) + debug(("solve_sub: depth = %d returning, ran out of recursion.\n", + depth)); + else + debug(("solve_sub: depth = %d returning, %d solutions.\n", + depth, ret)); +#endif + return ret; +} + +/* Fills in the (possibly partially-complete) game_state as far as it can, + * returning the number of possible solutions. If it returns >0 then the + * game_state will be in a solved state, but you won't know which one. */ +static int dosolve(game_state *state, int solve_flags, int *maxdepth) +{ + int x, y, nsol; + + for (x = 0; x < state->w; x++) { + for (y = 0; y < state->h; y++) { + GRID(state,flags,x,y) &= ~F_NUMBERUSED; + } + } + nsol = solve_sub(state, solve_flags, 0, maxdepth); + return nsol; +} + +static int strip_unused_nums(game_state *state) +{ + int x,y,n=0; + for (x = 0; x < state->w; x++) { + for (y = 0; y < state->h; y++) { + if ((GRID(state,flags,x,y) & F_NUMBERED) && + !(GRID(state,flags,x,y) & F_NUMBERUSED)) { + GRID(state,flags,x,y) &= ~F_NUMBERED; + GRID(state,lights,x,y) = 0; + n++; + } + } + } + debug(("Stripped %d unused numbers.\n", n)); + return n; +} + +static void unplace_lights(game_state *state) +{ + int x,y; + for (x = 0; x < state->w; x++) { + for (y = 0; y < state->h; y++) { + if (GRID(state,flags,x,y) & F_LIGHT) + set_light(state,x,y,0); + GRID(state,flags,x,y) &= ~F_IMPOSSIBLE; + GRID(state,flags,x,y) &= ~F_NUMBERUSED; + } + } +} + +static int puzzle_is_good(game_state *state, int difficulty) +{ + int nsol, mdepth = 0; + unsigned int sflags = flags_from_difficulty(difficulty); + + unplace_lights(state); + +#ifdef SOLVER_DIAGNOSTICS + debug(("Trying to solve with difficulty %d (0x%x):\n", + difficulty, sflags)); + if (verbose) debug_state(state); +#endif + + nsol = dosolve(state, sflags, &mdepth); + /* if we wanted an easy puzzle, make sure we didn't need recursion. */ + if (!(sflags & F_SOLVE_ALLOWRECURSE) && mdepth > 0) { + debug(("Ignoring recursive puzzle.\n")); + return 0; + } + + debug(("%d solutions found.\n", nsol)); + if (nsol <= 0) return 0; + if (nsol > 1) return 0; + return 1; +} + +/* --- New game creation and user input code. --- */ + +/* The basic algorithm here is to generate the most complex grid possible + * while honouring two restrictions: + * + * * we require a unique solution, and + * * either we require solubility with no recursion (!params->recurse) + * * or we require some recursion. (params->recurse). + * + * The solver helpfully keeps track of the numbers it needed to use to + * get its solution, so we use that to remove an initial set of numbers + * and check we still satsify our requirements (on uniqueness and + * non-recursiveness, if applicable; we don't check explicit recursiveness + * until the end). + * + * Then we try to remove all numbers in a random order, and see if we + * still satisfy requirements (putting them back if we didn't). + * + * Removing numbers will always, in general terms, make a puzzle require + * more recursion but it may also mean a puzzle becomes non-unique. + * + * Once we're done, if we wanted a recursive puzzle but the most difficult + * puzzle we could come up with was non-recursive, we give up and try a new + * grid. */ + +#define MAX_GRIDGEN_TRIES 20 + +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 i, j, run, x, y, wh = params->w*params->h, num; + char *ret, *p; + int *numindices; + + /* Construct a shuffled list of grid positions; we only + * do this once, because if it gets used more than once it'll + * be on a different grid layout. */ + numindices = snewn(wh, int); + for (j = 0; j < wh; j++) numindices[j] = j; + shuffle(numindices, wh, sizeof(*numindices), rs); + + while (1) { + for (i = 0; i < MAX_GRIDGEN_TRIES; i++) { + set_blacks(news, params, rs); /* also cleans board. */ + + /* set up lights and then the numbers, and remove the lights */ + place_lights(news, rs); + debug(("Generating initial grid.\n")); + place_numbers(news); + if (!puzzle_is_good(news, params->difficulty)) continue; + + /* 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); + strip_unused_nums(copys); + if (!puzzle_is_good(copys, params->difficulty)) { + debug(("Stripped grid is not good, reverting.\n")); + free_game(copys); + } else { + free_game(news); + news = copys; + } + + /* Go through grid removing numbers at random one-by-one and + * trying to solve again; if it ceases to be good put the number back. */ + for (j = 0; j < wh; j++) { + y = numindices[j] / params->w; + x = numindices[j] % params->w; + if (!(GRID(news, flags, x, y) & F_NUMBERED)) continue; + num = GRID(news, lights, x, y); + GRID(news, lights, x, y) = 0; + GRID(news, flags, x, y) &= ~F_NUMBERED; + if (!puzzle_is_good(news, params->difficulty)) { + GRID(news, lights, x, y) = num; + GRID(news, flags, x, y) |= F_NUMBERED; + } else + debug(("Removed (%d,%d) still soluble.\n", x, y)); + } + if (params->difficulty > 0) { + /* Was the maximally-difficult puzzle difficult enough? + * Check we can't solve it with a more simplistic solver. */ + if (puzzle_is_good(news, params->difficulty-1)) { + debug(("Maximally-hard puzzle still not hard enough, skipping.\n")); + continue; + } + } + + goto goodpuzzle; + } + /* Couldn't generate a good puzzle in however many goes. Ramp up the + * %age of black squares (if we didn't already have lots; in which case + * why couldn't we generate a puzzle?) and try again. */ + if (params->blackpc < 90) params->blackpc += 5; + debug(("New black layout %d%%.\n", params->blackpc)); + } +goodpuzzle: + /* Game is encoded as a long string one character per square; + * 'S' is a space + * 'B' is a black square with no number + * '0', '1', '2', '3', '4' is a black square with a number. */ + ret = snewn((params->w * params->h) + 1, char); + p = ret; + run = 0; + for (y = 0; y < params->h; y++) { + for (x = 0; x < params->w; x++) { + if (GRID(news,flags,x,y) & F_BLACK) { + if (run) { + *p++ = ('a'-1) + run; + run = 0; + } + if (GRID(news,flags,x,y) & F_NUMBERED) + *p++ = '0' + GRID(news,lights,x,y); + else + *p++ = 'B'; + } else { + if (run == 26) { + *p++ = ('a'-1) + run; + run = 0; + } + run++; + } + } + } + if (run) { + *p++ = ('a'-1) + run; + run = 0; + } + *p = '\0'; + assert(p - ret <= params->w * params->h); + free_game(news); + sfree(numindices); + + return ret; +} + +static char *validate_desc(const game_params *params, const char *desc) +{ + int i; + for (i = 0; i < params->w*params->h; i++) { + if (*desc >= '0' && *desc <= '4') + /* OK */; + else if (*desc == 'B') + /* OK */; + else if (*desc >= 'a' && *desc <= 'z') + i += *desc - 'a'; /* and the i++ will add another one */ + else if (!*desc) + return "Game description shorter than expected"; + else + return "Game description contained unexpected character"; + desc++; + } + if (*desc || i > params->w*params->h) + return "Game description longer than expected"; + + return NULL; +} + +static game_state *new_game(midend *me, const game_params *params, + const char *desc) +{ + game_state *ret = new_state(params); + int x,y; + int run = 0; + + for (y = 0; y < params->h; y++) { + for (x = 0; x < params->w; x++) { + char c = '\0'; + + if (run == 0) { + c = *desc++; + assert(c != 'S'); + if (c >= 'a' && c <= 'z') + run = c - 'a' + 1; + } + + if (run > 0) { + c = 'S'; + run--; + } + + switch (c) { + case '0': case '1': case '2': case '3': case '4': + GRID(ret,flags,x,y) |= F_NUMBERED; + GRID(ret,lights,x,y) = (c - '0'); + /* run-on... */ + + case 'B': + GRID(ret,flags,x,y) |= F_BLACK; + break; + + case 'S': + /* empty square */ + break; + + default: + assert(!"Malformed desc."); + break; + } + } + } + if (*desc) assert(!"Over-long desc."); + + return ret; +} + +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]; + int movelen, movesize, x, y, len; + unsigned int oldflags, solvedflags, sflags; + + /* We don't care here about non-unique puzzles; if the + * user entered one themself then I doubt they care. */ + + sflags = F_SOLVE_ALLOWRECURSE | F_SOLVE_DISCOUNTSETS; + + /* Try and solve from where we are now (for non-unique + * puzzles this may produce a different answer). */ + solved = dup_game(currstate); + if (dosolve(solved, sflags, NULL) > 0) goto solved; + free_game(solved); + + /* That didn't work; try solving from the clean puzzle. */ + solved = dup_game(state); + if (dosolve(solved, sflags, NULL) > 0) goto solved; + *error = "Unable to find a solution to this puzzle."; + goto done; + +solved: + movesize = 256; + move = snewn(movesize, char); + movelen = 0; + move[movelen++] = 'S'; + move[movelen] = '\0'; + for (x = 0; x < currstate->w; x++) { + for (y = 0; y < currstate->h; y++) { + len = 0; + oldflags = GRID(currstate, flags, x, y); + solvedflags = GRID(solved, flags, x, y); + if ((oldflags & F_LIGHT) != (solvedflags & F_LIGHT)) + len = sprintf(buf, ";L%d,%d", x, y); + else if ((oldflags & F_IMPOSSIBLE) != (solvedflags & F_IMPOSSIBLE)) + len = sprintf(buf, ";I%d,%d", x, y); + if (len) { + if (movelen + len >= movesize) { + movesize = movelen + len + 256; + move = sresize(move, movesize, char); + } + strcpy(move + movelen, buf); + movelen += len; + } + } + } + +done: + free_game(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(const game_state *state) +{ + int w = state->w, h = state->h, W = w+1, H = h+1; + int x, y, len, lights; + unsigned int flags; + char *ret, *p; + + len = (h+H) * (w+W+1) + 1; + ret = snewn(len, char); + p = ret; + + for (y = 0; y < H; y++) { + for (x = 0; x < W; x++) { + *p++ = '+'; + if (x < w) + *p++ = '-'; + } + *p++ = '\n'; + if (y < h) { + for (x = 0; x < W; x++) { + *p++ = '|'; + if (x < w) { + /* actual interesting bit. */ + flags = GRID(state, flags, x, y); + lights = GRID(state, lights, x, y); + if (flags & F_BLACK) { + if (flags & F_NUMBERED) + *p++ = '0' + lights; + else + *p++ = '#'; + } else { + if (flags & F_LIGHT) + *p++ = 'L'; + else if (flags & F_IMPOSSIBLE) + *p++ = 'x'; + else if (lights > 0) + *p++ = '.'; + else + *p++ = ' '; + } + } + } + *p++ = '\n'; + } + } + *p++ = '\0'; + + assert(p - ret == len); + return ret; +} + +struct game_ui { + int cur_x, cur_y, cur_visible; +}; + +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; + return ui; +} + +static void free_ui(game_ui *ui) +{ + sfree(ui); +} + +static char *encode_ui(const game_ui *ui) +{ + /* nothing to encode. */ + return NULL; +} + +static void decode_ui(game_ui *ui, const char *encoding) +{ + /* nothing to decode. */ +} + +static void game_changed_state(game_ui *ui, const game_state *oldstate, + const game_state *newstate) +{ + if (newstate->completed) + ui->cur_visible = 0; +} + +#define DF_BLACK 1 /* black square */ +#define DF_NUMBERED 2 /* black square with number */ +#define DF_LIT 4 /* display (white) square lit up */ +#define DF_LIGHT 8 /* display light in square */ +#define DF_OVERLAP 16 /* display light as overlapped */ +#define DF_CURSOR 32 /* display cursor */ +#define DF_NUMBERWRONG 64 /* display black numbered square as error. */ +#define DF_FLASH 128 /* background flash is on. */ +#define DF_IMPOSSIBLE 256 /* display non-light little square */ + +struct game_drawstate { + int tilesize, crad; + int w, h; + unsigned int *flags; /* width * height */ + int started; +}; + + +/* Believe it or not, this empty = "" hack is needed to get around a bug in + * the prc-tools gcc when optimisation is turned on; before, it produced: + lightup-sect.c: In function `interpret_move': + lightup-sect.c:1416: internal error--unrecognizable insn: + (insn 582 580 583 (set (reg:SI 134) + (pc)) -1 (nil) + (nil)) + */ +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; + unsigned int flags; + char buf[80], *nullret = NULL, *empty = "", c; + + if (button == LEFT_BUTTON || button == RIGHT_BUTTON) { + if (ui->cur_visible) + nullret = empty; + ui->cur_visible = 0; + cx = FROMCOORD(x); + cy = FROMCOORD(y); + action = (button == LEFT_BUTTON) ? FLIP_LIGHT : FLIP_IMPOSSIBLE; + } else if (IS_CURSOR_SELECT(button) || + button == 'i' || button == 'I' || + button == ' ' || button == '\r' || button == '\n') { + 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_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 + return NULL; + + switch (action) { + case FLIP_LIGHT: + case FLIP_IMPOSSIBLE: + if (cx < 0 || cy < 0 || cx >= state->w || cy >= state->h) + return nullret; + flags = GRID(state, flags, cx, cy); + 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; + + case NONE: + return nullret; + + default: + assert(!"Shouldn't get here!"); + } + return dupstr(buf); +} + +static game_state *execute_move(const game_state *state, const char *move) +{ + game_state *ret = dup_game(state); + int x, y, n, flags; + char c; + + if (!*move) goto badmove; + + while (*move) { + c = *move; + if (c == 'S') { + ret->used_solve = TRUE; + move++; + } else if (c == 'L' || c == 'I') { + move++; + if (sscanf(move, "%d,%d%n", &x, &y, &n) != 2 || + x < 0 || y < 0 || x >= ret->w || y >= ret->h) + goto badmove; + + flags = GRID(ret, flags, x, y); + if (flags & F_BLACK) goto badmove; + + /* LIGHT and IMPOSSIBLE are mutually exclusive. */ + if (c == 'L') { + GRID(ret, flags, x, y) &= ~F_IMPOSSIBLE; + set_light(ret, x, y, (flags & F_LIGHT) ? 0 : 1); + } else { + set_light(ret, x, y, 0); + GRID(ret, flags, x, y) ^= F_IMPOSSIBLE; + } + move += n; + } else goto badmove; + + if (*move == ';') + move++; + else if (*move) goto badmove; + } + if (grid_correct(ret)) ret->completed = 1; + return ret; + +badmove: + free_game(ret); + return NULL; +} + +/* ---------------------------------------------------------------------- + * Drawing routines. + */ + +/* XXX entirely cloned from fifteen.c; separate out? */ +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; + ads.tilesize = tilesize; + + *x = TILE_SIZE * params->w + 2 * BORDER; + *y = TILE_SIZE * params->h + 2 * BORDER; +} + +static void game_set_size(drawing *dr, game_drawstate *ds, + const game_params *params, int tilesize) +{ + ds->tilesize = tilesize; + ds->crad = 3*(tilesize-1)/8; +} + +static float *game_colours(frontend *fe, int *ncolours) +{ + float *ret = snewn(3 * NCOLOURS, float); + int i; + + frontend_default_colour(fe, &ret[COL_BACKGROUND * 3]); + + for (i = 0; i < 3; i++) { + ret[COL_BLACK * 3 + i] = 0.0F; + ret[COL_LIGHT * 3 + i] = 1.0F; + ret[COL_CURSOR * 3 + i] = ret[COL_BACKGROUND * 3 + i] / 2.0F; + ret[COL_GRID * 3 + i] = ret[COL_BACKGROUND * 3 + i] / 1.5F; + + } + + ret[COL_ERROR * 3 + 0] = 1.0F; + ret[COL_ERROR * 3 + 1] = 0.25F; + ret[COL_ERROR * 3 + 2] = 0.25F; + + ret[COL_LIT * 3 + 0] = 1.0F; + ret[COL_LIT * 3 + 1] = 1.0F; + ret[COL_LIT * 3 + 2] = 0.0F; + + *ncolours = NCOLOURS; + return ret; +} + +static game_drawstate *game_new_drawstate(drawing *dr, const game_state *state) +{ + struct game_drawstate *ds = snew(struct game_drawstate); + int i; + + ds->tilesize = ds->crad = 0; + ds->w = state->w; ds->h = state->h; + + ds->flags = snewn(ds->w*ds->h, unsigned int); + for (i = 0; i < ds->w*ds->h; i++) + ds->flags[i] = -1; + + ds->started = 0; + + return ds; +} + +static void game_free_drawstate(drawing *dr, game_drawstate *ds) +{ + sfree(ds->flags); + sfree(ds); +} + +/* At some stage we should put these into a real options struct. + * Note that tile_redraw has no #ifdeffery; it relies on tile_flags not + * to put those flags in. */ +#define HINT_LIGHTS +#define HINT_OVERLAPS +#define HINT_NUMBERS + +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); + unsigned int ret = 0; + + if (flashing) ret |= DF_FLASH; + if (ui && ui->cur_visible && x == ui->cur_x && y == ui->cur_y) + ret |= DF_CURSOR; + + if (flags & F_BLACK) { + ret |= DF_BLACK; + if (flags & F_NUMBERED) { +#ifdef HINT_NUMBERS + if (number_wrong(state, x, y)) + ret |= DF_NUMBERWRONG; +#endif + ret |= DF_NUMBERED; + } + } else { +#ifdef HINT_LIGHTS + if (lights > 0) ret |= DF_LIT; +#endif + if (flags & F_LIGHT) { + ret |= DF_LIGHT; +#ifdef HINT_OVERLAPS + if (lights > 1) ret |= DF_OVERLAP; +#endif + } + if (flags & F_IMPOSSIBLE) ret |= DF_IMPOSSIBLE; + } + return ret; +} + +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); + int lit = (ds_flags & DF_FLASH) ? COL_GRID : COL_LIT; + + if (ds_flags & DF_BLACK) { + 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[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 + * to redraw the tile. */ + 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, + ALIGN_VCENTRE | ALIGN_HCENTRE, ccol, str); + } + } else { + draw_rect(dr, dx, dy, TILE_SIZE, TILE_SIZE, + (ds_flags & DF_LIT) ? lit : COL_BACKGROUND); + draw_rect_outline(dr, dx, dy, TILE_SIZE, TILE_SIZE, COL_GRID); + if (ds_flags & DF_LIGHT) { + 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)) { + 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); + } + } + } + + if (ds_flags & DF_CURSOR) { + int coff = TILE_SIZE/8; + draw_rect_outline(dr, dx + coff, dy + coff, + TILE_SIZE - coff*2, TILE_SIZE - coff*2, COL_CURSOR); + } + + draw_update(dr, dx, dy, TILE_SIZE, TILE_SIZE); +} + +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; + + if (flashtime) flashing = (int)(flashtime * 3 / FLASH_TIME) != 1; + + if (!ds->started) { + draw_rect(dr, 0, 0, + TILE_SIZE * ds->w + 2 * BORDER, + TILE_SIZE * ds->h + 2 * BORDER, COL_BACKGROUND); + + draw_rect_outline(dr, COORD(0)-1, COORD(0)-1, + TILE_SIZE * ds->w + 2, + TILE_SIZE * ds->h + 2, + COL_GRID); + + draw_update(dr, 0, 0, + TILE_SIZE * ds->w + 2 * BORDER, + TILE_SIZE * ds->h + 2 * BORDER); + ds->started = 1; + } + + for (x = 0; x < ds->w; x++) { + for (y = 0; y < ds->h; y++) { + unsigned int ds_flags = tile_flags(ds, state, ui, x, y, flashing); + if (ds_flags != GRID(ds, flags, x, y)) { + GRID(ds, flags, x, y) = ds_flags; + tile_redraw(dr, ds, state, x, y); + } + } + } +} + +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(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 FLASH_TIME; + return 0.0F; +} + +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(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.0F; + *y = ph / 100.0F; +} + +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); + int paper = print_mono_colour(dr, 1); + int x, y; + + /* Ick: fake up `ds->tilesize' for macro expansion purposes */ + game_drawstate ads, *ds = &ads; + game_set_size(dr, ds, NULL, tilesize); + + /* + * Border. + */ + print_line_width(dr, TILE_SIZE / 16); + draw_rect_outline(dr, COORD(0), COORD(0), + TILE_SIZE * w, TILE_SIZE * h, ink); + + /* + * Grid. + */ + print_line_width(dr, TILE_SIZE / 24); + for (x = 1; x < w; x++) + draw_line(dr, COORD(x), COORD(0), COORD(x), COORD(h), ink); + for (y = 1; y < h; y++) + draw_line(dr, COORD(0), COORD(y), COORD(w), COORD(y), ink); + + /* + * Grid contents. + */ + for (y = 0; y < h; y++) + for (x = 0; x < w; x++) { + unsigned int ds_flags = tile_flags(ds, state, NULL, x, y, FALSE); + int dx = COORD(x), dy = COORD(y); + if (ds_flags & DF_BLACK) { + draw_rect(dr, dx, dy, TILE_SIZE, TILE_SIZE, ink); + if (ds_flags & DF_NUMBERED) { + 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, + ALIGN_VCENTRE | ALIGN_HCENTRE, paper, str); + } + } else if (ds_flags & DF_LIGHT) { + draw_circle(dr, dx + TILE_SIZE/2, dy + TILE_SIZE/2, + TILE_RADIUS, -1, ink); + } + } +} + +#ifdef COMBINED +#define thegame lightup +#endif + +const struct game thegame = { + "Light Up", "games.lightup", "lightup", + default_params, + game_fetch_preset, NULL, + decode_params, + encode_params, + free_params, + dup_params, + TRUE, game_configure, custom_params, + validate_params, + new_game_desc, + validate_desc, + new_game, + dup_game, + free_game, + TRUE, solve_game, + TRUE, game_can_format_as_text_now, game_text_format, + new_ui, + free_ui, + encode_ui, + decode_ui, + game_changed_state, + interpret_move, + execute_move, + PREFERRED_TILE_SIZE, game_compute_size, game_set_size, + game_colours, + game_new_drawstate, + game_free_drawstate, + game_redraw, + game_anim_length, + game_flash_length, + game_status, + TRUE, FALSE, game_print_size, game_print, + FALSE, /* wants_statusbar */ + FALSE, game_timing_state, + 0, /* flags */ +}; + +#ifdef STANDALONE_SOLVER + +int main(int argc, char **argv) +{ + game_params *p; + game_state *s; + char *id = NULL, *desc, *err, *result; + int nsol, diff, really_verbose = 0; + unsigned int sflags; + + while (--argc > 0) { + char *p = *++argv; + if (!strcmp(p, "-v")) { + really_verbose++; + } else if (*p == '-') { + fprintf(stderr, "%s: unrecognised option `%s'\n", argv[0], p); + return 1; + } else { + id = p; + } + } + + if (!id) { + fprintf(stderr, "usage: %s [-v] \n", argv[0]); + return 1; + } + + desc = strchr(id, ':'); + if (!desc) { + fprintf(stderr, "%s: game id expects a colon in it\n", argv[0]); + return 1; + } + *desc++ = '\0'; + + p = default_params(); + decode_params(p, id); + err = validate_desc(p, desc); + if (err) { + fprintf(stderr, "%s: %s\n", argv[0], err); + return 1; + } + s = new_game(NULL, p, desc); + + /* Run the solvers easiest to hardest until we find one that + * can solve our puzzle. If it's soluble we know that the + * hardest (recursive) solver will always find the solution. */ + nsol = sflags = 0; + for (diff = 0; diff <= DIFFCOUNT; diff++) { + printf("\nSolving with difficulty %d.\n", diff); + sflags = flags_from_difficulty(diff); + unplace_lights(s); + nsol = dosolve(s, sflags, NULL); + if (nsol == 1) break; + } + + printf("\n"); + if (nsol == 0) { + printf("Puzzle has no solution.\n"); + } else if (nsol < 0) { + printf("Unable to find a unique solution.\n"); + } else if (nsol > 1) { + printf("Puzzle has multiple solutions.\n"); + } else { + verbose = really_verbose; + unplace_lights(s); + printf("Puzzle has difficulty %d: solving...\n", diff); + dosolve(s, sflags, NULL); /* sflags from last successful solve */ + result = game_text_format(s); + printf("%s", result); + sfree(result); + } + + return 0; +} + +#endif + +/* vim: set shiftwidth=4 tabstop=8: */ -- cgit v1.2.3