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

栏目: Python · 发布时间: 5年前

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

我们来看一个有趣的问题:八皇后问题。这里的皇后是国际象棋中的皇后,虽然我只会玩中国象棋而不会玩国际象棋。这个问题和会不会国际象棋没有关系。

八皇后问题描述:如何能够在 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))))

输出

八皇后有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


以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持 码农网

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

算法分析导论

算法分析导论

(美)Robert Sedgewick、(法)Philippe Flajolet / 冯舜玺、李学武、裴伟东、等其他 / 机械工业出版社 / 2006-4 / 38.00元

本书阐述了用于算法数学分析的主要方法,所涉及的材料来自经典数学课题,包括离散数学、初等实分析、组合数学,以及来自经典的计算机科学课题,包括算法和数据结构,本书内容集中覆盖基础、重要和有趣的算法,前面侧重数学,后面集中讨论算法分析的应用,重点的算法分的的数学方法。每章包含大量习题以及参考文献,使读者可以更深入地理解书中的内容。 本书适合作为高等院校数学、计算机科学以及相关专业的本科生和研究生的......一起来看看 《算法分析导论》 这本书的介绍吧!

CSS 压缩/解压工具
CSS 压缩/解压工具

在线压缩/解压 CSS 代码

XML、JSON 在线转换
XML、JSON 在线转换

在线XML、JSON转换工具

UNIX 时间戳转换
UNIX 时间戳转换

UNIX 时间戳转换