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

2022-03-11 00:00:00 递归 采用 皇后
"""
皮蛋编程(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环境下测试通过

相关文章