Python 8-Puzzle问题BFS实现故障求助：无法扩展子节点

问题描述 #

实现基于BFS和DFS的8数码求解器时，BFS出现异常：仅输出初始节点的两个可能子节点后，终端持续运行无输出，无法从可行分支继续扩展求解路径。

原代码 #

import copy

#This is the only file you need to work on. You do NOT need to modify other files

# Below are the functions you need to implement. For the first project, you only need to finish implementing bfs() and dfs()

#here you need to implement the Breadth First Search Method
def bfs(puzzle):
    list = []
    #initialization 
    state = copy.deepcopy(puzzle)
    goal = [0,1,2,3,4,5,6,7,8]
    possible_move = [[1,3],[0,2,4],[1,5],[0,4,6],[1,3,5,7],[2,4,8],[3,7],[4,6,8],[5,7]]
     
     #appending the first state 
    queue = []
    queue = [Node(state)]
    
    for node in queue[:]:
      print('the state of this game position is:\n ' + str(node.state))
      loop = True
      notFound = True
      l = 0

    while loop:
        for node in queue:
            #blank index in each state 
            blank = node.state.index(8)
            print('the index of the blank is '+ str(blank))
            #The possible position 
            possible_pos = possible_move[blank]
            print('possible pos '+ str(possible_pos))
            if state != goal:
                for i in possible_pos:
                    possible_sw = copy.deepcopy(node.state)
                    print('index swap = '+ str(i))
                    
                    temp = possible_sw[i]
                    possible_sw[i] = 8
                    possible_sw[blank] = temp
                
                    print('the child nodes is ' + str(possible_sw))
                    node.insertChild(possible_sw)
                    
                    if possible_sw == goal:
                        print('end')
                        notFound = False
                        loop = False
                
    #check each child and find the goal state 
        for node in queue[:]:
            for child_state in node.children:
                if child_state == [0,1,2,3,4,5,6,7,8]:
                    final_state = child_state
                    print('the final state is '+ str(final_state.state))
            queue.pop(0)
            
        #find the parent path 
        while node.parent and loop is False:
            sol_path = final_state.state
            list.append(sol_path.index(8))
            if final_state.parent is not None:
                final_state = final_state.parent
            else: 
                parent = False
                list.reverse()
                list.pop(0)
                print('moves list '+ str(list))
    
    return list

#here you need to implement the Depth First Search Method
def dfs(puzzle):
    list = []
    return list

#This will be for next project
def astar(puzzle):
    list = []
    return list

def swap(list, pos1, pos2):
    list[pos1],list[pos2] = list[pos2], list[pos1]
    return list
        
class Node:
    def __init__(self,state,parent = None):
        self.parent = parent
        self.state = state
        self.children = []
        
    def insertChild(self, child_state):
        self.children.append(Node(child_state,self))

#test cases 

# p =[0, 1, 2, 3, 4, 5, 8, 6, 7]
p = [0, 1, 2, 3, 4, 5, 6, 8, 7]
#p = [0, 1, 2, 3, 8, 4, 6, 7, 5]
#p =[0, 4, 1, 3, 8, 2, 6, 7, 5]
bfs(p)
print("+++++++++++++++++++++")
#dfs(p)

核心错误分析 #

1. 队列未更新：生成子节点后未将其加入BFS队列，导致算法永远只处理初始节点，无法向下扩展。
2. 状态判断无效：用初始状态state和目标对比，而非当前节点的状态，导致即使初始状态不是目标，也会一直生成子节点。
3. 死循环触发：没有记录已访问状态，重复生成相同状态导致队列无限增长；循环终止条件逻辑混乱，找到目标后未正确退出。
4. 路径回溯逻辑错误：回溯代码位置错误，且变量作用域问题导致无法正确追溯路径。

修复后的代码 #

import copy

class Node:
    def __init__(self, state, parent=None):
        self.parent = parent
        self.state = state
        self.children = []
        
    def insertChild(self, child_state):
        self.children.append(Node(child_state, self))

def bfs(puzzle):
    sol_path = []
    goal = [0, 1, 2, 3, 4, 5, 6, 7, 8]
    possible_move = [[1,3],[0,2,4],[1,5],[0,4,6],[1,3,5,7],[2,4,8],[3,7],[4,6,8],[5,7]]
    
    # 初始化队列和已访问集合
    queue = [Node(copy.deepcopy(puzzle))]
    visited = set()
    visited.add(tuple(puzzle))
    
    while queue:
        current_node = queue.pop(0)  # BFS用队列，弹出队首
        current_state = current_node.state
        
        # 检查是否到达目标
        if current_state == goal:
            # 回溯路径
            while current_node:
                sol_path.append(current_node.state.index(8))
                current_node = current_node.parent
            sol_path.reverse()
            sol_path.pop(0)  # 移除初始状态的空白位置
            print('求解路径的空白移动索引：', sol_path)
            return sol_path
        
        # 生成所有可能的子节点
        blank_idx = current_state.index(8)
        for pos in possible_move[blank_idx]:
            new_state = copy.deepcopy(current_state)
            # 交换空白和目标位置
            new_state[blank_idx], new_state[pos] = new_state[pos], new_state[blank_idx]
            state_tuple = tuple(new_state)
            
            # 避免重复访问
            if state_tuple not in visited:
                visited.add(state_tuple)
                child_node = Node(new_state, current_node)
                current_node.insertChild(child_node)
                queue.append(child_node)
    
    # 无解情况
    print('该状态无解')
    return []

def dfs(puzzle):
    sol_path = []
    goal = [0, 1, 2, 3, 4, 5, 6, 7, 8]
    possible_move = [[1,3],[0,2,4],[1,5],[0,4,6],[1,3,5,7],[2,4,8],[3,7],[4,6,8],[5,7]]
    
    # 初始化栈和已访问集合
    stack = [Node(copy.deepcopy(puzzle))]
    visited = set()
    visited.add(tuple(puzzle))
    
    while stack:
        current_node = stack.pop()  # DFS用栈，弹出栈顶
        current_state = current_node.state
        
        if current_state == goal:
            # 回溯路径
            while current_node:
                sol_path.append(current_node.state.index(8))
                current_node = current_node.parent
            sol_path.reverse()
            sol_path.pop(0)
            print('求解路径的空白移动索引：', sol_path)
            return sol_path
        
        blank_idx = current_state.index(8)
        # 逆序添加，保证DFS的遍历顺序和BFS一致（可选）
        for pos in reversed(possible_move[blank_idx]):
            new_state = copy.deepcopy(current_state)
            new_state[blank_idx], new_state[pos] = new_state[pos], new_state[blank_idx]
            state_tuple = tuple(new_state)
            
            if state_tuple not in visited:
                visited.add(state_tuple)
                child_node = Node(new_state, current_node)
                current_node.insertChild(child_node)
                stack.append(child_node)
    
    print('该状态无解')
    return []

def astar(puzzle):
    sol_path = []
    return sol_path

# 测试用例
p = [0, 1, 2, 3, 4, 5, 6, 8, 7]
print('BFS求解结果：')
bfs(p)
print("+++++++++++++++++++++")
print('DFS求解结果：')
dfs(p)

修复说明 #

1. 队列/栈更新：BFS使用队列（pop(0)），DFS使用栈（pop()），生成子节点后立即加入对应的结构，保证算法能向下扩展。
2. 已访问集合：用tuple存储状态（列表不可哈希），避免重复访问相同状态，防止死循环和冗余计算。
3. 目标判断与路径回溯：在弹出节点时立即检查是否为目标，找到后直接回溯父节点生成路径，逻辑清晰。
4. 代码结构优化：整理变量命名，简化状态交换逻辑，移除无效的循环和判断。

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