Solving Google’s Knight Dialer With Graph Theory: Part 2

“Knight to E4!…. Yes Hermione, I think this is going to be exactly like wizard’s chess.” — Ronald Weasley

Binary Decomposition

Binary Decomposition Applied

lru_cache is the memoization portion, its a nice function to just throw onto a frequently called function

Non-Recursive Knight Solver

Our “fully” recursive solution

Out of the Box

Same Answer, Different Graph

Our New Diagram

How Much Better Is It?

All data was generated by measuring the time to complete with a starting position of 0
Solution 1 = linear solution, Solution 2 = Recursive solution, Solution 3 = Recursive solution + Memoization, Solution 4 = dynamic programing solution without reversing the powers, Solution 5 = dynamic programming solution with reversing the powers, Solution 6 = Nump’s matrix power solution

Lucky Number 7= condensed graph solution

Fun fact: at 1,750,000 turns, the number would be somewhere between 10⁵²⁶⁸⁰² and 10⁸³⁴⁹⁶³, an absolutely incomprehensibly large number

Wait, weren’t these O(log(N))?

How much further we can go?

I like helping people with Code & Math. I try to make everything I do a version of that.