没有合适的资源?快使用搜索试试~ 我知道了~
Python实现八皇后问题示例代码
11 下载量 152 浏览量
2020-09-19
21:05:50
上传
评论
收藏 96KB PDF 举报
温馨提示
试读
4页
主要给大家介绍了关于利用Python实现八皇后问题的相关资料,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧
资源推荐
资源详情
资源评论
Python实现八皇后问题示例代码实现八皇后问题示例代码
主要给大家介绍了关于利用Python实现八皇后问题的相关资料,文中通过示例代码介绍的非常详细,对大家的
学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧
八皇后问题描述八皇后问题描述
问题: 国际象棋棋盘是8 * 8的方格,每个方格里放一个棋子。皇后这种棋子可以攻击同一行或者同一列或者斜线(左上左下
右上右下四个方向)上的棋子。在一个棋盘上如果要放八个皇后,使得她们互相之间不能攻击(即任意两两之间都不同行不同
列不同斜线),求出一种(进一步的,所有)布局方式。
首先,我们想到递归和非递归两类算法来解决这个问题。首先说说递归地算法。
很自然的,我们可以基于行来做判断标准。八个皇后都不同行这是肯定的,也就说每行有且仅有一个皇后,问题就在于皇后要
放在哪个列。当然八个列下标也都不能有相同,除此之外还要保证斜线上不能有重叠的皇后。
第一个需要解决的小问题就是,如何用数学的语言来表述斜线上重叠的皇后。其实我们可以看到,对于位于(i,j)位置的皇后而
言,其四个方向斜线上的格子下标分别是 (i-n,j+n), (i-n,j-n), (i+n,j-n), (i+n,j+n)。当然i和j的±n都要在[0,7]的范围内,保持不越
界。暂时抛开越界限制不管,这个关系其实就是: 目标格子(a,b)和本格子(i,j)在同一条斜线上 等价于 |a - i| == |b - j| 。
然后,从递归的思想来看,我们在从第一行开始给每一行的皇后确定一个位置。每来到新的一行时,对本行的所有可能位置
(皇后放在这个位置和前面所有已放置的皇后无冲突)分别进行递归地深入;若某一行可能的位置数为0,则表明这是一条死
路,返回上一层递归寻找其他办法;若来到的这一行是第九行(不存在第九行,只不过是说明前八行都已经正确配置,已经得
到一个解决方案),这说明得到解决方案。
可以看到,寻找一行内皇后应该摆放的位置这是个递归过程,并且在进入递归时,应该要告诉这个过程的东西包括两个: 1.
之前皇后放置的状态, 2. 现在是第几行。
所以,递归主体函数可以设计为 EightQueen(board, row),其中board表示的是当前棋盘的状态(比如一个二维数组,0表示
未放置,1表示放有皇后的状态)。另外还可以有一个check(board,pos),pos可以是一个(x,y)元组,check函数用来返回以当
前的board棋盘状态,如果在pos再放置一个皇后是否会有冲突。
基于上面的想法,初步实现如下:
def check(board,pos):
# check函数暂时先不实现
pass
def EightQueen(board,row):
blen = len(board)
if row == blen: # 来到不存在的第九行了
print board
return True # 一定要return一个True,理由在下面
for possibleY in range(blen):
if check(board,(row,possibleY)):
board[row][possibleY] = 1 # 放置一个Queen
if not EightQueen(board,row+1): # 这里其实是本行下面所有行放置皇后的递归入口。但是如果最终这条路没有找到一个解,那么
# 此时应该将刚才放置的皇后收回,再去寻找下一个可能的解
board[row][possibleY] = 0
else:
return True
return False
最开始,可能在回归返回条件那里面不会想到要return True,而只是return。对应的,下面主循环中放置完Queen之后也只是
简单地递归调用EightQueen,不会做逻辑判断。但是很快可以发现这样做存在一个问题,即当某一层递归中for possibleY这
个循环走完却没有找到一个合适的解(即本行无合适位置),此时返回上一行,上一行的possibleY右移一格,此时之前放在
这一行的Queen的位置仍然是1。这样之后本行的所有check肯定都是通不过的。所以我们需要设计一个机制,使得第一个
possibleY没有找到合理的最终解决方案(这里就加上了一个判断条件),要右移一格到下一个possibleY时将本格的Queen收
回。
这个判断条件就是如果某层递归for possibleY循环整个走完未找到结果返回False(EightQueen整个函数最后的返回),上一
层根据这个False反馈把前一个Queen拿掉;如果找到了某个结果那么就可以一路return True回来,结束函数的运行。
另外,如果只是获取一个解的话,可以考虑在if row == blen的时候,打印出board,然后直接sys.exit(0)。此时就只需要for
possibleY循环完了之后return一个False就可以了。当然主循环中对于递归的返回的判断 if not EightQueen还是需要的。
上面没有实现check函数。其实仔细想一下,如果按照上面的设想来实现check函数还是有点困难的。比如令 x,y = pos,尽管
此时我们只需要去检查那些行下标小于x的board中的行,但是对于每一行中我们还是要一个个去遍历,找到相关行中值是1的
那个格子(突然发现这个是one-hot模式诶哈哈),然后将它再和x,y这个位置做冲突判断。所以但是这个check函数复杂度就
可能会达到O(n^2),再套上外面的循环,复杂度蹭蹭往上涨。下面是check函数的一个可能的实现:
def check(board,pos):
资源评论
weixin_38665944
- 粉丝: 6
- 资源: 914
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功