[已解决]求教一个关于马踏棋盘的问题，希望好心人帮忙

大腿壮

下面是我写的马踏棋盘问题，运行起来总是有问题，会出现第二张图那种情况？请问有大神帮忙指出代码哪里有问题么？

最佳答案

月排行榜 / 总排行榜

claws0n

2018-10-29 12:30:45

大腿壮 发表于 2018-10-24 08:30
倒是不急，就是不知道哪里有问题挺烦人的。。。希望能解答一下疑惑，感谢层主

变量名与函数小修改。board 去记录走过的路，tour 把坐标记下来。原本的 direct 我换了，不然真的是跑太慢了。主要的架构是 mark, find_path, unmark。其他得看题目的需求。这个大概需要两分钟，没有优化的就是这样。优化的不想搞

1. def printBoard(board):
   
2.     for each in board:
   
3.         for i in each:
   
4.             print(f'{i:3d}', end = ' ')
   
5.         print()
   
6. 
   
7. def mark(board, pos, n):
   
8.     board[pos[0]][pos[1]] = n
   
9. 
   
10. def unmark(board, pos):
    
11.     board[pos[0]][pos[1]] = 0
    
12. 
    
13. def isPossible(board, x, y, n):
    
14.     return 0 <= x < n and 0 <= y < n and board[x][y] ==  0
    
15. 
    
16. def knights_tour(board,pos):
    
17.     mark(board, pos, 1)
    
18.     tour = [pos]
    
19.     N = len(board)
    
20.     L = N * N
    
21.     moves = [(1,2),(2,1),(2,-1),(1,-2),(-1,-2),(-2,-1),(-2,1),(-1,2)]
    
22.    
    
23.     def find_path(board, pos, dep):
    
24.         for i in moves:
    
25.             next_pos = (pos[0] + i[0], pos[1] + i[1])
    
26.             
    
27.             if isPossible(board, *next_pos, N):
    
28.                 mark(board, next_pos, dep)
    
29.                 tour.append(next_pos)
    
30.                 if dep == L:
    
31.                     return 1
    
32.                 if find_path(board, next_pos, dep+1) == 1:
    
33.                     return 1
    
34.                 else:
    
35.                     unmark(board, next_pos)
    
36.                     tour.pop()
    
37.         return 0
    
38. 
    
39.     if find_path(board, pos, 2):
    
40.         print("Success!")
    
41.         print(tour,'\n')
    
42.         printBoard(board)
    
43.     else:
    
44.         print("Failed!")
    
45.     return tour
    
46. 
    
47. def create_chessboard(n):
    
48.     return [[0]*n for i in range(n)]
    
49. 
    
50. board = create_chessboard(8)
    
51. knights_tour(board,(0,0))

复制代码

跳转到最佳答案楼层

claws0n

可以发代码吗？
图贴旁边的 <>

大腿壮

1. direct = [[-2,-1],[-1,-2],[1,-2],[2,-1],[2,1],[1,2],[-1,2],[-2,1]]
   
2. #走过的位置标记为1
   
3. def mark(maze,pos):
   
4.         maze[pos[0]][pos[1]] = 1
   
5.         print(pos)
   
6. #判断下一步位置的条件
   
7. def possible(maze,pos):
   
8.         return (pos[0] in range(8)) and (pos[1] in range(8)) and (maze[pos[0]][pos[1]] ==  0)
   
9. #结束条件
   
10. def end_path(maze):
    
11.         for m in maze:
    
12.                 if 0 in m:
    
13.                         return False
    
14.         return True
    
15. 
    
16. def find_path(maze,pos):
    
17.         mark(maze,pos)
    
18.         if end_path(maze):
    
19.                 print(pos,end = ' ')
    
20.                 return True
    
21.         for i in direct:
    
22.                 next_pos = (pos[0] + i[0], pos[1] + i[1])
    
23.                 if possible(maze,next_pos):
    
24.                         if find_path(maze,next_pos):
    
25.                                 print(pos,end = ' ')
    
26.                                 return True
    
27.         return False
    
28. #创建一个二维8*8列表，元素为0
    
29. def create_maze():
    
30.         b = [[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]]
    
31.         return b
    
32. 
    
33. maze = create_maze()
    
34. find_path(maze,(0,0))

复制代码

大腿壮

claws0n 发表于 2018-10-23 16:03
可以发代码吗？
图贴旁边的

emmm发了，拜托大神救救菜鸡

claws0n

大腿壮 发表于 2018-10-23 16:14
emmm发了，拜托大神救救菜鸡

可以说没有问题。你的回溯不明显，但还是有就对了。(6,7)在边界了，尝试完全剩下的路径之后，跳出子函数，回到上一层或上几层的函数开始。这是递归头疼的地方。
打印的是 mark() ，只是尝试的路径，不是正确的路径

大腿壮

claws0n 发表于 2018-10-23 17:00
可以说没有问题。你的回溯不明显，但还是有就对了。(6,7)在边界了，尝试完全剩下的路径之后，跳出子函数 ...

但是最后打印的时候只有56个坐标值，我画了一下，有好多位置都没有被经过。我不知道为啥会这样

claws0n

大腿壮 发表于 2018-10-23 21:49
但是最后打印的时候只有56个坐标值，我画了一下，有好多位置都没有被经过。我不知道为啥会这样

诶，确实漏了，这个很急吗？这几天没空，应该要到礼拜五了，或者看谁路过

大腿壮

claws0n 发表于 2018-10-23 22:11
诶，确实漏了，这个很急吗？这几天没空，应该要到礼拜五了，或者看谁路过

倒是不急，就是不知道哪里有问题挺烦人的。。。希望能解答一下疑惑，感谢层主

claws0n

大腿壮 发表于 2018-10-24 08:30
倒是不急，就是不知道哪里有问题挺烦人的。。。希望能解答一下疑惑，感谢层主

变量名与函数小修改。board 去记录走过的路，tour 把坐标记下来。原本的 direct 我换了，不然真的是跑太慢了。主要的架构是 mark, find_path, unmark。其他得看题目的需求。这个大概需要两分钟，没有优化的就是这样。优化的不想搞

1. def printBoard(board):
   
2.     for each in board:
   
3.         for i in each:
   
4.             print(f'{i:3d}', end = ' ')
   
5.         print()
   
6. 
   
7. def mark(board, pos, n):
   
8.     board[pos[0]][pos[1]] = n
   
9. 
   
10. def unmark(board, pos):
    
11.     board[pos[0]][pos[1]] = 0
    
12. 
    
13. def isPossible(board, x, y, n):
    
14.     return 0 <= x < n and 0 <= y < n and board[x][y] ==  0
    
15. 
    
16. def knights_tour(board,pos):
    
17.     mark(board, pos, 1)
    
18.     tour = [pos]
    
19.     N = len(board)
    
20.     L = N * N
    
21.     moves = [(1,2),(2,1),(2,-1),(1,-2),(-1,-2),(-2,-1),(-2,1),(-1,2)]
    
22.    
    
23.     def find_path(board, pos, dep):
    
24.         for i in moves:
    
25.             next_pos = (pos[0] + i[0], pos[1] + i[1])
    
26.             
    
27.             if isPossible(board, *next_pos, N):
    
28.                 mark(board, next_pos, dep)
    
29.                 tour.append(next_pos)
    
30.                 if dep == L:
    
31.                     return 1
    
32.                 if find_path(board, next_pos, dep+1) == 1:
    
33.                     return 1
    
34.                 else:
    
35.                     unmark(board, next_pos)
    
36.                     tour.pop()
    
37.         return 0
    
38. 
    
39.     if find_path(board, pos, 2):
    
40.         print("Success!")
    
41.         print(tour,'\n')
    
42.         printBoard(board)
    
43.     else:
    
44.         print("Failed!")
    
45.     return tour
    
46. 
    
47. def create_chessboard(n):
    
48.     return [[0]*n for i in range(n)]
    
49. 
    
50. board = create_chessboard(8)
    
51. knights_tour(board,(0,0))

复制代码