注册 登录
  • 欢迎访问开心洋葱网站,在线教程,推荐使用最新版火狐浏览器和Chrome浏览器访问本网站,欢迎加入开心洋葱 QQ群
  • 为方便开心用户,开心洋葱官网已经开启复制功能!
  • 欢迎访问开心洋葱网站,手机也能访问哦~欢迎加入开心洋葱多维思维学习平台 QQ群
  • 如果您觉得本站非常有看点,那么赶紧使用Ctrl+D 收藏开心洋葱吧~~~~~~~~~~~~~!
  • 由于近期流量激增,小站的ECS没能经的起亲们的访问,本站依然没有盈利,如果各位看如果觉着文字不错,还请看官给小站打个赏~~~~~~~~~~~~~!

python采用右递归的超简单八皇后解决

python 水墨上仙 2909次浏览 已收录 手机上查看

凡是线性回溯都可以归结为右递归的形式,也即是二叉树,因此对于只要求一个解的问题,采用右递归实现的程序要比回溯法要优美的多。

def Test(queen,n):
    '''这个就不用说了吧,就是检验第n(下标,0-7)行皇后的位置是否合理'''
    q=queen[n]
    for i in xrange(n):
        if queen[i]==q or queen[i]-q==n-i or queen[i]-q==i-n:return False
    return True
def Settle(queen,n):
    '''这个负责安置第n(下标,0-7)行皇后,每次调用,皇后都至少会移动一步'''
    queen[n]+=1
    while queen[n]<8 and not Test(queen,n):queen[n]+=1
    return queen[n]<8

def Solve(queen,n):
    '''这个负责解决第n(下标,0-7)行皇后的安置以及随后所有皇后的安置'''
    if n==8:#安置完所有皇后了,故输出列表
        print queen
        return True#如果设为假,则会尝试所有的安置方案
    else:
        queen[n]=-1#初始化第n行皇后的起始位置(起始位置-1,可安置在0-7)
        while Settle(queen,n):#如果成功安置皇后
            if Solve(queen,n+1):#安置其余皇后
                return True#成功安置,返回真
    return False#失败,返回假
if __name__=='__main__':
    Solve([-1 for i in range(8)],0)#列表的值可以随便设置,因为会初始化
#虽然我们没有进行回溯,但事实上,我们每一个参数相同的Solve函数都尝试了多次
#输出:[0, 4, 7, 5, 2, 6, 1, 3]
#比回溯法容易多了吧

 


开心洋葱 , 版权所有丨如未注明 , 均为原创丨未经授权请勿修改 , 转载请注明python采用右递归的超简单八皇后解决
喜欢 (0)
[开心洋葱]
分享 (0)
水墨上仙
关于作者:
水墨上仙
……
加载中……