时间戳

首页 > 解决方案 > 使用回溯的骑士​​之旅

recursion - 使用回溯的骑士​​之旅

问题描述

我得到了一些初始化代码，并被告知要编写一个函数 knight(n,y,x) 来打印问题的解决方案。

这个初始化代码是

 size = 8
         board = []
         for y in range(size) :
             board = board + [[-1]*size]
         moves= [[1,2],[1,-2],[-1,2],[-1,-2],
                 [2,1],[2,-1],[-2,1],[-2,-1]]

到目前为止，我的代码似乎永远运行的是

def knight(n,y,x):
    if n == 0:
        board[y][x] = 0
        n = 1
    elif n == (size**2) :
        return board
    for j,i in moves:
        y1 = y+j
        x1 = x+i
        if y1 < size and x1 < size and y1>=0 and x1>=0 and board[y1][x1] == -1:
            board[y1][x1] = n
            knight(n+1,y1,x1)
            board[y1][x1] = -1
    return

但我不明白为什么这是一个问题。我已经浏览了这里的一些现有问题，但它们使用了多个功能，而我们被告知只使用一个。有人可以帮忙吗？

标签： recursionbacktrackingknights-tour

解决方案

我在您的代码中发现了一个问题，它修复了最多 7x7 板的所有问题。我认为它可以在 8x8 上运行，只是需要更长的时间。您可能必须实施一些算法改进以使其更快。无论如何，我发现的错误是：

您正在寻找电路板，但您只返回一帧。您需要对其进行设置，以便在找到电路板时，代码会一直返回它。

尝试替换以下行：

knight(n+1,y1,x1)

具有以下内容：

sol = knight(n+1,y1,x1)
if sol is not None:
    return sol

我将尝试从 8x8 获得答案，如果我能提供更多帮助，请更新此内容。

推荐阅读