Compute the two classic heuristics for the sliding puzzle.
What to build
A program that computes the misplaced-tiles and Manhattan-distance heuristics of an 8-puzzle position.
Requirements
- The goal position is
123/456/780, where 0 is the blank. - Print
misplaced N, the number of tiles not in their goal square, andmanhattan M, the sum over tiles of the row distance plus the column distance to their goal square.
Input
Three lines of three digits.
Output
Two lines.
Constraints
Each digit 0–8 appears once.
Example
Input:
123
456
708
Output:
misplaced 1
manhattan 1
Why it works
Both are relaxed versions of the puzzle (tiles jumping anywhere, or sliding through each other), so neither ever overestimates the real number of moves.
Examples
Example 1 · Input
123 456 708
Expected output
misplaced 1 manhattan 1
Example 2 · Input
813 402 765
Expected output
misplaced 5 manhattan 10
Prompts inside input() are ignored when checking, so input("n: ") is fine.
Hints
Hint 1
The goal is 1 2 3 / 4 5 6 / 7 8 blank; tile t belongs in row (t − 1) // 3 and column (t − 1) % 3.
Hint 2
Do not count the blank (0) in either heuristic.
Solution
Show one correct solution (try it yourself first)
grid = [input().strip() for _ in range(3)]
misplaced = manhattan = 0
for r in range(3):
for c in range(3):
tile = int(grid[r][c])
if tile == 0:
continue
goal_r, goal_c = divmod(tile - 1, 3)
if (r, c) != (goal_r, goal_c):
misplaced += 1
manhattan += abs(r - goal_r) + abs(c - goal_c)
print("misplaced", misplaced)
print("manhattan", manhattan)