# 跳马问题算法答案演示

## 如本文章标有价格,需议价或其它事情商议请加微信pythonxia

```"""
跳马问题算法
"""
from sprites import *

grid_width  = 50       # 格子宽度
grid_height = 40       # 格子高度
rows = 4               # 表示行数
cols = 8               # 表示列数
chess_width = grid_width * cols
chess_height = grid_height * rows

screen = Screen()      # 新建屏幕
screen.setup(600,480)
screen.title('跳马问题算法答案演示by李兴球')

s = Sprite(visible=False)
s.draw_grid2(rows,cols,grid_width,grid_height)
left,bottom = -chess_width/2,-chess_height/2
cors = []              # 每个顶点的坐标
for r in range(rows+1):
rcors = []
for c in range(cols+1):
x = left + c * grid_width
y = bottom + r * grid_height
rcors.append((x,y))
cors.append(rcors)
jack  = Sprite(visible=False)
ft = ('黑体',20,'bold')
jack.write("跳马问题算法答案演示",align='center',font=ft)
tom = Sprite(shape='res/马.png')
def output(points):
tom.clear()
tom.show()
for p in points:
i,j = p
pos = cors[j][i]
tom.goto(pos)
tom.pendown()
tom.dot(10,'magenta')
tom.wait(0.1)
tom.penup()
tom.stamp()
tom.hide()
tom.goto(0,-150)
tom.write(str(points),align='center')
tom.wait(1)

grids = [ ]
for r in range(rows+1):
grids.append([0 for i in range(cols+1)])

def outofrange(a,b):
"""是否超出范围"""
return a > cols or b > rows or a <0 or b<0

x = 0
y = 0
points = [(0,0)]                         # 记录路径的
grids[0][0] = 1                          # 标记第一个点
condition = [(1,2),(2,1),(2,-1),(1,-2)]  # 4个试探运算
records = {(0,0):-1}                     # 记录当前点已经试探过的运算
running = True
while running:
# 开始试探
if (x,y) in records:             # 如果有此键说明在此点试探过
start = records[(x,y)]
if start == 3 :              # 此点全部试完了,则回溯
x,y = points.pop()
grids[y][x] = 0          # 把此点标记为0
records[(x,y)] = -1      # 记录此点以后需要全部测试4个方向
if points == []:
running = False
else:
x,y = points[-1]     # 从这个点重新开始
else:
start = -1

for index in range(start+1,4):
records[(x,y)] = index       # 记录此点的运算已经试探过了
dx,dy = condition[index]
nextx = x + dx
nexty = y + dy
if outofrange(nextx,nexty):continue
elif nextx < cols and nexty <= rows:
grids[nexty][nextx] = 1
points.append((nextx,nexty))
x = nextx
y = nexty
break
elif nextx == cols:
grids[nexty][nextx] = 1
points.append((nextx,nexty))
if nexty == rows:  output(points)  # 到达了右上角,可输出这个路径了
# 回溯到上一个点
x,y = points.pop()
grids[y][x] = 0
records[(x,y)] = -1
if points == []:
running = False
else:
x,y = points[-1]

```

scratch