八皇后问题描述
“专业、务实、高效、创新、把客户的事当成自己的事”是我们每一个人一直以来坚持追求的企业文化。 创新互联是您可以信赖的网站建设服务商、专业的互联网服务提供商! 专注于成都网站设计、网站建设、软件开发、设计服务业务。我们始终坚持以客户需求为导向,结合用户体验与视觉传达,提供有针对性的项目解决方案,提供专业性的建议,创新互联建站将不断地超越自我,追逐市场,引领市场!问题: 国际象棋棋盘是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
网站标题:Python实现八皇后问题示例代码-创新互联
分享链接:http://scgulin.cn/article/djghid.html