少说话多写代码之Python学习055——类的成员(生成器的应用举例)

 发布日期:2018-12-13 12:23:26  阅读次数:阅读数:553  来源:
版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/yysyangyangyangshan/article/details/84867615

我们来看一个有趣的问题:八皇后问题。这里的皇后是国际象棋中的皇后,虽然我只会玩中国象棋而不会玩国际象棋。这个问题和会不会国际象棋没有关系。
八皇后问题描述:如何能够在 8×8 的国际象棋棋盘上放置八个皇后,使得任何一个皇后都无法直接吃掉其他的皇后?为了达到此目的,任两个皇后都不能处于同一条横行、纵行或斜线上。
解决这个问题前,我们引入一个回溯的概念。比如我们走迷宫,前路未可知,向前走总会碰到岔路且是二选一的,我们一路选择岔路,直到发现无法走通,就回到倒数第二次的岔路继续二选一。如此往复,理论上我们最终总能走出迷宫。
那么,八皇后问题,我们依然这样解决。首先尝试放置第一个皇后,在第一行。然后放置第二个皇后,一次类推。如果发现不能放置下一个皇后,就回溯到上一步。

下面我们开始代码实现。
我们定义是否下一个皇后放的位置是否合法。我们用数组指定每一行皇后的位置。比如state[0]=2,表示第1行第3列的位置。我们用下面的函数表示下一个皇后放置的位置是否是正确的。

def confict(state,nextX):
    nextY = len(state)
    for i in range(nextY):
        if abs(state[i]-nextX) in (0,nextY-i):
            return True
    return False

nextX表示下一个皇后的水平位置,即x坐标。nextY表示垂直位置,即y坐标。对这两个皇后的位置做一个检查,如果下一个皇后和前面的皇后同样有同样的水平位置,或者是在一条对角线上,就表示不合法,返回True。如果检查没问题,返回False。之所以这样返回,是因为这个函数的意思本地放的位置错误。True表示真的错了,False表示没毛病。
关键的一句是:abs(state[i]-nextX) in (0,nextY-1)。下一个皇后和前一个皇后水平距离为0,或者垂直距离为0,都表示有错误。

关键的代码来了,

def queens(num=8,state=()):
    for pos in range(num):
        if not confict(state,pos):
            if len(state) == num-1:
                yield (pos,)
            else:
                for result in queens(num,state+(pos,)):
                    yield (pos,)+result

回溯的问题一定是要递归来实现,才比较方便。假定最后一个皇后的位置是正确的,需要回溯到上一步,在前面的步骤中加入if else选择位置。这里是最难理解的。
我们先这样思考,当7个皇后都放好了位置,只剩最后一个皇后了,此时有两种情况:一是,根据前7个皇后能生成出最后一个皇后的所有位置。二是最后一个皇后没地方放了。
如果是情况一,那就解决问题了,此时事情做完了。如果是情况二,那么就要回溯到第七个皇后的位置问题了。第七个皇后需要重新放一次不同位置。

调用如下,

print(len(list(queens(3))))
print(len(list(queens(4))))
print(len(list(queens(8))))

输出

0
2
92 

八皇后有92中放法。我们用图形打印出其中一种看看,

def prettyprint(s):
    def line(pos,length=len(s)):
        return '. ' *(pos) + 'X ' +'. ' * (length-pos-1)
    for pos in s:
        print(line(pos))

import  random
prettyprint(random.choice(list(queens(8))))

92种中的一种图形如下,

. . . X . . . . 
. X . . . . . . 
. . . . . . X . 
. . X . . . . . 
. . . . . X . . 
. . . . . . . X 
X . . . . . . . 
. . . . X . . . 

工程文件下载:https://download.csdn.net/download/yysyangyangyangshan/10833745

如果您有好的新闻与建议,欢迎点击文章投稿

    发表评论

    电子邮件地址不会被公开。

  • 内容

  • 网名