跳马问题算法答案演示

"""
   跳马问题算法
"""
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.addy(150)
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]