精华内容
下载资源
问答
  • Python八皇后改造一个计数器,每次生成一个元num个元素的元组。解八皇后的前提是先理解这个计数器。 上代码: import datetime def queens(num,state=()): #用八皇后递归函数定义 for pos in range(num): ...

    Python 递归计数器

    用Python 的八皇后改造一个计数器,每次生成一个num 个元素的元组。解八皇后的前提是先理解这个计数器。这个计数器加上限制条件,就可以组成八皇后的解法或组合成各种解法。

    上代码:

    import datetime
    
    def queens(num,state=()):          #用八皇后的递归函数定义
        for pos in range(num):
            if len(state)==num-1:
                yield (pos,)
            else:
                for result in queens(num,state+(pos,)):
                    yield (pos,)+result
      
           
    a=datetime.datetime.now()     #开始的时间
    for i in queens(6):
         print(i)
       
    b=datetime.datetime.now()       #结束递归时间
    print(b-a)                                   #计算一下用时多长
    

    计算6位的结果片段如下:

    (5, 5, 5, 5, 4, 5)
    (5, 5, 5, 5, 5, 0)
    (5, 5, 5, 5, 5, 1)
    (5, 5, 5, 5, 5, 2)
    (5, 5, 5, 5, 5, 3)
    (5, 5, 5, 5, 5, 4)
    (5, 5, 5, 5, 5, 5)
    0:00:02.965189
    
    展开全文
  • 八皇后问题出自国际象棋:皇后可以在横、竖、斜线上不限步数地吃掉其他...那么python怎么实现以及对于八皇后问题的求解呢?鉴于初学者水平只能讲讲递归回溯算法对于八皇后问题的求解 核心代码如下: def isNotConfic

    这里是对于周一课上的老师教学的python八皇后问题的个人学习记录

    八皇后问题出自国际象棋:皇后可以在横、竖、斜线上不限步数地吃掉其他棋子。如何将8个皇后放在棋盘上(有8 * 8个方格),使它们谁也不能被吃掉!这就是著名八皇后问题。 对于某个满足要求的8皇后的摆放方法,定义一个皇后串a与之对应,即a=b1b2…b8,其中bi为相应摆法中第i行皇后所处的列数。已经知道8皇后问题一共有92组解(即92个不同的皇后串)

    那么python怎么实现以及对于八皇后问题的求解呢?鉴于初学者水平只能讲讲递归回溯算法对于八皇后问题的求解

    核心代码如下:

    def isNotConfict(queen, row):   #判断是否冲突
        for i in range(0, row):
            if queen[i] == queen[row] or abs(i - row) == abs(queen[i] - queen[row]):
                return False
        return True

    对于皇后间不能在同一行,以及在对角线位置,这里采用循环遍历的方式,前一个皇后与后一个皇后之间的行数不等,对角线下表元素相减绝对值也不能等判断其位置是否冲突,这里采用老师给的代码

    def confict(state,nextX):
        nextY=len(state)
        for i in range(nextY):
            if abs(state[i]-nextX)in(0,nextY-i):
                return True
            return False

     

    同一垂直线上abs(state[i]-nextX)==0,对角线上abs(state[i]-nextX)==nextY-i

    把已知的皇后位置传给conflict函数进行判断,决定下一个皇后的位置是否会产生冲突


    当只剩最后一个皇后时,只需要根据其他皇后位置自动形成他合适位置

    def queen(num,state):
        if len(state)==num-1:
            for pos in range(num):
                if not conflict(state,pos):
                    yield pos

    这里采用生成器的方法,需要递归的方法,完成基本情况后需要做的就是为前面的queens函数实现if语句后增加else语句,在递归中想要得到更高位置皇后的位置,需要将位置信息作为一个元组返回,即yield(pos,),为了继续运行,需要把当前位置信息添加到元组中并传入给后面的皇后

    else:
        for pos in range(num):
            if not conflict(state,pos):
                for result in queens(num,state+(pos,)): 
                    yield(pos,)+result
    

     

    老师完整代码,采用了元组不可个更改的性质,生成器yield自动循环遍历下一个皇后的位置

    
    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, 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

     

    展开全文
  • 今天小编就为大家分享一篇python 使用递归回溯完美解决八皇后的问题,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧
  • python八皇后问题,递归算法

    千次阅读 2019-01-22 11:58:37
    python八皇后问题,递归算法问题描述思路代码运行结果 问题描述 在8×8格的国际象棋上摆放八个皇后,使其不能互相攻击,即任意两个皇后都不能处于同一行、同一列或同一斜线上,输出所有摆法。 思路 每个皇后都不处于...

    python八皇后问题,递归算法

    问题描述

    在8×8格的国际象棋上摆放八个皇后,使其不能互相攻击,即任意两个皇后都不能处于同一行、同一列或同一斜线上,输出所有摆法。

    思路

    每个皇后都不处于同一行、一列,可以用一维数组来表示皇后的位置,如a[0]=3表示皇后在第一行第四列,用一维数组可以保证皇后不会在同一行中
    判断冲突,如果同列,数组中的元素会有平相同,如果同斜线,2皇后位置的列差绝对值等于行差绝对值,用这种计算判断皇后是否在同一斜线上。

    代码

    #检查是否冲突
    def check(board,row,col):
        i = 0
        while i < row:
            if abs(col-board[i]) in (0,abs(row-i)):
                return False
            i += 1
        return True
    def EightQueen(board,row):
        blen = len(board)
        if row == blen:    
            print (board)
            return True
        col = 0
        while col < blen:
            if check(board,row,col):
                board[row] = col
                if EightQueen(board,row+1):
                    pass
            col += 1
    return False
    a=[None]*8
    EightQueen(a,0)
    
    

    运行结果

    在这里插入图片描述在这里插入图片描述
    部分结果截图,八皇后问题摆法共92种。

    展开全文
  • 八皇后问题,采用递归!!!!!!!!!!!!!!!!!!!!!!!
  • 如果列的插值等于行的插值,说明两皇后在对角线上 """ if abs(column-nextColumn)in[0,nextRow-row]: return False return True def queens(num,state=()): """ 基于递归采用回溯算法,算出每一种结果 num:八皇后的...

    首先我们将8*8的棋盘放在我们的坐标轴上,放在第一象限。

    每个点的坐标,就代表在棋盘中的行列,从0开始表示,为了在程序中存储方便。
    推出斜线上的点的表达式为Y=X+n或者Y=-X+n(n是常数),进而可以推导出Y-X=n或者Y+X=n。也就是说在同一斜线上的两个棋子行号与列号之和或者之差相等。X1+Y1=X2+Y2或者X1-Y1=X2-Y2。再进行变换能够得到X1-X2=Y2-Y1或者X1-X2=Y1-Y2,也就是说|X1-x2|=|Y1-Y2|。
    那么判断两个棋子是否在同一斜线上,只要判断出两个棋子的列号之差是否等于两个棋子的行号之差的绝对值就可以了。
    下面我们来编写代码,我们需要一个判断函数Judgment()以及递归回溯函数queens()

    
    def judgment(state,nextColumn):#每次只判断一个坐标值,(len(state),nextColumn)
        """
        判断是否符合条件
        坐标从0开始,state的长度就代表下一行的行坐标
        state:索引代表行,值代表列(7,4,0)分别代表第一行第八列,第二行第五列,第三行第一列
        nextColumn:下一行的列坐标,这个很重要,需要拿去向上面每一行的列坐标比较
        """
        nextRow=rows=len(state)#获得下一行的行坐标
        for row in range(rows):#遍历前面所有行
            column=state[row]#获得对应行的列
            """
            判断是否符合条件:
                1.如果列的差值为0,说明在同一列
                2.如果列的插值等于行的插值,说明两皇后在对角线上
            """
            if  abs(column-nextColumn)in[0,nextRow-row]:
                return False
        return True
    
    def queens(num,state=()):
        """
        基于递归采用回溯算法,算出每一种结果
        num:八皇后的数量,也代表棋盘的行数和列数
        state:索引代表行坐标,取值代表列坐标。参数的元祖不是列表,因为参数为不可变类型
        """
        for pos in range(num):
            #默认state为空,为0,但是符合条件
            if judgment(state,pos):#回溯法的体现
                if len(state)==num-1:
                    #如果state的长度等于7,则代表前面七行皇后已经找到位置,最后一行也符合条件,返回最后一行的列坐标,也就是这里的pos
                    yield(pos,)#这里加逗号是因为是元祖
                else:#不是最后一行,继续摆放皇后
                    for result in queens(num,state+(pos,)):
                        yield(pos,)+result
                        
    for index,solution in enumerate(queens(8)):
        print('test')
        print('第%d种情况:'%(index+1),solution)
    

    运行结果
    在这里插入图片描述
    一共92种未截取全

    递归函数需要注意的是:
    1.首先是yield,这个是python里的关键字,带有yield的函数被称作为生成器函数。这里推荐这篇博文,我觉得解释的很清楚
    链接: https://blog.csdn.net/mieleizhi0522/article/details/82142856/
    里面将其看为简单的return以及暂停的意思
    2.递归函数不易想的太复杂,容易绕进去

    展开全文
  • 八皇后python

    2020-03-11 09:54:33
    八皇后问题是经典的回溯问题,可以通过八皇后的学习来体会回溯法的使用,通过对回溯法算法框架的学习,python代码如下: number = 0 queen = [[ '. ' for i in range(8)]for j in range(8)] def backtrack(queen,row...
  • 主要介绍了python基于右递归解决八皇后问题的方法,实例分析了右递归算法的相关使用技巧,需要的朋友可以参考下
  • Python 递归函数基例2. 关于递归函数基例的说明,以下选项中错误的是 A 递归函数的基例决定所谓基例就是不需要递归就能分享解的,一般来说是问题的最小规模下的解。 例如:斐波那契数列递归,f(n) = f(n-1) + f(n-2)...
  • #include <iostream> #include <fstream> #include <...八皇后问题递归方法实现 */ using namespace std; ofstream file; //用以计数计算结果的数目 int count = 1; /** 打印的棋盘其中...
  • 参考链接: Python递归 移动宽带检查显示 CRM,radius状态不一致是怎么回事啊?您可以把电信宽带猫等设备重启试一下,如果仍然不行,可以拨打10000号请工作人员帮您查看、处理。 电信宽带诊断显示AAA带宽寓CRM带宽不...
  • Python实现递归经典问题:迷宫回溯问题、八皇后问题
  • 八皇后问题递归求解

    2019-12-11 16:11:58
    * 判断当前放置的皇后跟之前的是否在同一列或者一条斜线上 */ public static boolean judge ( int n ) { for ( int i = 0 ; i < n ; i ++ ) { //如果和之前放置的皇后在同一行或者...
  • python 使用递归回溯解决八皇后问题详细解释

    千次阅读 多人点赞 2018-04-21 23:56:35
    八皇后问题描述:在一个8✖️8的棋盘上,任意摆放8个棋子,要求任意两个棋子不能在同一行,同一列,同一斜线上,问有多少种解法。规则分析:任意两个棋子不能在同一行比较好办,设置一个队列,队列里的每个元素代表...
  • 递归题的时候,做到了八皇后问题,又再去回顾了一下生成器(generator)的用法。以下仅是个人学习笔记,因此着重记录的都是本人在学习过程中的理解难点。欢迎讨论指点^^ 八皇后问题:八皇后问题,一个古老而著名的...
  • (后附Python代码)如何解决八皇后问题?所谓递归回溯,本质上是一种枚举法。这种方法从棋盘的第一行开始尝试摆放第一个皇后,摆放成功后,递归一层,再遵循规则在棋盘第二行来摆放第二个皇后。如果当前位置无法摆放...
  • 上图展示了一个8*8的国际象棋棋盘,八皇后问题就是指在该棋盘上放8个皇后,使得任意两个皇后不在同一行也不在同一列,还不在同一斜线(与水平线呈45。角)或反斜线(与水平线呈135。角)上。换句话说,就是避免任意两个...
  • 本文介绍八皇后问题的解决思路,并使用python3实现。   1.问题阐述 目标: 8×8 的国际象棋棋盘上放置八个皇后 规则:任两个皇后都不能处于同一条横行、纵行或斜线上 显然可知: 由于任意皇后不能同行,所以...
  • '''判断新皇后的落点是否与前一皇后冲突 1、如果新皇后与前一皇后在同一列,则 state[i] == nextX 2、如果新皇后与前一皇后在同一行,则 i == nextY 3、如果新皇后在前一皇后右对角线 ,则 nextX - s...
  • python 递归

    2020-03-06 20:46:39
    1、递归判断回文串的2种方法 # 递归判断回文串 def isPalidrome(s): if len(s) <=1: return True elif s[0]!=s[len(s)-1]: return False else: return isPalidrome(s[1:len(s)-1]) def main(): ...
  • 八皇后的非递归

    2018-10-08 15:37:17
    八皇后的非递归代码:全部代码分享,方便各位java初学者学习
  • Python基础基础教程中,第九章讲到了八皇后,书中的代码中迭代器、递归的使用比较难理解,对代码进行了就修改以方便理解。 书中的解决方案 def conflict(state, nextX): nextY = len(state) for i in range(nextY)...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 871
精华内容 348
关键字:

八皇后python递归

python 订阅