# 688. Knight Probability in Chessboard

n = 8
k = 30
row = 6
column = 4

``````def knightProbability(self, n: int, k: int, row: int, column: int) -> float:

tracker = dict()

def recur( x , y , moves ):

if (x,y) in tracker:
return tracker[(x,y)]

if moves == 0:
if (x < 0 or x > (n-1) or y < 0 or y > (n-1)) :
return 0
else:
return 1
elif moves > 0:
if (x < 0 or x > (n-1) or y < 0 or y > (n-1)) :
return 0

count = 0

count += recur(x - 2, y - 1, moves - 1)
count += recur(x - 1, y - 2, moves - 1)
count += recur(x + 2, y - 1, moves - 1)
count += recur(x + 1, y - 2, moves - 1)
count += recur(x - 2, y + 1, moves - 1)
count += recur(x - 1, y + 2, moves - 1)
count += recur(x + 2, y + 1, moves - 1)
count += recur(x + 1, y + 2, moves - 1)

tracker[(x,y)] = count / 8

return count / 8

print(tracker)

return recur( row , column , k  )
``````

Expected : 0.00019
My Output : 0.49870

The primary problem with the current code is that it uses recursion to calculate the probability of reaching a specific cell on the chessboard after a given number of moves. This approach is not efficient and may lead to incorrect results due to a large number of redundant calculations.

To resolve this, we can use dynamic programming to store the intermediate results in a table (e.g., a 3D array) and avoid recomputing the same probabilities multiple times.

class Solution:
def knightProbability(self, n: int, k: int, row: int, column: int) â float:
# Create a 3D array âdpâ to store the probabilities of the knight being at each cell after each move.
dp = [[[0] * n for _ in range(n)] for _ in range(k + 1)]
# Define the possible directions the knight can move in one step.
directions = [(1, 2), (2, 1), (2, -1), (1, -2), (-1, -2), (-2, -1), (-2, 1), (-1, 2)]

``````# Function to check if the knight is inside the chessboard.
def is_inside(x, y):
return 0 <= x < n and 0 <= y < n

# Set the initial probability of the knight being at the starting cell to 1 (since it starts there).
dp[0][row][column] = 1

# Use dynamic programming to calculate probabilities after each move.
for move in range(1, k + 1):
for i in range(n):
for j in range(n):
for dx, dy in directions:
# Check the possible cells the knight can move to from the current cell (i, j).
x, y = i + dx, j + dy
# If the cell (x, y) is inside the chessboard, add the probability of reaching it
# to the probability of being at cell (i, j) after (move - 1) moves.
if is_inside(x, y):
dp[move][i][j] += dp[move - 1][x][y] / 8

# Calculate the overall probability of the knight being anywhere on the chessboard after 'k' moves.
probability = sum(dp[k][i][j] for i in range(n) for j in range(n))
return probability
``````