八皇后问题_利用Python生成器完美分析解决

文章目录什么是八皇后问题？一、生成器是什么，如何使用？二、如何分析这种问题将其转化为程序？1.找到回溯问题的基线2.找到排查皇后位置的冲突条件3.找到问题迭代的条件4.了解列表类型的特殊之处3.如何将找到的结果反馈出来？3.完整代码总结什么是八皇后问题？八皇后问题（英文：Eight queens），是由国际象棋棋手马克斯·贝瑟尔于1848年提出的问题，是回溯算法的典型案例。问题表述为：在8×8格的

PittDing

1125人浏览 · 2022-05-10 22:11:08

PittDing · 2022-05-10 22:11:08 发布

提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档

什么是八皇后问题？

八皇后问题（英文：Eight queens），是由国际象棋棋手马克斯·贝瑟尔于1848年提出的问题，是回溯算法的典型案例。
问题表述为：在8×8格的国际象棋上摆放8个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。高斯认为有76种方案。1854年在柏林的象棋杂志上不同的作者发表了40种不同的解，后来有人用图论的方法解出92种结果。如果经过±90度、±180度旋转，和对角线对称变换的摆法看成一类，共有42类。计算机发明后，有多种计算机语言可以编程解决此问题。

一、生成器是什么，如何使用？

生成器是专门用于迭代的函数，相应的能够作为生成器的函数必须带有yield关键字，那么有了生成器有什么好处呢？

我们先看一个示例：
从列表里找同5相同的一个数将其索引号打印出来

list1 = [1,2,3,4,5,6,3,4,2,5,7,5,8,5]

def findNumber(lis1,iNum):
    for l1 in range(len(list1)):
        if list1[l1] == iNum:
            return l1

print(findNumber(list1, 5));

上例中我将找到的索引数利用Return 找了出来，这个非常简单

那么我们增加点难度，将所有与5相同的索引号通过一个列表打印出来应该怎么做呢？

此时最先想法是用Return语句已经不合适了，因为一旦Return了那列表查询就结束了，要再调用只是重新来一次，这样后面的索引我们永远也拿不到了~
总有方法可以办到，我们可以创建一个列表，然后在For 语句里去一个个查找将找到的索引号加入到列表里不就完成了？

list1 = [1,2,3,4,5,6,3,4,2,5,7,5,8,5]
list2 =[]

def findNumber(lis1,iNum):

    for l1 in range(len(list1)):
        if list1[l1] == iNum:
            list2.append(l1);

    
findNumber(list1, 5)
print(list2);

这也非常完美完成了任务，只是为了找到所要的结果多生成了一个列表。

那么我们再提高下难度，假如我要找的索引号很多，并且我只想先知道前面的几个数，后面的数后面再说，应该怎么办呢？（其实这种情况同样适用于我要找的列表很大，如果一次计算出来会耽误很多时间并且会占用很大内存，而我只想得到一个结果再找下一个结果，这样就没必要占用很多资源去一次性处理没有数据）

这时候就比较复杂了，怎么能让一个函数运行稍微暂停下呢，没有这样的函数吧？
这就需要引入生成器这样强大的功能了，它可以完美解决以上的问题：

我们先来看下代码：

list1 = [1,2,3,4,5,6,3,4,2,5,7,5,8,5]


def findNumber(lis1,iNum):
    for l1 in range(len(list1)):
        if list1[l1] == iNum:
            yield l1


print(list(findNumber(list1, 5)));

通过与上述Return示例的函数进行对比，我们发现函数仅仅是将return更改成了yield关键字，而后我们就可以通过List函数将结果生成列表了

通过对比我们可以发现yield与Return功能有相似之处，都可以返回一个数字，
不同之处在于，yield在返回数字之后我们仍然可以继续进行迭代让返回继续进行

list1 = [1,2,3,4,5,6,3,4,2,5,7,5,8,5]


def findNumber(lis1,iNum):
    for l1 in range(len(list1)):
        if list1[l1] == iNum:
            yield l1

index = findNumber(list1, 5);
print(next(index));
print("i was dealing with the result")
print(next(index));
print("i was dealing with the result")
print(next(index));
print("i was dealing with the result")

将此例与上述的For循环列表进行对比，我们发现其实也没有多大变化，仅仅是在找到索引号后我们利用yield返回数值而已。

但是在功能实现上已经不一样了，前例的For循环在运行时只能是一次性的得到结果，我们不能让其暂停下结果，而如果换成yield后就完全不一样了，我们可以”随取随用“了，就好像我们不用因为吃饭而必须将一整天的面包全部吃下，而是将面包切片，如果我们饿了就一片一片拿过来吃。这太方便了

下面我们就来看下生成器如何解决八皇后的问题：

二、如何分析这种问题将其转化为程序？

首先分析下问题解决方式，8*8的棋盘依次放下一个皇后，我们可以想象生成的结果都可以由8个长度的列表表示，其中索引0-7分别表示在每一列上的列数，而这个列表在每个索引上的数值就可以表示在每一列上的皇后的行位置。这样就可以完美表示一个可能的答案。注意，生成的结果我们尽量在一个小的数据类型上表达，我们可以用一个二维列表表示结果，但列表的维数越多复杂程序及运算性能损耗越多。在放下一个皇后时保证其位置不会与前面所有的皇后有干涉，就是不能被前面的皇后吃到。这里就隐藏到几个条件：

有一个判断条件，就是在放皇后的时候要判断其位置是否与前面皇后的位置有干涉
当找到一个位置时就需要将位置与前面的位置叠加到在下一次找位置时做判断
当找够8个位置时需要将所得到的位置结果保留起来

上述的几个条件整理起来就是我们的解决方法，整理如下：

1.找到排查皇后位置的冲突条件

通过确认冲突条件我们可以确认所找到的位置是否是我们需要的，此处冲突条件是当前位置与前面所有的皇后位置不冲突
如下示例：我们将皇后的位置组合成一个列表，然后通过条件判断所输入的位置与列表内皇后位置是否有冲突
冲突的条件是，当前位置与前面的位置不在同一行且，当前位置不在前面皇后所在位置的对角线上。

# 确认冲突的条件
def conflict(list1,y):
    len1 = len(list1)
    for var in range(len1):
        if y == list1[var] or abs(y-list1[var]) == abs(len1-var) :
            return True;
    return False;

2.找到回溯问题的基线

首先根据八次寻找位置我们确定需要构建递归函数，此函数定义了每次回溯寻找位置的方法，而回溯问题的基线就是其结束点，即第8次找位置的方法，其与前面的方法略有不同，需要定义回溯结束的条件，在此问题中基线就是我们已经找到了8个位置

def FoundQueen(List1,m):
    print("list1 value is",List1)
    for var1 in range(8):
        
        if not conflict(List1, var1):
            if len(List1)==m-1 :#基线判断，当找到最后一个皇后位置后应当终止递归函数并返回
                print("search completeed")
                
                yield [var1];

3.找到回溯问题的条件

我们在编写递归函数的时候需要确认下递归调用的条件，当找到与前面皇后不冲突的位置后，在下一次调用递归函数时就需要将刚找到的位置加入到递归的参数中。

#确认最后的基线及迭代条件
def FoundQueen(List1,m):
    print("list1 value is",List1)
    for var1 in range(8):
        
        if not conflict(List1, var1): 
            if len(List1)==m-1 :
                print("search completeed")
                
                yield [var1];
            else:#当找到的位置并非是最后一个皇后时，应当继续调用递归函数，同时将找到的位置加入到下一次递归函数的列表中
                List2=(List1+[var1]).copy();
                print(List2)
                for result in FoundQueen(List2, m):
                    yield [var1]+result;

4.了解列表类型的特殊之处

我们首先需要明确一下可更改对象与不可更改对象的概念：

可更改对象：其存储的内存地址不会因为其数值变化而改变，简言之就是，当更改数值时其存储的内存地址是不会变的；列表，字典数据类型是可更改对象

a = [1,2,3,4]
print(id(a));#id()用于找出变量所在的内存地址
a.append(5);
print(id(a));

输出结果如下：

2455242793984
2455242793984

不可更改对象：类推出来，其存储的内存地址会因为其数值的变化而发生改变，简言之就是当你更改其数值后，其内部的内存地址也随之更改了。整数，字符串及元组都是不可更改对象

a = 5;
print(id(a));
a=1;
print(id(a));

输出如下
1712037888368
1712037888240

但这样的区别对功能实现上有什么影响吗？来看个示例

a = [1,2,3,4]

def printAddress(var):

    print(id(var));

print(id(a));
a.append(5);
printAddress(a);

b = 5;
print(id(b));
b = 4;
printAddress(b);

3006964425088
3006964425088
3006912463216
3006912463184

从上述的结果可以看出来，当可变对象作为参数输入到函数内部时，函数内部是引用的变量的内存地址，当其数值在函数内变化时变量的数值也发生了变化，这表示当将可变对象传送到函数后其数值可能会发生变化
当不可变对象作为参数输入到函数内部后，当值发生变化后其与外部的变量已经没有关系了，因为函数内部已经引用了另一个内存地址，已经与前面的变量没有关联。

所以在我们的示例中，递归函数在调用后面的函数时我们对前面的列表进行了一次额外的Copy，这个函数的功能就是为后面的参数重新分配一个内存地址，将后面列表与前面的列表变量关第打断，否则后面的更改了数值前面的列表会莫名的被更改，导致前面的函数运算异常，在应用列表及字典时应额外注意这个问题，否则会发生异常但不会报警。如下示例

   else:#当找到的位置并非是最后一个皇后时，应当继续调用递归函数，同时将找到的位置加入到下一次递归函数的列表中
                List2=(List1+[var1]).copy();#重新生成一个列表并仅将List1数值复制过来，将列表前后的关系打断
                for result in FoundQueen(List2, m):
                    yield [var1]+result;

3.如何将找到的结果反馈出来？

从回溯问题的基线来开始讨论：当找到了最后一个皇后位置，我们就需要将所有的数值返回出去生成一个列表，所以在基线上我们将最后皇后的位置创建列表并返回到上级调用
再在上级递归函数上看下如何返回列表，其需要将本次找到的皇后位置和其调用递归函数返回的位置列表返回到上级，这样在最初调用时我们就可以正常得到一组满足条件的皇后位置列表

def FoundQueen(List1,m):
    for var1 in range(8):
        
        if not conflict(List1, var1): 
            if len(List1)==m-1 : 
                yield [var1];#基线上的列表返回
            else:
                List2=(List1+[var1]).copy();
                for result in FoundQueen(List2, m):
                    yield [var1]+result;#递归函数上的列表返回

我们也可以考虑在基线条件上直接将List1及最后的皇后位置全部一次性返回，这样也可以容易理解，代码如下：

#确认最后的基线及迭代条件
def FoundQueen(List1,m):
    for var1 in range(8):
        if not conflict(List1, var1): 
            if len(List1)==m-1 :
                yield List1+[var1];#一次性返回所有的皇后位置
            else:
                List2=(List1+[var1]).copy();
                for result in FoundQueen(List2, m):
                    yield result;#上级调用函数仅将结果返回即可

3.完整代码

代码如下：

#确认最后的基线及迭代条件
def FoundQueen(List1,m):
    for var1 in range(8):
        
        if not conflict(List1, var1): 
            if len(List1)==m-1 :
                yield [var1];
            else:
                List2=(List1+[var1]).copy();
                for result in FoundQueen(List2, m):
                    yield [var1]+result;
        
# 确认冲突的条件
def conflict(list1,y):
    len1 = len(list1)
    for var in range(len1):
        if y == list1[var] or abs(y-list1[var]) == abs(len1-var) :
            return True;
    return False;

queens = list(FoundQueen([], 8))
print(queens);
print(len(queens));

该处使用的url网络请求的数据。

输出结果如下：

[[0, 4, 7, 5, 2, 6, 1, 3], [0, 5, 7, 2, 6, 3, 1, 4], [0, 6, 3, 5, 7, 1, 4, 2], [0, 6, 4, 7, 1, 3, 5, 2], [1, 3, 5, 7, 2, 0, 6, 4], [1, 4, 6, 0, 2, 7, 5, 3], [1, 4, 6, 3, 0, 7, 5, 2], [1, 5, 0, 6, 3, 7, 2, 4], [1, 5, 7, 2, 0, 3, 6, 4], [1, 6, 2, 5, 7, 4, 0, 3], [1, 6, 4, 7, 0, 3, 5, 2], [1, 7, 5, 0, 2, 4, 6, 3], [2, 0, 6, 4, 7, 1, 3, 5], [2, 4, 1, 7, 0, 6, 3, 5], [2, 4, 1, 7, 5, 3, 6, 0], [2, 4, 6, 0, 3, 1, 7, 5], [2, 4, 7, 3, 0, 6, 1, 5], [2, 5, 1, 4, 7, 0, 6, 3], [2, 5, 1, 6, 0, 3, 7, 4], [2, 5, 1, 6, 4, 0, 7, 3], [2, 5, 3, 0, 7, 4, 6, 1], [2, 5, 3, 1, 7, 4, 6, 0], [2, 5, 7, 0, 3, 6, 4, 1], [2, 5, 7, 0, 4, 6, 1, 3], [2, 5, 7, 1, 3, 0, 6, 4], [2, 6, 1, 7, 4, 0, 3, 5], [2, 6, 1, 7, 5, 3, 0, 4], [2, 7,
3, 6, 0, 5, 1, 4], [3, 0, 4, 7, 1, 6, 2, 5], [3, 0, 4, 7, 5, 2, 6, 1], [3, 1, 4, 7, 5, 0, 2, 6], [3, 1, 6, 2, 5, 7, 0, 4], [3, 1, 6, 2, 5, 7,
4, 0], [3, 1, 6, 4, 0, 7, 5, 2], [3, 1, 7, 4, 6, 0, 2, 5], [3, 1, 7, 5, 0, 2, 4, 6], [3, 5, 0, 4, 1, 7, 2, 6], [3, 5, 7, 1, 6, 0, 2, 4], [3, 5, 7, 2, 0, 6, 4, 1], [3, 6, 0, 7, 4, 1, 5, 2], [3, 6, 2, 7, 1, 4, 0, 5], [3, 6, 4, 1, 5, 0, 2, 7], [3, 6, 4, 2, 0, 5, 7, 1], [3, 7, 0, 2, 5, 1, 6, 4], [3, 7, 0, 4, 6, 1, 5, 2], [3, 7, 4, 2, 0, 6, 1, 5], [4, 0, 3, 5, 7, 1, 6, 2], [4, 0, 7, 3, 1, 6, 2, 5], [4, 0, 7, 5, 2, 6, 1, 3], [4, 1, 3, 5, 7, 2, 0, 6], [4, 1, 3, 6, 2, 7, 5, 0], [4, 1, 5, 0, 6, 3, 7, 2], [4, 1, 7, 0, 3, 6, 2, 5], [4, 2, 0, 5, 7, 1, 3, 6], [4, 2, 0, 6, 1, 7, 5, 3], [4, 2, 7, 3, 6, 0, 5, 1], [4, 6, 0, 2, 7, 5, 3, 1], [4, 6, 0, 3, 1, 7, 5, 2], [4, 6, 1, 3, 7, 0, 2, 5], [4, 6, 1, 5, 2, 0, 3, 7], [4, 6, 1, 5, 2, 0, 7, 3], [4, 6, 3, 0, 2, 7, 5, 1], [4, 7, 3, 0, 2, 5, 1, 6], [4, 7, 3, 0, 6, 1, 5, 2], [5, 0, 4, 1, 7, 2, 6, 3], [5, 1, 6, 0,
2, 4, 7, 3], [5, 1, 6, 0, 3, 7, 4, 2], [5, 2, 0, 6, 4, 7, 1, 3], [5, 2, 0, 7, 3, 1, 6, 4], [5, 2, 0, 7, 4, 1, 3, 6], [5, 2, 4, 6, 0, 3, 1, 7], [5, 2, 4, 7, 0, 3, 1, 6], [5, 2, 6, 1, 3, 7, 0, 4], [5, 2, 6, 1, 7, 4, 0, 3], [5, 2, 6, 3, 0, 7, 1, 4], [5, 3, 0, 4, 7, 1, 6, 2], [5, 3, 1, 7, 4, 6, 0, 2], [5, 3, 6, 0, 2, 4, 1, 7], [5, 3, 6, 0, 7, 1, 4, 2], [5, 7, 1, 3, 0, 6, 4, 2], [6, 0, 2, 7, 5, 3, 1, 4], [6, 1, 3, 0, 7, 4, 2, 5], [6, 1, 5, 2, 0, 3, 7, 4], [6, 2, 0, 5, 7, 4, 1, 3], [6, 2, 7, 1, 4, 0, 5, 3], [6, 3, 1, 4, 7, 0, 2, 5], [6, 3, 1, 7, 5, 0, 2, 4], [6, 4, 2, 0, 5, 7, 1, 3], [7, 1, 3, 0, 6, 4, 2, 5], [7, 1, 4, 2, 0, 6, 3, 5], [7, 2, 0, 5, 1, 4, 6, 3], [7, 3, 0, 2, 5, 1, 6, 4]]
92

总结

八皇后问题是一个经典的回溯案例，同时也是计算机编程的经典案例，他可以很好的考察我们对递归及生成器的理解程度。针对这个问题积极思考及自主演练非常重要，如果没有整理思路很可能想很长时间也没有解决办法，想到办法又因为对编程理解不熟悉而得不到结果，但主动编程仍非常必要，这会加深你对一门语言的理解，同时也可以对比所编的程序是否是最快的，是否是最简洁的，是否是最省力的，总这花费一些时间在上面会受益良多。