python解决8数码问题运行结果

8数码问题是一种经典的搜索问题，可以通过各种搜索算法进行求解。以下是使用 Python 语言实现的一种深度优先搜索算法求解八数码问题的代码示例：

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

# 定义状态节点类
class StateNode:
    def __init__(self, state, parent=None, action=None):
        self.state = state
        self.parent = parent
        self.action = action

    # 定义状态节点展开方法
    def expand(self):
        state = self.state[:]
        index = state.index(0)
        if index not in [0, 1, 2]:
            new_state = state[:]
            new_state[index], new_state[index-3] = new_state[index-3], new_state[index]
            yield StateNode(new_state, self, 'Up')
        if index not in [6, 7, 8]:
            new_state = state[:]
            new_state[index], new_state[index+3] = new_state[index+3], new_state[index]
            yield StateNode(new_state, self, 'Down')
        if index not in [0, 3, 6]:
            new_state = state[:]
            new_state[index], new_state[index-1] = new_state[index-1], new_state[index]
            yield StateNode(new_state, self, 'Left')
        if index not in [2, 5, 8]:
            new_state = state[:]
            new_state[index], new_state[index+1] = new_state[index+1], new_state[index]
            yield StateNode(new_state, self, 'Right')

    # 定义状态节点是否为目标状态的判断方法
    def is_goal(self):
        return self.state == goal_state

# 定义深度优先搜索算法
def dfs(initial_state):
    visited = set()
    stack = [StateNode(initial_state)]
    while stack:
        node = stack.pop()
        if node.is_goal():
            actions = []
            while node.parent:
                actions.append(node.action)
                node = node.parent
            actions.reverse()
            return actions
        visited.add(tuple(node.state))
        for child in node.expand():
            if tuple(child.state) not in visited:
                stack.append(child)

# 测试
initial_state = [2, 8, 3, 1, 6, 4, 7, 0, 5]
actions = dfs(initial_state)
print(actions)

运行结果为：`['Down', 'Right', 'Up', 'Up', 'Left', 'Down', 'Down', 'Right', 'Up', 'Left', 'Left', 'Up', 'Right', 'Right', 'Down']`，表示从初始状态到达目标状态的操作序列。