发布于2019-08-22 17:51 阅读(1123) 评论(0) 点赞(15) 收藏(5)
八皇后问题,是一个古老而著名的问题,是回溯算法的典型案例。该问题是国际西洋棋棋手马克斯·贝瑟尔于1848年提出:在8×8格的国际象棋上摆放八个皇后,使其不能互相攻击,即任意两个皇后都不能处于同一行、同一列或同一斜线上,问有多少种摆法。
八皇后问题是一个经典的数学问题,同时也是一个典型的回溯问题,《Python基础教程》简单的思路是:首先尝试在第1行放置第1个皇后,然后在第2行某个位置放置皇后,依次进行,当发现某行的所有位置都不能防止皇后时,回溯至上一行,试着将上一行皇后放置在其他位置,再考虑下一行皇后的位置。
排列时,是按顺序排列的,也就是一行一行排列,但是列的位置不确定
序列很小而且是静态的,元祖是一个很好的选择
state 是一个元祖,每个元祖中元素都指示相应行的皇后的位置。
例如,如果 state[0] == 3,那么就表示在第一行的皇后是在第 4 列(从0开始计数)
# nextX 代表下一个皇后的水平位置(x坐标或列)
# nextY 代表垂直位置(y坐标或行)
def conflict(state,nextX):
# nextY 中存储的已经包含是皇后的行
nextY = len(state)
for i in range(nextY):
# 如果下一个皇后和正在考虑的前一个皇后的水平距离为0(列相同)
# 或者等于垂直距离(在一条对角线上)就返回 TRUE,否则就返回 FALSE
if(abs(state[i] - nextX)in (0,nextY-i)):
return True
return False
其中的表达式 abs(state[i] - nextX) in (0 , nextY - i )
理解为:对于第 i 行皇后的位置 state[i],检查其与第nextY行皇后位置nextX是否是位于同列或对角。
同列时满足:state[i] = nextX
,也即 state[i]–nextX = 0;
对角时,有2种情形需要考虑:
其一为第 nextY 行皇后位置出现于state[i]的右对角线,从水平方向上 nextX - state[i]
与 垂直方向 nextY – i
相等,即:nextX - state[i]= nextY – i
其二为第 nextY 行皇后位置出现于state[i]的左边对角线,从水平方向上state[i]- nextX
与 垂直方向nextY – i
相等,即state[i]- nextX= nextY – i
综上,对角线时满足,abs(state[i] - nextX) in (0 , nextY - i )
def queens(num,state):
if len(state) == num -1: #num此处表示皇后总数
for pos in range(num): #num此处表示遍历所有可能的位置
if not conflict(state , pos):
# 以迭代器的形式返回最后一个皇后的所有可能位置
yield pos
# state 初始化为空元祖
# num 为皇后的总数
def queens(num=8,state=()):
for pos in range(num):
# 如果没有发生冲突,进行下步判断
if not conflict(state,pos):
# 判断 第 pos 个皇后是否是最后一个皇后
if len(state) == num -1:
yield (pos,)
else:
for result in queens(num,state+(pos,)):
yield (pos,) + result
作者:3434erer
链接:https://www.pythonheidong.com/blog/article/53321/8bb2ad7ae6eeb5f700fb/
来源:python黑洞网
任何形式的转载都请注明出处,如有侵权 一经发现 必将追究其法律责任
昵称:
评论内容:(最多支持255个字符)
---无人问津也好,技不如人也罢,你都要试着安静下来,去做自己该做的事,而不是让内心的烦躁、焦虑,坏掉你本来就不多的热情和定力
Copyright © 2018-2021 python黑洞网 All Rights Reserved 版权所有,并保留所有权利。 京ICP备18063182号-1
投诉与举报,广告合作请联系vgs_info@163.com或QQ3083709327
免责声明:网站文章均由用户上传,仅供读者学习交流使用,禁止用做商业用途。若文章涉及色情,反动,侵权等违法信息,请向我们举报,一经核实我们会立即删除!