求教一个关于马踏棋盘的问题，希望好心人帮忙
下面是我写的马踏棋盘问题，运行起来总是有问题，会出现第二张图那种情况？请问有大神帮忙指出代码哪里有问题么？ {:5_99:} 可以发代码吗？ {:5_92:}图贴旁边的 <> direct = [[-2,-1],[-1,-2],,,,,[-1,2],[-2,1]]
#走过的位置标记为1
def mark(maze,pos):
maze]] = 1
print(pos)
#判断下一步位置的条件
def possible(maze,pos):
return (pos in range(8)) and (pos in range(8)) and (maze]] ==0)
#结束条件
def end_path(maze):
for m in maze:
if 0 in m:
return False
return True
def find_path(maze,pos):
mark(maze,pos)
if end_path(maze):
print(pos,end = ' ')
return True
for i in direct:
next_pos = (pos + i, pos + i)
if possible(maze,next_pos):
if find_path(maze,next_pos):
print(pos,end = ' ')
return True
return False
#创建一个二维8*8列表，元素为0
def create_maze():
b = [,,,,,,,]
return b
maze = create_maze()
find_path(maze,(0,0)) claws0n 发表于 2018-10-23 16:03
可以发代码吗？
图贴旁边的
emmm发了，拜托大神救救菜鸡{:5_100:} 大腿壮 发表于 2018-10-23 16:14
emmm发了，拜托大神救救菜鸡
可以说没有问题。你的回溯不明显，但还是有就对了。(6,7)在边界了，尝试完全剩下的路径之后，跳出子函数，回到上一层或上几层的函数开始。这是递归头疼的地方。
打印的是 mark() ，只是尝试的路径，不是正确的路径 claws0n 发表于 2018-10-23 17:00
可以说没有问题。你的回溯不明显，但还是有就对了。(6,7)在边界了，尝试完全剩下的路径之后，跳出子函数 ...
但是最后打印的时候只有56个坐标值，我画了一下，有好多位置都没有被经过。我不知道为啥会这样 大腿壮 发表于 2018-10-23 21:49
但是最后打印的时候只有56个坐标值，我画了一下，有好多位置都没有被经过。我不知道为啥会这样
诶，确实漏了，这个很急吗？这几天没空，应该要到礼拜五了，或者看谁路过 claws0n 发表于 2018-10-23 22:11
诶，确实漏了，这个很急吗？这几天没空，应该要到礼拜五了，或者看谁路过
倒是不急，就是不知道哪里有问题挺烦人的。。。希望能解答一下疑惑，感谢层主 大腿壮 发表于 2018-10-24 08:30
倒是不急，就是不知道哪里有问题挺烦人的。。。希望能解答一下疑惑，感谢层主
变量名与函数小修改。board 去记录走过的路，tour 把坐标记下来。原本的 direct 我换了，不然真的是跑太慢了。主要的架构是 mark, find_path, unmark。其他得看题目的需求。这个大概需要两分钟，没有优化的就是这样。优化的不想搞{:10_250:}def printBoard(board):
for each in board:
for i in each:
print(f'{i:3d}', end = ' ')
print()
def mark(board, pos, n):
board]] = n
def unmark(board, pos):
board]] = 0
def isPossible(board, x, y, n):
return 0 <= x < n and 0 <= y < n and board ==0
def knights_tour(board,pos):
mark(board, pos, 1)
tour =
N = len(board)
L = N * N
moves = [(1,2),(2,1),(2,-1),(1,-2),(-1,-2),(-2,-1),(-2,1),(-1,2)]
def find_path(board, pos, dep):
for i in moves:
next_pos = (pos + i, pos + i)
if isPossible(board, *next_pos, N):
mark(board, next_pos, dep)
tour.append(next_pos)
if dep == L:
return 1
if find_path(board, next_pos, dep+1) == 1:
return 1
else:
unmark(board, next_pos)
tour.pop()
return 0
if find_path(board, pos, 2):
print("Success!")
print(tour,'\n')
printBoard(board)
else:
print("Failed!")
return tour
def create_chessboard(n):
return [*n for i in range(n)]
board = create_chessboard(8)
knights_tour(board,(0,0))
页:
[1]