少说话多写代码之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


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

查看所有标签

猜你喜欢:

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

美团机器学习实践

美团机器学习实践

美团算法团队 / 人民邮电出版社 / 2018-8-1 / 79.00元

人工智能技术正以一种超快的速度深刻地改变着我们的生活,引导了第四次工业革命。美团作为国内O2O领域领 先的服务平台,结合自身的业务场景和数据,积极进行了人工智能领域的应用探索。在美团的搜索、推荐、计算广告、风控、图像处理等领域,相关的人工智能技术得到广泛的应用。本书包括通用流程、数据挖掘、搜索和推荐、计算广告、深度学习以及算法工程6大部分内容,全面介绍了美团在多个重要方面对机器学习的应用。 ......一起来看看 《美团机器学习实践》 这本书的介绍吧!

JSON 在线解析
JSON 在线解析

在线 JSON 格式化工具

Markdown 在线编辑器
Markdown 在线编辑器

Markdown 在线编辑器

正则表达式在线测试
正则表达式在线测试

正则表达式在线测试