Knight Probability in Chessboard (DP)
Question:
On an n*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, as illustrated below. Each move is two cells in a cardinal direction, then one cell is 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.
Solution:
First we’ll start with recursive solution. If k==0 where k is the number of moves then we return 1 . This is a base case because any position (i,j) within board boundary with k==0 is a right candidate. We’ll aim to reach towards this base case.
Now let’s list all the possible positions a cell (0,0) can go to in a clockwise direction: (1,2), (2,1), (-1,2), (-2,1), (1,-2), (2,-1), (-1,-2), (-2,-1) .
Each of these position can go all these eight directions. So there we have recursion. As we pop off the stack we’ll divide the total right cell candidates by 8 as there are total 8 positions.
Here’s the implementation:
def knight_probability_helper(n: int, k: int, row: int, col: int) -> int:
# if elif condition's order matters
if not (0<=row<n and 0<=col<n):
return 0
elif k == 0: # only after checking that row,col is within boundary
return 1
else:
probability = 0
for r,c in [(1,2), (2,1), (-1,2), (-2,1), (1,-2), (2,-1), (-1,-2), \
(-2,-1)]:
probability += knight_probability_helper(n, k-1, row+r, col+c)
return probability/8
def knight_probability(n: int, k: int, row: int, column: int) -> float:
return knight_probability_helper(n, k, row, column)
n = 3
k = 2
row = 0
column = 0
print(knight_probability(n, k, row, column))The recursive tree looks like this:
Runtime Complexity: O(k*N^2) where k is the size of the move and N the size of the board.
Space Complexity: O(k*N^2) where k is the size of the move and N the size of the board.
To avoid repetitive compute, we’ll use memoization to store computed keys. Here’s the implementation:
from typing import Dict, Tuple
from collections import defaultdict
def knight_probability_helper(n: int, k: int, row: int, col: int, \
memo: Dict[Tuple[int, int, int], int]) -> int:
if not (0<=row<n and 0<=col<n):
return 0
elif k == 0:
return 1
elif (row,col,k) in memo:
return memo[(row,col,k)]
else:
probability = 0
for r,c in [(1,2), (2,1), (-1,2), (-2,1), (1,-2), (2,-1), \
(-1,-2), (-2,-1)]:
probability += knight_probability_helper(n, k-1, row+r, col+c, \
memo)
memo[(row,col,k)] = probability/8
return memo[(row,col,k)]
def knight_probability(n: int, k: int, row: int, column: int) -> float:
memo = defaultdict(int)
return knight_probability_helper(n, k, row, column, memo)
n = 3
k = 2
row = 0
column = 0
print(knight_probability(n, k, row, column)) # prints 0.0625
n1 = 1
k1 = 0
row1 = 0
column1 = 0
print(knight_probability(n1, k1, row1, column1)) # prints 1Runtime complexity: O(k*N^2) where k is the size of the move and N is the size of the board.
Space complexity: O(N^2) where N is the size of the board.
Now let’s do the Dynamic Programming (DP) implementation. Two things to remember in DP is to recognize the subproblem and using the subproblem’s solution to build the solution of your target.
We know for k=0 and the initial position (i,j) of the knight, move count is 1. We’ll use this information and previous knight’s move to calculate the current move.
After checking all 8 positions move, we’ll register in our dp matrix the total possible move divided by 8.
We’ll sum the probability for k moves.
Let’s see the implementation:
def knight_probability(n: int, k: int, row: int, column: int):
dp = [[[0]*n for _ in range(n)] for _ in range(k+1)]
dp[0][row][column] = 1
for move in range(1, k+1):
for i in range(n):
for j in range(n):
for m_i, m_j in [(1,2), (2,1), (-1,2), (-2,1), (1,-2), \
(2,-1), (-1,-2), (-2,-1)]:
prev_i, prev_j = i-m_i, j-m_j
if 0<=prev_i<n and 0<=prev_j<n:
dp[move][i][j] += dp[move-1][prev_i][prev_j]
dp[move][i][j]/=8
total_probability = sum(dp[k][i][j] for i in range(n) for j in range(n))
return total_probability
n = 3
k = 2
row = 0
column = 0
print(knight_probability(n, k, row, column)) # prints 0.0625
n1 = 1
k1 = 0
row1 = 0
column1 = 0
print(knight_probability(n1, k1, row1, column1)) # prints 1
Runtime complexity: O(k*N^2) where k is the size of the move and N is the size of the board.
Space complexity: (k*N^2) where k is the size of the move and N is the size of the board.
There’s the DP implementation!
Now let’s do one more question: Longest Substring Without Repeating Characters
Question: Given a string s, find the length of the longest substring without repeating characters.
We’ll use a sliding window principle to check if a character is present in a substring. If present, we’ll create a new substring from the previous substring but starting after the character’s index.
def length_of_longest_substring(s: str) -> int:
res = 0
sub_str = ""
for i in range(len(s)):
char = s[i]
# if a character is present create a new substring
if char in sub_str:
sub_str = sub_str[sub_str.index(char)+1:]
sub_str += char
res = max(res, len(sub_str))
return res
print(length_of_longest_substring("abcabcbb")) # prints 3
print(length_of_longest_substring("bbbbb")) # prints 1Runtime complexity: O(n) where n is the length of the string.
Space complexity: O(1)
Congratulations for coming this far on the algorithm journey! 🎈Hope the post was helpful.
Until next time, ✨.
Inspiration:
You can support me in Patreon!
