Learn
Practice
Interview
Resources
Newsletter
F
Toggle theme
0
F
0
Toggle menu
Animations
← Back to All Animations
Knight Probability in Chessboard
Bookmark
Recursion
Memoization
Bottom-Up DP
Input
3×3, 2 moves
4×4, center
3×3, 1 move
5×5, center
4×4, 3 moves (cache hits)
Custom
n
=
3
,
k
=
2
,
row
=
0
,
column
=
0
move
0
/ 2
P(on board) =
1.00000
each move splits a square's probability across its 8 knight jumps
move
0
/ 2
P(on board) =
1.00000
each move splits a square's probability across its 8 knight jumps
move
0
/ 2
P(on board) =
1.00000
♞
off
off
off
off
off
off
/ 8 =
to each on-board jump; off-board jumps are lost
call stack
f(2,0,0)
3 calls
move
0
/ 2
P(on board) =
1.00000
♞
off
off
off
off
off
off
/ 8 =
to each on-board jump; off-board jumps are lost
call stack
f(1,1,2)
f(2,0,0)
7 calls
move
0
/ 2
P(on board) =
1.00000
♞
off
off
off
off
off
off
/ 8 =
to each on-board jump; off-board jumps are lost
call stack
f(0,0,0)
f(1,1,2)
f(2,0,0)
10 calls
move
0
/ 2
P(on board) =
1.00000
♞
off
off
off
off
off
off
/ 8 =
to each on-board jump; off-board jumps are lost
call stack
f(1,1,2)
f(2,0,0)
12 calls
move
0
/ 2
P(on board) =
1.00000
♞
off
off
off
off
off
off
/ 8 =
to each on-board jump; off-board jumps are lost
call stack
f(1,1,2)
f(2,0,0)
15 calls
move
0
/ 2
P(on board) =
1.00000
♞
off
off
off
off
off
off
/ 8 =
to each on-board jump; off-board jumps are lost
call stack
f(0,0,0)
f(1,2,1)
f(2,0,0)
18 calls
move
0
/ 2
P(on board) =
1.00000
♞
off
off
off
off
off
off
/ 8 =
to each on-board jump; off-board jumps are lost
call stack
f(1,2,1)
f(2,0,0)
20 calls
move
0
/ 2
P(on board) =
1.00000
/ 8 =
to each on-board jump; off-board jumps are lost
call stack
f(0,4,0)
f(1,2,1)
f(2,0,0)
24 calls
move
0
/ 2
P(on board) =
0.06250
P(on board) = 0.06250
algo
master
.
io
Step:
Knight starts at (0, 0) on an 3×3 board and makes 2 random knight moves. Find P(still on board).
0 / 85
Input
3×3, 2 moves
4×4, center
3×3, 1 move
5×5, center
4×4, 3 moves (cache hits)
Custom
n
=
3
,
k
=
2
,
row
=
0
,
column
=
0
0 / 85
algo
master
.
io
Step:
Knight starts at (0, 0) on an 3×3 board and makes 2 random knight moves. Find P(still on board).
