八皇后

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

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

image.png

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 Falsedef 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工具书籍下载-持续更新
• 本文配套视频在线播放 下载

原著是一个有趣的人,若有侵权,请通知删除