# Python recursive solution with cache

• ``````class Solution:
def work(self, N, K, r, c, onboard, cache):
offboard = r < 0 or c < 0 or r >= N or c >= N
if K == 0 or offboard:
if not offboard:
onboard += 1
return onboard
if (K, r, c) in cache:
return cache[(K, r, c)]

count = self.work(N, K - 1, r + 1, c + 2, onboard, cache) + \
self.work(N, K - 1, r + 1, c - 2, onboard, cache) + \
self.work(N, K - 1, r - 1, c + 2, onboard, cache) + \
self.work(N, K - 1, r - 1, c - 2, onboard, cache) + \
self.work(N, K - 1, r + 2, c + 1, onboard, cache) + \
self.work(N, K - 1, r + 2, c - 1, onboard, cache) + \
self.work(N, K - 1, r - 2, c + 1, onboard, cache) + \
self.work(N, K - 1, r - 2, c - 1, onboard, cache)
cache[(K, r, c)] = count
return count

def knightProbability(self, N, K, r, c):
"""
:type N: int
:type K: int
:type r: int
:type c: int
:rtype: float
"""
cache = {}
onboard = self.work(N, K, r, c, 0, cache)
return onboard / (8 ** K)
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.