经典骑士巡演问题，1个单元未访问

Question

我正试图用回溯法解决奈特之旅，奈特必须访问所有的牢房 不管怎么说，我总是有一间牢房无人看管。 例如，对于4x4棋盘大小，我得到的输出为：

1 8 13 10

141147

529912

0 15 6 3

如您所见，最左下角的单元格始终未被访问。如何修复它，使其访问所有单元格。 下面是我的代码：

import sys
from pandas import *
class knightTour:

    xMoves = [2, 1, -1, -2, -2, -1, 1, 2] 
    yMoves = [1, 2, 2, 1, -1, -2, -2, -1] 

    def KT(self,size):
        self.size=size
        visited = [[0 for i in range(size) ]for i in range(size)]

        visited[0][0]=1

        if(self.solveKT(visited,2,0,0)):
            self.printSolution(visited)
        else:
            print("No solution Found")
    
    def solveKT(self,visited,moveCount,x,y):
        if(moveCount == self.size**2):
            return True
        
        for i in range(8):
            nextX= x+self.xMoves[i]
            nextY= y+self.yMoves[i]



            if self.isValidMove(visited,nextX,nextY):
                
                visited[nextX][nextY] = moveCount

                if(self.solveKT(visited,moveCount+1,nextX,nextY)):
                    return True
                

                visited[nextX][nextY]=0
            
        return False

    def isValidMove(self,visited,x,y):
        n=len(visited)
        if x >= 0 and y >= 0 and x < n and y < n and visited[x][y]==0:
            return True
        else:
            return False
        
    def printSolution(self,visited):
        print(DataFrame(visited))
        
        # for i in range(len(visited)):
        #     print(visited[i])
        # print("\n")

obj=knightTour()
obj.KT(4)

Answer 1

更改代码的这一部分：

if(moveCount == self.size**2+1):
          return True

此外，从位置[0][0]开始的4x4电路板没有解决方案，但此代码适用于8x8电路板