From 2ac6d24e968232e9040ee0bca5e605b3a75e9c39 Mon Sep 17 00:00:00 2001 From: simon Date: Mon, 2 May 2005 13:17:10 +0000 Subject: [PATCH] Added an automatic `Solve' feature to most games. This is useful for various things: - if you haven't fully understood what a game is about, it gives you an immediate example of a puzzle plus its solution so you can understand it - in some games it's useful to compare your solution with the real one and see where you made a mistake - in the rearrangement games (Fifteen, Sixteen, Twiddle) it's handy to be able to get your hands on a pristine grid quickly so you can practise or experiment with manoeuvres on it - it provides a good way of debugging the games if you think you've encountered an unsolvable grid! git-svn-id: svn://svn.tartarus.org/sgt/puzzles@5731 cda61777-01e9-0310-a592-d414129be87e --- cube.c | 7 +++++ fifteen.c | 50 +++++++++++++++++++++++++++++---- gtk.c | 19 +++++++++++++ midend.c | 32 ++++++++++++++++++++++ net.c | 84 +++++++++++++++++++++++++++++++++++++++++++++++++++++--- netslide.c | 91 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++---- nullgame.c | 9 +++++- osx.m | 20 ++++++++++++++ pattern.c | 78 ++++++++++++++++++++++++++++++++++++++++++++++------ puzzles.but | 23 ++++++++++++++++ puzzles.h | 3 ++ rect.c | 67 +++++++++++++++++++++++++++++++++++++++++---- sixteen.c | 49 +++++++++++++++++++++++++++++---- solo.c | 41 +++++++++++++++++++++++++--- twiddle.c | 59 +++++++++++++++++++++++++++++++++++---- windows.c | 23 ++++++++++++---- 16 files changed, 604 insertions(+), 51 deletions(-) diff --git a/cube.c b/cube.c index 33ef6d3..5166762 100644 --- a/cube.c +++ b/cube.c @@ -985,6 +985,12 @@ static void free_game(game_state *state) sfree(state); } +static game_state *solve_game(game_state *state, game_aux_info *aux, + char **error) +{ + return NULL; +} + static char *game_text_format(game_state *state) { return NULL; @@ -1557,6 +1563,7 @@ const struct game thegame = { new_game, dup_game, free_game, + FALSE, solve_game, NULL, game_text_format, new_ui, free_ui, diff --git a/fifteen.c b/fifteen.c index e31843d..c29e9fe 100644 --- a/fifteen.c +++ b/fifteen.c @@ -41,6 +41,8 @@ struct game_state { int *tiles; int gap_pos; int completed; + int just_used_solve; /* used to suppress undo animation */ + int used_solve; /* used to suppress completion flash */ int movecount; }; @@ -268,7 +270,7 @@ static char *new_game_seed(game_params *params, random_state *rs, return ret; } -void game_free_aux_info(game_aux_info *aux) +static void game_free_aux_info(game_aux_info *aux) { assert(!"Shouldn't happen"); } @@ -351,6 +353,7 @@ static game_state *new_game(game_params *params, char *seed) assert(state->tiles[state->gap_pos] == 0); state->completed = state->movecount = 0; + state->used_solve = state->just_used_solve = FALSE; return state; } @@ -367,6 +370,8 @@ static game_state *dup_game(game_state *state) ret->gap_pos = state->gap_pos; ret->completed = state->completed; ret->movecount = state->movecount; + ret->used_solve = state->used_solve; + ret->just_used_solve = state->just_used_solve; return ret; } @@ -376,6 +381,28 @@ static void free_game(game_state *state) sfree(state); } +static game_state *solve_game(game_state *state, game_aux_info *aux, + char **error) +{ + game_state *ret = dup_game(state); + int i; + + /* + * Simply replace the grid with a solved one. For this game, + * this isn't a useful operation for actually telling the user + * what they should have done, but it is useful for + * conveniently being able to get hold of a clean state from + * which to practise manoeuvres. + */ + for (i = 0; i < ret->n; i++) + ret->tiles[i] = (i+1) % ret->n; + ret->gap_pos = ret->n-1; + ret->used_solve = ret->just_used_solve = TRUE; + ret->completed = ret->movecount; + + return ret; +} + static char *game_text_format(game_state *state) { char *ret, *p, buf[80]; @@ -467,6 +494,7 @@ static game_state *make_move(game_state *from, game_ui *ui, up = C(from, ux, uy); ret = dup_game(from); + ret->just_used_solve = FALSE; /* zero this in a hurry */ ret->gap_pos = C(from, dx, dy); assert(ret->gap_pos >= 0 && ret->gap_pos < ret->n); @@ -739,9 +767,13 @@ static void game_redraw(frontend *fe, game_drawstate *ds, game_state *oldstate, if (oldstate) state = oldstate; - sprintf(statusbuf, "%sMoves: %d", - (state->completed ? "COMPLETED! " : ""), - (state->completed ? state->completed : state->movecount)); + if (state->used_solve) + sprintf(statusbuf, "Moves since auto-solve: %d", + state->movecount - state->completed); + else + sprintf(statusbuf, "%sMoves: %d", + (state->completed ? "COMPLETED! " : ""), + (state->completed ? state->completed : state->movecount)); status_bar(fe, statusbuf); } @@ -750,13 +782,18 @@ 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) { - return ANIM_TIME; + if ((dir > 0 && newstate->just_used_solve) || + (dir < 0 && oldstate->just_used_solve)) + return 0.0F; + else + return ANIM_TIME; } static float game_flash_length(game_state *oldstate, game_state *newstate, int dir) { - if (!oldstate->completed && newstate->completed) + if (!oldstate->completed && newstate->completed && + !oldstate->used_solve && !newstate->used_solve) return 2 * FLASH_FRAME; else return 0.0F; @@ -787,6 +824,7 @@ const struct game thegame = { new_game, dup_game, free_game, + TRUE, solve_game, TRUE, game_text_format, new_ui, free_ui, diff --git a/gtk.c b/gtk.c index 66ee767..d721320 100644 --- a/gtk.c +++ b/gtk.c @@ -913,6 +913,17 @@ static void menu_copy_event(GtkMenuItem *menuitem, gpointer data) } } +static void menu_solve_event(GtkMenuItem *menuitem, gpointer data) +{ + frontend *fe = (frontend *)data; + char *msg; + + msg = midend_solve(fe->me); + + if (msg) + error_box(fe->window, msg); +} + static void menu_config_event(GtkMenuItem *menuitem, gpointer data) { frontend *fe = (frontend *)data; @@ -1050,6 +1061,14 @@ static frontend *new_window(char *game_id, char **error) GTK_SIGNAL_FUNC(menu_copy_event), fe); gtk_widget_show(menuitem); } + if (thegame.can_solve) { + add_menu_separator(GTK_CONTAINER(menu)); + menuitem = gtk_menu_item_new_with_label("Solve"); + gtk_container_add(GTK_CONTAINER(menu), menuitem); + gtk_signal_connect(GTK_OBJECT(menuitem), "activate", + GTK_SIGNAL_FUNC(menu_solve_event), fe); + gtk_widget_show(menuitem); + } add_menu_separator(GTK_CONTAINER(menu)); add_menu_item_with_key(fe, GTK_CONTAINER(menu), "Exit", 'q'); diff --git a/midend.c b/midend.c index dbbaad4..084cd16 100644 --- a/midend.c +++ b/midend.c @@ -595,3 +595,35 @@ char *midend_text_format(midend_data *me) else return NULL; } + +char *midend_solve(midend_data *me) +{ + game_state *s; + char *msg; + + if (!me->ourgame->can_solve) + return "This game does not support the Solve operation"; + + if (me->statepos < 1) + return "No game set up to solve"; /* _shouldn't_ happen! */ + + msg = "Solve operation failed"; /* game _should_ overwrite on error */ + s = me->ourgame->solve(me->states[0], me->aux_info, &msg); + if (!s) + return msg; + + /* + * Now enter the solved state as the next move.~|~ + */ + midend_stop_anim(me); + while (me->nstates > me->statepos) + me->ourgame->free_game(me->states[--me->nstates]); + ensure(me); + me->states[me->nstates] = s; + me->statepos = ++me->nstates; + me->anim_time = 0.0; + midend_finish_move(me); + midend_redraw(me); + activate_timer(me->frontend); + return NULL; +} diff --git a/net.c b/net.c index 3d4daa7..c8cafc1 100644 --- a/net.c +++ b/net.c @@ -75,10 +75,18 @@ struct game_params { float barrier_probability; }; +struct solved_game_state { + int width, height; + int refcount; + unsigned char *tiles; +}; + struct game_state { int width, height, cx, cy, wrapping, completed, last_rotate_dir; + int used_solve, just_used_solve; unsigned char *tiles; unsigned char *barriers; + struct solved_game_state *solution; }; #define OFFSET(x2,y2,x1,y1,dir,state) \ @@ -309,7 +317,7 @@ static char *new_game_seed(game_params *params, random_state *rs, return dupstr(buf); } -void game_free_aux_info(game_aux_info *aux) +static void game_free_aux_info(game_aux_info *aux) { assert(!"Shouldn't happen"); } @@ -347,7 +355,7 @@ static game_state *new_game(game_params *params, char *seed) state->cy = state->height / 2; state->wrapping = params->wrapping; state->last_rotate_dir = 0; - state->completed = FALSE; + state->completed = state->used_solve = state->just_used_solve = FALSE; state->tiles = snewn(state->width * state->height, unsigned char); memset(state->tiles, 0, state->width * state->height); state->barriers = snewn(state->width * state->height, unsigned char); @@ -559,6 +567,25 @@ static game_state *new_game(game_params *params, char *seed) } /* + * Save the unshuffled grid. We do this using a separate + * reference-counted structure since it's a large chunk of + * memory which we don't want to have to replicate in every + * game state while playing. + */ + { + struct solved_game_state *solution; + + solution = snew(struct solved_game_state); + solution->width = state->width; + solution->height = state->height; + solution->refcount = 1; + solution->tiles = snewn(state->width * state->height, unsigned char); + memcpy(solution->tiles, state->tiles, state->width * state->height); + + state->solution = solution; + } + + /* * Now shuffle the grid. */ for (y = 0; y < state->height; y++) { @@ -689,22 +716,58 @@ static game_state *dup_game(game_state *state) ret->cy = state->cy; ret->wrapping = state->wrapping; ret->completed = state->completed; + ret->used_solve = state->used_solve; + ret->just_used_solve = state->just_used_solve; ret->last_rotate_dir = state->last_rotate_dir; ret->tiles = snewn(state->width * state->height, unsigned char); memcpy(ret->tiles, state->tiles, state->width * state->height); ret->barriers = snewn(state->width * state->height, unsigned char); memcpy(ret->barriers, state->barriers, state->width * state->height); + ret->solution = state->solution; + if (ret->solution) + ret->solution->refcount++; return ret; } static void free_game(game_state *state) { + if (state->solution && --state->solution->refcount <= 0) { + sfree(state->solution->tiles); + sfree(state->solution); + } sfree(state->tiles); sfree(state->barriers); sfree(state); } +static game_state *solve_game(game_state *state, game_aux_info *aux, + char **error) +{ + game_state *ret; + + if (!state->solution) { + /* + * 2005-05-02: This shouldn't happen, at the time of + * writing, because Net is incapable of receiving a puzzle + * description from outside. If in future it becomes so, + * then we will have puzzles for which we don't know the + * solution. + */ + *error = "Solution not known for this puzzle"; + return NULL; + } + + assert(state->solution->width == state->width); + assert(state->solution->height == state->height); + ret = dup_game(state); + memcpy(ret->tiles, state->solution->tiles, ret->width * ret->height); + ret->used_solve = ret->just_used_solve = TRUE; + ret->completed = TRUE; + + return ret; +} + static char *game_text_format(game_state *state) { return NULL; @@ -877,6 +940,7 @@ static game_state *make_move(game_state *state, game_ui *ui, if (button == MIDDLE_BUTTON) { ret = dup_game(state); + ret->just_used_solve = FALSE; tile(ret, tx, ty) ^= LOCKED; ret->last_rotate_dir = 0; return ret; @@ -895,6 +959,7 @@ static game_state *make_move(game_state *state, game_ui *ui, * turns anticlockwise; right button turns clockwise. */ ret = dup_game(state); + ret->just_used_solve = FALSE; orig = tile(ret, tx, ty); if (button == LEFT_BUTTON) { tile(ret, tx, ty) = A(orig); @@ -911,6 +976,7 @@ static game_state *make_move(game_state *state, game_ui *ui, */ int jx, jy; ret = dup_game(state); + ret->just_used_solve = FALSE; for (jy = 0; jy < ret->height; jy++) { for (jx = 0; jx < ret->width; jx++) { if (!(tile(ret, jx, jy) & LOCKED)) { @@ -1436,7 +1502,8 @@ static void game_redraw(frontend *fe, game_drawstate *ds, game_state *oldstate, a++; sprintf(statusbuf, "%sActive: %d/%d", - (state->completed ? "COMPLETED! " : ""), a, n); + (state->used_solve ? "Auto-solved. " : + state->completed ? "COMPLETED! " : ""), a, n); status_bar(fe, statusbuf); } @@ -1450,6 +1517,13 @@ static float game_anim_length(game_state *oldstate, int x, y, last_rotate_dir; /* + * Don't animate an auto-solve move. + */ + if ((dir > 0 && newstate->just_used_solve) || + (dir < 0 && oldstate->just_used_solve)) + return 0.0F; + + /* * Don't animate if last_rotate_dir is zero. */ last_rotate_dir = dir==-1 ? oldstate->last_rotate_dir : @@ -1478,7 +1552,8 @@ static float game_flash_length(game_state *oldstate, * If the game has just been completed, we display a completion * flash. */ - if (!oldstate->completed && newstate->completed) { + if (!oldstate->completed && newstate->completed && + !oldstate->used_solve && !newstate->used_solve) { int size; size = 0; if (size < newstate->cx+1) @@ -1520,6 +1595,7 @@ const struct game thegame = { new_game, dup_game, free_game, + TRUE, solve_game, FALSE, game_text_format, new_ui, free_ui, diff --git a/netslide.c b/netslide.c index a7c3292..f367621 100644 --- a/netslide.c +++ b/netslide.c @@ -82,8 +82,15 @@ struct game_params { float barrier_probability; }; +struct solved_game_state { + int width, height; + int refcount; + unsigned char *tiles; +}; + struct game_state { int width, height, cx, cy, wrapping, completed; + int used_solve, just_used_solve; int move_count; /* position (row or col number, starting at 0) of last move. */ @@ -94,6 +101,7 @@ struct game_state { unsigned char *tiles; unsigned char *barriers; + struct solved_game_state *solution; }; #define OFFSET(x2,y2,x1,y1,dir,state) \ @@ -327,7 +335,7 @@ static char *new_game_seed(game_params *params, random_state *rs, return dupstr(buf); } -void game_free_aux_info(game_aux_info *aux) +static void game_free_aux_info(game_aux_info *aux) { assert(!"Shouldn't happen"); } @@ -365,6 +373,7 @@ static game_state *new_game(game_params *params, char *seed) state->cy = state->height / 2; state->wrapping = params->wrapping; state->completed = 0; + state->used_solve = state->just_used_solve = FALSE; state->move_count = 0; state->last_move_row = -1; state->last_move_col = -1; @@ -580,6 +589,25 @@ static game_state *new_game(game_params *params, char *seed) } /* + * Save the unshuffled grid. We do this using a separate + * reference-counted structure since it's a large chunk of + * memory which we don't want to have to replicate in every + * game state while playing. + */ + { + struct solved_game_state *solution; + + solution = snew(struct solved_game_state); + solution->width = state->width; + solution->height = state->height; + solution->refcount = 1; + solution->tiles = snewn(state->width * state->height, unsigned char); + memcpy(solution->tiles, state->tiles, state->width * state->height); + + state->solution = solution; + } + + /* * Now shuffle the grid. * FIXME - this simply does a set of random moves to shuffle the pieces. * A better way would be to number all the pieces, generate a placement @@ -727,6 +755,8 @@ static game_state *dup_game(game_state *state) ret->cy = state->cy; ret->wrapping = state->wrapping; ret->completed = state->completed; + ret->used_solve = state->used_solve; + ret->just_used_solve = state->just_used_solve; ret->move_count = state->move_count; ret->last_move_row = state->last_move_row; ret->last_move_col = state->last_move_col; @@ -735,17 +765,51 @@ static game_state *dup_game(game_state *state) memcpy(ret->tiles, state->tiles, state->width * state->height); ret->barriers = snewn(state->width * state->height, unsigned char); memcpy(ret->barriers, state->barriers, state->width * state->height); + ret->solution = state->solution; + if (ret->solution) + ret->solution->refcount++; return ret; } static void free_game(game_state *state) { + if (state->solution && --state->solution->refcount <= 0) { + sfree(state->solution->tiles); + sfree(state->solution); + } sfree(state->tiles); sfree(state->barriers); sfree(state); } +static game_state *solve_game(game_state *state, game_aux_info *aux, + char **error) +{ + game_state *ret; + + if (!state->solution) { + /* + * 2005-05-02: This shouldn't happen, at the time of + * writing, because Net is incapable of receiving a puzzle + * description from outside. If in future it becomes so, + * then we will have puzzles for which we don't know the + * solution. + */ + *error = "Solution not known for this puzzle"; + return NULL; + } + + assert(state->solution->width == state->width); + assert(state->solution->height == state->height); + ret = dup_game(state); + memcpy(ret->tiles, state->solution->tiles, ret->width * ret->height); + ret->used_solve = ret->just_used_solve = TRUE; + ret->completed = ret->move_count; + + return ret; +} + static char *game_text_format(game_state *state) { return NULL; @@ -909,6 +973,7 @@ static game_state *make_move(game_state *state, game_ui *ui, } ret = dup_game(state); + ret->just_used_solve = FALSE; if (dx == 0) slide_col(ret, dy, cx); else slide_row(ret, dx, cy); @@ -1478,10 +1543,15 @@ static void game_redraw(frontend *fe, game_drawstate *ds, game_state *oldstate, if (active[i]) a++; - sprintf(statusbuf, "%sMoves: %d Active: %d/%d", - (state->completed ? "COMPLETED! " : ""), - (state->completed ? state->completed : state->move_count), - a, n); + if (state->used_solve) + sprintf(statusbuf, "Moves since auto-solve: %d", + state->move_count - state->completed); + else + sprintf(statusbuf, "%sMoves: %d", + (state->completed ? "COMPLETED! " : ""), + (state->completed ? state->completed : state->move_count)); + + sprintf(statusbuf + strlen(statusbuf), " Active: %d/%d", a, n); status_bar(fe, statusbuf); } @@ -1492,6 +1562,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) { + /* + * Don't animate an auto-solve move. + */ + if ((dir > 0 && newstate->just_used_solve) || + (dir < 0 && oldstate->just_used_solve)) + return 0.0F; + return ANIM_TIME; } @@ -1502,7 +1579,8 @@ static float game_flash_length(game_state *oldstate, * If the game has just been completed, we display a completion * flash. */ - if (!oldstate->completed && newstate->completed) { + if (!oldstate->completed && newstate->completed && + !oldstate->used_solve && !newstate->used_solve) { int size; size = 0; if (size < newstate->cx+1) @@ -1544,6 +1622,7 @@ const struct game thegame = { new_game, dup_game, free_game, + TRUE, solve_game, FALSE, game_text_format, new_ui, free_ui, diff --git a/nullgame.c b/nullgame.c index 296e76e..6eb427c 100644 --- a/nullgame.c +++ b/nullgame.c @@ -94,7 +94,7 @@ static char *new_game_seed(game_params *params, random_state *rs, return dupstr("FIXME"); } -void game_free_aux_info(game_aux_info *aux) +static void game_free_aux_info(game_aux_info *aux) { assert(!"Shouldn't happen"); } @@ -127,6 +127,12 @@ static void free_game(game_state *state) sfree(state); } +static game_state *solve_game(game_state *state, game_aux_info *aux, + char **error) +{ + return NULL; +} + static char *game_text_format(game_state *state) { return NULL; @@ -234,6 +240,7 @@ const struct game thegame = { new_game, dup_game, free_game, + FALSE, solve_game, FALSE, game_text_format, new_ui, free_ui, diff --git a/osx.m b/osx.m index f769043..a27c840 100644 --- a/osx.m +++ b/osx.m @@ -581,10 +581,28 @@ struct frontend { NSBeep(); } +- (void)solveGame:(id)sender +{ + char *msg; + NSAlert *alert; + + msg = midend_solve(me); + + if (msg) { + alert = [[[NSAlert alloc] init] autorelease]; + [alert addButtonWithTitle:@"Bah"]; + [alert setInformativeText:[NSString stringWithCString:msg]]; + [alert beginSheetModalForWindow:self modalDelegate:nil + didEndSelector:nil contextInfo:nil]; + } +} + - (BOOL)validateMenuItem:(NSMenuItem *)item { if ([item action] == @selector(copy:)) return (ourgame->can_format_as_text ? YES : NO); + else if ([item action] == @selector(solveGame:)) + return (ourgame->can_solve ? YES : NO); else return [super validateMenuItem:item]; } @@ -1239,6 +1257,8 @@ int main(int argc, char **argv) item = newitem(menu, "Cut", "x", NULL, @selector(cut:)); item = newitem(menu, "Copy", "c", NULL, @selector(copy:)); item = newitem(menu, "Paste", "v", NULL, @selector(paste:)); + [menu addItem:[NSMenuItem separatorItem]]; + item = newitem(menu, "Solve", "S-s", NULL, @selector(solveGame:)); menu = newsubmenu([NSApp mainMenu], "Type"); typemenu = menu; diff --git a/pattern.c b/pattern.c index 55f840f..0f0a9c6 100644 --- a/pattern.c +++ b/pattern.c @@ -1,9 +1,5 @@ /* * pattern.c: the pattern-reconstruction game known as `nonograms'. - * - * TODO before checkin: - * - * - make some sort of stab at number-of-numbers judgment */ #include @@ -52,7 +48,7 @@ struct game_state { unsigned char *grid; int rowsize; int *rowdata, *rowlen; - int completed; + int completed, cheated; }; #define FLASH_TIME 0.13F @@ -541,7 +537,7 @@ static char *new_game_seed(game_params *params, random_state *rs, return seed; } -void game_free_aux_info(game_aux_info *aux) +static void game_free_aux_info(game_aux_info *aux) { assert(!"Shouldn't happen"); } @@ -604,7 +600,7 @@ static game_state *new_game(game_params *params, char *seed) state->rowdata = snewn(state->rowsize * (state->w + state->h), int); state->rowlen = snewn(state->w + state->h, int); - state->completed = FALSE; + state->completed = state->cheated = FALSE; for (i = 0; i < params->w + params->h; i++) { state->rowlen[i] = 0; @@ -642,6 +638,7 @@ static game_state *dup_game(game_state *state) (ret->w + ret->h) * sizeof(int)); ret->completed = state->completed; + ret->cheated = state->cheated; return ret; } @@ -654,6 +651,69 @@ static void free_game(game_state *state) sfree(state); } +static game_state *solve_game(game_state *state, game_aux_info *aux, + char **error) +{ + game_state *ret; + + /* + * I could have stored the grid I invented in the game_aux_info + * and extracted it here where available, but it seems easier + * just to run my internal solver in all cases. + */ + + ret = dup_game(state); + ret->completed = ret->cheated = TRUE; + + { + int w = state->w, h = state->h, i, j, done_any, max; + unsigned char *matrix, *workspace; + int *rowdata; + + matrix = snewn(w*h, unsigned char); + max = max(w, h); + workspace = snewn(max*3, unsigned char); + rowdata = snewn(max+1, int); + + memset(matrix, 0, w*h); + + do { + done_any = 0; + for (i=0; irowdata + state->rowsize*(w+i), + max*sizeof(int)); + rowdata[state->rowlen[w+i]] = 0; + done_any |= do_row(workspace, workspace+max, workspace+2*max, + matrix+i*w, w, 1, rowdata); + } + for (i=0; irowdata + state->rowsize*i, max*sizeof(int)); + rowdata[state->rowlen[i]] = 0; + done_any |= do_row(workspace, workspace+max, workspace+2*max, + matrix+i, h, w, rowdata); + } + } while (done_any); + + for (i = 0; i < h; i++) { + for (j = 0; j < w; j++) { + int c = (matrix[i*w+j] == BLOCK ? GRID_FULL : + matrix[i*w+j] == DOT ? GRID_EMPTY : GRID_UNKNOWN); + ret->grid[i*w+j] = c; + if (c == GRID_UNKNOWN) + ret->completed = FALSE; + } + } + + if (!ret->completed) { + free_game(ret); + *error = "Solving algorithm cannot complete this puzzle"; + return NULL; + } + } + + return ret; +} + static char *game_text_format(game_state *state) { return NULL; @@ -1011,7 +1071,8 @@ static float game_anim_length(game_state *oldstate, static float game_flash_length(game_state *oldstate, game_state *newstate, int dir) { - if (!oldstate->completed && newstate->completed) + if (!oldstate->completed && newstate->completed && + !oldstate->cheated && !newstate->cheated) return FLASH_TIME; return 0.0F; } @@ -1041,6 +1102,7 @@ const struct game thegame = { new_game, dup_game, free_game, + TRUE, solve_game, FALSE, game_text_format, new_ui, free_ui, diff --git a/puzzles.but b/puzzles.but index 9b88d18..6d7d11f 100644 --- a/puzzles.but +++ b/puzzles.but @@ -110,6 +110,29 @@ format, so that you can paste it into (say) an e-mail client or a web message board if you're discussing the game with someone else. (Not all games support this feature.) +\dt \ii\e{Solve} + +\dd Transforms the puzzle instantly into its solved state. For some +games (Cube) this feature is not supported at all because it is of +no particular use. For other games (such as Pattern), the solved +state can be used to give you information, if you can't see how a +solution can exist at all or you want to know where you made a +mistake. For still other games (such as Sixteen), automatic solution +tells you nothing about how to \e{get} to the solution, but it does +provide a useful way to get there quickly so that you can experiment +with set-piece moves and transformations. + +\lcont{ + +Some games (such as Solo) are capable of solving a game ID you have +typed in from elsewhere. Other games (such as Rectangles) cannot +solve a game ID they didn't invent themself, but when they did +invent the game ID they know what the solution is already. Still +other games (Pattern) can solve \e{some} external game IDs, but only +if they aren't too difficult. + +} + \dt \I{exit}\ii\e{Quit} (\q{Q}, Ctrl+\q{Q}) \dd Closes the application entirely. diff --git a/puzzles.h b/puzzles.h index 1a4f10f..a9323f5 100644 --- a/puzzles.h +++ b/puzzles.h @@ -142,6 +142,7 @@ config_item *midend_get_config(midend_data *me, int which, char **wintitle); char *midend_set_config(midend_data *me, int which, config_item *cfg); char *midend_game_id(midend_data *me, char *id, int def_seed); char *midend_text_format(midend_data *me); +char *midend_solve(midend_data *me); /* * malloc.c @@ -197,6 +198,8 @@ struct game { game_state *(*new_game)(game_params *params, char *seed); game_state *(*dup_game)(game_state *state); void (*free_game)(game_state *state); + int can_solve; + game_state *(*solve)(game_state *state, game_aux_info *aux, char **error); int can_format_as_text; char *(*text_format)(game_state *state); game_ui *(*new_ui)(game_state *state); diff --git a/rect.c b/rect.c index c0606dd..abfd332 100644 --- a/rect.c +++ b/rect.c @@ -82,7 +82,7 @@ struct game_state { int *grid; /* contains the numbers */ unsigned char *vedge; /* (w+1) x h */ unsigned char *hedge; /* w x (h+1) */ - int completed; + int completed, cheated; }; static game_params *default_params(void) @@ -386,6 +386,12 @@ static void display_grid(game_params *params, int *grid, int *numbers, int all) } #endif +struct game_aux_info { + int w, h; + unsigned char *vedge; /* (w+1) x h */ + unsigned char *hedge; /* w x (h+1) */ +}; + static char *new_game_seed(game_params *params, random_state *rs, game_aux_info **aux) { @@ -829,6 +835,31 @@ static char *new_game_seed(game_params *params, random_state *rs, } /* + * Store the rectangle data in the game_aux_info. + */ + { + game_aux_info *ai = snew(game_aux_info); + + ai->w = params->w; + ai->h = params->h; + ai->vedge = snewn(ai->w * ai->h, unsigned char); + ai->hedge = snewn(ai->w * ai->h, unsigned char); + + for (y = 0; y < params->h; y++) + for (x = 1; x < params->w; x++) { + vedge(ai, x, y) = + index(params, grid, x, y) != index(params, grid, x-1, y); + } + for (y = 1; y < params->h; y++) + for (x = 0; x < params->w; x++) { + hedge(ai, x, y) = + index(params, grid, x, y) != index(params, grid, x, y-1); + } + + *aux = ai; + } + + /* * Place numbers. */ numbers = snewn(params->w * params->h, int); @@ -899,9 +930,11 @@ static char *new_game_seed(game_params *params, random_state *rs, return seed; } -void game_free_aux_info(game_aux_info *aux) +static void game_free_aux_info(game_aux_info *ai) { - assert(!"Shouldn't happen"); + sfree(ai->vedge); + sfree(ai->hedge); + sfree(ai); } static char *validate_seed(game_params *params, char *seed) @@ -945,7 +978,7 @@ static game_state *new_game(game_params *params, char *seed) state->grid = snewn(area, int); state->vedge = snewn(area, unsigned char); state->hedge = snewn(area, unsigned char); - state->completed = FALSE; + state->completed = state->cheated = FALSE; i = 0; while (*seed) { @@ -987,6 +1020,7 @@ static game_state *dup_game(game_state *state) ret->grid = snewn(state->w * state->h, int); ret->completed = state->completed; + ret->cheated = state->cheated; memcpy(ret->grid, state->grid, state->w * state->h * sizeof(int)); memcpy(ret->vedge, state->vedge, state->w*state->h*sizeof(unsigned char)); @@ -1003,6 +1037,27 @@ static void free_game(game_state *state) sfree(state); } +static game_state *solve_game(game_state *state, game_aux_info *ai, + char **error) +{ + game_state *ret; + + if (!ai) { + *error = "Solution not known for this puzzle"; + return NULL; + } + + assert(state->w == ai->w); + assert(state->h == ai->h); + + ret = dup_game(state); + memcpy(ret->vedge, ai->vedge, ai->w * ai->h * sizeof(unsigned char)); + memcpy(ret->hedge, ai->hedge, ai->w * ai->h * sizeof(unsigned char)); + ret->cheated = TRUE; + + return ret; +} + static char *game_text_format(game_state *state) { char *ret, *p, buf[80]; @@ -1684,7 +1739,8 @@ static float game_anim_length(game_state *oldstate, static float game_flash_length(game_state *oldstate, game_state *newstate, int dir) { - if (!oldstate->completed && newstate->completed) + if (!oldstate->completed && newstate->completed && + !oldstate->cheated && !newstate->cheated) return FLASH_TIME; return 0.0F; } @@ -1714,6 +1770,7 @@ const struct game thegame = { new_game, dup_game, free_game, + TRUE, solve_game, TRUE, game_text_format, new_ui, free_ui, diff --git a/sixteen.c b/sixteen.c index 36c4281..cd6ae3b 100644 --- a/sixteen.c +++ b/sixteen.c @@ -42,6 +42,8 @@ struct game_state { int w, h, n; int *tiles; int completed; + int just_used_solve; /* used to suppress undo animation */ + int used_solve; /* used to suppress completion flash */ int movecount; int last_movement_sense; }; @@ -279,7 +281,7 @@ static char *new_game_seed(game_params *params, random_state *rs, return ret; } -void game_free_aux_info(game_aux_info *aux) +static void game_free_aux_info(game_aux_info *aux) { assert(!"Shouldn't happen"); } @@ -359,6 +361,7 @@ static game_state *new_game(game_params *params, char *seed) assert(!*p); state->completed = state->movecount = 0; + state->used_solve = state->just_used_solve = FALSE; state->last_movement_sense = 0; return state; @@ -375,6 +378,8 @@ static game_state *dup_game(game_state *state) memcpy(ret->tiles, state->tiles, state->w * state->h * sizeof(int)); ret->completed = state->completed; ret->movecount = state->movecount; + ret->used_solve = state->used_solve; + ret->just_used_solve = state->just_used_solve; ret->last_movement_sense = state->last_movement_sense; return ret; @@ -385,6 +390,27 @@ static void free_game(game_state *state) sfree(state); } +static game_state *solve_game(game_state *state, game_aux_info *aux, + char **error) +{ + game_state *ret = dup_game(state); + int i; + + /* + * Simply replace the grid with a solved one. For this game, + * this isn't a useful operation for actually telling the user + * what they should have done, but it is useful for + * conveniently being able to get hold of a clean state from + * which to practise manoeuvres. + */ + for (i = 0; i < ret->n; i++) + ret->tiles[i] = i+1; + ret->used_solve = ret->just_used_solve = TRUE; + ret->completed = ret->movecount; + + return ret; +} + static char *game_text_format(game_state *state) { char *ret, *p, buf[80]; @@ -464,6 +490,7 @@ static game_state *make_move(game_state *from, game_ui *ui, } ret = dup_game(from); + ret->just_used_solve = FALSE; /* zero this in a hurry */ do { cx += dx; @@ -786,9 +813,13 @@ static void game_redraw(frontend *fe, game_drawstate *ds, game_state *oldstate, if (oldstate) state = oldstate; - sprintf(statusbuf, "%sMoves: %d", - (state->completed ? "COMPLETED! " : ""), - (state->completed ? state->completed : state->movecount)); + if (state->used_solve) + sprintf(statusbuf, "Moves since auto-solve: %d", + state->movecount - state->completed); + else + sprintf(statusbuf, "%sMoves: %d", + (state->completed ? "COMPLETED! " : ""), + (state->completed ? state->completed : state->movecount)); status_bar(fe, statusbuf); } @@ -797,13 +828,18 @@ 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) { - return ANIM_TIME; + if ((dir > 0 && newstate->just_used_solve) || + (dir < 0 && oldstate->just_used_solve)) + return 0.0F; + else + return ANIM_TIME; } static float game_flash_length(game_state *oldstate, game_state *newstate, int dir) { - if (!oldstate->completed && newstate->completed) + if (!oldstate->completed && newstate->completed && + !oldstate->used_solve && !newstate->used_solve) return 2 * FLASH_FRAME; else return 0.0F; @@ -834,6 +870,7 @@ const struct game thegame = { new_game, dup_game, free_game, + TRUE, solve_game, TRUE, game_text_format, new_ui, free_ui, diff --git a/solo.c b/solo.c index 4b4adea..dc3bbc4 100644 --- a/solo.c +++ b/solo.c @@ -107,7 +107,7 @@ struct game_state { int c, r; digit *grid; unsigned char *immutable; /* marks which digits are clues */ - int completed; + int completed, cheated; }; static game_params *default_params(void) @@ -1514,7 +1514,7 @@ static char *new_game_seed(game_params *params, random_state *rs, return seed; } -void game_free_aux_info(game_aux_info *aux) +static void game_free_aux_info(game_aux_info *aux) { assert(!"Shouldn't happen"); } @@ -1560,7 +1560,7 @@ static game_state *new_game(game_params *params, char *seed) state->immutable = snewn(area, unsigned char); memset(state->immutable, FALSE, area); - state->completed = FALSE; + state->completed = state->cheated = FALSE; i = 0; while (*seed) { @@ -1602,6 +1602,7 @@ static game_state *dup_game(game_state *state) memcpy(ret->immutable, state->immutable, area); ret->completed = state->completed; + ret->cheated = state->cheated; return ret; } @@ -1613,6 +1614,36 @@ static void free_game(game_state *state) sfree(state); } +static game_state *solve_game(game_state *state, game_aux_info *aux, + char **error) +{ + game_state *ret; + int c = state->c, r = state->r; + int rsolve_ret; + + /* + * I could have stored the grid I invented in the game_aux_info + * and extracted it here where available, but it seems easier + * just to run my internal solver in all cases. + */ + + ret = dup_game(state); + ret->completed = ret->cheated = TRUE; + + rsolve_ret = rsolve(c, r, ret->grid, NULL, 2); + + if (rsolve_ret != 1) { + free_game(ret); + if (rsolve_ret == 0) + *error = "No solution exists for this puzzle"; + else + *error = "Multiple solutions exist for this puzzle"; + return NULL; + } + + return ret; +} + static char *grid_text_format(int c, int r, digit *grid) { int cr = c*r; @@ -1940,7 +1971,8 @@ static float game_anim_length(game_state *oldstate, game_state *newstate, static float game_flash_length(game_state *oldstate, game_state *newstate, int dir) { - if (!oldstate->completed && newstate->completed) + if (!oldstate->completed && newstate->completed && + !oldstate->cheated && !newstate->cheated) return FLASH_TIME; return 0.0F; } @@ -1970,6 +2002,7 @@ const struct game thegame = { new_game, dup_game, free_game, + TRUE, solve_game, TRUE, game_text_format, new_ui, free_ui, diff --git a/twiddle.c b/twiddle.c index e296f48..8a389b4 100644 --- a/twiddle.c +++ b/twiddle.c @@ -46,6 +46,8 @@ struct game_state { int orientable; int *grid; int completed; + int just_used_solve; /* used to suppress undo animation */ + int used_solve; /* used to suppress completion flash */ int movecount; int lastx, lasty, lastr; /* coordinates of last rotation */ }; @@ -359,7 +361,7 @@ static char *new_game_seed(game_params *params, random_state *rs, return ret; } -void game_free_aux_info(game_aux_info *aux) +static void game_free_aux_info(game_aux_info *aux) { assert(!"Shouldn't happen"); } @@ -406,6 +408,7 @@ static game_state *new_game(game_params *params, char *seed) state->n = n; state->orientable = params->orientable; state->completed = 0; + state->used_solve = state->just_used_solve = FALSE; state->movecount = 0; state->lastx = state->lasty = state->lastr = -1; @@ -445,6 +448,8 @@ static game_state *dup_game(game_state *state) ret->lastx = state->lastx; ret->lasty = state->lasty; ret->lastr = state->lastr; + ret->used_solve = state->used_solve; + ret->just_used_solve = state->just_used_solve; ret->grid = snewn(ret->w * ret->h, int); memcpy(ret->grid, state->grid, ret->w * ret->h * sizeof(int)); @@ -458,6 +463,37 @@ static void free_game(game_state *state) sfree(state); } +static int compare_int(const void *av, const void *bv) +{ + const int *a = (const int *)av; + const int *b = (const int *)bv; + if (*a < *b) + return -1; + else if (*a > *b) + return +1; + else + return 0; +} + +static game_state *solve_game(game_state *state, game_aux_info *aux, + char **error) +{ + game_state *ret = dup_game(state); + + /* + * Simply replace the grid with a solved one. For this game, + * this isn't a useful operation for actually telling the user + * what they should have done, but it is useful for + * conveniently being able to get hold of a clean state from + * which to practise manoeuvres. + */ + qsort(ret->grid, ret->w*ret->h, sizeof(int), compare_int); + ret->used_solve = ret->just_used_solve = TRUE; + ret->completed = ret->movecount; + + return ret; +} + static char *game_text_format(game_state *state) { char *ret, *p, buf[80]; @@ -538,6 +574,7 @@ static game_state *make_move(game_state *from, game_ui *ui, int x, int y, * This is a valid move. Make it. */ ret = dup_game(from); + ret->just_used_solve = FALSE; /* zero this in a hurry */ ret->movecount++; dir = (button == LEFT_BUTTON ? 1 : -1); do_rotate(ret->grid, w, h, n, ret->orientable, x, y, dir); @@ -822,13 +859,18 @@ static int highlight_colour(float angle) static float game_anim_length(game_state *oldstate, game_state *newstate, int dir) { - return ANIM_PER_RADIUS_UNIT * sqrt(newstate->n-1); + if ((dir > 0 && newstate->just_used_solve) || + (dir < 0 && oldstate->just_used_solve)) + return 0.0F; + else + return ANIM_PER_RADIUS_UNIT * sqrt(newstate->n-1); } static float game_flash_length(game_state *oldstate, game_state *newstate, int dir) { - if (!oldstate->completed && newstate->completed) + if (!oldstate->completed && newstate->completed && + !oldstate->used_solve && !newstate->used_solve) return 2 * FLASH_FRAME; else return 0.0F; @@ -963,9 +1005,13 @@ static void game_redraw(frontend *fe, game_drawstate *ds, game_state *oldstate, if (oldstate) state = oldstate; - sprintf(statusbuf, "%sMoves: %d", - (state->completed ? "COMPLETED! " : ""), - (state->completed ? state->completed : state->movecount)); + if (state->used_solve) + sprintf(statusbuf, "Moves since auto-solve: %d", + state->movecount - state->completed); + else + sprintf(statusbuf, "%sMoves: %d", + (state->completed ? "COMPLETED! " : ""), + (state->completed ? state->completed : state->movecount)); status_bar(fe, statusbuf); } @@ -996,6 +1042,7 @@ const struct game thegame = { new_game, dup_game, free_game, + TRUE, solve_game, TRUE, game_text_format, new_ui, free_ui, diff --git a/windows.c b/windows.c index c570b29..4df9175 100644 --- a/windows.c +++ b/windows.c @@ -28,11 +28,12 @@ #define IDM_UNDO 0x0030 #define IDM_REDO 0x0040 #define IDM_COPY 0x0050 -#define IDM_QUIT 0x0060 -#define IDM_CONFIG 0x0070 -#define IDM_SEED 0x0080 -#define IDM_HELPC 0x0090 -#define IDM_GAMEHELP 0x00A0 +#define IDM_SOLVE 0x0060 +#define IDM_QUIT 0x0070 +#define IDM_CONFIG 0x0080 +#define IDM_SEED 0x0090 +#define IDM_HELPC 0x00A0 +#define IDM_GAMEHELP 0x00B0 #define IDM_PRESETS 0x0100 #define HELP_FILE_NAME "puzzles.hlp" @@ -487,6 +488,10 @@ static frontend *new_window(HINSTANCE inst, char *game_id, char **error) AppendMenu(menu, MF_SEPARATOR, 0, 0); AppendMenu(menu, MF_ENABLED, IDM_COPY, "Copy"); } + if (thegame.can_solve) { + AppendMenu(menu, MF_SEPARATOR, 0, 0); + AppendMenu(menu, MF_ENABLED, IDM_SOLVE, "Solve"); + } AppendMenu(menu, MF_SEPARATOR, 0, 0); AppendMenu(menu, MF_ENABLED, IDM_QUIT, "Exit"); if (fe->help_path) { @@ -930,6 +935,14 @@ static LRESULT CALLBACK WndProc(HWND hwnd, UINT message, MessageBeep(MB_ICONWARNING); } break; + case IDM_SOLVE: + { + char *msg = midend_solve(fe->me); + if (msg) + MessageBox(hwnd, msg, "Unable to solve", + MB_ICONERROR | MB_OK); + } + break; case IDM_QUIT: if (!midend_process_key(fe->me, 0, 0, 'q')) PostQuitMessage(0); -- 2.11.0