# coding: utf-8 __author__ = 'Administrator' # 冲突函数 # 如果下一个皇后和正在考虑的前一个皇后的水平距离为0, # 或者等于垂直距离(在一条对角线上),返回True def conflict(state, nextX): nextY = len(state) for i in range(nextY): if abs(state[i] - nextX) in (0, nextY - i): return True return False # num:皇后的总数 # state:已经注册了的每行的皇后的位置列表(X坐标) def queens(num=8, state=()): print(state) find = False for pos in range(num): if not conflict(state, pos): find = True if len(state) == num - 1: # 如果state大小已经是num-1了,那么yield最后一个位置 yield (pos,) else: for result in queens(num, state + (pos,)): yield (pos,) + result if not find: print("HO, NO..." + str(state)) print(list(queens(4)))
回溯法原理:
打个比方,想象一下你要出席一个很重要的会议,但你不知道在哪儿开会,在你面前有两扇门,开会地点就在其中一扇门后面,于是有人挑了左边的进入,然后又发现两扇门,后来再选了左边的门,结果却错了,于是回溯到刚才的两扇门那里,并选择右边的门,结果还是错的,于是再次回溯,直到回到开始点,在那里选择了右边的门。
比较难理解的是这两行代码:
for result in queens(num, state + (pos,)):
递归的调用queens生成器,将state + (pos)当做参数传给queens,state是已经存在的合法状态列表,而pos是对要操作的该行进行遍历的位置参数,请注意state + (pos) 并没有将它赋值给state,是因为如果后面的返回没有合法值的话可以回溯到前面的状态,也就是说这次迭代里面我并没有说pos是合法状态,只是可能是合法状态,那么当往下的迭代无合法值,一级一级的跳出的时候,每次跳到一级,这个state都是合法的状态。
yield (pos,) + result:
这行的意思是我将当前状态pos作为前缀再加上一直到到底的迭代位置序列,也就是正序排列位置。就好比是这样的调用:(0+(1+(2+(3+(.....))))),这样够清楚了吧。^_^
本人博客已搬家,新地址为:http://www.pycoding.com/
相关推荐
八皇后问题 c++ 八皇后问题 c++ 八皇后问题 c++
八皇后问题课程设计论文
解决八皇后问题的源码,带有注释,由于数据结构即算法的学习,如有其他需要,请留言
作业代码,汇编写八皇后问题,自己写了一份,在网上找的也在里面
八皇后问题,是一个古老而著名的问题,是回溯算法的典型案例。该问题是国际西洋棋棋手马克斯·贝瑟尔于1848年提出:在8X8格的国际象棋上摆放八个皇后,使其不能互相攻击,即任意两个皇后都不能处于同一行、同一列或...
解决八皇后问题。利用mfc加了界面,输出结果放在一个文档中。
linux c语言实现八皇后问题。希望对你的学习
八皇后问题,是一个古老而著名的问题,是回溯算法的典型例题。该问题是十九世纪著名的数学家高斯1850年提出:在8X8格的国际象棋上摆放八个皇后,使其不能互相攻击,即任意两个皇后都不能处于同一行、同一列或同一...
C++面向对象编程八皇后问题 BOOL CMyqueenApp::InitInstance() { AfxEnableControlContainer(); // Standard initialization // If you are not using these features and wish to reduce the size // of your ...
这个文档关于八皇后问题,一共两种代码,输出分别为0和1的矩阵或者直接输出位置序号两种输出结果。代码是C++语言编写。
八皇后问题 递归算法 可以输入皇后的值 输出排列的结果
八皇后问题是一个古老而著名的问题,是回溯算法的典型例题。该问题是十九世纪著名的数学家高斯1850年提出:在8X8格的国际象棋上摆放八个皇后,使其不能互相攻击,即任意两个皇后都不能处于同一行、同一列或同一斜线...
经典的算法,八皇后问题,c++实现,回溯法
这是通过遗传算法求解八皇后问题的例子(比较经典) 步骤: 1,先是随机生成一定种群数量的染色体; 2,从种群中选择较为优秀的染色体个体; 3,按顺序让两个父染色体生成两个子染色体,理论上,子染色体会随着...
八皇后问题详细的解法-23页 PPT PDF版.pdf
包含prolog求解修八皇后问题的实验报告、源代码及试验运行截图
八皇后问题,是一个古老而著名的问题,是回溯算法的典型案例。该问题是国际西洋棋棋手马克斯·贝瑟尔于1848年提出:在8X8格的国际象棋上摆放八个皇后,使其不能互相攻击,即任意两个皇后都不能处于同一行、同一列或...
个人写的一个八皇后问题,有需要的,可以下载。用C++编写的!
八皇后问题 数据结构八皇后问题 数据结构八皇后问题 数据结构八皇后问题 数据结构八皇后问题 数据结构八皇后问题 数据结构八皇后问题 数据结构
C语言八皇后问题