Python跳棋游戏合法跳步查找算法：适配方案与实现概念问询

核心适配算法与编程概念 #

• 深度优先搜索（DFS）/递归：这是实现连跳逻辑的核心。每次完成一次合法跳步后，新位置可能仍具备跳步条件，需要递归地从新位置出发重复检查，直到没有可跳路径为止。
• 状态回溯：递归过程中需临时修改棋盘状态（如移除被跳过的敌方棋子、移动当前棋子到目标位置），递归结束后必须恢复原状态，避免干扰其他方向的跳步检查。

具体实现步骤 #

1. 基础单步跳检查函数
   先实现一个函数，用于验证单个方向（西北/东北）是否满足跳步条件：

   • 计算中间位置（敌方棋子应处的位置）和目标空位坐标
   • 验证中间位置在棋盘范围内且为敌方棋子
   • 验证目标位置在棋盘范围内且为空
     满足所有条件则返回目标位置，否则返回空值。

2. 递归查找所有连跳路径
   编写递归函数遍历所有可能的连跳路径：

   • 对当前位置的西北、东北方向逐一调用单步跳检查函数
   • 对每个合法目标位置：
     • 临时修改棋盘状态，模拟跳步操作
     • 将目标位置加入结果列表，再递归调用自身查找后续跳步
     • 递归返回后，将后续跳步的所有位置合并到结果中
     • 恢复棋盘原状态（回溯），继续检查其他方向
   • 最终返回所有合法的跳步位置（含单步跳和多步连跳的所有可达位置）

3. 整合现有逻辑
   将递归得到的跳步位置列表，与你已实现的相邻空位移动列表合并，即可得到完整的合法移动选项。

简化版代码示例 #

def check_single_jump(current_pos, direction, board, player):
    # 定义方向偏移：(中间步偏移, 目标步偏移)
    mid_offset, target_offset = direction
    mid_x = current_pos[0] + mid_offset[0]
    mid_y = current_pos[1] + mid_offset[1]
    target_x = current_pos[0] + target_offset[0]
    target_y = current_pos[1] + target_offset[1]

    # 边界检查
    board_rows, board_cols = len(board), len(board[0])
    if not (0 <= mid_x < board_rows and 0 <= mid_y < board_cols):
        return None
    if not (0 <= target_x < board_rows and 0 <= target_y < board_cols):
        return None

    # 敌方棋子判定
    enemy = 'O' if player == 'X' else 'X'
    if board[mid_x][mid_y] == enemy and board[target_x][target_y] == '.':
        return (target_x, target_y)
    return None

def find_all_valid_jumps(current_pos, board, player, visited=None):
    if visited is None:
        visited = set()
    valid_jumps = []
    # 定义需检查的方向：西北、东北
    check_directions = [ ((-1, -1), (-2, -2)), ((-1, 1), (-2, 2)) ]

    for dir_pair in check_directions:
        target_pos = check_single_jump(current_pos, dir_pair, board, player)
        if target_pos and target_pos not in visited:
            # 临时修改棋盘状态
            orig_current = board[current_pos[0]][current_pos[1]]
            orig_mid = board[current_pos[0]+dir_pair[0][0]][current_pos[1]+dir_pair[0][1]]
            board[current_pos[0]][current_pos[1]] = '.'
            board[current_pos[0]+dir_pair[0][0]][current_pos[1]+dir_pair[0][1]] = '.'
            board[target_pos[0]][target_pos[1]] = player

            # 递归查找后续跳步
            sub_jumps = find_all_valid_jumps(target_pos, board, player, visited | {target_pos})
            valid_jumps.append(target_pos)
            valid_jumps.extend(sub_jumps)

            # 回溯恢复棋盘
            board[current_pos[0]][current_pos[1]] = orig_current
            board[current_pos[0]+dir_pair[0][0]][current_pos[1]+dir_pair[0][1]] = orig_mid
            board[target_pos[0]][target_pos[1]] = '.'

    # 去重后返回结果
    return list(set(valid_jumps))

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