python笔试面试项目实战2020百练9八皇后

八皇后

这是一个深受大家喜爱的计算机科学谜题:你需要将8个皇后放在棋盘上,条件是任何一个皇后都不能威胁其他皇后,即任何两个皇后都不能吃掉对方。怎样才能做到这一点呢?应将这些皇后放在什么地方呢?

这是一个典型的回溯问题:在棋盘的第一行尝试为第一个皇后选择一个位置,再在第二行尝试为第二个皇后选择一个位置,依次类推。在发现无法为一个皇后选择合适的位置后,回溯到前一个皇后,并尝试为它选择另一个位置。最后,要么尝试完所有的可能性,要么找到了答案。在前面描述的问题中,只有8个皇后,但这里假设可以有任意数量的皇后,从而更像现实世界的回溯问题。如何解决这个问题呢?如果你想自己试一试,就不要再往下读了,因为马上就会提供解决方案。

def conflict(state, next_x):
    next_y = len(state)
    for i in range(next_y):
        if abs(state[i] - next_x) in (0, next_y - i):
            return True
    return False


def queens(num=8, 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
                  
result = queens(8)

print(list(result))   

参考资料

• 本文最新版本地址
• 本文涉及的python测试开发库 谢谢点赞！
• 本文相关海量书籍下载
• python工具书籍下载-持续更新
• 本文配套视频在线播放 下载