Classic Knight Tour Problem , 1 cell unvisited

Question

I am trying to solve Knight's tour using Backtracking, where Knight has to visit all the cells Anyhow I am always getting 1 cell unvisited. Example for 4x4 chessBoard size, I am getting output as:

1 8 13 10

14 11 4 7

5 2 9 12

0 15 6 3

As you can see, that Left Bottom most cell is unvisited always. How can I fix it so it visits all cells. Below is my code:

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

Change this part of your code:

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

Also, there is no solution for 4x4 board starting at position [0][0], but this code will work for 8x8 board.