八数码 python

八数码（Eight Puzzle）是一个经典的数字滑块游戏，目标是将九个编号为1到8的方块按照特定顺序排列，留下一个空格。你可以使用python编写一个解决八数码问题的程序。

以下是一个使用广度优先搜索算法（BFS）解决八数码问题的示例代码：

from collections import deque

# 定义目标状态
goal_state = [[1, 2, 3], [4, 5, 6], [7, 8, 0]]

# 定义可移动的方向
directions = [(0, -1), (1, 0), (0, 1), (-1, 0)]  # 左、下、右、上

# 检查当前状态是否为目标状态
def is_goal_state(state):
    return state == goal_state

# 找到空格的位置
def find_blank(state):
    for i in range(3):
        for j in range(3):
            if state[i][j] == 0:
                return i, j

# 移动方块
def move(state, direction):
    blank_i, blank_j = find_blank(state)
    new_i = blank_i + direction[0]
    new_j = blank_j + direction[1]
    if 0 <= new_i < 3 and 0 <= new_j < 3:
        new_state = [row[:] for row in state]  # 创建新的状态副本
        new_state[blank_i][blank_j], new_state[new_i][new_j] = new_state[new_i][new_j], new_state[blank_i][blank_j]
        return new_state
    else:
        return None

# 广度优先搜索
def bfs(initial_state):
    queue = deque()
    visited = set()
    queue.append((initial_state, []))
    while queue:
        state, path = queue.popleft()
        visited.add(tuple(map(tuple, state)))
        if is_goal_state(state):
            return path
        for direction in directions:
            new_state = move(state, direction)
            if new_state and tuple(map(tuple, new_state)) not in visited:
                queue.append((new_state, path + [direction]))

    return None

# 测试
initial_state = [[2, 8, 3], [1, 6, 4], [7, 0, 5]]
path = bfs(initial_state)
print("移动路径：", path)