X-Git-Url: https://git.distorted.org.uk/~mdw/sgt/puzzles/blobdiff_plain/26801d29c8305a5cb9bd3709909b1eeb896aa3e4..39c86385a35e8ae4c2eb5487464787d6fb15a782:/rect.c diff --git a/rect.c b/rect.c index 524d97b..0448958 100644 --- a/rect.c +++ b/rect.c @@ -45,6 +45,7 @@ enum { struct game_params { int w, h; float expandfactor; + int unique; }; #define INDEX(state, x, y) (((y) * (state)->w) + (x)) @@ -84,6 +85,7 @@ static game_params *default_params(void) ret->w = ret->h = 7; ret->expandfactor = 0.0F; + ret->unique = TRUE; return ret; } @@ -96,9 +98,14 @@ static int game_fetch_preset(int i, char **name, game_params **params) switch (i) { case 0: w = 7, h = 7; break; - case 1: w = 11, h = 11; break; - case 2: w = 15, h = 15; break; - case 3: w = 19, h = 19; break; + case 1: w = 9, h = 9; break; + case 2: w = 11, h = 11; break; + case 3: w = 13, h = 13; break; + case 4: w = 15, h = 15; break; +#ifndef SLOW_SYSTEM + case 5: w = 17, h = 17; break; + case 6: w = 19, h = 19; break; +#endif default: return FALSE; } @@ -108,6 +115,7 @@ static int game_fetch_preset(int i, char **name, game_params **params) ret->w = w; ret->h = h; ret->expandfactor = 0.0F; + ret->unique = TRUE; return TRUE; } @@ -135,6 +143,12 @@ static void decode_params(game_params *ret, char const *string) if (*string == 'e') { string++; ret->expandfactor = atof(string); + while (*string && + (*string == '.' || isdigit((unsigned char)*string))) string++; + } + if (*string == 'a') { + string++; + ret->unique = FALSE; } } @@ -145,6 +159,8 @@ static char *encode_params(game_params *params, int full) sprintf(data, "%dx%d", params->w, params->h); if (full && params->expandfactor) sprintf(data + strlen(data), "e%g", params->expandfactor); + if (full && !params->unique) + strcat(data, "a"); return dupstr(data); } @@ -174,10 +190,15 @@ static config_item *game_configure(game_params *params) ret[2].sval = dupstr(buf); ret[2].ival = 0; - ret[3].name = NULL; - ret[3].type = C_END; + ret[3].name = "Ensure unique solution"; + ret[3].type = C_BOOLEAN; ret[3].sval = NULL; - ret[3].ival = 0; + ret[3].ival = params->unique; + + ret[4].name = NULL; + ret[4].type = C_END; + ret[4].sval = NULL; + ret[4].ival = 0; return ret; } @@ -189,15 +210,16 @@ static game_params *custom_params(config_item *cfg) ret->w = atoi(cfg[0].sval); ret->h = atoi(cfg[1].sval); ret->expandfactor = atof(cfg[2].sval); + ret->unique = cfg[3].ival; return ret; } static char *validate_params(game_params *params) { - if (params->w <= 0 && params->h <= 0) + if (params->w <= 0 || params->h <= 0) return "Width and height must both be greater than zero"; - if (params->w < 2 && params->h < 2) + if (params->w*params->h < 2) return "Grid area must be greater than one"; if (params->expandfactor < 0.0F) return "Expansion factor may not be negative"; @@ -304,7 +326,7 @@ static void remove_number_placement(int w, int h, struct numberdata *number, } static int rect_solver(int w, int h, int nrects, struct numberdata *numbers, - random_state *rs) + game_state *result, random_state *rs) { struct rectlist *rectpositions; int *overlaps, *rectbyplace, *workspace; @@ -722,7 +744,7 @@ static int rect_solver(int w, int h, int nrects, struct numberdata *numbers, * rectangle) which overlaps a candidate placement of the * number for some other rectangle. */ - { + if (rs) { struct rpn { int rect; int placement; @@ -827,8 +849,28 @@ static int rect_solver(int w, int h, int nrects, struct numberdata *numbers, i, rectpositions[i].n); #endif assert(rectpositions[i].n > 0); - if (rectpositions[i].n > 1) + if (rectpositions[i].n > 1) { ret = FALSE; + } else if (result) { + /* + * Place the rectangle in its only possible position. + */ + int x, y; + struct rect *r = &rectpositions[i].rects[0]; + + for (y = 0; y < r->h; y++) { + if (r->x > 0) + vedge(result, r->x, r->y+y) = 1; + if (r->x+r->w < result->w) + vedge(result, r->x+r->w, r->y+y) = 1; + } + for (x = 0; x < r->w; x++) { + if (r->y > 0) + hedge(result, r->x+x, r->y) = 1; + if (r->y+r->h < result->h) + hedge(result, r->x+x, r->y+r->h) = 1; + } + } } /* @@ -1017,7 +1059,7 @@ struct game_aux_info { }; static char *new_game_desc(game_params *params, random_state *rs, - game_aux_info **aux) + game_aux_info **aux, int interactive) { int *grid, *numbers = NULL; struct rectlist *list; @@ -1505,7 +1547,11 @@ static char *new_game_desc(game_params *params, random_state *rs, } } - ret = rect_solver(params->w, params->h, nnumbers, nd, rs); + if (params->unique) + ret = rect_solver(params->w, params->h, nnumbers, nd, + NULL, rs); + else + ret = TRUE; /* allow any number placement at all */ if (ret) { /* @@ -1650,7 +1696,7 @@ static char *validate_desc(game_params *params, char *desc) return NULL; } -static game_state *new_game(game_params *params, char *desc) +static game_state *new_game(midend_data *me, game_params *params, char *desc) { game_state *state = snew(game_state); int x, y, i, area; @@ -1728,8 +1774,45 @@ static game_state *solve_game(game_state *state, game_aux_info *ai, game_state *ret; if (!ai) { - *error = "Solution not known for this puzzle"; - return NULL; + int i, j, n; + struct numberdata *nd; + + /* + * Attempt the in-built solver. + */ + + /* Set up each number's (very short) candidate position list. */ + for (i = n = 0; i < state->h * state->w; i++) + if (state->grid[i]) + n++; + + nd = snewn(n, struct numberdata); + + for (i = j = 0; i < state->h * state->w; i++) + if (state->grid[i]) { + nd[j].area = state->grid[i]; + nd[j].npoints = 1; + nd[j].points = snewn(1, struct point); + nd[j].points[0].x = i % state->w; + nd[j].points[0].y = i / state->w; + j++; + } + + assert(j == n); + + ret = dup_game(state); + ret->cheated = TRUE; + + rect_solver(state->w, state->h, n, nd, ret, NULL); + + /* + * Clean up. + */ + for (i = 0; i < n; i++) + sfree(nd[i].points); + sfree(nd); + + return ret; } assert(state->w == ai->w); @@ -2100,13 +2183,14 @@ static void ui_draw_rect(game_state *state, game_ui *ui, } } -static game_state *make_move(game_state *from, game_ui *ui, - int x, int y, int button) -{ +static game_state *make_move(game_state *from, game_ui *ui, game_drawstate *ds, + int x, int y, int button) { int xc, yc; int startdrag = FALSE, enddrag = FALSE, active = FALSE; game_state *ret; + button &= ~MOD_MASK; + if (button == LEFT_BUTTON) { startdrag = TRUE; } else if (button == LEFT_RELEASE) { @@ -2198,16 +2282,15 @@ static game_state *make_move(game_state *from, game_ui *ui, * Drawing routines. */ -#define CORRECT 65536 +#define CORRECT (1L<<16) #define COLOUR(k) ( (k)==1 ? COL_LINE : COL_DRAG ) -#define MAX(x,y) ( (x)>(y) ? (x) : (y) ) -#define MAX4(x,y,z,w) ( MAX(MAX(x,y),MAX(z,w)) ) +#define MAX4(x,y,z,w) ( max(max(x,y),max(z,w)) ) struct game_drawstate { int started; int w, h; - unsigned int *visible; + unsigned long *visible; }; static void game_size(game_params *params, int *x, int *y) @@ -2254,7 +2337,7 @@ static game_drawstate *game_new_drawstate(game_state *state) ds->started = FALSE; ds->w = state->w; ds->h = state->h; - ds->visible = snewn(ds->w * ds->h, unsigned int); + ds->visible = snewn(ds->w * ds->h, unsigned long); for (i = 0; i < ds->w * ds->h; i++) ds->visible[i] = 0xFFFF; @@ -2380,7 +2463,7 @@ static void game_redraw(frontend *fe, game_drawstate *ds, game_state *oldstate, for (x = 0; x < state->w; x++) for (y = 0; y < state->h; y++) { - unsigned int c = 0; + unsigned long c = 0; if (HRANGE(state,x,y)) c |= index(state,hedge,x,y); @@ -2396,12 +2479,14 @@ static void game_redraw(frontend *fe, game_drawstate *ds, game_state *oldstate, if (y+1 < state->h) c |= index(state,corners,x,y+1) << 12; if (x+1 < state->w && y+1 < state->h) - c |= index(state,corners,x+1,y+1) << 14; + /* cast to prevent 2<<14 sign-extending on promotion to long */ + c |= (unsigned long)index(state,corners,x+1,y+1) << 14; if (index(state, correct, x, y) && !flashtime) c |= CORRECT; if (index(ds,ds->visible,x,y) != c) { - draw_tile(fe, state, x, y, hedge, vedge, corners, c & CORRECT); + draw_tile(fe, state, x, y, hedge, vedge, corners, + (c & CORRECT) ? 1 : 0); index(ds,ds->visible,x,y) = c; } } @@ -2416,13 +2501,13 @@ static void game_redraw(frontend *fe, game_drawstate *ds, game_state *oldstate, } static float game_anim_length(game_state *oldstate, - game_state *newstate, int dir) + 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_state *newstate, int dir, game_ui *ui) { if (!oldstate->completed && newstate->completed && !oldstate->cheated && !newstate->cheated) @@ -2435,6 +2520,11 @@ static int game_wants_statusbar(void) return FALSE; } +static int game_timing_state(game_state *state) +{ + return TRUE; +} + #ifdef COMBINED #define thegame rect #endif @@ -2468,4 +2558,6 @@ const struct game thegame = { game_anim_length, game_flash_length, game_wants_statusbar, + FALSE, game_timing_state, + 0, /* mouse_priorities */ };