AI: Solve the 8-puzzle with A*

Use A* with a good heuristic to solve a search problem with 181,440 reachable states.

What to build

A program that finds the fewest moves that solve an 8-puzzle position.

Requirements

  • A move slides a tile next to the blank into the blank. The goal is 123 / 456 / 780.
  • Print N moves for the fewest moves, or unsolvable if the goal cannot be reached.

Input

Three lines of three digits (0 is the blank).

Output

One line.

Constraints

Solvable test positions need at most 22 moves; the program should finish in a few seconds.

Example

Input:

123
456
708

Output:

1 moves

Why it works

Manhattan distance never overestimates the moves left, so A* returns an optimal solution while expanding only a small part of the state space.

Examples

Example 1 · Input
123
456
708
Expected output
1 moves
Example 2 · Input
213
456
780
Expected output
unsolvable

Prompts inside input() are ignored when checking, so input("n: ") is fine.

Hints

Hint 1

First check solvability: count pairs of tiles (ignoring the blank) that are out of order; the position is solvable only if that count is even.

Hint 2

Use A* with the Manhattan heuristic, storing positions as strings, and stop when the goal is taken out of the frontier.

Solution

Show one correct solution (try it yourself first)
import heapq

GOAL = "123456780"
start = "".join(input().strip() for _ in range(3))
tiles = [t for t in start if t != "0"]
inversions = sum(1 for i in range(8) for j in range(i + 1, 8) if tiles[i] > tiles[j])


def manhattan(state):
    total = 0
    for index, tile in enumerate(state):
        if tile != "0":
            goal = int(tile) - 1
            total += abs(index // 3 - goal // 3) + abs(index % 3 - goal % 3)
    return total


def neighbours(state):
    blank = state.index("0")
    r, c = divmod(blank, 3)
    for nr, nc in ((r - 1, c), (r + 1, c), (r, c - 1), (r, c + 1)):
        if 0 <= nr < 3 and 0 <= nc < 3:
            cells = list(state)
            other = nr * 3 + nc
            cells[blank], cells[other] = cells[other], cells[blank]
            yield "".join(cells)


if inversions % 2:
    print("unsolvable")
else:
    best = {start: 0}
    frontier = [(manhattan(start), 0, start)]
    while frontier:
        f, g, state = heapq.heappop(frontier)
        if g > best[state]:
            continue
        if state == GOAL:
            print(f"{g} moves")
            break
        for nxt in neighbours(state):
            if nxt not in best or g + 1 < best[nxt]:
                best[nxt] = g + 1
                heapq.heappush(frontier, (g + 1 + manhattan(nxt), g + 1, nxt))

Lesson: Heuristics and A* search →