八皇后问题其实很有趣,借助这个问题可以很好检验对一门新的语言的理解程度。
使用生成器,在8皇后的时候,以下非独立解决代码的计算次数为46752次:
# !/usr/bin/python # coding:utf-8 # __author__=watson 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 def queens(num=1, state=()): for pos in range(num): if not conflict(state, pos): if len(state) == num-1: yield (pos,) else: for result in queens(num, state + (pos,)): yield (pos,) + result if __name__ == "__main__": print list(queens(8))
使用记忆算法,在8皇后的时候,以下非独立解决代码的计算次数为15720次:
# !/usr/bin/python # coding:utf-8 # __author__=watson column = rup = lup = [] def conflict(line, col, num): if column[col] == 0 and rup[line+col] == 0 and lup[line-col+num] == 0: return False return True def queens(num=1, line=1): for col in range(1, num + 1): if not conflict(line, col, num): if line == num: yield (col,) else: column[col] = rup[line+col] = lup[line-col+num] = 1 for result in queens(num, line + 1): yield (col,) + result column[col] = rup[line+col] = lup[line-col+num] = 0 if __name__ == "__main__": number = 8 column = [0] * (number + 1) rup = [0] * (2*number + 1) lup = [0] * (2*number + 1) print list(queens(number))
使用记忆算法,不使用生成器:
# !/usr/bin/python # coding:utf-8 # __author__=watson number = 0 result = [0] column = [0] rup = [0] lup = [0] no = 0 def backtrack(line): if line > number: show_result() else: for col in range(1, number+1): if column[col] == 0 and rup[line+col] == 0 and lup[line-col+number] == 0: result[line] = col column[col] = rup[line+col] = lup[line-col+number] = 1 backtrack(line + 1) column[col] = rup[line+col] = lup[line-col+number] = 0 def show_result(): global no no += 1 print "result no %r:" % no for i in range(1, number + 1): for j in range(1, number + 1): if result[i] == j: print " Q ", else: print " . ", print "\n" if __name__ == "__main__": number = 8 result = [0] * (number + 1) column = [0] * (number + 1) rup = [0] * (2*number + 1) lup = [0] * (2*number + 1) # print column[number] backtrack(1)
上述算法都是递归算法,在皇后数多的都比较消耗内存。
独立解参考《八皇后问题独立解JAVA代码》:
http://kingxss.iteye.com/blog/2290026
相关推荐
Qbasic 高效解法-递归版 c#实现 C++实现 Python实现 PASCAL实现 SHELL实现 独立解 VB实现 还有图形化显示 等等很多解决方法的综合,本人自己找资料整合出来的,望大家有用。
【压缩包子文件的文件名称列表】"leecode"可能代表压缩包内包含了一个或多个文件,这些文件可能是每个LeetCode问题的独立Python代码实现。文件名可能是问题的ID或者简要描述,例如"20_two_sum.py"表示第20题的两数之...
6. **回溯法**:如八皇后问题和N皇后问题,回溯法是解决约束满足问题的有效手段。 7. **递归**:如阶乘计算、汉诺塔问题和树的遍历,递归是理解和解决问题的重要工具。 **二、设计模式** 1. **单例模式**:确保一...
9. **递归和回溯**:八皇后问题、N皇后问题、迷宫求解等,演示了如何用递归解决复杂问题。 通过学习和实践这些代码,学习者不仅可以掌握Python编程,还能深入理解算法和数据结构背后的数学原理。此外,这种实践性的...
回溯算法常用于解决组合优化问题,如八皇后问题、迷宫问题等。 - **动态规划**: - 动态规划通过构建状态转移表来求解最优化问题,如背包问题、最长公共子序列等。 - **贪心算法**: - 贪心算法在每一步选择...
2. 回溯:八皇后问题、数独、迷宫问题等。 这个"algorithm_learn-master"项目提供了丰富的实例,涵盖了计算机科学基础算法的方方面面,是Python初学者和进阶者提升算法能力的良好资源。通过实践这些代码,读者不仅...
还有一些其他重要算法,如回溯法用于解决组合优化问题,如八皇后问题;贪心算法在每一步选择局部最优解,如霍夫曼编码;以及随机化算法,如蒙特卡洛方法,常用于模拟和概率计算。 Python库如NumPy、SciPy和Pandas...
回溯法,如“八皇后问题”或“排列组合”,Python的递归函数可以清晰地展示解空间的遍历过程。对于二叉树问题,如“树的遍历”,Python的类定义和递归方法能够优雅地实现前序、中序和后序遍历。 除了代码本身,通常...
回溯算法是一种强大的搜索策略,常用于解决组合优化问题,如八皇后问题、数独、图着色等。它通过尝试逐步构建解决方案,并在遇到无法继续的情况时撤销上一步,来寻找所有可能的解或最优解。在这个"Top-20-...
常见的应用场景包括八皇后问题、图的着色问题等。 5. **图论**:GCJ中的很多题目涉及到图的处理,如最短路径问题(Dijkstra算法、Floyd-Warshall算法)、最小生成树(Prim算法、Kruskal算法)等。 6. **数据结构**...
回溯是一种尝试所有可能解决方案,但一旦发现不可行就回退到上一步的方法,常用于解决迷宫问题、八皇后问题等。 7. **字符串处理**:字符串匹配算法(如KMP、Rabin-Karp)、编辑距离、正则表达式等在文本处理和搜索...
- 递归和分治策略常常相辅相成,例如在解决汉诺塔问题、八皇后问题等经典问题时,递归提供了简洁的解决方案。 7. **递归的理论基础——递归论** - 递归论是研究可计算性的数学分支,涉及递归函数、部分递归函数和...
- 八皇后问题:在棋盘上放置八个皇后,不允许有任意两个皇后在同一行、同一列或同一斜线上。 - N皇后问题:N皇后问题的扩展,解决在N×N棋盘上放置N个皇后的问题。 9. **分治算法**: - Strassen矩阵乘法:将...
- **回溯法**:用于在搜索解空间树中寻找所有可能的解,如八皇后问题。 - **分治法**:将大问题分解为小问题,如归并排序、快速排序等。 4. **算法实现**: 在Python中,你可以直接编写函数实现算法,利用其内置...
这个压缩包文件"LeetCode-master"可能包含了用户在LeetCode上所编写的Python代码,这些代码可能覆盖了广义的算法问题,旨在提升编程技能和解决复杂问题的能力。 在LeetCode上,你通常会遇到各种类型的题目,包括但...
6. **回溯法**:用于解决组合优化问题,如八皇后问题、N皇后问题、括号匹配等。 7. **滑动窗口**:在数组或字符串问题中,滑动窗口是一种常见的解决方法,用于寻找连续子序列的某些属性。 8. **贪心算法**:在每...
14. 回溯法和剪枝:用于寻找所有可能解或最优解的方法,如八皇后问题、N-皇后问题等。 通过对"CodeChef_Solutions-master"压缩包内的文件进行分析,我们可以深入学习这些Python编程技巧和算法,并结合CodeChef的...
回溯法常用于解决组合优化问题,如八皇后问题、N皇后问题等。Test3或Test5可能会包含这类题目。 5. **贪心算法**:贪心策略是在每一步选择当前最优解,期望得到全局最优解。这在资源分配、任务调度等问题中常见。...
4. **递归与回溯**:在解决组合优化问题和搜索问题时,递归和回溯方法经常被使用,例如八皇后问题、迷宫问题等。 5. **字符串处理**:涉及到模式匹配、字符串操作(如KMP算法、Rabin-Karp算法)和文本分析。 6. **...
5. **回溯法**:用于解决组合优化问题,如八皇后问题、数独求解等。 6. **字符串处理**:模式匹配、KMP算法、Rabin-Karp算法等。 通过参与蓝桥杯,开发者不仅可以提升编程技能,还能锻炼解决实际问题的能力,这对于...