# python – Is this BFS solution ‘slow’ – 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(0), move(1), move(2)):
pos_moves.append((next_move(0), next_move(1), next_move(2)))

i += 1

ans = 0
for m in pos_moves:
ans += m(2)

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(2) = 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!