八皇后问题（借助Pyhton生成器解决）- Python

文章目录

一、什么是八皇后？

八皇后问题，是一个古老而著名的问题，是回溯算法的典型案例。该问题是国际西洋棋棋手马克斯·贝瑟尔于1848年提出：在8×8格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。
在这里插入图片描述

二、解决思路

八皇后问题是一个经典的数学问题，同时也是一个典型的回溯问题，《Python基础教程》简单的思路是：首先尝试在第1行放置第1个皇后，然后在第2行某个位置放置皇后，依次进行，当发现某行的所有位置都不能防止皇后时，回溯至上一行，试着将上一行皇后放置在其他位置，再考虑下一行皇后的位置。

排列时，是按顺序排列的，也就是一行一行排列，但是列的位置不确定

三、代码实现

序列很小而且是静态的，元祖是一个很好的选择
state 是一个元祖，每个元祖中元素都指示相应行的皇后的位置。
例如，如果 state[0] == 3，那么就表示在第一行的皇后是在第 4 列（从0开始计数）

冲突函数：
已知皇后的位置被传递给 conflict 函数(以状态元祖的形式)
然后由函数判断下一个的皇后的位置会不会有新的冲突

# nextX 代表下一个皇后的水平位置(x坐标或列)
# nextY 代表垂直位置(y坐标或行)
def conflict(state,nextX):
# nextY 中存储的已经包含是皇后的行
    nextY = len(state)
    for i in range(nextY):
    # 如果下一个皇后和正在考虑的前一个皇后的水平距离为0(列相同)
    # 或者等于垂直距离(在一条对角线上)就返回 TRUE，否则就返回 FALSE
        if(abs(state[i] - nextX)in (0,nextY-i)):
            return True
    return False

其中的表达式 abs(state[i] - nextX) in (0 , nextY - i )
理解为：对于第 i 行皇后的位置 state[i]，检查其与第nextY行皇后位置nextX是否是位于同列或对角。
同列时满足：state[i] = nextX，也即 state[i]–nextX = 0；

对角时，有2种情形需要考虑：
其一为第 nextY 行皇后位置出现于state[i]的右对角线，从水平方向上 nextX - state[i] 与垂直方向 nextY – i 相等，即：nextX - state[i]= nextY – i
其二为第 nextY 行皇后位置出现于state[i]的左边对角线，从水平方向上state[i]- nextX 与垂直方向nextY – i 相等，即state[i]- nextX= nextY – i

综上，对角线时满足，abs(state[i] - nextX) in (0 , nextY - i )

从基本情形开始考虑：当剩余最后一个皇后时，遍历它所有可能的位置，并返回没有冲突发生的位置。

def queens(num,state):
    if len(state) == num -1:  #num此处表示皇后总数
        for pos in range(num): #num此处表示遍历所有可能的位置
            if not conflict(state , pos):
            # 以迭代器的形式返回最后一个皇后的所有可能位置
                yield pos
1
2
3
4
5
6

递归解决
基本情形完成之后，需要考虑此时所剩余的皇后不是最后一个的情形，此时由于需要递归调用 queens 函数，则可为前面 queens 函数添加 else 部分，遍历所有可能位置的可能情形，也即将 num 中的所有可能位置加到当前元组中，直至遇到基本情形。
代码如下：

# state 初始化为空元祖
# num 为皇后的总数
def queens(num=8,state=()):
    for pos in range(num):
    # 如果没有发生冲突，进行下步判断
        if not conflict(state,pos):
        # 判断 第 pos 个皇后是否是最后一个皇后
            if len(state) == num -1:
                yield (pos,)
            else:
                for result in queens(num,state+(pos,)):
                    yield (pos,) + result      
12