八皇后问题是一个以国际象棋为背景的问题,如何在8*8的棋盘上放置8个皇后,使得任何一个皇后都无法直接吃掉其他的皇后。其实8皇后问题也可以推广为更为一般的n皇后问题,棋盘大小变为n*n,当n=2或者3时,是不存在解的,问题的限制有:
- 所有的皇后都不能在同一行或同一列,也就是说每行或每列都只能存在一个皇后;
- 所有的皇后都不能在对角线上,假设两个皇后的坐标为(i, j)和(k, l),明显当且仅当|i-k|=|j-l|时,两个皇后在一个对角线上。
回溯法是穷尽搜索算法的一种,采用试错的思想,尝试分步骤去解决一个问题,在分步解决问题的时候,当尝试不能得到有效的解答时,取消上一步或上几步的计算,通过其他可能的分步去得到可能的答案。
八皇后问题使用回溯法解决的思想是,假设某一行为当前状态,不断检查该行所有位置能否放置一个皇后:
- 从一行中的第一个位置开始检查,如果不能放置,接着检查该行的第二个位置,依次检查下去,直到在该行中能够找到一个可以放置一个皇后的位置,然后保存该状态,转到下一行重复该步骤;
- 如果检查了该行中的所有位置都不能放置一个皇后,说明上一行皇后放置的位置无法让所有的皇后找到自己的位置,需要回溯到上一行,继续将上一行中的皇后位置后移,直到找到合理的位置为止;
'''print current status''' def print_current_status(queen): print "----new-result--" for i in range(0, max): line = "" for j in range(0, max): if queen[i] != j: line += "-" else: line += "*" print line '''judge that whether the n position can place here''' def can_place(n, queen): for i in range(0, n): if queen[i] == queen[n] or abs(queen[i] - queen[n]) == abs(i - n): return False return True '''recursive execute n queen problem''' def n_queen(n, queen): for i in range(0, max): queen[n] = i if can_place(n, queen): if n == max - 1: print_current_status(queen) else: n_queen(n + 1, queen) if __name__ == '__main__': queen = [0 for i in range(max)] n_queen(0, queen)
其中核心的方法就是n_queen方法,方法接收的第一个参数就是当前已经遍历到了第n行,顺序地将第n行尝试0~max,如果期间有合适的,递归看一下n+1行是否可行;如果已经到了最后一行,就直接将数据结果输出,这就是其中的一个解;如果探索所有的可能解之后没有正确的结果,回溯至上一层,最多可能遍历8*8次(在max=8的情况下)。
其中的一个结果数据类似(*表示皇后位置)如下所示:
*------- ----*--- -------* -----*-- --*----- ------*- -*------ ---*----
相关推荐
第六章 回溯法学习要点理解回溯法的概念。着重讨论可以用回溯法求解的问题的一般特征。掌握回溯算法的基本要素理解回溯算法的一般理论通过应用范例学习。(1)一般方法;
算法设计与分析实验报告,附已通过源码,供学习参考,共勉♪ 目录摘要如下: 1.问题描述 2.实验目的 3.实验原理 4.实验设计 (包括输入格式、算法、输出格式) 5.实验结果与分析 (除了截图外,实验结果还用...
ACM程序设计,算法竞赛,分治法的课件,相关练习,以及各种题型,由简单到复杂,由容易到困难的各个阶段。是学习这一基本算法的很好的辅助资料。
用回溯算法解决背包问题,和我上传的另一个资源一样的只不过哪个用贪心算法解决,大家可以下来对比学习,用netbeans做的。百分百下载就可以直接运行。有WORD文档实验报告,和 JAVA 源文件。
第8章 回溯法学习要点:理解回溯法的深度优先搜索策略理解剪枝函数(约束函数和限界函数)的作用掌握回溯法解题的算法框架(1)递归回溯的算法框架(2)迭代回溯的算法
这是算法的精髓部分,回溯法运用广泛,对于学习算法非常重要,尤其是参加ACM竞赛的同学,可以多学习回溯的思想,本文档给你充分的学习指导.
本资源是从众多学生中选取出来的优秀...其中包含了带权调度问题,最小独钓等5个基于回溯法的实现,每个范例都有详尽问题描述,可执行完整代码和算法分析PPT! 其他基于该算法问题都可以参考本范例,是学习的绝佳材料。
大一时候使用javascript写的全排列算法演示(分为回溯法演示和交换法演示),既可以用来学习javascript,又可以用来加深对全排列算法的理解,有需要的朋友们可以下载~
这是算法设计与分析的课件,主讲回溯法,希望对想学习这个的朋友有所帮助!
经典算法 回溯法。学习算法,必定知道。5.1 回溯法算法框架 5.2 装载问题 5.3 批处理作业调度 5.4 符号三角形问题 5.5 n后问题 5.6 0-1背包问题 5.8 图的m着色问题 5.9 旅行售货员问题
通过n后问题、电路板排列、符号三角形、旅行售货员问题、批处理作业调度、图的m着色、圆排列、最大团问题、装载问题和子集和等经典问题的学习掌握了回溯法的思想,学会了子集树和排列数组织并搜索解空间的方法,将...
c++ 算法学习 用回溯法解决经典的N皇后问题。
算法分析与设计之世界名画陈列馆问题(回溯法)java源代码和实验报告 算法作为计算机专业学生的必修课,同时也是软件开发过程中必备的编程思想,对学习研究计算机专业意义重大;正因为这门课程难,所以除了相关方面...
学习常用算法之(3)回溯法
算法回溯法PPT学习教案.pptx
数据结构走迷宫算法,学习了他人的之后自己写的程序,运行OK
回溯法求解0.docx
计算机算法回溯法PPT学习教案.pptx
算法设计与分析回溯法PPT学习教案.pptx