Python八皇后问题解答过程详解

最近看Python看得都不用tab键了，哈哈。今天看了一个经典问题--八皇后问题，说实话，以前学C、C++的时候有这个问题，但是当时不爱学，没搞会，后来算法课上又碰到，只是学会了思想，应该是学回溯法的时候碰到的。八皇后问题是说要在一个棋盘上放置8个皇后，但是不能发生战争，皇后们都小心眼，都爱争风吃醋，如果有人和自己在一条线上（水平、垂直、对角线）就会引发撕13大战，所以我们就是要妥当的安排8位娘娘，以保后宫太平。

言归正传，首先，我们得想好解决方案怎么表示，这种事首先想到列表，当然规模小的话用元组最好啦，列表都比较熟悉，这次试试元组。每个元组元素指定相应行皇后位置，如state[0] = 3表示第一行皇后在第4列。然后还要知道什么情况不行，就是说找到矛盾，我们定义一个函数：

def conflict(state,nextx):
 '定义冲突函数,state为元组，nextx为下一个皇后的水平位置，nexty为下一个皇后的垂直位置'
 nexty = len(state)
 for i in range(nexty):
  if abs(state[i]-nextx) in (0,nexty-i):#若下一个皇后和前面的皇后列相同或者在一条对角线上，则冲突
   return True
 return False

最后，我们要解决娘娘们的位置了，先找到一个不冲突的位置，如果这位娘娘是最后一位，那么我们就把娘娘们安排好了，返回该位置到解决方案；如果不是最后一位，也把该位置信息返回到状态元组（最后的解决方案是含全部位置信息的状态元组）并传给后面的皇后，看代码：

def queens(num=8,state=()):
 '八皇后问题，这里num表示规模'
 for pos in range(num):
  if not conflict(state,pos):#位置不冲突
   if len(state) == num - 1:#若是最后一个皇后，则返回该位置
    yield (pos,)
   else:#若不是最后一个皇后，则将该位置返回到state元组并传给后面的皇后
    for result in queens(num,state + (pos,)):
     yield (pos,) + result

哦，最后的最后，我们还得看看解决方案什么样，定义一个打印函数：

def prettyp(solution):
 '打印函数'
 def line(pos,length = len(solution)):
  '打印一行，皇后位置用X填充，其余用0填充'
  return 'O'*(pos)+'X'+'O'*(length-pos-1)
 for pos in solution:
  print(line(pos))

让我们看看效果：

import random
#随机打印一种
prettyp(random.choice(list(queens(8))))

D:\Python34\python.exe D:/Python34/hanshu.py
OOOOOOOX
OOXOOOOO
XOOOOOOO
OOOOOXOO
OXOOOOOO
OOOOXOOO
OOOOOOXO
OOOXOOOO
Process finished with exit code 0

完美达到预期，pass，哈哈。

以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持我们。

赞 (0)

相关推荐

  • python基于右递归解决八皇后问题的方法

    本文实例讲述了python基于右递归解决八皇后问题的方法.分享给大家供大家参考.具体分析如下: 凡是线性回溯都可以归结为右递归的形式,也即是二叉树,因此对于只要求一个解的问题,采用右递归实现的程序要比回溯法要优美的多. def Test(queen,n): '''这个就不用说了吧,就是检验第n(下标,0-7)行皇后的位置是否合理''' q=queen[n] for i in xrange(n): if queen[i]==q or queen[i]-q==n-i or queen[i]-q==i

  • python八皇后问题的解决方法

    本文为大家分享了python八皇后问题的解决方法,供大家参考,具体内容如下 题目: 给定一个 N*N 正方形棋盘,在上面放置 N个棋子,又叫皇后,使每两个棋子都不在同一条横线上.竖线上.斜线上.一般我们都讨论8皇后,但是只要N > 4,都会存在解的. 分析: 方法1:根据定义来处理,即每往棋盘中放置皇后的时候,都要判断哪些位置可以放新加入的皇后,而哪些地方如果放置皇后的话,会造成冲突.我下面写的这个代码就是基于此. 方法2.我看了下别人的优化,主要是采用位运算来实现计算复杂度降低的,我没有用Py

  • Python实现八皇后问题示例代码

    八皇后问题描述 问题: 国际象棋棋盘是8 * 8的方格,每个方格里放一个棋子.皇后这种棋子可以攻击同一行或者同一列或者斜线(左上左下右上右下四个方向)上的棋子.在一个棋盘上如果要放八个皇后,使得她们互相之间不能攻击(即任意两两之间都不同行不同列不同斜线),求出一种(进一步的,所有)布局方式. 首先,我们想到递归和非递归两类算法来解决这个问题.首先说说递归地算法. 很自然的,我们可以基于行来做判断标准.八个皇后都不同行这是肯定的,也就说每行有且仅有一个皇后,问题就在于皇后要放在哪个列.当然八个列下

  • Python基于生成器迭代实现的八皇后问题示例

    本文实例讲述了Python基于生成器迭代实现的八皇后问题.分享给大家供大家参考,具体如下: 问题:有一个棋盘和8个要放到上面的皇后,唯一的要求是皇后之间不能形成威胁.也就是说,必须把他们防止成每个皇后都不能吃掉其他皇后的状态. # -*- coding: utf-8 -*- #python 2.7.13 __metaclass__ = type def confict(state, nextX): nextY = len(state) for i in range(nextY): if abs(

  • Python解决八皇后问题示例

    Python解决八皇后问题示例

    本文实例讲述了Python解决八皇后问题的方法.分享给大家供大家参考,具体如下: 八皇后问题是一个以国际象棋为背景的问题:如何能够在 8×8 的国际象棋棋盘上放置八个皇后,使得任何一个皇后都无法直接吃掉其他的皇后?为了达到此目的,任两个皇后都不能处于同一条横行.纵行或斜线上.八皇后问题可以推广为更一般的n皇后摆放问题:这时棋盘的大小变为n1×n1,而皇后个数也变成n2.而且仅当 n2 = 1 或 n1 ≥ 3 时问题有解. 这是一个典型的回溯算法,我们可以将问题进行分解: 首先,我们要想到某种方

  • Python八皇后问题解答过程详解

    最近看Python看得都不用tab键了,哈哈.今天看了一个经典问题--八皇后问题,说实话,以前学C.C++的时候有这个问题,但是当时不爱学,没搞会,后来算法课上又碰到,只是学会了思想,应该是学回溯法的时候碰到的.八皇后问题是说要在一个棋盘上放置8个皇后,但是不能发生战争,皇后们都小心眼,都爱争风吃醋,如果有人和自己在一条线上(水平.垂直.对角线)就会引发撕13大战,所以我们就是要妥当的安排8位娘娘,以保后宫太平. 言归正传,首先,我们得想好解决方案怎么表示,这种事首先想到列表,当然规模小的话用元

  • 基于python实现雪花算法过程详解

    基于python实现雪花算法过程详解

    这篇文章主要介绍了基于python实现雪花算法过程详解,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下 Snowflake是Twitter提出来的一个算法,其目的是生成一个64bit的整数: 1bit:一般是符号位,不做处理 41bit:用来记录时间戳,这里可以记录69年,如果设置好起始时间比如今年是2018年,那么可以用到2089年,到时候怎么办?要是这个系统能用69年,我相信这个系统早都重构了好多次了. 10bit:10bit用来记录机器ID

  • Python读取YAML文件过程详解

    这篇文章主要介绍了Python读取YAML文件过程详解,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下 YAML语法 学习手册 Python读取方法: import yaml with open('demo1.yaml', 'r', encoding='utf-8') as f: file_content = f.read() content = yaml.load(file_content, yaml.FullLoader) print(con

  • Python守护进程实现过程详解

    这篇文章主要介绍了Python守护进程实现过程详解,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下 如果你设置一个线程为守护线程,就表示你在说这个线程是不重要的,在进程退出的时候,不用等待这个线程退出.如果你的主线程在退出的时候,不用等待那些子线程完成,那就设置这些线程的daemon属性.即在线程开始(thread.start())之前,调用setDeamon()函数,设定线程的daemon标志.(thread.setDaemon(True))就

  • 如何用Python破解wifi密码过程详解

    如何用Python破解wifi密码过程详解

    前言 Python真的是无所不能,原因就是因为Python有数目庞大的库,无数的现成的轮子,让你做很多很多应用都非常方便.wifi跟我们的生活息息相关,无处不在.今天从WiFi连接的原理,再结合代码为大家详细的出一期关于Python破译wifi密码的Python学习教程! 01.如何连接wifi 首先我们的电脑是如何连接wifi的呢?就拿我们的笔记本电脑来说,我们的笔记本电脑都有无线网卡,如下图所示: 当我们连接WiFi时,无线网卡会自动帮助我们扫描附近的WiFi信号,并且会返回WiFi信号的一

  • 新手如何发布Python项目开源包过程详解

    新手如何发布Python项目开源包过程详解

    本文假设你在 GitHub 上已经有一个想要打包和发布的项目. 第 0 步:获取项目许可证 在做其他事之前,由于你的项目要开源,因此应该有一个许可证.获取哪种许可证取决于项目包的使用方式.开源项目中一些常见许可证有 MIT 或 BSD. 要在项目中添加许可证,只需参照以下链接中的步骤,将 LICENSE 文件添加到项目库中的根目录即可:  https://help.github.com/en/articles/adding-a-license-to-a-repository 第 1 步:让你的代

  • python解析yaml文件过程详解

    YAML语法规则: http://www.ibm.com/developerworks/cn/xml/x-cn-yamlintro/ 下载PyYAML: http://www.yaml.org/ 解压安装: python setup.py install 1.新建test.yaml文件,内容如下: name: Tom Smith age: 37 spouse: name: Jane Smith age: 25 children: - name: Jimmy Smith age: 15 - nam

  • Python 变量的创建过程详解

    Python 变量的创建过程详解

    一.变量创建过程 首先,当我们定义了一个变量name = 'Kwan'的时候,在内存中其实是做了这样一件事: 程序开辟了一块内存空间,将'Kwan'存储进去,再让变量名name指向'Kwan'所在的内存地址.如下图所示: 我们可以通过id()方法查看这个变量在内存中的地址. name = 'Kwan' print(id(name)) 二.变量的修改 一般我们认为修改一个变量就是用新值把就旧值覆盖掉,可Python真是这么实现的么? name = 'Kwan' print(id(name)) na

  • Python接口测试get请求过程详解

    python 做借口测试用到的是requests模块,首先要导入requests库,pip install requests 1.get直接请求方式 以豆瓣网为例: url = 'https://read.douban.com/' respose = requests.get(url=url) # status_code 为返回的状态码 print(respose.status_code) # text为返回的数据 print(respose.text) 请求结果:返回状态码为200,表明请求的

  • Python发送邮件封装实现过程详解

    引言 在做接口测试的时候,我们不仅需要将测试结果以报告的形式展示,还需要将测试结果以邮件的形式发送到需要知道的人手中.那么如何发送邮件呢? 邮件发送方式 测试结果以邮件形式发送的方式有两种: 第一种:手动统计结果数据及报告,用邮件客户端或web版形式发送,比如:用QQ邮箱,foxmail邮箱... 第二种:使用脚本发送,比如:利用python内置对SMTP协议的支持,发送邮件. 介绍一下: SMTP是发送邮件的协议,Python内置对SMTP的支持,可以发送纯文本邮件.HTML邮件以及带附件的邮

随机推荐