X-Git-Url: http://www.chiark.greenend.org.uk/ucgi/~ian/git?a=blobdiff_plain;f=fifteen.c;h=648271489da6635ad39c3333c6c535a1026f49d9;hb=3234912f921916a1b8da164fd61dc75579358577;hp=c4b0adda4ab404ceee8448e22d5e98e1703be09c;hpb=a3b837c69845e5ccfd3bc29ee72c9b3e6ea9adec;p=sgt-puzzles.git diff --git a/fifteen.c b/fifteen.c index c4b0add..6482714 100644 --- a/fifteen.c +++ b/fifteen.c @@ -25,6 +25,11 @@ #define Y(state, i) ( (i) / (state)->w ) #define C(state, x, y) ( (y) * (state)->w + (x) ) +#define PARITY_P(params, gap) (((X((params), (gap)) - ((params)->w - 1)) ^ \ + (Y((params), (gap)) - ((params)->h - 1)) ^ \ + (((params)->w * (params)->h) + 1)) & 1) +#define PARITY_S(state) PARITY_P((state), ((state)->gap_pos)) + enum { COL_BACKGROUND, COL_TEXT, @@ -57,6 +62,11 @@ static game_params *default_params(void) static int game_fetch_preset(int i, char **name, game_params **params) { + if (i == 0) { + *params = default_params(); + *name = dupstr("4x4"); + return TRUE; + } return FALSE; } @@ -65,7 +75,7 @@ static void free_params(game_params *params) sfree(params); } -static game_params *dup_params(game_params *params) +static game_params *dup_params(const game_params *params) { game_params *ret = snew(game_params); *ret = *params; /* structure copy */ @@ -82,7 +92,7 @@ static void decode_params(game_params *ret, char const *string) } } -static char *encode_params(game_params *params, int full) +static char *encode_params(const game_params *params, int full) { char data[256]; @@ -91,7 +101,7 @@ static char *encode_params(game_params *params, int full) return dupstr(data); } -static config_item *game_configure(game_params *params) +static config_item *game_configure(const game_params *params) { config_item *ret; char buf[80]; @@ -118,7 +128,7 @@ static config_item *game_configure(game_params *params) return ret; } -static game_params *custom_params(config_item *cfg) +static game_params *custom_params(const config_item *cfg) { game_params *ret = snew(game_params); @@ -128,7 +138,7 @@ static game_params *custom_params(config_item *cfg) return ret; } -static char *validate_params(game_params *params, int full) +static char *validate_params(const game_params *params, int full) { if (params->w < 2 || params->h < 2) return "Width and height must both be at least two"; @@ -150,7 +160,7 @@ static int perm_parity(int *perm, int n) return ret; } -static char *new_game_desc(game_params *params, random_state *rs, +static char *new_game_desc(const game_params *params, random_state *rs, char **aux, int interactive) { int gap, n, i, x; @@ -226,9 +236,7 @@ static char *new_game_desc(game_params *params, random_state *rs, * rather than 0,...,n-1; this is a cyclic permutation of * the starting point and hence is odd iff n is even.) */ - parity = ((X(params, gap) - (params->w-1)) ^ - (Y(params, gap) - (params->h-1)) ^ - (n+1)) & 1; + parity = PARITY_P(params, gap); /* * Try the last two tiles one way round. If that fails, swap @@ -266,9 +274,10 @@ static char *new_game_desc(game_params *params, random_state *rs, return ret; } -static char *validate_desc(game_params *params, char *desc) +static char *validate_desc(const game_params *params, const char *desc) { - char *p, *err; + const char *p; + char *err; int i, area; int *used; @@ -281,7 +290,7 @@ static char *validate_desc(game_params *params, char *desc) used[i] = FALSE; for (i = 0; i < area; i++) { - char *q = p; + const char *q = p; int n; if (*p < '0' || *p > '9') { @@ -317,11 +326,12 @@ static char *validate_desc(game_params *params, char *desc) return err; } -static game_state *new_game(midend *me, game_params *params, char *desc) +static game_state *new_game(midend *me, const game_params *params, + const char *desc) { game_state *state = snew(game_state); int i; - char *p; + const char *p; state->w = params->w; state->h = params->h; @@ -349,7 +359,7 @@ static game_state *new_game(midend *me, game_params *params, char *desc) return state; } -static game_state *dup_game(game_state *state) +static game_state *dup_game(const game_state *state) { game_state *ret = snew(game_state); @@ -372,13 +382,18 @@ static void free_game(game_state *state) sfree(state); } -static char *solve_game(game_state *state, game_state *currstate, - char *aux, char **error) +static char *solve_game(const game_state *state, const game_state *currstate, + const char *aux, char **error) { return dupstr("S"); } -static char *game_text_format(game_state *state) +static int game_can_format_as_text_now(const game_params *params) +{ + return TRUE; +} + +static char *game_text_format(const game_state *state) { char *ret, *p, buf[80]; int x, y, col, maxlen; @@ -420,7 +435,7 @@ static char *game_text_format(game_state *state) return ret; } -static game_ui *new_ui(game_state *state) +static game_ui *new_ui(const game_state *state) { return NULL; } @@ -429,17 +444,17 @@ static void free_ui(game_ui *ui) { } -static char *encode_ui(game_ui *ui) +static char *encode_ui(const game_ui *ui) { return NULL; } -static void decode_ui(game_ui *ui, char *encoding) +static void decode_ui(game_ui *ui, const char *encoding) { } -static void game_changed_state(game_ui *ui, game_state *oldstate, - game_state *newstate) +static void game_changed_state(game_ui *ui, const game_state *oldstate, + const game_state *newstate) { } @@ -450,44 +465,272 @@ struct game_drawstate { int tilesize; }; -static char *interpret_move(game_state *state, game_ui *ui, game_drawstate *ds, - int x, int y, int button) +static int flip_cursor(int button) +{ + switch (button) { + case CURSOR_UP: return CURSOR_DOWN; + case CURSOR_DOWN: return CURSOR_UP; + case CURSOR_LEFT: return CURSOR_RIGHT; + case CURSOR_RIGHT: return CURSOR_LEFT; + } + return 0; +} + +static void next_move_3x2(int ax, int ay, int bx, int by, + int gx, int gy, int *dx, int *dy) +{ + /* When w = 3 and h = 2 and the tile going in the top left corner + * is at (ax, ay) and the tile going in the bottom left corner is + * at (bx, by) and the blank tile is at (gx, gy), how do you move? */ + + /* Hard-coded shortest solutions. Sorry. */ + static const unsigned char move[120] = { + 1,2,0,1,2,2, + 2,0,0,2,0,0, + 0,0,2,0,2,0, + 0,0,0,2,0,2, + 2,0,0,0,2,0, + + 0,3,0,1,1,1, + 3,0,3,2,1,2, + 2,1,1,0,1,0, + 2,1,2,1,0,1, + 1,2,0,2,1,2, + + 0,1,3,1,3,0, + 1,3,1,3,0,3, + 0,0,3,3,0,0, + 0,0,0,1,2,1, + 3,0,0,1,1,1, + + 3,1,1,1,3,0, + 1,1,1,1,1,1, + 1,3,1,1,3,0, + 1,1,3,3,1,3, + 1,3,0,0,0,0 + }; + static const struct { int dx, dy; } d[4] = {{+1,0},{-1,0},{0,+1},{0,-1}}; + + int ea = 3*ay + ax, eb = 3*by + bx, eg = 3*gy + gx, v; + if (eb > ea) --eb; + if (eg > ea) --eg; + if (eg > eb) --eg; + v = move[ea + eb*6 + eg*5*6]; + *dx = d[v].dx; + *dy = d[v].dy; +} + +static void next_move(int nx, int ny, int ox, int oy, int gx, int gy, + int tx, int ty, int w, int *dx, int *dy) +{ + const int to_tile_x = (gx < nx ? +1 : -1); + const int to_goal_x = (gx < tx ? +1 : -1); + const int gap_x_on_goal_side = ((nx-tx) * (nx-gx) > 0); + + assert (nx != tx || ny != ty); /* not already in place */ + assert (nx != gx || ny != gy); /* not placing the gap */ + assert (ty <= ny); /* because we're greedy (and flipping) */ + assert (ty <= gy); /* because we're greedy (and flipping) */ + + /* TODO: define a termination function. Idea: 0 if solved, or + * the number of moves to solve the next piece plus the number of + * further unsolved pieces times an upper bound on the number of + * moves required to solve any piece. If such a function can be + * found, we have (termination && (termination => correctness)). + * The catch is our temporary disturbance of 2x3 corners. */ + + /* handles end-of-row, when 3 and 4 are in the top right 2x3 box */ + if (tx == w - 2 && + ny <= ty + 2 && (nx == tx || nx == tx + 1) && + oy <= ty + 2 && (ox == tx || ox == tx + 1) && + gy <= ty + 2 && (gx == tx || gx == tx + 1)) + { + next_move_3x2(oy - ty, tx + 1 - ox, + ny - ty, tx + 1 - nx, + gy - ty, tx + 1 - gx, dy, dx); + *dx *= -1; + return; + } + + if (tx == w - 1) { + if (ny <= ty + 2 && (nx == tx || nx == tx - 1) && + gy <= ty + 2 && (gx == tx || gx == tx - 1)) { + next_move_3x2(ny - ty, tx - nx, 0, 1, gy - ty, tx - gx, dy, dx); + *dx *= -1; + } else if (gy == ty) + *dy = +1; + else if (nx != tx || ny != ty + 1) { + next_move((w - 1) - nx, ny, -1, -1, (w - 1) - gx, gy, + 0, ty + 1, -1, dx, dy); + *dx *= -1; + } else if (gx == nx) + *dy = -1; + else + *dx = +1; + return; + } + + /* note that *dy = -1 is unsafe when gy = ty + 1 and gx < tx */ + if (gy < ny) + if (nx == gx || (gy == ty && gx == tx)) + *dy = +1; + else if (!gap_x_on_goal_side) + *dx = to_tile_x; + else if (ny - ty > abs(nx - tx)) + *dx = to_tile_x; + else *dy = +1; + + else if (gy == ny) + if (nx == tx) /* then we know ny > ty */ + if (gx > nx || ny > ty + 1) + *dy = -1; /* ... so this is safe */ + else + *dy = +1; + else if (gap_x_on_goal_side) + *dx = to_tile_x; + else if (gy == ty || (gy == ty + 1 && gx < tx)) + *dy = +1; + else + *dy = -1; + + else if (nx == tx) /* gy > ny */ + if (gx > nx) + *dy = -1; + else + *dx = +1; + else if (gx == nx) + *dx = to_goal_x; + else if (gap_x_on_goal_side) + if (gy == ty + 1 && gx < tx) + *dx = to_tile_x; + else + *dy = -1; + + else if (ny - ty > abs(nx - tx)) + *dy = -1; + else + *dx = to_tile_x; +} + +static int compute_hint(const game_state *state, int *out_x, int *out_y) { - int gx, gy, dx, dy; + /* The overall solving process is this: + * 1. Find the next piece to be put in its place + * 2. Move it diagonally towards its place + * 3. Move it horizontally or vertically towards its place + * (Modulo the last two tiles at the end of each row/column) + */ + + int gx = X(state, state->gap_pos); + int gy = Y(state, state->gap_pos); + + int tx, ty, nx, ny, ox, oy, /* {target,next,next2}_{x,y} */ i; + int dx = 0, dy = 0; + + /* 1. Find the next piece + * if (there are no more unfinished columns than rows) { + * fill the top-most row, left to right + * } else { fill the left-most column, top to bottom } + */ + const int w = state->w, h = state->h, n = w*h; + int next_piece = 0, next_piece_2 = 0, solr = 0, solc = 0; + int unsolved_rows = h, unsolved_cols = w; + + assert(out_x); + assert(out_y); + + while (solr < h && solc < w) { + int start, step, stop; + if (unsolved_cols <= unsolved_rows) + start = solr*w + solc, step = 1, stop = unsolved_cols; + else + start = solr*w + solc, step = w, stop = unsolved_rows; + for (i = 0; i < stop; ++i) { + const int j = start + i*step; + if (state->tiles[j] != j + 1) { + next_piece = j + 1; + next_piece_2 = next_piece + step; + break; + } + } + if (i < stop) break; + + (unsolved_cols <= unsolved_rows) + ? (++solr, --unsolved_rows) + : (++solc, --unsolved_cols); + } + + if (next_piece == n) + return FALSE; + + /* 2, 3. Move the next piece towards its place */ + + /* gx, gy already set */ + tx = X(state, next_piece - 1); /* where we're going */ + ty = Y(state, next_piece - 1); + for (i = 0; i < n && state->tiles[i] != next_piece; ++i); + nx = X(state, i); /* where we're at */ + ny = Y(state, i); + for (i = 0; i < n && state->tiles[i] != next_piece_2; ++i); + ox = X(state, i); + oy = Y(state, i); + + if (unsolved_cols <= unsolved_rows) + next_move(nx, ny, ox, oy, gx, gy, tx, ty, w, &dx, &dy); + else + next_move(ny, nx, oy, ox, gy, gx, ty, tx, h, &dy, &dx); + + assert (dx || dy); + + *out_x = gx + dx; + *out_y = gy + dy; + return TRUE; +} + +static char *interpret_move(const game_state *state, game_ui *ui, + const game_drawstate *ds, + int x, int y, int button) +{ + int cx = X(state, state->gap_pos), nx = cx; + int cy = Y(state, state->gap_pos), ny = cy; char buf[80]; button &= ~MOD_MASK; - gx = X(state, state->gap_pos); - gy = Y(state, state->gap_pos); - - if (button == CURSOR_RIGHT && gx > 0) - dx = gx - 1, dy = gy; - else if (button == CURSOR_LEFT && gx < state->w-1) - dx = gx + 1, dy = gy; - else if (button == CURSOR_DOWN && gy > 0) - dy = gy - 1, dx = gx; - else if (button == CURSOR_UP && gy < state->h-1) - dy = gy + 1, dx = gx; - else if (button == LEFT_BUTTON) { - dx = FROMCOORD(x); - dy = FROMCOORD(y); - if (dx < 0 || dx >= state->w || dy < 0 || dy >= state->h) + if (button == LEFT_BUTTON) { + nx = FROMCOORD(x); + ny = FROMCOORD(y); + if (nx < 0 || nx >= state->w || ny < 0 || ny >= state->h) return NULL; /* out of bounds */ - /* - * Any click location should be equal to the gap location - * in _precisely_ one coordinate. - */ - if ((dx == gx && dy == gy) || (dx != gx && dy != gy)) - return NULL; + } else if (IS_CURSOR_MOVE(button)) { + static int invert_cursor = -1; + if (invert_cursor == -1) { + char *env = getenv("FIFTEEN_INVERT_CURSOR"); + invert_cursor = (env && (env[0] == 'y' || env[0] == 'Y')); + } + button = flip_cursor(button); /* the default */ + if (invert_cursor) + button = flip_cursor(button); /* undoes the first flip */ + move_cursor(button, &nx, &ny, state->w, state->h, FALSE); + } else if ((button == 'h' || button == 'H') && !state->completed) { + if (!compute_hint(state, &nx, &ny)) + return NULL; /* shouldn't happen, since ^^we^^checked^^ */ } else return NULL; /* no move */ - sprintf(buf, "M%d,%d", dx, dy); - return dupstr(buf); + /* + * Any click location should be equal to the gap location + * in _precisely_ one coordinate. + */ + if ((cx == nx) ^ (cy == ny)) { + sprintf(buf, "M%d,%d", nx, ny); + return dupstr(buf); + } + + return NULL; } -static game_state *execute_move(game_state *from, char *move) +static game_state *execute_move(const game_state *from, const char *move) { int gx, gy, dx, dy, ux, uy, up, p; game_state *ret; @@ -560,8 +803,8 @@ static game_state *execute_move(game_state *from, char *move) * Drawing routines. */ -static void game_compute_size(game_params *params, int tilesize, - int *x, int *y) +static void game_compute_size(const game_params *params, int tilesize, + int *x, int *y) { /* Ick: fake up `ds->tilesize' for macro expansion purposes */ struct { int tilesize; } ads, *ds = &ads; @@ -572,7 +815,7 @@ static void game_compute_size(game_params *params, int tilesize, } static void game_set_size(drawing *dr, game_drawstate *ds, - game_params *params, int tilesize) + const game_params *params, int tilesize) { ds->tilesize = tilesize; } @@ -591,7 +834,7 @@ static float *game_colours(frontend *fe, int *ncolours) return ret; } -static game_drawstate *game_new_drawstate(drawing *dr, game_state *state) +static game_drawstate *game_new_drawstate(drawing *dr, const game_state *state) { struct game_drawstate *ds = snew(struct game_drawstate); int i; @@ -614,7 +857,7 @@ static void game_free_drawstate(drawing *dr, game_drawstate *ds) sfree(ds); } -static void draw_tile(drawing *dr, game_drawstate *ds, game_state *state, +static void draw_tile(drawing *dr, game_drawstate *ds, const game_state *state, int x, int y, int tile, int flash_colour) { if (tile == 0) { @@ -648,9 +891,10 @@ static void draw_tile(drawing *dr, game_drawstate *ds, game_state *state, draw_update(dr, x, y, TILE_SIZE, TILE_SIZE); } -static void game_redraw(drawing *dr, game_drawstate *ds, game_state *oldstate, - game_state *state, int dir, game_ui *ui, - float animtime, float flashtime) +static void game_redraw(drawing *dr, game_drawstate *ds, + const game_state *oldstate, const game_state *state, + int dir, const game_ui *ui, + float animtime, float flashtime) { int i, pass, bgcolour; @@ -804,14 +1048,14 @@ static void game_redraw(drawing *dr, game_drawstate *ds, game_state *oldstate, } } -static float game_anim_length(game_state *oldstate, - game_state *newstate, int dir, game_ui *ui) +static float game_anim_length(const game_state *oldstate, + const game_state *newstate, int dir, game_ui *ui) { return ANIM_TIME; } -static float game_flash_length(game_state *oldstate, - game_state *newstate, int dir, game_ui *ui) +static float game_flash_length(const game_state *oldstate, + const game_state *newstate, int dir, game_ui *ui) { if (!oldstate->completed && newstate->completed && !oldstate->used_solve && !newstate->used_solve) @@ -820,16 +1064,21 @@ static float game_flash_length(game_state *oldstate, return 0.0F; } -static int game_timing_state(game_state *state, game_ui *ui) +static int game_status(const game_state *state) +{ + return state->completed ? +1 : 0; +} + +static int game_timing_state(const game_state *state, game_ui *ui) { return TRUE; } -static void game_print_size(game_params *params, float *x, float *y) +static void game_print_size(const game_params *params, float *x, float *y) { } -static void game_print(drawing *dr, game_state *state, int tilesize) +static void game_print(drawing *dr, const game_state *state, int tilesize) { } @@ -838,7 +1087,7 @@ static void game_print(drawing *dr, game_state *state, int tilesize) #endif const struct game thegame = { - "Fifteen", "games.fifteen", + "Fifteen", "games.fifteen", "fifteen", default_params, game_fetch_preset, decode_params, @@ -853,7 +1102,7 @@ const struct game thegame = { dup_game, free_game, TRUE, solve_game, - TRUE, game_text_format, + TRUE, game_can_format_as_text_now, game_text_format, new_ui, free_ui, encode_ui, @@ -868,8 +1117,99 @@ const struct game thegame = { game_redraw, game_anim_length, game_flash_length, + game_status, FALSE, FALSE, game_print_size, game_print, TRUE, /* wants_statusbar */ FALSE, game_timing_state, 0, /* flags */ }; + +#ifdef STANDALONE_SOLVER + +int main(int argc, char **argv) +{ + game_params *params; + game_state *state; + char *id = NULL, *desc, *err; + int grade = FALSE; + char *progname = argv[0]; + + char buf[80]; + int limit, x, y, solvable; + + while (--argc > 0) { + char *p = *++argv; + if (!strcmp(p, "-v")) { + /* solver_show_working = TRUE; */ + } else if (!strcmp(p, "-g")) { + grade = TRUE; + } else if (*p == '-') { + fprintf(stderr, "%s: unrecognised option `%s'\n", progname, p); + return 1; + } else { + id = p; + } + } + + if (!id) { + fprintf(stderr, "usage: %s [-g | -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'; + + params = default_params(); + decode_params(params, id); + err = validate_desc(params, desc); + if (err) { + free_params(params); + fprintf(stderr, "%s: %s\n", argv[0], err); + return 1; + } + + state = new_game(NULL, params, desc); + free_params(params); + + solvable = (PARITY_S(state) == perm_parity(state->tiles, state->n)); + if (grade || !solvable) { + free_game(state); + fputs(solvable ? "Game is solvable" : "Game is unsolvable", + grade ? stdout : stderr); + return !grade; + } + + for (limit = 5 * state->n * state->n * state->n; limit; --limit) { + game_state *next_state; + if (!compute_hint(state, &x, &y)) { + fprintf(stderr, "couldn't compute next move while solving %s:%s", + id, desc); + return 1; + } + printf("Move the space to (%d, %d), moving %d into the space\n", + x + 1, y + 1, state->tiles[C(state, x, y)]); + sprintf(buf, "M%d,%d", x, y); + next_state = execute_move(state, buf); + + free_game(state); + if (!next_state) { + fprintf(stderr, "invalid move when solving %s:%s\n", id, desc); + return 1; + } + state = next_state; + if (next_state->completed) { + free_game(state); + return 0; + } + } + + free_game(state); + fprintf(stderr, "ran out of moves for %s:%s\n", id, desc); + return 1; +} + +#endif