文档章节

八皇后问题的python实现,附带输出图解

李艳青1987
 李艳青1987
发布于 2016/11/17 01:33
字数 208
阅读 176
收藏 0

利用python实现八皇后问题,输出图解。

 

bahuanghou.py

#!/usr/local/bin/python3.5 -u

def checkAvaliable(occupiedPoints, point):
    for i in range(len(occupiedPoints)):
        if occupiedPoints[i] == point or point - occupiedPoints[i] == len(occupiedPoints) - i or point - occupiedPoints[i] == i - len(occupiedPoints):
            return(1)
    return(0)

def func(num, avaliablePoints, occupiedPoints):
    if len(occupiedPoints) == num:
        global solutionNum
        print("Solution " + str(solutionNum) + ":")
        solutionNum = solutionNum + 1
        for i in range(len(occupiedPoints)):
            occupiedPoint = occupiedPoints[i]
            print("+---"*num + "+")
            print("+   "*occupiedPoint + "+ Q " + "+   "*(num-occupiedPoint-1) + "+")
        print("+---"*num + "+")
        print("")
        return(0)
    else:
        if len(avaliablePoints) == 0:
            return(1)
        else:
            for j in range(len(avaliablePoints)):
                avaliablePoint = avaliablePoints[j]
                if not checkAvaliable(occupiedPoints, avaliablePoint):
                    avaliablePointsTemp = avaliablePoints[:]
                    avaliablePointsTemp.remove(avaliablePoint)
                    occupiedPointsTemp = occupiedPoints[:]
                    occupiedPointsTemp.append(avaliablePoint)
                    func(num, avaliablePointsTemp, occupiedPointsTemp)

def main():
    num = 8
    avaliablePoints = list(range(num))
    occupiedPoints = []
    global solutionNum
    solutionNum = 1
    func(num, avaliablePoints, occupiedPoints)

###################
## Main Function ##
###################
if __name__ == "__main__":
    main()

 

输出图解:

... ...

 

可变更程序中的“n = 8”来实现n皇后问题,随着n的增大,解决方案数目也会急剧增加。

© 著作权归作者所有

李艳青1987
粉丝 17
博文 23
码字总数 36080
作品 0
通州
高级程序员
私信 提问
一行 Python 能实现什么丧心病狂的功能?

解码一个 base64 编码格式的文件 一行python解八皇后,其中一大半代码是用于打印出来带格式的 打印出输入文件中的每行代码,但移除前两个字段 终端路径切换到某文件夹下,键入: 然后浏览器打...

加米谷大数据
2018/07/23
5
0
[codeup] 2046 八皇后

题目描述 会下国际象棋的人都很清楚:皇后可以在横、竖、斜线上不限步数地吃掉其他棋子。如何将8个皇后放在棋盘上(有8 * 8个方格),使它们谁也不能被吃掉!这就是著名的八皇后问题。 对于某...

trav
02/08
0
0
回溯算法思想与八皇后问题解的个数

八皇后问题: 在88的国际象棋棋盘上,皇后是威力较大的棋子,它可以攻击到与自己同行、同列以及同一斜线上的棋子,如下图,所有橙色格子上的棋子,都可能会被皇后攻击: 而八皇后问题就是在8...

yawn-silence
2018/03/04
677
0
DFS算法

DFS算法 三个经典例子 1 排列数 问题: 生成1~n的排列 思路: 一颗N层的树 每层节点为n^n个 在生成结果数组前把重复的去掉 DFS出口: 遍历到排列结果数组长度 DFS实现: 尝试安排数字给结果数组 ...

hakase
2016/10/27
130
0
回溯VS递归,回溯法(八皇后问题)及C语言实现

回溯法 回溯法,又被称为“试探法”。解决问题时,每进行一步,都是抱着试试看的态度,如果发现当前选择并不是最好的,或者这么走下去肯定达不到目标,立刻做回退操作重新选择。这种走不通就...

这个人很懒什么都没留下
03/07
0
0

没有更多内容

加载失败,请刷新页面

加载更多

CentOS 7系统增加swap

转载请注明文章出处:CentOS 7系统增加swap swap是位于磁盘上的特殊文件(或分区),属于“虚拟内存”的一部分。通俗点就是内存的备胎,内存充足的情况下,基本上没swap什么事(和设置有关)...

tlanyan
17分钟前
2
0
基于Prometheus和Grafana的监控平台 - 环境搭建

相关概念 微服务中的监控分根据作用领域分为三大类,Logging,Tracing,Metrics。 Logging - 用于记录离散的事件。例如,应用程序的调试信息或错误信息。它是我们诊断问题的依据。比如我们说...

JAVA日知录
57分钟前
5
0
PHP运行时全局构造体

struct _php_core_globals { zend_bool magic_quotes_gpc; // 是否对输入的GET/POST/Cookie数据使用自动字符串转义。 zend_bool magic_quotes_runtime; //是否对运行时从外部资源产生的数据使...

冻结not
58分钟前
4
0
webpack插件html-webpack-plugin

本文转载于:专业的前端网站→webpack插件html-webpack-plugin 1、插件安装 npm install html-webpack-plugin --save-dev 2、插件使用 webpack.config.js配置文件为: var htmlWebpackPlugin=...

前端老手
今天
6
0
数据挖掘

zhengchen1996
今天
4
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部