Knight Dialer problem

https://leetcode.com/problems/knight-dialer/description/

Resolver este problemita si me esta constando un poco de trabajo:

Mi primer aproximación, fue un desastre y solo la pense para n=2, así que no vale ni la pena ponerla, y no usaba recursión. Tarde un monton en llegar a ella, 12 horas dormido y otras 5 despierto.

La segunda aproximación, me tomo 30 minutos, y use recursión para recorrer el arbol combinatorio, funciona, pero está limitada por el limite de pila de llamadas, que es de 1000, aunque en la práctica el tiempo de recorrido se vuelve algo desesperante a partir de n=22.

#!/usr/local/bin/python

# https://leetcode.com/problems/knight-dialer/

import time

keys = ['1','2','3','4','5','6','7','8','9','0']

options = {
 '1': ['6','8']
 , '2': ['7','9']
 , '3': ['4','8']
 , '4': ['3','9','0']
 , '6': ['1','7','0']
 , '7': ['2','6']
 , '8': ['1','3']
 , '9': ['2','4']
 , '0': ['4','6']
}

class Solution:
 def knightDialer(self, n: int, imprimir=False) -> int:
  r = 0

  def iterar(combo, pos):
   nonlocal r
   if pos == 0:
    col = list(options.keys())
   else:
    col = options[ combo[pos-1] ]
   for e in col:
    combo[pos] = e
    if pos == n-1:
     if imprimir: print(combo)
     r += 1
    else:
     iterar(combo, pos+1)

  if n == 1:
   combo = [None] * n
   for e in keys:
    combo[0] = e
    if imprimir: print(combo)
    r += 1
  else:
   combo = [None] * n
   iterar(combo, 0)

  if imprimir:
   print()
   print(f'{r:,}')
  return r

sol = Solution()
#assert sol.knightDialer(1) = 10…