* up on compactness and just bite the bullet and have the
* target area right outside the main wall, but mostly I
* think it's OK.
- * * but adjust the presets, because 8x6 is _slow_ to
- * generate.
- * * also, introduce a difficulty scheme, in the form of
- * limiting the minimum move count. This is obviously
- * sensible, because it also speeds up generation since the
- * solver can bomb out once it hits that ceiling!
- * + I was going to say I'd need to work out a minimum move
- * count for each grid size, but actually I think not: if
- * you ask for too few moves, it just has to remove still
- * more singletons, until at move count 1 you end up with
- * nothing in your way at all and it SERVES YOU RIGHT!
+ * * the move limit tends to make the game _slower_ to
+ * generate, which is odd. Perhaps investigate why.
*
* - Improve the graphics.
* * All the colours are a bit wishy-washy. _Some_ dark
struct game_params {
int w, h;
+ int maxmoves;
};
struct game_immutable_state {
{
game_params *ret = snew(game_params);
- ret->w = 8;
+ ret->w = 7;
ret->h = 6;
+ ret->maxmoves = 40;
return ret;
}
static const struct game_params slide_presets[] = {
- {6, 5},
- {7, 5},
- {7, 6},
- {8, 6},
+ {7, 6, 25},
+ {7, 6, -1},
+ {8, 6, -1},
};
static int game_fetch_preset(int i, char **name, game_params **params)
*ret = slide_presets[i];
sprintf(str, "%dx%d", ret->w, ret->h);
+ if (ret->maxmoves >= 0)
+ sprintf(str + strlen(str), ", max %d moves", ret->maxmoves);
+ else
+ sprintf(str + strlen(str), ", no move limit");
*name = dupstr(str);
*params = ret;
if (*string == 'x') {
string++;
params->h = atoi(string);
+ while (*string && isdigit((unsigned char)*string)) string++;
+ }
+ if (*string == 'm') {
+ string++;
+ params->maxmoves = atoi(string);
+ while (*string && isdigit((unsigned char)*string)) string++;
+ } else if (*string == 'u') {
+ string++;
+ params->maxmoves = -1;
}
}
char data[256];
sprintf(data, "%dx%d", params->w, params->h);
+ if (params->maxmoves >= 0)
+ sprintf(data + strlen(data), "m%d", params->maxmoves);
+ else
+ sprintf(data + strlen(data), "u");
return dupstr(data);
}
config_item *ret;
char buf[80];
- ret = snewn(3, config_item);
+ ret = snewn(4, config_item);
ret[0].name = "Width";
ret[0].type = C_STRING;
ret[1].sval = dupstr(buf);
ret[1].ival = 0;
- ret[2].name = NULL;
- ret[2].type = C_END;
- ret[2].sval = NULL;
+ ret[2].name = "Solution length limit";
+ ret[2].type = C_STRING;
+ sprintf(buf, "%d", params->maxmoves);
+ ret[2].sval = dupstr(buf);
ret[2].ival = 0;
+ ret[3].name = NULL;
+ ret[3].type = C_END;
+ ret[3].sval = NULL;
+ ret[3].ival = 0;
+
return ret;
}
ret->w = atoi(cfg[0].sval);
ret->h = atoi(cfg[1].sval);
+ ret->maxmoves = atoi(cfg[2].sval);
return ret;
}
/*
* 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)
+ unsigned char *forcefield, int tx, int ty,
+ int movelimit, int **moveout)
{
int wh = w*h;
struct board *b, *b2, *b3;
while ((b = delpos234(queue, 0)) != NULL) {
qlen--;
+ if (movelimit >= 0 && b->dist >= movelimit) {
+ /*
+ * The problem is not soluble in under `movelimit'
+ * moves, so we can quit right now.
+ */
+ b2 = NULL;
+ goto done;
+ }
if (b->dist != lastdist) {
#ifdef SOLVER_DIAGNOSTICS
printf("dist %d (%d)\n", b->dist, count234(sorted));
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);
static void generate_board(int w, int h, int *rtx, int *rty, int *minmoves,
random_state *rs, unsigned char **rboard,
- unsigned char **rforcefield)
+ unsigned char **rforcefield, int movelimit)
{
int wh = w*h;
unsigned char *board, *board2, *forcefield;
* See if the board is already soluble.
*/
if ((moves = solve_board(w, h, board, forcefield,
- tx, ty)) >= 0)
+ tx, ty, movelimit, NULL)) >= 0)
goto soluble;
/*
c1 = dsf_canonify(dsf, p1);
c2 = dsf_canonify(dsf, p2);
if (tried_merge[c1 * wh + c2])
-{printf("aha\n");
continue;
-}
/*
* In order to be mergeable, these two squares must each
} while (p2 < wh && board[p2] != DIST(p2-i));
}
}
- j = solve_board(w, h, board, forcefield, tx, ty);
+ j = solve_board(w, h, board, forcefield, tx, ty, movelimit, NULL);
if (j < 0) {
/*
* Didn't work. Revert the merge.
int i;
generate_board(params->w, params->h, &tx, &ty, &minmoves, rs,
- &board, &forcefield);
+ &board, &forcefield, params->maxmoves);
#ifdef GENERATOR_DIAGNOSTICS
{
char *t = board_text_format(params->w, params->h, board);
int w = params->w, h = params->h, wh = w*h;
int *active, *link;
int mains = 0, mpos = -1;
- int i, j, tx, ty, minmoves;
+ int i, tx, ty, minmoves;
char *ret;
active = snewn(wh, int);
}
link[i] = i - dist;
- for (j = i; j > 0; j = link[j])
- if (j == i-1 || j == i-w)
- break;
- if (j < 0) {
- ret = "Disconnected piece in game description";
- goto done;
- }
active[i] = TRUE;
active[link[i]] = FALSE;
FALSE, game_timing_state,
0, /* flags */
};
+
+#ifdef STANDALONE_SOLVER
+
+#include <stdarg.h>
+
+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] <game_id>\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
~mdw / sgt / puzzles / blobdiff