Solving the 8-Puzzle with A*: Revisiting an Early Lisp Project

The Programs page on my earlier website listed an 8-tile puzzle solver written in Lisp. Its description identified A* as the search technique and mentioned XLISP-Plus 3.04 on Windows. That makes it a useful starting point for revisiting an idea that appears in route planning, games and many other state-space problems.

This article explains the algorithm and provides a new Python implementation so the example can be run with a standard Python installation. It is not recovered Lisp source, and I am not assuming details of the original program that the archive does not establish. The connection is the problem and search method; the implementation below was written for this explanation.

Represent the board and the legal moves

The board contains eight numbered tiles and one empty position in a three-by-three grid. A legal move slides an adjacent tile into the empty position. The goal used here is the sequence one through eight followed by the blank. We represent the board as a nine-element tuple, using zero for the blank, so a position can be used as a dictionary key.

A state is the whole board, not just the blank’s location. Two arrangements can have the blank in the same place while requiring different next moves. The neighbor generator locates the blank, checks the four directions and swaps it with an in-bounds adjacent tile. It does not allow a left edge to wrap around to the previous row.

Combine distance already traveled with an estimate

A* prioritizes a state using f = g + h. Here, g is the number of moves used to reach the board, and h estimates how many moves remain. Breadth-first search does not use that estimate, while greedy best-first search can ignore the path cost already spent. The combination is what gives A* its useful balance.

The heuristic in this example is Manhattan distance: add each numbered tile’s horizontal and vertical distance from its goal position. The blank is excluded. A move shifts one numbered tile by one square, so this total cannot overestimate the remaining number of moves for our unit-cost puzzle. It also has the consistency property needed for a clean shortest-path argument.

That does not mean the heuristic knows the solution. Tiles can obstruct each other, so the actual number of moves can be larger. The heuristic supplies a lower bound that helps choose what to explore next. A more informed admissible estimate may reduce search effort, but it also needs its own correctness argument and computational cost analysis.

Keep the cheapest known route to each board

Moving a tile and immediately moving it back creates a repeated state. Many different sequences can also reach the same board. The solver records the lowest discovered path cost and only inserts a new route when it improves that record. This avoids treating every sequence as an entirely separate problem.

A priority queue can still contain an old entry after a cheaper route has been inserted. The code checks that the popped cost matches the current best cost and skips stale entries. A separate predecessor dictionary remembers how to rebuild the solution after reaching the goal. These bookkeeping choices are essential parts of a working search, not optional polish.

Run the new Python solver

The complete example uses only Python’s standard library. Save it as eight-puzzle.py or download the solver. Run it with Python 3. The supplied start position needs two moves, and the printed path contains the starting board as well as each resulting board.

from heapq import heappop, heappush
from itertools import count

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


def manhattan(board):
    distance = 0
    for index, tile in enumerate(board):
        if tile:
            row, col = divmod(index, 3)
            target_row, target_col = divmod(tile - 1, 3)
            distance += abs(row - target_row) + abs(col - target_col)
    return distance


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


def solve(start):
    start = tuple(start)
    if (len(start) != 9 or any(type(x) is not int for x in start)
            or set(start) != set(range(9))):
        raise ValueError("Use each integer 0 through 8 exactly once")
    tiles = [tile for tile in start if tile]
    inversions = sum(a > b for i, a in enumerate(tiles) for b in tiles[i + 1:])
    if inversions % 2:
        return None  # For this odd-width board and fixed goal only.

    serial = count()
    frontier = [(manhattan(start), next(serial), 0, start)]
    best_cost = {start: 0}
    previous = {start: None}
    while frontier:
        _, _, cost, board = heappop(frontier)
        if cost != best_cost[board]:
            continue  # An older, more expensive entry for this board.
        if board == GOAL:
            path = []
            while board is not None:
                path.append(board)
                board = previous[board]
            return path[::-1]
        for candidate in neighbors(board):
            new_cost = cost + 1
            if new_cost < best_cost.get(candidate, float("inf")):
                best_cost[candidate] = new_cost
                previous[candidate] = board
                heappush(frontier, (new_cost + manhattan(candidate),
                                    next(serial), new_cost, candidate))
    return None


if __name__ == "__main__":
    path = solve((1, 2, 3, 4, 5, 6, 0, 7, 8))
    print("Moves:", len(path) - 1)
    for board in path:
        for row in range(0, 9, 3):
            print(board[row:row + 3])
        print()

Distinguish invalid input from an unsolvable board

An input must contain each integer from zero through eight exactly once. The solver raises an error if that contract fails. A correctly formed board can still be unsolvable. For this three-wide board and fixed goal, an odd inversion count among the numbered tiles identifies the other unreachable parity class, so the function returns no path before searching.

Do not reuse that parity test unchanged for a four-wide sliding puzzle. The blank’s row enters the solvability rule for even-width boards, and a different goal arrangement also changes how the condition is expressed. Writing the assumptions beside the test prevents a compact helper from quietly becoming an incorrect general puzzle solver.

Check shortest paths rather than attractive output

A path should begin at the requested state, end at the goal and contain only legal neighboring transitions. Counting the boards alone is insufficient: the number of moves is one less than the number of states. Also test an already solved board, which should return a one-state path with zero moves.

For small test instances, compare the path length with a breadth-first reference search. That gives an independent check on optimality without trusting the same heuristic implementation twice. Harder instances can exercise the queue and repeated-state handling, but a solver that prints a long path is not automatically correct.

Memory is an important limitation. The frontier and dictionaries retain many states, and increasing the puzzle size changes the practical cost dramatically. A compact program that handles the 8-puzzle is not evidence that the same approach will solve arbitrarily large planning problems within a reasonable time.

What this project still teaches

A* is a useful lesson in combining a representation, legal transitions, a cost model and an informed estimate. The language can change while those design questions stay recognizable. Revisiting the project this way preserves the documented history while making the algorithm accessible to a current reader.

The archive identifies the original Lisp project. For additional background, Amit Patel’s heuristics guide discusses how estimates affect search. Continue with machine learning versus AI to see why an effective search algorithm does not require a trained model.