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)]
            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
            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!

  • 1
    \$\begingroup\$ 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. \$\endgroup\$ – FMc May 4 at 23:30

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.