eight_puzzle.py

# 8-Puzzle Solver using Breadth-First Search.
#
# The 8-puzzle is a 3×3 grid containing tiles 1–8 and one blank (0).
# Tiles slide into the blank space. The goal is to reach:
#   1 2 3
#   4 5 6
#   7 8 0
#
# BFS guarantees the shortest solution (fewest moves).
# Solvability is determined by counting inversions — a puzzle is solvable
# if and only if the number of inversions is even.

from collections import deque

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


def is_solvable(grid):
    flat = [x for x in grid if x != 0]
    inversions = sum(
        1 for i in range(len(flat))
          for j in range(i + 1, len(flat))
          if flat[i] > flat[j]
    )
    return inversions % 2 == 0


def solve(start):
    if tuple(start) == GOAL:
        return []
    if not is_solvable(start):
        return None

    queue = deque([(tuple(start), [])])
    visited = {tuple(start)}

    while queue:
        state, path = queue.popleft()
        zero = state.index(0)
        row, col = zero // 3, zero % 3

        moves = []
        if row > 0: moves.append(('up',    zero - 3))
        if row < 2: moves.append(('down',  zero + 3))
        if col > 0: moves.append(('left',  zero - 1))
        if col < 2: moves.append(('right', zero + 1))

        for direction, swap in moves:
            new_state = list(state)
            new_state[zero], new_state[swap] = new_state[swap], new_state[zero]
            new_state = tuple(new_state)

            if new_state == GOAL:
                return path + [direction]

            if new_state not in visited:
                visited.add(new_state)
                queue.append((new_state, path + [direction]))

    return None


def print_grid(grid):
    for i in range(0, 9, 3):
        print(' '.join(str(x) if x else '.' for x in grid[i:i+3]))


if __name__ == '__main__':
    examples = [
        [1, 2, 3, 4, 5, 6, 7, 0, 8],   # 1 move
        [1, 2, 3, 4, 5, 6, 0, 7, 8],   # 2 moves
        [1, 2, 3, 0, 4, 6, 7, 5, 8],   # a few moves
        [1, 2, 3, 4, 5, 6, 8, 7, 0],   # unsolvable
    ]

    for grid in examples:
        print('Start:')
        print_grid(grid)
        solution = solve(grid)
        if solution is None:
            print('No solution (unsolvable).')
        else:
            print(f'Solved in {len(solution)} move(s): {solution}')
        print()