'''
Approach: Use backtracking, Starting every position, find how many ways can the knight reach the last point.
every time it makes a valid move, mark square as True, increment move++, recurse then mark it back as False, to check further possibilities.
if at any point, it reaches to the last square, at that time moves=n*n -> return 1
Keep count of every successful recursion call from each neighbor and return the count so far.
This method ^^ gives count for cell (0,0) as first knight move, now place it on (0,1) & start.. and so on.. up to (n-1,n-1)
get total count of them.
Time complexity: O(8^(n^2)). For every cell we're checking 8 neighbors (even if they're visited, we still have to check whether they're marked as visited or not)
Space: O(n^2) => matrix board size.
'''
def get_neighbors(i,j,matrix):
    n=len(matrix)
    directions=[(-2,-1),(-2,1),(-1,2),(1,2),(2,1),(2,-1),(1,-2),(-1,-2)]
    neighbors=[]
    for direction in directions:
        x=i+direction[0]
        y=j+direction[1]
        if x>-1 and x<n and y>-1 and y<n:
            if not matrix[x][y]:
                neighbors.append((x,y))
    return neighbors

def knight_tour(n):
    matrix=[[False for _ in range(n)]for _ in range(n)]

    def tour(matrix,i,j,moves):
        n=len(matrix)
        if moves==n*n:
            return 1
        count=0
        for neighbor in get_neighbors(i,j,matrix):
            matrix[neighbor[0]][neighbor[1]] = True
            count+=tour(matrix,neighbor[0],neighbor[1],moves+1)
            matrix[neighbor[0]][neighbor[1]] = False
        return count

    total=0
    for i in range(n):
        for j in range(n):
            matrix[i][j]=True
            total+=tour(matrix,i,j,1)
            matrix[i][j]=False
    return total

print(knight_tour(5))