python八皇后问题的解决方法
本文为大家分享了python八皇后问题的解决方法，供大家参考，具体内容如下
题目：
给定一个 N*N 正方形棋盘，在上面放置 N个棋子，又叫皇后，使每两个棋子都不在同一条横线上、竖线上、斜线上。一般我们都讨论8皇后，但是只要N > 4，都会存在解的。
分析：
方法1：根据定义来处理，即每往棋盘中放置皇后的时候，都要判断哪些位置可以放新加入的皇后，而哪些地方如果放置皇后的话，会造成冲突。我下面写的这个代码就是基于此。
方法2、我看了下别人的优化，主要是采用位运算来实现计算复杂度降低的，我没有用Python 实现这个，所以在这里挖一个坑。
代码：
代码里的注释有详细的说明，设定N值，即可返回一个符合要求的解。但是这个问题还有一个进阶，那就是讨论究竟会有多少个解，这就需要数论的知识了，而且我对这块数学没研究过，所以也没有代码实现。大家将就使用一下代码就好了。
class EightQueensPuzzle(object):
'''
八皇后问题求解
代码使用方法：
eight_q = EightQueensPuzzle(4, 5)
print "EIGHT QUEEDS PUZZLE:"
result = eight_q.eight_queens_puzzle()
for i in result:
print i
'''
def __init__(self, n, char):
self.n = n # 棋盘维度
self.char = char # 皇后标记字符
def init_chess_board(self, n):
'''
初始化一个棋盘，棋盘规格可以按参数 n 随意选定,一般都讨论八皇后，就选择 8
:return: 返回棋盘，是一个 8*8 矩阵
'''
chess_board = []
for i in xrange(0, n):
line = []
for j in xrange(0, n):
line.append(0)
chess_board.append(line)
return chess_board
def update_conflict_board(self, conflict_board, position):
for k in xrange(0, self.n): # 为行添加 1
conflict_board[position[0]][k] = 1
for id in xrange(position[0]+1, self.n):
conflict_board[id][position[1]] = 1 # 为列添加 1
if position[0] + position[1] - id >= 0: # 为左斜添加 1
conflict_board[id][position[0] + position[1] - id] = 1
if position[1] - position[0] + id < self.n: # 为右斜添加 1
conflict_board[id][position[1] - position[0] + id] = 1
def queens_conflict(self, conflict_board, position):
'''
当前棋盘的状态是 conflict_board, 判定如果在 position 位置给一个皇后的话，会不会出现问题。
如果有问题则返回 False，如果没有问题返回 True
'''
if conflict_board[position[0]][position[1]] != 0:
return False
else:
return True
def eight_queens_puzzle(self):
'''
给出一个八皇后的求解答案。
:return:返回一个结果并打印.
'''
import random
while True: # 不停寻找符合条件的八皇后排列
chess_board = self.init_chess_board(self.n)
conflict_board = self.init_chess_board(self.n)
for i in xrange(0, self.n):
flag = 0
for cnt in conflict_board[i]:
if cnt != 0:
flag += 1
if flag == self.n: # 如果已经1被填满了，说明这个答案错误
break
while True:
pos = [i, random.randint(0, self.n-1)] # 元组构成皇后的位置
if self.queens_conflict(conflict_board, pos): # 如果没有冲突
chess_board[i][pos[1]] = self.char
self.update_conflict_board(conflict_board, pos)
break
if self.char in chess_board[self.n-1]:
return chess_board
以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持我们。
相关推荐
-
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看得都不用tab键了,哈哈.今天看了一个经典问题--八皇后问题,说实话,以前学C.C++的时候有这个问题,但是当时不爱学,没搞会,后来算法课上又碰到,只是学会了思想,应该是学回溯法的时候碰到的.八皇后问题是说要在一个棋盘上放置8个皇后,但是不能发生战争,皇后们都小心眼,都爱争风吃醋,如果有人和自己在一条线上(水平.垂直.对角线)就会引发撕13大战,所以我们就是要妥当的安排8位娘娘,以保后宫太平. 言归正传,首先,我们得想好解决方案怎么表示,这种事首先想到列表,当然规模小的话用元
-
Python实现八皇后问题示例代码
八皇后问题描述 问题: 国际象棋棋盘是8 * 8的方格,每个方格里放一个棋子.皇后这种棋子可以攻击同一行或者同一列或者斜线(左上左下右上右下四个方向)上的棋子.在一个棋盘上如果要放八个皇后,使得她们互相之间不能攻击(即任意两两之间都不同行不同列不同斜线),求出一种(进一步的,所有)布局方式. 首先,我们想到递归和非递归两类算法来解决这个问题.首先说说递归地算法. 很自然的,我们可以基于行来做判断标准.八个皇后都不同行这是肯定的,也就说每行有且仅有一个皇后,问题就在于皇后要放在哪个列.当然八个列下
-
Python解决八皇后问题示例
本文实例讲述了Python解决八皇后问题的方法.分享给大家供大家参考,具体如下: 八皇后问题是一个以国际象棋为背景的问题:如何能够在 8×8 的国际象棋棋盘上放置八个皇后,使得任何一个皇后都无法直接吃掉其他的皇后?为了达到此目的,任两个皇后都不能处于同一条横行.纵行或斜线上.八皇后问题可以推广为更一般的n皇后摆放问题:这时棋盘的大小变为n1×n1,而皇后个数也变成n2.而且仅当 n2 = 1 或 n1 ≥ 3 时问题有解. 这是一个典型的回溯算法,我们可以将问题进行分解: 首先,我们要想到某种方
-
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 sqlobject(mysql)中文乱码解决方法
UnicodeEncodeError: 'latin-1' codec can't encode characters in position: 找了一天终于搞明白了,默认情况下,mysql连接的编码是latin-1,你需要指定使用什么编码方式: connectionForURI(mysql://user:password@localhost:3306/eflow?use_unicode=1&charset=utf8) Python mysql 中文乱码 的解决方法,有需要的朋友不妨看看. 先来
-
浅谈c++调用python链接的问题及解决方法
python 版本3.3 系统:windows 问题:链接时报告 1>pythonIniti.obj : error LNK2019: 无法解析的外部符号 __imp___Py_NegativeRefcount,该符号在函数 "public: __thiscall boost::python::api::object_base::~object_base(void)" (??1object_base@api@python@boost@@QAE@XZ) 中被引用 1>pyth
-
Python安装pycurl失败的解决方法
Centos安装pycurl centos 安装pycurl yum install python-devel curl-devel pip3 install pycurl Mac(老版本)安装pycurl 解决MacOS升级后出现xcrun: error: invalid active developer path, missing xcrun的问题 xcode-select --install 然后 dongchang-5:qqmusic baoshan$ pip3 install pycu
-
selenium+python截图不成功的解决方法
selenium+python,使用webdriver的截图函数get_screenshot_as_file()截图,代码如下: from selenium import webdriver from time import sleep driver=webdriver.Chrome() driver.get("https://www.baidu.com") driver.find_element_by_id("kw").send_keys("seleni
-
在pycharm中python切换解释器失败的解决方法
在pycharm中我们有时需要切换python的版本,这里需要注意的是我们是在PyCharm中的Preferences中切换的, 在File的Setting中切换可能会导致失败 以上这篇在pycharm中python切换解释器失败的解决方法就是小编分享给大家的全部内容了,希望能给大家一个参考,也希望大家多多支持我们.
-
python中常见错误及解决方法
python常见的错误有 1.NameError变量名错误 2.IndentationError代码缩进错误 3.AttributeError对象属性错误 详细讲解 1.NameError变量名错误 报错: >>> print a<br>Traceback (most recent call last):<br>File "<stdin>", line 1, in <module><br>NameError:
-
python多线程死锁现象及解决方法
目录 本节重点 一 死锁现象 二 递归锁 本节重点 了解死锁现象与解决方法 本节时长需控制在15分钟内 一 死锁现象 所谓死锁: 是指两个或两个以上的进程或线程在执行过程中,因争夺资源而造成的一种互相等待的现象,若无外力作用,它们都将无法推进下去.此时称系统处于死锁状态或系统产生了死锁,这些永远在互相等待的进程称为死锁进程,如下就是死锁 from threading import Thread,Lock import time mutexA=Lock() mutexB=Lock() class
-
Ubuntu18.04下python版本完美切换的解决方法
ubuntu18.04版本,python版本python2.7,python3.5,python3.6 因为安装一些库会安装到python3.6上,而默认使用的是python2.7,使用python3,默认会使用python3.5,无法调用安装包. 解决方法: 一.使用python xx.py运行程序时,加上版本号.比如python3.6 xx.py 二.1.要以root身份操作 yz@yz-pc:~$ sudo su 2.确认本机下的python默认版本.调出终端,输入python即可查看默认