a guest Nov 15th, 2019 91 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
- 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):
- for direction in directions:
- if x>-1 and x<n and y>-1 and y<n:
- if not matrix[x][y]:
- return neighbors
- def knight_tour(n):
- matrix=[[False for _ in range(n)]for _ in range(n)]
- def tour(matrix,i,j,moves):
- if moves==n*n:
- return 1
- for neighbor in get_neighbors(i,j,matrix):
- matrix[neighbor][neighbor] = True
- matrix[neighbor][neighbor] = False
- return count
- for i in range(n):
- for j in range(n):
- return total
RAW Paste Data