带回溯的骑士​​之旅

Question

我正在尝试编写一个 Python 程序，它将使用回溯解决 Knight's Tour 问题。对于那些不熟悉的人：“马被放置在一个空棋盘的第一个格子上，根据国际象棋规则移动，必须恰好访问每个格子一次。”

我的代码大部分工作但不完全。它通常得到第 7 步，然后 returns 未完成的棋盘。为什么？

board = [
[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]]

def move(x, y, count, move_x, move_y):
    if count == len(board)**2:
        return True
    for i in range(8):
        if is_valid(x + int(move_x[i]), y + int(move_y[i]), board):
            if move(x + move_x[i], y + move_y[i], count + 1, move_x, move_y):
                board[x][y] = count
                return True
    return False
    

def print_board(bo):
    for i in range(len(bo)):
        for j in range(len(bo[0])):
            if j == (len(board[0]) - 1):
                print(bo[i][j])
            else:
                print(bo[i][j], end = " ")


def is_valid(x, y, board):
    if x >= 0 and y >= 0 and x < len(board) and y < len(board) and board[x][y] == 0:
        return True
    return False



def solve(bo):
    print_board(board)
    move_x = [1, 2, 2, 1, -1, -2, -2, -1]
    move_y = [2, 1, -1, -2, -2, -1, 1, 2]
    counter = 1
    x_loc = 0
    y_loc = 0

    if not(move(x_loc, y_loc, counter, move_x, move_y)):
        print("No solution")
    else:
        print("                 ")
        print_board(board)

solve(board)
    

Answer 1

• 对move()的递归调用应该在设置board[x][y] = count之后进行。
  • 此外，如果move() returns false，那么你应该board[x][y] = 0
• 其实count并不需要在每个board cell中存储。它只需要在每次递归调用中传递和递增。您可以使用布尔值指示单元格是否已被访问。
• 最后的想法：有 2^64 种棋盘状态和更多的路径可以反复击中失败状态。因此，失败状态应存储在哈希中以避免重复搜索失败路径。

Answer 2

    def process(i,j,cnt,board,n,query):
    board[i][j]=cnt
    cnt+=1
    if cnt==n*n+1:
        for a in range(n):
            print(board[a])
        print()
        if query==0:
            return True
        else:
            True
    stack=[]
    
    if i+2<n and j-1>-1 and board[i+2][j-1]==-1:
        stack.append([i+2,j-1])
    if i+1<n and j-2>-1 and board[i+1][j-2]==-1:
        stack.append([i+1,j-2])
    if i-1>-1 and j-2>-1 and board[i-1][j-2]==-1:
        stack.append([i-1,j-2])
    if i-2>-1 and j-1>-1 and board[i-2][j-1]==-1:
        stack.append([i-2,j-1])
    if i-2>-1 and j+1<n and board[i-2][j+1]==-1:
        stack.append([i-2,j+1])
    if i-1>-1 and j+2<n and board[i-1][j+2]==-1:
        stack.append([i-1,j+2])
    if i+1<n and j+2<n and board[i+1][j+2]==-1:
        stack.append([i+1,j+2])
    if i+2<n and j+1<n and board[i+2][j+1]==-1:
        stack.append([i+2,j+1])

    while (len(stack))>0:
        curr=stack.pop()
        if query==0:
            if(process(curr[0],curr[1],cnt,board,n,query)):
                return True
            else :
                board[curr[0]][curr[1]]=-1
        else:
            process(curr[0],curr[1],cnt,board,n,query)
            board[curr[0]][curr[1]]=-1
    return


########     Driver Code     ########



    query=input("If you want program to output all possible ways of KNIGHT'S TOUR, say Yes or else say No :- ")
    if query[0]=='y' or query[0]=='Y':
        query=input("This process may be too slow for N greater than 5, it will work fast if N is less than 6. Are u sure u want to go for it? (Yes/No) :- ")
    if query[0]=='y' or query[0]=='Y':
        query=1
    else :
        query=0
    n=int(input("Enter the value of N :- "))
    if(n<5):
        print("Not possible for N less than 5")
    else:
        board= [[-1]*n for i in range(n)]
        cnt=1
        process(0,0,cnt,board,n,query)

    

########     Some precomputed outputs     ########


# N = 5
#
# [1, 12, 3, 18, 21]
# [4, 17, 20, 13, 8]
# [11, 2, 7, 22, 19]
# [16, 5, 24, 9, 14]
# [25, 10, 15, 6, 23]


# N = 6
#
# [1, 20, 3, 18, 5, 22]
# [36, 11, 28, 21, 30, 17]
# [27, 2, 19, 4, 23, 6]
# [12, 35, 10, 29, 16, 31]
# [9, 26, 33, 14, 7, 24]
# [34, 13, 8, 25, 32, 15]


# N = 7
#
# [1, 14, 3, 38, 5, 34, 7]
# [12, 39, 10, 33, 8, 37, 26]
# [15, 2, 13, 4, 25, 6, 35]
# [40, 11, 32, 9, 36, 27, 44]
# [19, 16, 21, 24, 45, 48, 29]
# [22, 41, 18, 31, 28, 43, 46]
# [17, 20, 23, 42, 47, 30, 49]


# N = 8
#
# [1, 60, 39, 34, 31, 18, 9, 64]        
# [38, 35, 32, 61, 10, 63, 30, 17]      
# [59, 2, 37, 40, 33, 28, 19, 8]        
# [36, 49, 42, 27, 62, 11, 16, 29]      
# [43, 58, 3, 50, 41, 24, 7, 20]        
# [48, 51, 46, 55, 26, 21, 12, 15]      
# [57, 44, 53, 4, 23, 14, 25, 6]        
# [52, 47, 56, 45, 54, 5, 22, 13]