Classi c Knight Tour Problem, 1 ячейка без посещения

Question

Я пытаюсь решить тур Рыцаря, используя Обратное отслеживание, где Рыцарь должен посетить все ячейки. В любом случае, я всегда получаю 1 ячейку без посещения. Пример для размера ChessBoard 4x4, я получаю вывод как:

1 8 13 10

14 11 4 7

5 2 9 12

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

Кроме того, нет решения для платы 4x4, начинающейся с позиции [0] [0], но этот код будет работать для платы 8x8.