回溯递归实现骑士复制填充棋盘时陷入循环的问题排查

问题描述 #

编写Python代码实现国际象棋骑士每次移动时复制出2个，直至填满整个棋盘。采用回溯法遍历所有可能的位置组合，但程序很快陷入循环，重复相同位置，无法推进。

原代码 #

alphabet = ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z']

def print_board(board):
    for row in board:
        print(" ".join(str(square) for square in row))

def is_valid_move(x, y, board_size):
    return 0 <= x < board_size and 0 <= y < board_size

def knight_moves(board, position):
    possible_moves = []
    moves = [(-2, -1), (-2, 1), (-1, -2), (-1, 2), (1, -2), (1, 2), (2, -1), (2, 1)]
    for move in moves:
        new_x = position[0] + move[0]
        new_y = position[1] + move[1]
        if is_valid_move(new_x, new_y, len(board)) and board[new_x][new_y] == 'E':
            possible_moves.append((new_x, new_y))
    return possible_moves

def convert_to_chess_row(row_number, board_length):
    return board_length - row_number

def is_filled(board):
    for row in board:
        for e in row:
            if e == 'E':
                return False
    return True

def backtrack(board, current_pos, moves):
    if is_filled(board):
        return True
    possible_moves = knight_moves(board, current_pos)
    if len(possible_moves) >= 2:
        board[current_pos[0]][current_pos[1]] = 'F'
        for pos_first in possible_moves:
            for pos_second in possible_moves:
                if pos_first == pos_second:
                    continue
                board[pos_first[0]][pos_first[1]] = 'K'
                board[pos_second[0]][pos_second[1]] = 'K'
                print(str(pos_first) + str(pos_second))
                print_board(board)
                print("\n\n")
                if backtrack(board, pos_first, moves):
                    return True
                if backtrack(board, pos_second, moves):
                    return True
                board[pos_first[0]][pos_first[1]] = 'E'
                board[pos_second[0]][pos_second[1]] = 'E'
        board[current_pos[0]][current_pos[1]] = 'E'
    return False

def play(board_size: int, pos: str):
    from typing import Optional, List
    board = [['E' for _ in range(board_size)] for _ in range(board_size)]
    position = pos[-2:]
    pos_tuple = (convert_to_chess_row(int(position[1]), len(board)), alphabet.index(position[0]))
    if not is_valid_move(pos_tuple[0], pos_tuple[1], len(board)):
        return None
    moves = []
    board[pos_tuple[0]][pos_tuple[1]] = 'K'
    backtrack(board, pos_tuple, moves)
    if is_filled(board):
        return moves
    else:
        return None

print(play(6, "qKc3"))

问题根源分析 #

1. 数学可行性问题：6x6棋盘共36个格子，初始1个骑士，每次操作新增2个骑士，总骑士数始终为1+2k（奇数），无法等于36（偶数），因此不存在解，程序会无限回溯尝试不可能的路径。
2. 回溯逻辑错误：
   • 每次复制出两个骑士后，递归仅处理第一个新骑士的路径，忽略了两个骑士同时存在的并行扩展需求，导致搜索路径完全偏离预期。
   • 双重循环遍历所有位置对，会重复处理(pos1,pos2)和(pos2,pos1)这类等价组合，造成大量重复计算和循环。
3. 状态管理混乱：递归调用第二个骑士时，棋盘已经被第一个递归修改过，状态未重置就再次递归，导致后续搜索基于错误的棋盘状态进行。

修复思路 #

1. 先做可行性检查 #

在play函数开头，先判断棋盘总格子数是否符合1+2k的形式（即总格子数为奇数），如果是偶数直接返回无解，避免无效搜索：

def play(board_size: int, pos: str) -> Optional[List[str]]:
    total_cells = board_size * board_size
    # 初始1个K，每次加2个，总数量必须是奇数
    if total_cells % 2 == 0:
        print("棋盘格子数为偶数，无法通过每次新增2个骑士填满")
        return None
    # 剩余原代码...

2. 调整回溯逻辑，支持双骑士并行扩展 #

修改回溯函数，通过维护活跃骑士列表，模拟多个骑士同时扩展的过程，避免串行处理的错误：

def backtrack(board, active_knights, moves):
    if is_filled(board):
        return True
    # 遍历每个活跃骑士的可能移动
    for idx, knight_pos in enumerate(active_knights):
        possible_moves = knight_moves(board, knight_pos)
        # 每个骑士需要选2个不同的空位置生成新骑士，自身标记为已使用
        if len(possible_moves) >= 2:
            board[knight_pos[0]][knight_pos[1]] = 'F'
            # 遍历不重复的位置对，避免重复计算
            for i in range(len(possible_moves)):
                for j in range(i+1, len(possible_moves)):
                    pos1 = possible_moves[i]
                    pos2 = possible_moves[j]
                    board[pos1[0]][pos1[1]] = 'K'
                    board[pos2[0]][pos2[1]] = 'K'
                    # 生成新的活跃骑士列表：移除当前骑士，加入两个新骑士
                    new_active = active_knights[:idx] + active_knights[idx+1:] + [pos1, pos2]
                    if backtrack(board, new_active, moves):
                        return True
                    # 回溯状态
                    board[pos1[0]][pos1[1]] = 'E'
                    board[pos2[0]][pos2[1]] = 'E'
            # 恢复当前骑士状态
            board[knight_pos[0]][knight_pos[1]] = 'K'
    return False

3. 修改play函数的调用逻辑 #

将初始活跃骑士列表传入回溯函数：

def play(board_size: int, pos: str) -> Optional[List[str]]:
    from typing import Optional, List
    total_cells = board_size * board_size
    if total_cells % 2 == 0:
        print("棋盘格子数为偶数，无法通过每次新增2个骑士填满")
        return None
    board = [['E' for _ in range(board_size)] for _ in range(board_size)]
    position = pos[-2:]
    pos_tuple = (convert_to_chess_row(int(position[1]), len(board)), alphabet.index(position[0]))
    if not is_valid_move(pos_tuple[0], pos_tuple[1], len(board)):
        return None
    moves = []
    board[pos_tuple[0]][pos_tuple[1]] = 'K'
    # 初始活跃骑士列表只有起始位置
    if backtrack(board, [pos_tuple], moves):
        return moves
    else:
        print("未找到可行解")
        return None

关键说明 #

• 原问题中6x6棋盘无解，建议测试3x3（9个格子，1+2*4=9）这类奇数格子数的棋盘。
• 新的回溯逻辑通过维护活跃骑士列表，准确模拟了多个骑士同时扩展的过程，避免了原逻辑的路径偏离问题。
• 遍历位置对时使用i<j的方式，避免重复处理等价组合，减少无效搜索次数。

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