* cases.
*
* - Improve the generator.
+ * * actually, we seem to be mostly sensible already now. I
+ * want more choice over the type of main block and location
+ * of the exit/target, and I think I probably ought to give
+ * 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.
+ * * the move limit tends to make the game _slower_ to
+ * generate, which is odd. Perhaps investigate why.
*
- * - All the colours are a bit wishy-washy. _Some_ dark colours
- * would surely not be excessive? Probably darken the tiles,
- * the walls and the main block, and leave the target marker
- * pale.
+ * - Improve the graphics.
+ * * All the colours are a bit wishy-washy. _Some_ dark
+ * colours would surely not be excessive? Probably darken
+ * the tiles, the walls and the main block, and leave the
+ * target marker pale.
+ * * The cattle grid effect is still disgusting. Think of
+ * something completely different.
*/
#include <stdio.h>
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;
+ unsigned char *tried_merge;
+ int *dsf;
int *list, nlist, pos;
int tx, ty;
int i, j;
for (i = 0; i < h; i++)
board[i*w] = board[i*w+(w-1)] = WALL;
+ tried_merge = snewn(wh * wh, unsigned char);
+ memset(tried_merge, 0, wh*wh);
+ dsf = snew_dsf(wh);
+
/*
* Invent a main piece at one extreme. (FIXME: vary the
* extreme, and the piece.)
* 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;
/*
/*
* Now go through that list in random order, trying to merge
* the blocks on each side of each edge.
- *
- * FIXME: this seems to produce unpleasantly unbalanced
- * results. Perhaps we'd do better if we always tried to
- * combine the _smallest_ block with something?
- *
- * FIXME: also one reason it's slow might be because we aren't
- * tracking which blocks we've already tried to merge, when
- * another edge ends up linking the same ones.
*/
shuffle(list, nlist, sizeof(*list), rs);
while (nlist > 0) {
- int x1, y1, p1;
- int x2, y2, p2;
+ int x1, y1, p1, c1;
+ int x2, y2, p2, c2;
pos = list[--nlist];
y1 = y2 = pos / (w*2);
p2 = y2*w+x2;
/*
+ * Immediately abandon the attempt if we've already tried
+ * to merge the same pair of blocks along a different
+ * edge.
+ */
+ c1 = dsf_canonify(dsf, p1);
+ c2 = dsf_canonify(dsf, p2);
+ if (tried_merge[c1 * wh + c2])
+ continue;
+
+ /*
* In order to be mergeable, these two squares must each
* either be, or belong to, a non-main anchor, and their
* anchors must also be distinct.
} 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.
*/
memcpy(board, board2, wh);
+ tried_merge[c1 * wh + c2] = tried_merge[c2 * wh + c1] = TRUE;
} else {
+ int c;
+
moves = j;
+
+ dsf_merge(dsf, c1, c2);
+ c = dsf_canonify(dsf, c1);
+ for (i = 0; i < wh; i++)
+ tried_merge[c*wh+i] = (tried_merge[c1*wh+i] |
+ tried_merge[c2*wh+i]);
+ for (i = 0; i < wh; i++)
+ tried_merge[i*wh+c] = (tried_merge[i*wh+c1] |
+ tried_merge[i*wh+c2]);
}
}
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);
sprintf(statusbuf, "%sMoves: %d",
(state->completed >= 0 ? "COMPLETED! " : ""),
(state->completed >= 0 ? state->completed : state->movecount));
- if (state->minmoves)
+ if (state->minmoves >= 0)
sprintf(statusbuf+strlen(statusbuf), " (min %d)",
state->minmoves);
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