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[0]
  18.         y=j+direction[1]
  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[0]][neighbor[1]] = True
  34.             count+=tour(matrix,neighbor[0],neighbor[1],moves+1)
  35.             matrix[neighbor[0]][neighbor[1]] = 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
  44.     return total
  45.  
  46. print(knight_tour(5))
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!
 
Top