Sliding Tile Puzzle — One Move at a Time

When Each Graph Vertex Is an Entire Board

In grid pathfinding, your position (r, c) is the state. In a Sliding Puzzle (such as the classic 3 × 3 8-Puzzle or 2 × 3 LeetCode 773), moving one tile changes which moves become legal next — so one vertex in the implicit graph is an immutable tuple of the whole board:

START = (1, 2, 3, 5, 0, 6, 4, 7, 8)
GOAL  = (1, 2, 3, 4, 5, 6, 7, 8, 0)

From any board, locating blank = board.index(0) yields up to 4 neighbor tuples, each separated by an edge of weight 1.

Why Counting the Blank Breaks Admissibility

To guide A* with f(board) = g(board) + h(board), we sum how many horizontal + vertical steps each numbered tile (1..8) sits away from its home slot:

• Each move swaps 0 with one numbered tile, changing that single tile’s Manhattan distance by +1 or −1.
• Therefore, reducing the numbered-tile Manhattan sum to 0 takes at least h(board) moves (h(board) <= true_remaining_moves).
• If you accidentally added the blank’s distance too, a single swap could reduce h by 2 in just 1 move — overestimating the remaining cost and potentially returning a non-optimal move sequence!

Complete Python Solution (With Inversion Parity Check)

from heapq import heappop, heappush
from itertools import count

GOAL = (1, 2, 3, 4, 5, 6, 7, 8, 0)


def manhattan(board: tuple[int, ...]) -> int:
    total = 0
    for index, tile in enumerate(board):
        if tile == 0:
            continue
        row, col = divmod(index, 3)
        goal_row, goal_col = divmod(tile - 1, 3)
        total += abs(row - goal_row) + abs(col - goal_col)
    return total


def neighbors(board: tuple[int, ...]):
    blank = board.index(0)
    row, col = divmod(blank, 3)
    for dr, dc in ((-1, 0), (0, -1), (0, 1), (1, 0)):
        nr, nc = row + dr, col + dc
        if 0 <= nr < 3 and 0 <= nc < 3:
            other = 3 * nr + nc
            moved = list(board)
            moved[blank], moved[other] = moved[other], moved[blank]
            yield tuple(moved)


def solvable(board: tuple[int, ...]) -> bool:
    tiles = [t for t in board if t != 0]
    inversions = sum(a > b for i, a in enumerate(tiles) for b in tiles[i + 1:])
    return inversions % 2 == 0


def a_star_puzzle(start: tuple[int, ...]) -> list[tuple[int, ...]] | None:
    if not solvable(start):
        return None
    best = {start: 0}
    parent: dict[tuple[int, ...], tuple[int, ...] | None] = {start: None}
    serial = count()
    h0 = manhattan(start)
    frontier = [(h0, h0, next(serial), 0, start)]

    while frontier:
        _, _, _, cost, board = heappop(frontier)
        if cost != best[board]:
            continue
        if board == GOAL:
            path = []
            curr: tuple[int, ...] | None = board
            while curr is not None:
                path.append(curr)
                curr = parent[curr]
            return path[::-1]

        for nxt in neighbors(board):
            candidate = cost + 1
            if candidate < best.get(nxt, float("inf")):
                best[nxt] = candidate
                parent[nxt] = board
                h = manhattan(nxt)
                heappush(frontier, (candidate + h, h, next(serial), candidate, nxt))

    return None