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 movesfor the fewest moves, orunsolvableif 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
123 456 708
1 moves
213 456 780
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))