Python用迭代（yield）和递归解决八皇后问题

问题

​
国际象棋的皇后行走具有最高的灵活性，可以横、竖、斜共八个方向无限步行走。你需要将国际象棋8个皇后放在棋盘上，条件是任何一个皇后都不能威胁其他皇后，即任何两个皇后都不能吃掉对方。
​
分析：在棋盘的第一行尝试为第一个皇后选择一个位置，再在第二行尝试为第二个皇后选择一个位置，依次类推。在发现无法为一个皇后选择合适的位置后，回溯到前一个皇后，并尝试为它选择另一个位置。当八个皇后都放在棋盘上时即得到一种解。
​

状态表示

用元组（其他序列也可以）表示可能的解（或一部分），例如（1，3，5）表示当前共摆放了三个皇后，第一个皇后在1行1列，第二个皇后在2行3列，第三个皇后在3行5列。
​

冲突检测

​
当前状态state，下一个皇后在下一行的next_x位置，根据皇后的行走规则，如果已有的皇后可以吃掉下一个皇后，则表示有冲突，否则没有。
​
函数conflict定义：接受用状态元组表示的既有皇后的位置，并确定下一个皇后的位置是否会导致冲突。
​

def conflict(state, next_x):
    next_y = len(state)
    for i in range(next_y):
        if abs(state[i] - next_x) in (0, next_y - i):
            return True
    return False

参数 next_x 表示下一个皇后的水平位置（x 坐标，即列），而 next_y 为下一个皇后的垂直位置（y 坐标，即行）。这个函数对既有的每个皇后执行简单的检查：如果下一个皇后与当前皇后的 x 坐标相同或在同一条对角线上，将发生冲突，因此返回True ；如果没有发生冲突，就返回False 。
​
abs(state[i] - next_x) in (0, next_y - i) 表示两个皇后的水平距离为0或等于垂直距离时为真、否则为假。
​

迭代递归

​

def queens(num=8, state=()):
    for pos in range(num):
        if not conflict(state, pos):
           if len(state) == num-1:  # 基线条件
              yield (pos,)
           else:  # 递归条件
              for result in queens(num, state + (pos,)):
                  yield (pos,) + result

​

• 基线条件：最后一个皇后。如果当前已经摆放到最后一个皇后（len(state) == num-1），找到所有不冲突的位置，并返回（yield (pos,)）。
• 处理好基线条件后，可在递归条件中假设来自更低层级（编号更大的皇后）的结果都是正确的。因此，只需在函数queens的基线条件的另一分支返回当前层级的所有正确结果。
• 对于递归调用，向它提供的是由当前行上面的皇后位置组成的元组。对于当前皇后的每个合法位置，递归调用返回的是由下面的皇后位置组成的元组。为了让这个过程不断进行下去，需将当前皇后的位置插入返回的结果开头。
  ​