Problem Statement: Given a N*N board with the Knight placed on the first block of an empty board. Moving according to the rules of chess knight must visit each square exactly once. Print the order of each the cell in which they are visited.
Example:
Input :
N = 8
Output:
0 59 38 33 30 17 8 63
37 34 31 60 9 62 29 16
58 1 36 39 32 27 18 7
35 48 41 26 61 10 15 28
42 57 2 49 40 23 6 19
47 50 45 54 25 20 11 14
56 43 52 3 22 13 24 5
51 46 55 44 53 4 21 12
My code:
def knightTravels(i,j,count,n,mat):
if count == n**2:
for list1 in mat:
print(mat)
print("====================")
return
if i < 0 or j < 0 or i >= n or j >= n:
return
if mat[i][j] != 0:
return
mat[i][j] = count
knightTravels(i-2,j-1,count+1,n,mat) # check
knightTravels(i-2,j+1,count+1,n,mat) # check
knightTravels(i-1,j-2,count+1,n,mat) # check
knightTravels(i+1,j-2,count+1,n,mat) # check
knightTravels(i+2,j-1,count+1,n,mat) # check
knightTravels(i+2,j+1,count+1,n,mat) # check
knightTravels(i-1,j+2,count+1,n,mat) # check
knightTravels(i+1,j+2,count+1,n,mat) # check
mat[i][j] = 0
def knightTour(n):
mat = []
for x in range(n):
list1 = []
for y in range(n):
list1.append(0)
mat.append(list1)
i = j = count = 0
knightTravels(i,j,count,n,mat)
knightTour(8)
Problem: The code is throwing TLE, I am using backtracking the same way we solve rat in a maze problem. What is wrong with my code?
