Python递归列表代码运行不正常

Question

我试图创建一个递归算法，以解决“骑士之旅”的国际象棋谜题，在那里你试图访问一个棋盘上的每个空间正好一次与一个骑士。我的代码使用递归分割成每一个可能的下一步，每次骑士应该再次移动，但我遇到了一个错误，骑士没有移动一个回合，然后继续下一个回合。这是我的密码：

def recursivePlay(board, knightSpot, myMoves):

    if(len(board) == 63):
        print("FOUND IT\n")
        print("the seed is: ")
        print(myMoves+"\n")
        print(board)

    for i in range(8):
        moving = bash(i)
        x = moving.x + knightSpot.x
        y = moving.y + knightSpot.y

        if(not(steppedOn(board,x,y)) and validMove(knightSpot,x,y)):


            board.append(knightSpot)

            knightSpot = Spot(x,y)

            myMoves.append(i)

            recursivePlay(board,knightSpot,myMoves)

def bash(num):
    if(num < 4):
        num += 2
        return Spot(2*((-1)**int(num/2)), (-1)**int(num))
    else:
        num -= 2
        return Spot((-1)**int(num), 2*((-1)**int(num/2)))   

def validMove(knightSpot, x, y):
    tempx = knightSpot.x
    tempy = knightSpot.y

    if(tempx == x and tempy == y):
        return False

    if(abs(tempx-x) == 2):
        return (abs(tempy-y) == 1)

    if(abs(tempy-y) == 2):
        return (abs(tempx-x) == 1)


def steppedOn(myList, mySpotX, mySpotY):

    if(mySpotX < 0 or mySpotX > 7 or mySpotY < 0 or mySpotY > 7):
        return True

    check = False

    for i in myList:
        if(i.compare(mySpotX, mySpotY)):
            check = True

    return check

class Spot(object):
    def __init__(self, x, y):
        self.x = x
        self.y = y

    def __repr__(self):
        return ("{"+str(self.x)+", "+str(self.y)+"}")

    def compare(self, compx, compy):
        return self.x == compx and self.y == compy

当我运行方法recursivePlay时，我的输出是：

    FOUND IT

    the seed is: 

    [2, 0, 2, 0, 2, 0, 2, 3, 2, 4, 0, 0, 1, 3, 1, 3, 1, 3, 1, 6, 0, 2, 0, 2, 0, 4,
 2, 0, 3, 1, 1, 3, 1, 3, 2, 2, 0, 2, 5, 0, 2, 0, 2, 0, 5, 3, 1, 3, 1, 7, 2, 0, 2,
 6, 6, 4, 0, 1, 0, 5, 1, 6, 3]


    Spaces visited: 

    [{0, 0}, {2, 1}, {0, 2}, {2, 3}, {0, 4}, {2, 5}, {0, 6}, {2, 7}, {4, 6}, 
{6, 7}, {7, 5}, {5, 6}, {3, 7}, {1, 6}, {3, 5}, {1, 4}, {3, 3}, {1, 2}, {3, 1},
 {1, 0}, {2, 2}, {0, 3}, {2, 4}, {0, 5}, {2, 6}, {0, 7}, {1, 5}, {3, 6}, {3, 6},
 {5, 5}, {3, 4}, {1, 3}, {3, 2}, {1, 1}, {3, 0}, {5, 1}, {7, 2}, {5, 3}, {7, 4},
 {6, 2}, {4, 3}, {6, 4}, {4, 5}, {6, 6}, {6, 6}, {5, 4}, {7, 3}, {5, 2}, {7, 1},
 {5, 0}, {4, 2}, {6, 3}, {4, 4}, {6, 5}, {6, 5}, {5, 2}, {6, 0}, {4, 1}, {2, 0},
 {7, 3}, {6, 1}, {4, 5}, {5, 7}]

如您所见，它在第5行第5点访问的空间和第6行第5点访问的空间中重复了一个点。bash函数永远不应该返回0，即缺少移动，validMove函数还包含一个条件来防止这种情况。有人能告诉我为什么会这样吗？你知道吗

Answer 1

主要的问题是你没有正确地处理递归你设置了临时状态和递归，但是在尝试另一种可能性之前没有处理递归的潜在失败和解除临时状态。这就是为什么你积累重复和退出太早，由于总长度。我已经重新编写了您的代码，但请阅读下面关于一个更大问题的注释：

def recursivePlay(layout, board, knightSpot, moves):

    if len(board) == layout.x * layout.y - 1:
        return True

    for i in range(8):
        newSpot = bash(i)

        newSpot.x += knightSpot.x
        newSpot.y += knightSpot.y

        if not steppedOn(board, newSpot) and validMove(layout, knightSpot, newSpot):

            board.append(knightSpot)
            knightSpot = newSpot
            moves.append(i)

            if recursivePlay(layout, board, knightSpot, moves):
                return True

            knightSpot = board.pop()
            moves.pop()

    return False

def bash(num):
    if num < 4:
        num += 2
        return Spot(2 * (-1)**(num // 2), (-1)**num)
    num -= 2
    return Spot((-1)**num, 2 * (-1)**(num // 2))

def validMove(layout, knightSpot, spot):

    if spot.x < 0 or spot.x >= layout.x or spot.y < 0 or spot.y >= layout.y:
        return False

    if abs(knightSpot.x - spot.x) == 2:
        return abs(knightSpot.y - spot.y) == 1

    if abs(knightSpot.y - spot.y) == 2:
        return abs(knightSpot.x - spot.x) == 1

    return False

def steppedOn(used_spots, spot):

    for used_spot in used_spots:
        if used_spot == spot:
            return True

    return False

class Spot(object):
    def __init__(self, x, y):
        self.x = x
        self.y = y

    def __repr__(self):
        return "{" + str(self.x) + ", " + str(self.y) + "}"

    def __eq__(self, other):
        return self.x == other.x and self.y == other.y

myMoves = []
myBoard = []
myLayout = Spot(5, 5)

if recursivePlay(myLayout, myBoard, Spot(0, 0), myMoves):

    print("FOUND IT FOR", myLayout, "\n")
    print("the seed is: ")
    print(myMoves, "\n")
    print(myBoard)

我添加了指定电路板大小的功能。你的解决方案是暴力。如果您阅读Wikipedia article on Knight's Tour，特别是brute-force algorithms，您将看到，对于8x8板，您不能期望此代码在短时间内返回结果。我留下了一个5 x 5板的代码集，你的算法可以很快解决，你可以增加耐心和/或你添加启发式。你知道吗