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

大腿壮

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

最佳答案

月排行榜 / 总排行榜

claws0n

2018-10-29 12:30:45

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

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

def printBoard(board):
    for each in board:
        for i in each:
            print(f'{i:3d}', end = ' ')
        print()

def mark(board, pos, n):
    board[pos[0]][pos[1]] = n

def unmark(board, pos):
    board[pos[0]][pos[1]] = 0

def isPossible(board, x, y, n):
    return 0 <= x < n and 0 <= y < n and board[x][y] ==  0

def knights_tour(board,pos):
    mark(board, pos, 1)
    tour = [pos]
    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[0] + i[0], pos[1] + i[1])
            
            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 [[0]*n for i in range(n)]

board = create_chessboard(8)
knights_tour(board,(0,0))

跳转到最佳答案楼层

claws0n

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

大腿壮

direct = [[-2,-1],[-1,-2],[1,-2],[2,-1],[2,1],[1,2],[-1,2],[-2,1]]
#走过的位置标记为1
def mark(maze,pos):
        maze[pos[0]][pos[1]] = 1
        print(pos)
#判断下一步位置的条件
def possible(maze,pos):
        return (pos[0] in range(8)) and (pos[1] in range(8)) and (maze[pos[0]][pos[1]] ==  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[0] + i[0], pos[1] + i[1])
                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 = [[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]]
        return b

maze = create_maze()
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。其他得看题目的需求。这个大概需要两分钟，没有优化的就是这样。优化的不想搞

def printBoard(board):
    for each in board:
        for i in each:
            print(f'{i:3d}', end = ' ')
        print()

def mark(board, pos, n):
    board[pos[0]][pos[1]] = n

def unmark(board, pos):
    board[pos[0]][pos[1]] = 0

def isPossible(board, x, y, n):
    return 0 <= x < n and 0 <= y < n and board[x][y] ==  0

def knights_tour(board,pos):
    mark(board, pos, 1)
    tour = [pos]
    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[0] + i[0], pos[1] + i[1])
            
            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 [[0]*n for i in range(n)]

board = create_chessboard(8)
knights_tour(board,(0,0))