From 12fabc4add608622da87096bb3bed586efee10d9 Mon Sep 17 00:00:00 2001 From: =?utf8?q?Jonas=20K=C3=B6lker?= Date: Thu, 8 Oct 2015 12:20:15 +0200 Subject: [PATCH 1/1] Add hinting feature to Fifteen (press 'h' for a hint). This is really an incremental solver. It alternates between solving rows and solving columns. Each row and column is solved one piece at a time. Except for some temporary trickery with the last two pieces in a row or column, once a piece is solved it is never moved again. (On non-square grids it first solves some rows or some columns until the unsolved part is a square, then starts alternating.) --- fifteen.c | 214 ++++++++++++++++++++++++++++++++++++++++++++++++++++ puzzles.but | 4 + 2 files changed, 218 insertions(+) diff --git a/fifteen.c b/fifteen.c index e1371f1..ffb5d25 100644 --- a/fifteen.c +++ b/fifteen.c @@ -473,6 +473,217 @@ static int flip_cursor(int button) 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) +{ + /* 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) @@ -498,6 +709,9 @@ static char *interpret_move(const game_state *state, game_ui *ui, 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 */ diff --git a/puzzles.but b/puzzles.but index d67f653..8ad466f 100644 --- a/puzzles.but +++ b/puzzles.but @@ -617,6 +617,10 @@ mouse pointer. The arrow keys will move a tile adjacent to the space in the direction indicated (moving the space in the \e{opposite} direction). +Pressing \q{h} will make a suggested move. Pressing \q{h} enough +times will solve the game, but it may scramble your progress while +doing so. + (All the actions described in \k{common-actions} are also available.) \H{fifteen-params} \I{parameters, for Fifteen}Fifteen parameters -- 2.30.2