国际象棋的棋盘为8×8的方格棋盘。现将“马”放在任意指定的方格中，按照“马”走棋的规则将“马”进行移动。
要求每个方格只能进入一次，最终使得“马”走遍棋盘的64个方格。
现在问题来了，用一段程序实现马踏棋盘操作，要求用1～64这64个数字标注“马”移动的路径，也就是按照求出的行走路线，将数字1～64依次填入棋盘的方格中，并输出结果。
下面直接上代码：
########################
def nextxy(x, y, count):# 找到基于（x,y）位置的下一个可走的位置
if count == 0 and x + 2 <= X - 1 and y - 1 >= 0 \
and chess[x + 2][y - 1]== 0: # 找到坐标(x+2,y-1)
x = x + 2
y = y - 1
flag = True
elif count == 1 and x + 2 <= X - 1 and y + 1 <= Y - 1 \
and chess[x + 2][y + 1] == 0:# 找到坐标(x+2,y+1)
x = x + 2
y = y + 1
flag = True
elif count == 2 and x + 1 <= X - 1 and y - 2 >= 0 \
and chess[x + 1][y - 2] == 0: # 找到坐标(x+1,y-2)
x = x + 1
y = y - 2
flag = True
elif count == 3 and x + 1 <= X - 1 and y+2 <= Y-1 \
and chess[x+1][y+2] == 0: # 找到坐标(x+1,y+2)
x = x + 1
y = y + 2
flag = True
elif count == 4 and x - 2 >= 0 and y - 1 >= 0 \
and chess[x - 2][y - 1]== 0: # 找到坐标(x-2,y-1)
x = x - 2
y = y - 1
flag = True
elif count == 5 and x - 2 >= 0 and y + 1 <= Y - 1 \
and chess[x - 2][y +1] == 0: # 找到坐标(x-2,y+1)
x = x - 2
y = y + 1
flag = True
elif count == 6 and x - 1 >= 0 and y - 2 >= 0 \
and chess[x - 1][y - 2] == 0: # 找到坐标(x-1,y-2)
x = x - 1
y = y - 2
flag = True
elif count == 7 and x - 1 >= 0 and y + 2 <= Y - 1 \
and chess[x - 1][y + 2] == 0: # 找到坐标(x-1,y+2)
x = x - 1
y = y + 2
flag = True
else:
flag = False
return flag, x, y
def TravelChessBoard(x, y, tag):# 深度优先搜索
x1, y1, flag, count = x, y, False, 0
chess[x][y] = tag
if tag == 60: # 搜索成功，返回1
return True
flag, x1, y1 = nextxy(x1, y1, count) # 找到基于(x1,y1)的下一个可走位置
# 上一步未找到，则在其余几种可走位置中寻找下一个可走位置
while not flag and count < 7:
count = count + 1
# print('(1): ', count)
flag, x1, y1 = nextxy(x1, y1, count)
while flag: # 找到下一个可走位置，则进行深度优先搜索
if TravelChessBoard(x1, y1, tag + 1): # 递归
return True
x1 = x
y1 = y
count = count + 1
flag, x1, y1 = nextxy(x1, y1, count) # 寻找下一个(x,y)
while not flag and count < 7: # 循环地寻找下一个(x,y)
count = count + 1
# print('(2): ', count)
flag, x1, y1 = nextxy(x1, y1, count)
if not flag:
chess[x][y] = 0 # 搜索不成功，擦除足迹，返回0
return False
if __name__ == '__main__':
X = 8
Y = 8
chess = [[0]*X for i in range(Y)] # 初始化，棋盘的所有位置都置0
if TravelChessBoard(2, 0, 1): # 深度优先搜索
for i in range(X):
for j in range(Y):
print("%-5d" % chess[i][j],
end='')
print()
print("马走棋盘成功，顺序如上面123...64顺序")
else:
print("马走棋盘失败")
########################
执行结果如下：
0 60 39 44 53 58 49 0
40 43 52 59 50 47 54 57
1 34 41 38 45 56 31 48
42 15 36 51 32 29 46 55
35 2 33 16 37 24 0 30
14 5 12 9 22 19 28 25
3 10 7 20 17 26 23 0
6 13 4 11 8 21 18 27
马走棋盘成功，顺序如上面123...顺序
________________END______________
网友评论