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.)

diff --git a/fifteen.c b/fifteen.c
index e1371f19bec39be36a0640beddc9c413469d7538..ffb5d2567abfc016003b0f85d1c82025fdcc203e 100644 (file)
--- 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 d67f6533795353edac589871d925f72e330bf3aa..8ad466fa6ac56945926b6aa3247a0177aff8dcd0 100644 (file)
--- 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