# Calculate probability that knight does not attempt to leave chessboard after at most k random moves (LeetCode #688)

I'm learning competitive programming and came across this question on LeetCode : 688. Knight Probability in Chessboard

On an n x n chessboard, a knight starts at the cell (row, column) and attempts to make exactly k moves. The rows and columns are 0-indexed, so the top-left cell is (0, 0), and the bottom-right cell is (n - 1, n-1).

A chess knight has eight possible moves it can make, each move is two cells in a cardinal direction, then one cell in an orthogonal direction. Each time the knight is to move, it chooses one of eight > possible moves uniformly at random (even if the piece would go off the chessboard) and moves there.

The knight continues moving until it has made exactly k moves or has moved off the chessboard.

Return the probability that the knight remains on the board after it has stopped moving.

I wrote following BFS solution for it

from collections import deque

class Solution:
def knightProbability(self, N: int, K: int, r: int, c: int) -> float:
i = 0
pos_moves = deque([[r, c, 1]])  # (r, c, prob)
self.moves_memo = {}
while i < K and len(pos_moves):
increase_i_after = len(pos_moves)
for j in range(increase_i_after):
move = pos_moves.popleft()

for next_move in self.get_pos_moves(N, move, move, move):
pos_moves.append((next_move, next_move, next_move))

i += 1

ans = 0
for m in pos_moves:
ans += m

return ans/len(pos_moves) if len(pos_moves) > 0 else 0

def get_pos_moves(self, n, r, c, prev_p):
# Returns a list of possible moves
if (r, c) in self.moves_memo:
pos_moves = self.moves_memo[(r, c)]
else:
pos_moves = deque([])
if r+2 < n:
if c+1 < n:
pos_moves.append([r+2, c+1, 0])
if c-1 >= 0:
pos_moves.append([r+2, c-1, 0])
if r+1 < n:
if c+2 < n:
pos_moves.append([r+1, c+2, 0])
if c-2 >= 0:
pos_moves.append([r+2, c-2, 0])
if r-2 >= 0:
if c+1 < n:
pos_moves.append([r-2, c+1, 0])
if c-1 >= 0:
pos_moves.append([r-2, c-1, 0])
if r-1 >= 0:
if c+2 < n:
pos_moves.append([r-1, c+2, 0])
if c-2 >= 0:
pos_moves.append([r-1, c-2, 0])

self.moves_memo[(r, c)] = pos_moves

l = len(pos_moves)
if l == 0:
return pos_moves
else:
for move in pos_moves:
move = prev_p*l/8

return pos_moves



For n = 8, K = 30, r = 6, c = 4, this solution exceeds time limits. I am not able to figure out why is this solution less time efficient than this. I'm looking for reasons why my code is 'slow'. Thank you!

• At a high level, the linked answer is faster than yours because of @functools.lru_cache -- in other words, memoization. During the computation, travels() is called many times -- sometimes with the same arguments as a prior call. Whenever that happens, the memoized-function can return immediately, without repeating the same calculation again. Your BFS code, by contrast, is doing a lot of repetitive work.
– FMc
May 4, 2021 at 23:30