python采用右递归的超简单八皇后解决
""" 皮蛋编程(https://www.pidancode.com) 创建日期:2022/3/27 功能描述:python采用右递归的超简单八皇后解决 """ def Test(queen, n): '''这个就不用说了吧,就是检验第n(下标,0-7)行皇后的位置是否合理''' q = queen[n] for i in range(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] # 比回溯法容易多了吧
以上代码在python3.9环境下测试通过
相关文章