AI: Two heuristics for the 8-puzzle

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, and manhattan 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)

Lesson: Heuristics and A* search →