Python嵌套For循环执行时结果出现冗余元素问题

嘿，我来帮你分析下为什么会从预期的72种变成108种——咱们先理清楚核心逻辑：X先行有9种选择，每个选择后O有8种空位可选，所以合法状态应该是9×8=72种。出现108种，说明你的程序多统计了36种状态，这36种大概率是非法状态或者重复状态，下面是最常见的原因和排查方法：

一、最可能的原因：程序混入了「X连续走两步」的非法状态 #

36正好是从9个位置选2个放X的组合数（C(9,2)=36），这说明你的程序可能在生成过程中，把「X走一步后再走一步」的非法情况也统计进去了。

为什么会出现这种情况？

• 回溯逻辑错误：比如放完O并保存状态后，你正确回溯了O的位置，但忘记回溯X的位置，导致下一轮循环时，棋盘上还保留着上一个X，新的X又被放置，形成两个X的状态。
• 代码笔误：比如在O的走法循环里，不小心把放置'O'写成了放置'X'，导致生成的是两个X的状态。

验证方法： #

随机打印几个状态看看，是否存在棋盘上有两个X但没有O的情况，或者有两个X和一个O的情况（这也是回溯错误导致的）。

修正方案： #

确保每次放置X/O后，都正确回溯棋盘状态。比如正确的代码框架应该是这样的：

# 初始化空棋盘
board = [[' ' for _ in range(3)] for _ in range(3)]
valid_states = []

# 遍历X的所有可能首步位置
for x_row in range(3):
    for x_col in range(3):
        # 放置X
        board[x_row][x_col] = 'X'
        # 遍历O的所有可能首步位置（必须是空位）
        for o_row in range(3):
            for o_col in range(3):
                if board[o_row][o_col] == ' ':
                    # 放置O
                    board[o_row][o_col] = 'O'
                    # 深拷贝棋盘并保存状态（避免后续修改影响已保存的状态）
                    valid_states.append([row.copy() for row in board])
                    # 回溯O的位置
                    board[o_row][o_col] = ' '
        # 回溯X的位置（这一步很关键！）
        board[x_row][x_col] = ' '

# 打印结果数量
print(f"合法状态数量：{len(valid_states)}")  # 应该输出72

二、另一个可能原因：重复统计了等价状态 #

虽然108的数量不太符合对称等价的情况，但如果你的程序没有对旋转/翻转后的等价状态去重，且同时存在重复计数的情况，也可能导致数量增加。不过这种情况通常会导致数量远大于72，所以优先级低于第一种原因。

比如，X走左上角和X走右上角的棋盘，在旋转后是等价的，但如果你的程序把它们当成不同状态统计，不过这不会导致增加36种，所以可能性较低。

三、排查小技巧 #

1. 统计状态时，把棋盘转换成唯一的字符串表示（比如''.join([''.join(row) for row in board])），然后用集合去重，看看去重后的数量是多少：

   state_strings = set(''.join([''.join(row) for row in state]) for state in valid_states)
   print(f"去重后的状态数量：{len(state_strings)}")
   

   如果去重后是72，说明你的程序生成了重复的合法状态；如果去重后是108，说明确实有36种额外的非法状态。

2. 统计非法状态的数量：遍历所有状态，检查每个状态中X和O的数量：

   invalid_count = 0
   for state in valid_states:
       x_count = sum(row.count('X') for row in state)
       o_count = sum(row.count('O') for row in state)
       if x_count != 1 or o_count != 1:
           invalid_count += 1
   print(f"非法状态数量：{invalid_count}")  # 如果是36，就对应第一种原因
   

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