`
kingxss
  • 浏览: 973336 次
  • 性别: Icon_minigender_1
  • 来自: 上海
社区版块
存档分类
最新评论

八皇后问题独立解Python代码

阅读更多

八皇后问题其实很有趣,借助这个问题可以很好检验对一门新的语言的理解程度。

 

使用生成器,在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常见代码收集

    【压缩包子文件的文件名称列表】"leecode"可能代表压缩包内包含了一个或多个文件,这些文件可能是每个LeetCode问题的独立Python代码实现。文件名可能是问题的ID或者简要描述,例如"20_two_sum.py"表示第20题的两数之...

    Python-所有算法在Python中实现用于教育

    6. **回溯法**:如八皇后问题和N皇后问题,回溯法是解决约束满足问题的有效手段。 7. **递归**:如阶乘计算、汉诺塔问题和树的遍历,递归是理解和解决问题的重要工具。 **二、设计模式** 1. **单例模式**:确保一...

    此存储库包含与“使用Python中的算法”Safari视频关联的代码。httpshop.oreilly.comprodu.zip

    9. **递归和回溯**:八皇后问题、N皇后问题、迷宫求解等,演示了如何用递归解决复杂问题。 通过学习和实践这些代码,学习者不仅可以掌握Python编程,还能深入理解算法和数据结构背后的数学原理。此外,这种实践性的...

    Python-Python描述的数据结构和算法

    回溯算法常用于解决组合优化问题,如八皇后问题、迷宫问题等。 - **动态规划**: - 动态规划通过构建状态转移表来求解最优化问题,如背包问题、最长公共子序列等。 - **贪心算法**: - 贪心算法在每一步选择...

    经典计算机科学问题的Python实现algorithm-learn-master.zip

    2. 回溯:八皇后问题、数独、迷宫问题等。 这个"algorithm_learn-master"项目提供了丰富的实例,涵盖了计算机科学基础算法的方方面面,是Python初学者和进阶者提升算法能力的良好资源。通过实践这些代码,读者不仅...

    python-algorithm:Python算法示例

    还有一些其他重要算法,如回溯法用于解决组合优化问题,如八皇后问题;贪心算法在每一步选择局部最优解,如霍夫曼编码;以及随机化算法,如蒙特卡洛方法,常用于模拟和概率计算。 Python库如NumPy、SciPy和Pandas...

    leetcode全套解答python版本

    回溯法,如“八皇后问题”或“排列组合”,Python的递归函数可以清晰地展示解空间的遍历过程。对于二叉树问题,如“树的遍历”,Python的类定义和递归方法能够优雅地实现前序、中序和后序遍历。 除了代码本身,通常...

    Top-20-Backtracking-Algorithms:使用python的顶级回溯算法

    回溯算法是一种强大的搜索策略,常用于解决组合优化问题,如八皇后问题、数独、图着色等。它通过尝试逐步构建解决方案,并在遇到无法继续的情况时撤销上一步,来寻找所有可能的解或最优解。在这个"Top-20-...

    Algorithm-GoogleCodeJam-2014.zip

    常见的应用场景包括八皇后问题、图的着色问题等。 5. **图论**:GCJ中的很多题目涉及到图的处理,如最短路径问题(Dijkstra算法、Floyd-Warshall算法)、最小生成树(Prim算法、Kruskal算法)等。 6. **数据结构**...

    华为OD算法题解,并采用模块化代码,形成解题思路

    回溯是一种尝试所有可能解决方案,但一旦发现不可行就回退到上一步的方法,常用于解决迷宫问题、八皇后问题等。 7. **字符串处理**:字符串匹配算法(如KMP、Rabin-Karp)、编辑距离、正则表达式等在文本处理和搜索...

    递归的资料大全,教材、文档、代码

    - 递归和分治策略常常相辅相成,例如在解决汉诺塔问题、八皇后问题等经典问题时,递归提供了简洁的解决方案。 7. **递归的理论基础——递归论** - 递归论是研究可计算性的数学分支,涉及递归函数、部分递归函数和...

    python-algorithm:用Python实现的所有算法

    - 八皇后问题:在棋盘上放置八个皇后,不允许有任意两个皇后在同一行、同一列或同一斜线上。 - N皇后问题:N皇后问题的扩展,解决在N×N棋盘上放置N个皇后的问题。 9. **分治算法**: - Strassen矩阵乘法:将...

    算法:python,cpp

    - **回溯法**:用于在搜索解空间树中寻找所有可能的解,如八皇后问题。 - **分治法**:将大问题分解为小问题,如归并排序、快速排序等。 4. **算法实现**: 在Python中,你可以直接编写函数实现算法,利用其内置...

    LeetCode:leetcode.com上的代码

    这个压缩包文件"LeetCode-master"可能包含了用户在LeetCode上所编写的Python代码,这些代码可能覆盖了广义的算法问题,旨在提升编程技能和解决复杂问题的能力。 在LeetCode上,你通常会遇到各种类型的题目,包括但...

    Algorithm-leetcode.zip

    6. **回溯法**:用于解决组合优化问题,如八皇后问题、N皇后问题、括号匹配等。 7. **滑动窗口**:在数组或字符串问题中,滑动窗口是一种常见的解决方法,用于寻找连续子序列的某些属性。 8. **贪心算法**:在每...

    CodeChef_Solutions:该存储库为您提供了不同的CodeChef问题的解决方案

    14. 回溯法和剪枝:用于寻找所有可能解或最优解的方法,如八皇后问题、N-皇后问题等。 通过对"CodeChef_Solutions-master"压缩包内的文件进行分析,我们可以深入学习这些Python编程技巧和算法,并结合CodeChef的...

    2021编程比赛试题.zip

    回溯法常用于解决组合优化问题,如八皇后问题、N皇后问题等。Test3或Test5可能会包含这类题目。 5. **贪心算法**:贪心策略是在每一步选择当前最优解,期望得到全局最优解。这在资源分配、任务调度等问题中常见。...

    前几年的蓝桥杯的一些试题

    4. **递归与回溯**:在解决组合优化问题和搜索问题时,递归和回溯方法经常被使用,例如八皇后问题、迷宫问题等。 5. **字符串处理**:涉及到模式匹配、字符串操作(如KMP算法、Rabin-Karp算法)和文本分析。 6. **...

    第十届初赛程序.zip

    5. **回溯法**:用于解决组合优化问题,如八皇后问题、数独求解等。 6. **字符串处理**:模式匹配、KMP算法、Rabin-Karp算法等。 通过参与蓝桥杯,开发者不仅可以提升编程技能,还能锻炼解决实际问题的能力,这对于...

Global site tag (gtag.js) - Google Analytics