From b48c4c04e849eda08ea2b8ddee7b92dbee416e51 Mon Sep 17 00:00:00 2001 From: simon Date: Mon, 7 May 2007 19:36:19 +0000 Subject: [PATCH] Stand-alone slidesolver. git-svn-id: svn://svn.tartarus.org/sgt/puzzles@7558 cda61777-01e9-0310-a592-d414129be87e --- unfinished/slide.R | 3 ++ unfinished/slide.c | 146 ++++++++++++++++++++++++++++++++++++++++++++++++++--- 2 files changed, 141 insertions(+), 8 deletions(-) diff --git a/unfinished/slide.R b/unfinished/slide.R index c6df86c..a88e48e 100644 --- a/unfinished/slide.R +++ b/unfinished/slide.R @@ -6,6 +6,9 @@ slide : [X] GTK COMMON SLIDE slide-icon|no-icon slide : [G] WINDOWS COMMON SLIDE slide.res|noicon.res +slidesolver : [U] slide[STANDALONE_SOLVER] dsf tree234 STANDALONE +slidesolver : [C] slide[STANDALONE_SOLVER] dsf tree234 STANDALONE + ALL += SLIDE !begin gtk diff --git a/unfinished/slide.c b/unfinished/slide.c index 58bd6eb..854d483 100644 --- a/unfinished/slide.c +++ b/unfinished/slide.c @@ -400,13 +400,18 @@ static struct board *newboard(int w, int h, unsigned char *data) /* * The actual solver. Given a board, attempt to find the minimum * length of move sequence which moves MAINANCHOR to (tx,ty), or - * -1 if no solution exists. Returns that minimum length, and - * (FIXME) optionally also writes out the actual moves into an - * as-yet-unprovided parameter. + * -1 if no solution exists. Returns that minimum length. + * + * Also, if `moveout' is provided, writes out the moves in the + * form of a sequence of pairs of integers indicating the source + * and destination points of the anchor of the moved piece in each + * move. Exactly twice as many integers are written as the number + * returned from solve_board(), and `moveout' receives an int * + * which is a pointer to a dynamically allocated array. */ static int solve_board(int w, int h, unsigned char *board, unsigned char *forcefield, int tx, int ty, - int movelimit) + int movelimit, int **moveout) { int wh = w*h; struct board *b, *b2, *b3; @@ -571,10 +576,49 @@ static int solve_board(int w, int h, unsigned char *board, done: - if (b2) + if (b2) { ret = b2->dist; - else + if (moveout) { + /* + * Now b2 represents the solved position. Backtrack to + * output the solution. + */ + *moveout = snewn(ret * 2, int); + j = ret * 2; + + while (b2->prev) { + int from = -1, to = -1; + + b = b2->prev; + + /* + * Scan b and b2 to find out which piece has + * moved. + */ + for (i = 0; i < wh; i++) { + if (ISANCHOR(b->data[i]) && !ISANCHOR(b2->data[i])) { + assert(from == -1); + from = i; + } else if (!ISANCHOR(b->data[i]) && ISANCHOR(b2->data[i])){ + assert(to == -1); + to = i; + } + } + + assert(from >= 0 && to >= 0); + assert(j >= 2); + (*moveout)[--j] = to; + (*moveout)[--j] = from; + + b2 = b; + } + assert(j == 0); + } + } else { ret = -1; /* no solution */ + if (moveout) + *moveout = NULL; + } freetree234(queue); @@ -653,7 +697,7 @@ static void generate_board(int w, int h, int *rtx, int *rty, int *minmoves, * See if the board is already soluble. */ if ((moves = solve_board(w, h, board, forcefield, - tx, ty, movelimit)) >= 0) + tx, ty, movelimit, NULL)) >= 0) goto soluble; /* @@ -753,7 +797,7 @@ static void generate_board(int w, int h, int *rtx, int *rty, int *minmoves, } while (p2 < wh && board[p2] != DIST(p2-i)); } } - j = solve_board(w, h, board, forcefield, tx, ty, movelimit); + j = solve_board(w, h, board, forcefield, tx, ty, movelimit, NULL); if (j < 0) { /* * Didn't work. Revert the merge. @@ -1979,3 +2023,89 @@ const struct game thegame = { FALSE, game_timing_state, 0, /* flags */ }; + +#ifdef STANDALONE_SOLVER + +#include + +int main(int argc, char **argv) +{ + game_params *p; + game_state *s; + char *id = NULL, *desc, *err; + int count = FALSE; + int ret, really_verbose = FALSE; + int *moves; + + while (--argc > 0) { + char *p = *++argv; + if (!strcmp(p, "-v")) { + really_verbose = TRUE; + } else if (!strcmp(p, "-c")) { + count = TRUE; + } else if (*p == '-') { + fprintf(stderr, "%s: unrecognised option `%s'\n", argv[0], p); + return 1; + } else { + id = p; + } + } + + if (!id) { + fprintf(stderr, "usage: %s [-c | -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); + + ret = solve_board(s->w, s->h, s->board, s->imm->forcefield, + s->tx, s->ty, -1, &moves); + if (ret < 0) { + printf("No solution found\n"); + } else { + int index = 0; + if (count) { + printf("%d moves required\n", ret); + return 0; + } + while (1) { + int moveret; + char *text = board_text_format(s->w, s->h, s->board, + s->imm->forcefield); + game_state *s2; + + printf("position %d:\n%s", index, text); + + if (index >= ret) + break; + + s2 = dup_game(s); + moveret = move_piece(s->w, s->h, s->board, + s2->board, s->imm->forcefield, + moves[index*2], moves[index*2+1]); + assert(moveret); + + free_game(s); + s = s2; + index++; + } + } + + return 0; +} + +#endif -- 2.11.0