• API
• FAQ
• Tools
• Archive
SHARE
TWEET # Untitled a guest Nov 15th, 2019 91 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1.
2. '''
3. Approach: Use backtracking, Starting every position, find how many ways can the knight reach the last point.
4. every time it makes a valid move, mark square as True, increment move++, recurse then mark it back as False, to check further possibilities.
5. if at any point, it reaches to the last square, at that time moves=n*n -> return 1
6. Keep count of every successful recursion call from each neighbor and return the count so far.
7. 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)
8. get total count of them.
9. 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)
10. Space: O(n^2) => matrix board size.
11. '''
12. def get_neighbors(i,j,matrix):
13.     n=len(matrix)
14.     directions=[(-2,-1),(-2,1),(-1,2),(1,2),(2,1),(2,-1),(1,-2),(-1,-2)]
15.     neighbors=[]
16.     for direction in directions:
17.         x=i+direction
18.         y=j+direction
19.         if x>-1 and x<n and y>-1 and y<n:
20.             if not matrix[x][y]:
21.                 neighbors.append((x,y))
22.     return neighbors
23.
24. def knight_tour(n):
25.     matrix=[[False for _ in range(n)]for _ in range(n)]
26.
27.     def tour(matrix,i,j,moves):
28.         n=len(matrix)
29.         if moves==n*n:
30.             return 1
31.         count=0
32.         for neighbor in get_neighbors(i,j,matrix):
33.             matrix[neighbor][neighbor] = True
34.             count+=tour(matrix,neighbor,neighbor,moves+1)
35.             matrix[neighbor][neighbor] = False
36.         return count
37.
38.     total=0
39.     for i in range(n):
40.         for j in range(n):
41.             matrix[i][j]=True
42.             total+=tour(matrix,i,j,1)
43.             matrix[i][j]=False