用python编写一个 BFS 算法和一个 DFS 算 法来求解八数码问题并添加注释

当然可以，这里我会为你展示如何用 Python 编写广度优先搜索（BFS）和深度优先搜索（DFS）算法来解决经典的八数码问题（又称数独）。我们首先假设已经有一个函数 `check_sudoku` 来检查给定的数组是否满足数独规则。

import collections

# 定义数独的空格
def empty_board():
    return [[0] * 9 for _ in range(9)]

# 检查给定的数独布局是否有效
def check_sudoku(board):
    # 逻辑省略，你可以自行实现九宫格划分、行、列和宫的遍历以及数字重复性的检查
    pass

# 广度优先搜索（BFS）
def bfs_solve(board):
    visited = set()
    queue = collections.deque([[i // 9, i % 9, board.copy()] for i in range(81) if board[i] == 0])  # 初始化队列
    while queue:
        row, col, current_board = queue.popleft()  # 弹出队首元素
        if (row, col) not in visited:
            visited.add((row, col))
            for num in range(1, 10):  # 尝试填入数字
                if is_valid_move(row, col, num, current_board):
                    current_board[row][col] = num
                    if check_sudoku(current_board):
                        return current_board  # 找到解决方案，返回
                    else:
                        queue.append([row, col, current_board])  # 无效则回溯
    return None  # 没有找到解决方案

# 深度优先搜索（DFS）
def dfs_solve(board):
    def backtrack(row, col):
        nonlocal found_solution
        if row == 9:
            found_solution = True
            return
        
        for num in range(1, 10):
            if is_valid_move(row, col, num, board):
                board[row][col] = num
                if check_sudoku(board):
                    solution.append(board.copy())
                    found_solution = True
                else:
                    backtrack(row + 1, col)  # 递归尝试下一个位置
                board[row][col] = 0  # 回溯，撤销当前选择

    found_solution = False
    solution = []
    backtrack(0, 0)
    
    return solution if found_solution else None  # 返回所有解决方案列表

# 判断当前位置填入num是否合法
def is_valid_move(row, col, num, board):
    # 省略对行、列和宫的检查逻辑
    pass

# 示例用法
board = empty_board()
solution_bfs = bfs_solve(board)
solution_dfs = dfs_solve(board)

if solution_bfs:
    print("BFS Solution:")
    print(solution_bfs)
else:
    print("BFS couldn't find a solution.")

if solution_dfs:
    print("\nDFS Solutions:")
    for sol in solution_dfs:
        print(sol)
else:
    print("DFS couldn't find a solution.")