八皇后
这是一个深受大家喜爱的计算机科学谜题:你需要将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 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))
参考资料
网友评论