遥记我20岁左右的时候，拿着一本数据结构与算法书，PASCAL的，那个时候也是否对计算机编程充满了热爱和向往。时光飞速，我还是那个“少年”。仍旧兴趣盎然地在编程，想想我曾经是熟练的掌握了汇编语言的，可是现在我却看不懂了。写的八皇后算法那代码好糟糕。去年用我自己编写的精灵模块把八皇后代码重写了一遍，最近再次学习数据结构与算法，对动态规划、哈夫曼树、汉密尔顿路径等，感觉又有较大的长颈，确实体验到了温故而知新，收获不少。今天又把八皇后算法写了一遍，逻辑清晰了很多，对程序=数据结构+算法有了更深刻的体验。
这个程序使用一个stack列表存储皇后的位置，当成栈使用。使用常见的回溯法，不断地去试探下一个位置，如果和前面的位置有冲突，则继续尝试。如果一行所有的列都尝试完了，再次回溯。代码中有注释，详情见代码：
import turtle
from eight_queen import *
def check_collision(stack):
"""检测皇后在row,col位置是否和其它皇后冲突"""
row,col = stack[-1] # 最后摆放的
for x,y in stack[:-1]:
if abs(y-col) in (0,row-x) :return True # 列的差值等于0或者和最后一行到x行的差值一样
return False
def traceback(chess,):
"""从栈中弹出上次坐标,清除所盖图章"""
i,j = stack.pop()
chess[i][j] = 0
turtle.clearstamps(-1) # 清除这个坐标的皇后
j = j + 1 # 上一行的下一列位置
return i,j
def output(stack): # 以文本方式输出一个解
for i,j in stack:
print(j,end='')
print()
chess = [[0,0,0,0,0,0,0,0],
[0,0,0,0,0,0,0,0],
[0,0,0,0,0,0,0,0],
[0,0,0,0,0,0,0,0],
[0,0,0,0,0,0,0,0],
[0,0,0,0,0,0,0,0],
[0,0,0,0,0,0,0,0],
[0,0,0,0,0,0,0,0]]
turtle.setup(800,800)
turtle.speed(0)
draw_cross(770) # 画坐标线
draw_grid(8,70) # 画格子
turtle.penup() # 抬笔
turtle.addshape('queen.gif')
turtle.shape('queen.gif')
turtle.speed(1)
turtle.title('八皇后问题回溯法动态演示2021_11_18版by李兴球')
w = turtle.Turtle(visible=False)
w.penup()
w.sety(300)
ft = ('黑体',32,'normal')
w.write("八皇后问题回溯法动态演示",align='center',font=ft)
stack = [] # 新建一个列表存储当前皇后坐标,当栈用
i ,j = 0,0
while True:
if j<8:
chess[i][j] = 1 # 放皇后
place_queen(8,70,i,j) # 在棋盘上放置皇后(盖图章)
else: # 一行都尝试完了,超过最右边了，需要回溯
if stack: # 如果栈不是空的
i,j = traceback(chess) # 回溯到上一个位置的右边一列
continue
else:
break
stack.append((i,j)) # 放入stack中，保存以便回到上一个位置
if check_collision(stack) :# 发生冲突
i,j = traceback(chess) # 和其它皇后发生冲突，需要回溯
continue
else:
i = i + 1 # 到下一行
j = 0 # 从0开始放皇后
if i==8:
output(stack) # 到了最后输出一个解
i,j = traceback(chess) # 这当然也要继续到上一行继续试探
xsleep(3)
