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

Question

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!

Answer 1

Both answers basically try all k-length paths and count the number of paths that remain on the board compared to all possible paths.

A major difference between your answer and the recursive solution you link to is what is cached (i.e., memoized). You code caches the possible moves from a square. The linked code caches partial solutions. That is, the cache key is the position on the board and the number of moves remaining.

Consider starting at (0,0) with k steps. One path might start (0,0,k)->(1,2,k-1)->(3,3,k-2),.... When calculating the path that starts with (0,0,k)->(2,1,k-1)->(3,3,k-2), the linked code has already calculated and cached the partial solution for (3,3,k-2) and doesn't need to calculate all those paths again. In contrast, you solution only caches the legal moves from (3,3) and does need to go through all the paths again.

Note, the linked answer could be sped up significantly by using the symmetry of the board to cache partial solutions for reflected and rotated squares. For the paths mentioned above, the solution for (2,1,k-1) and (1,2,k-1) are the same because of board symmetry. For each square on the diagonal or horizontal/vertical centerlines (if any) there are 3 squares with the same solutions due to symmetry. For other squares there are 7 other equivalent squares. A caching algorithm that uses this symmetry could be much faster.