使用Python BFS实现八数码问题时遭遇哈希错误求助

错误原因 #

你遇到的TypeError: unhashable type: 'list'是因为列表（list）是可变类型，无法被哈希计算，而集合（set）要求存储的元素必须是可哈希的（不可变类型）。你的代码中child.state是二维列表，直接将其加入visited集合就会触发这个错误。

解决方案 #

把所有表示状态的二维列表转换成元组（tuple）——元组是不可变类型，支持哈希计算，可以正常存入集合。需要修改以下几个部分：

1. 初始化状态改用元组 #

将初始状态和目标状态从列表嵌套改为元组嵌套：

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

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

2. 修改子状态生成逻辑 #

在get_children函数中，生成新状态时先将元组转成可修改的列表嵌套，修改后再转回元组：

# 以向下移动为例，其他方向同理
if i != 2:           
    # 把元组状态转成可修改的列表的列表
    state_list = [list(row) for row in node.state]
    state_list[i][j], state_list[i+1][j] = state_list[i+1][j], state_list[i][j]
    # 修改完成后转回元组
    new_state = tuple(tuple(row) for row in state_list)
    children.append(Node(new_state, node))

3. 优化BFS的访问判断逻辑（可选） #

原代码中在添加子节点时判断是否已访问，可能导致重复入队。建议改为取出节点时判断是否已访问，避免无效操作：

while queue:
    node = queue.pop(0)
    if node.state == goal_state:
        return node
    # 若已访问过，直接跳过
    if node.state in visited:
        continue
    visited.add(node.state)
    
    for child in get_children(node):
        queue.append(child)

修改后的完整代码 #

class Node:
    def __init__(self, state, parent):
        self.state = state
        self.parent = parent


def get_children(node):
    children = []

    for i in range(3):
        for j in range(3):
            if node.state[i][j] == 0:
                # 向下移动
                if i != 2:           
                    state_list = [list(row) for row in node.state]
                    state_list[i][j], state_list[i+1][j] = state_list[i+1][j], state_list[i][j]
                    new_state = tuple(tuple(row) for row in state_list)
                    children.append(Node(new_state, node))

                # 向上移动
                if i != 0:           
                    state_list = [list(row) for row in node.state]
                    state_list[i][j], state_list[i-1][j] = state_list[i-1][j], state_list[i][j]
                    new_state = tuple(tuple(row) for row in state_list)
                    children.append(Node(new_state, node))

                # 向右移动
                if j != 2:           
                    state_list = [list(row) for row in node.state]
                    state_list[i][j], state_list[i][j+1] = state_list[i][j+1], state_list[i][j]
                    new_state = tuple(tuple(row) for row in state_list)
                    children.append(Node(new_state, node))

                # 向左移动
                if j != 0:           
                    state_list = [list(row) for row in node.state]
                    state_list[i][j], state_list[i][j-1] = state_list[i][j-1], state_list[i][j]
                    new_state = tuple(tuple(row) for row in state_list)
                    children.append(Node(new_state, node))

    return children


def bfs(initial_state, goal_state):
    queue = [Node(initial_state, None)]
    visited = set()

    while queue:
        node = queue.pop(0)
        if node.state == goal_state:
            return node

        if node.state in visited:
            continue
        visited.add(node.state)

        for child in get_children(node):
            queue.append(child)

    return None


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

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

solution = bfs(initial_state, goal_state)

if solution is not None:
    print("找到解")
    path = []
    node = solution
    while node is not None:
        path.append(node.state)
        node = node.parent

    path.reverse()
    for state in path:
        for row in state:
            print(row)
        print("---")
else:
    print("无解")

内容的提问来源于stack exchange，提问作者Shrey Kumar