simshadows
About Web Apps Blog

Knight Dialer

Possible positions:

1 2 3
4   6
7 8 9
  0

Adjacency list:

0→4,61→6,82→7,93→4,84→0,3,96→0,1,77→2,68→1,39→2,4\begin{align*} 0 &\to 4, 6 \\ 1 &\to 6, 8 \\ 2 &\to 7, 9 \\ 3 &\to 4, 8 \\ 4 &\to 0, 3, 9 \\ 6 &\to 0, 1, 7 \\ 7 &\to 2, 6 \\ 8 &\to 1, 3 \\ 9 &\to 2, 4 \end{align*}

Let’s change to letters to make things easier.

a b c
d   e
f g h
  z
z→d+ea→e+gb→f+hc→d+gd→z+c+he→z+a+ff→b+eg→a+ch→b+d\begin{align*} z &\to d + e \\ a &\to e + g \\ b &\to f + h \\ c &\to d + g \\ d &\to z + c + h \\ e &\to z + a + f \\ f &\to b + e \\ g &\to a + c \\ h &\to b + d \end{align*}

As recursive equations:

zi=di−1+ei−1ai=ei−1+gi−1bi=fi−1+hi−1ci=di−1+gi−1di=zi−1+ci−1+hi−1ei=zi−1+ai−1+fi−1fi=bi−1+ei−1gi=ai−1+ci−1hi=bi−1+di−1\begin{align*} z_i &= d_{i-1} + e_{i-1} \\ a_i &= e_{i-1} + g_{i-1} \\ b_i &= f_{i-1} + h_{i-1} \\ c_i &= d_{i-1} + g_{i-1} \\ d_i &= z_{i-1} + c_{i-1} + h_{i-1} \\ e_i &= z_{i-1} + a_{i-1} + f_{i-1} \\ f_i &= b_{i-1} + e_{i-1} \\ g_i &= a_{i-1} + c_{i-1} \\ h_i &= b_{i-1} + d_{i-1} \end{align*} z1=a1=b1=c1=d1=e1=f1=g1=h1=1z_1 = a_1 = b_1 = c_1 = d_1 = e_1 = f_1 = g_1 = h_1 = 1

For reference, the Fibonnaci numbers are:

F0=0,F1=1,Fi=Fi−1+Fi−2F_0 = 0, \qquad F_1 = 1, \qquad F_i = F_{i-1} + F_{i-2}

The solution should be:

Ki=zi+ai+bi+ci+di+ei+fi+gi+hiK_i = z_i + a_i + b_i + c_i + d_i + e_i + f_i + g_i + h_i

What happens if we just substitute the previous term…

Ki=(di−1+ei−1)+(ei−1+gi−1)+(fi−1+hi−1)+(di−1+gi−1)+(zi−1+ci−1+hi−1)+(zi−1+ai−1+fi−1)+(bi−1+ei−1)+(ai−1+ci−1)+(bi−1+di−1)=2ai−1+2bi−1+2ci−1+3di−1+3ei−1+2fi−1+2gi−1+2hi−1+2zi−1=2Ki−1+di−1+ei−1\begin{align*} K_i &= \parens{d_{i-1} + e_{i-1}} + \parens{e_{i-1} + g_{i-1}} + \parens{f_{i-1} + h_{i-1}} + \parens{d_{i-1} + g_{i-1}} \\ &\qquad + \parens{z_{i-1} + c_{i-1} + h_{i-1}} + \parens{z_{i-1} + a_{i-1} + f_{i-1}} + \parens{b_{i-1} + e_{i-1}} + \parens{a_{i-1} + c_{i-1}} + \parens{b_{i-1} + d_{i-1}} \\ &= 2 a_{i-1} + 2 b_{i-1} + 2 c_{i-1} + {\color{red}\boldsymbol{3 d_{i-1}}} + {\color{red}\boldsymbol{3 e_{i-1}}} + 2 f_{i-1} + 2 g_{i-1} + 2 h_{i-1} + 2 z_{i-1} \\ &= 2 K_{i-1} + d_{i-1} + e_{i-1} \end{align*}

What happens if we compress the coding?

IMPORTANT: The previous symbols are being redefined here.

1 2                [3]
4                  [6]
7 8                [9]
  0
z:0→4,4a:1→4,8b:2→7,7c:4→0,1,7d:7→2,4e:8→1,1\begin{align*} z: 0 &\to 4, 4 \\ a: 1 &\to 4, 8 \\ b: 2 &\to 7, 7 \\ c: 4 &\to 0, 1, 7 \\ d: 7 &\to 2, 4 \\ e: 8 &\to 1, 1 \end{align*} Ki=zi+2ai+bi+2ci+2di+eiK_i = z_i + 2 a_i + b_i + 2 c_i + 2 d_i + e_i z1=a1=b1=c1=d1=e1=1z_1 = a_1 = b_1 = c_1 = d_1 = e_1 = 1 zi=ci−1+ci−1=2ci−1ai=ci−1+ei−1bi=di−1+di−1=2di−1ci=zi−1+ai−1+di−1di=bi−1+ci−1ei=ai−1+ai−1=2ai−1\begin{align*} z_i &= c_{i-1} + c_{i-1} = 2 c_{i-1} \\ a_i &= c_{i-1} + e_{i-1} \\ b_i &= d_{i-1} + d_{i-1} = 2 d_{i-1} \\ c_i &= z_{i-1} + a_{i-1} + d_{i-1} \\ d_i &= b_{i-1} + c_{i-1} \\ e_i &= a_{i-1} + a_{i-1} = 2 a_{i-1} \end{align*}

If we try substituting our recursions into the solution formula again:

Ki=(2ci−1)+2(ci−1+ei−1)+(2di−1)+2(zi−1+ai−1+di−1)+2(bi−1+ci−1)+(2ai−1)=2ci−1+2ci−1+2ei−1+2di−1+2zi−1+2ai−1+2di−1+2bi−1+2ci−1+2ai−1=2zi−1+4ai−1+2bi−1+6ci−1+4di−1+2ei−1=(2zi−1+4ai−1+2bi−1+4ci−1+4di−1+2ei−1)+2ci−1=2Ki−1+2ci−12ci−1=Ki−2Ki−1ci=12Ki+1−Ki\begin{align*} K_i &= \parens{2 c_{i-1}} + 2 \parens{c_{i-1} + e_{i-1}} + \parens{2 d_{i-1}} + 2 \parens{z_{i-1} + a_{i-1} + d_{i-1}} + 2 \parens{b_{i-1} + c_{i-1}} + \parens{2 a_{i-1}} \notag\\ {} &= 2 c_{i-1} + 2 c_{i-1} + 2 e_{i-1} + 2 d_{i-1} + 2 z_{i-1} + 2 a_{i-1} + 2 d_{i-1} + 2 b_{i-1} + 2 c_{i-1} + 2 a_{i-1} \notag\\ {} &= 2 z_{i-1} + 4 a_{i-1} + 2 b_{i-1} + 6 c_{i-1} + 4 d_{i-1} + 2 e_{i-1} \notag\\ {} &= \parens{ 2 z_{i-1} + 4 a_{i-1} + 2 b_{i-1} + 4 c_{i-1} + 4 d_{i-1} + 2 e_{i-1} } + 2 c_{i-1} \notag\\ {} &= 2 K_{i-1} + 2 c_{i-1} \notag\\[4mm] 2 c_{i-1} &= K_i - 2 K_{i-1} \notag\\ c_i &= \frac{1}{2} K_{i+1} - K_i \tag{eq:2023-04-15--1b} \end{align*}

Can we turn ci−1c_{i-1} into terms of KiK_i?

ci=zi−1+ai−1+di−1=(zi−1+2ai−1+bi−1+2ci−1+2di−1+ei−1)−ai−1−bi−1−2ci−1−di−1−ei−1=Ki−1−ai−1−bi−1−2ci−1−di−1−ei−1=2ci−2+ci−2+ei−2+bi−2+ci−2=4ci−2+ei−2+bi−2=4(zi−3+ai−3+di−3)+2ai−3+2di−3=4zi−3+4ai−3+4di−3+2ai−3+2di−3=4zi−3+6ai−3+6di−3=4(2ci−4)+6(ci−4+ei−4)+6(bi−4+ci−4)=8ci−4+6ci−4+6ei−4+6bi−4+6ci−4=20ci−4+6ei−4+6bi−4=2 (10ci−4+3ei−4+3bi−4)\begin{align*} c_i &= z_{i-1} + a_{i-1} + d_{i-1} % \\ %{} % &= 2 c_{i-2} % + c_{i-2} + e_{i-2} % + b_{i-2} + c_{i-2} % \\ %{} % &= b_{i-2} % + 4 c_{i-2} % + e_{i-2} % \\ %{} % &= \parens{ % z_{i-2} % + 2 a_{i-2} % + b_{i-2} % + 2 c_{i-2} % + 2 d_{i-2} % + e_{i-2} % } % - z_{i-2} % - 2 a_{i-2} % + 2 c_{i-2} % - 2 d_{i-2} \notag\\ {} &= \parens{ z_{i-1} + 2 a_{i-1} + b_{i-1} + 2 c_{i-1} + 2 d_{i-1} + e_{i-1} } - a_{i-1} - b_{i-1} - 2 c_{i-1} - d_{i-1} - e_{i-1} \notag\\ {} &= K_{i-1} - a_{i-1} - b_{i-1} - 2 c_{i-1} - d_{i-1} - e_{i-1} \notag\\[3mm] {} &= 2 c_{i-2} + c_{i-2} + e_{i-2} + b_{i-2} + c_{i-2} \notag\\ {} &= 4 c_{i-2} + e_{i-2} + b_{i-2} \tag{eq:2023-04-15--2b}\\[3mm] {} &= 4 \parens{z_{i-3} + a_{i-3} + d_{i-3}} + 2 a_{i-3} + 2 d_{i-3} \notag\\ {} &= 4 z_{i-3} + 4 a_{i-3} + 4 d_{i-3} + 2 a_{i-3} + 2 d_{i-3} \notag\\ {} &= 4 z_{i-3} + 6 a_{i-3} + 6 d_{i-3} \notag\\[3mm] %{} % &= 4 \parens{2 c_{i-4}} % + 6 \parens{c_{i-4} + e_{i-4}} % + 6 \parens{b_{i-4} + c_{i-4}} % \\ %{} % &= {\color{red} \boldsymbol{4 c_{i-2}}} + 2 a_{i-3} + 2 d_{i-3} {} &= 4 \parens{2 c_{i-4}} + 6 \parens{c_{i-4} + e_{i-4}} + 6 \parens{b_{i-4} + c_{i-4}} \notag\\ {} &= 8 c_{i-4} + 6 c_{i-4} + 6 e_{i-4} + 6 b_{i-4} + 6 c_{i-4} \notag\\ {} &= 20 c_{i-4} + 6 e_{i-4} + 6 b_{i-4} \notag\\ {} &= 2 \, \parens{10 c_{i-4} + 3 e_{i-4} + 3 b_{i-4}} \tag{eq:2023-04-15--2d} \end{align*}

Here, we notice we can rearrange (eq:2023-04-15—2d) and use (eq:2023-04-15—2b):

ci=2 (12ci−4+3ei−4+3bi−4−2ci−4)=2 (3 (4ci−4+ei−4+bi−4)−2ci−4)=2 (3ci−2−2ci−4)\begin{align*} c_i &= 2 \, \parens{12 c_{i-4} + 3 e_{i-4} + 3 b_{i-4} - 2 c_{i-4}} \\ {} &= 2 \, \parens{3 \, \parens{4 c_{i-4} + e_{i-4} + b_{i-4}} - 2 c_{i-4}} \\ {} &= 2 \, \parens{3 c_{i-2} - 2 c_{i-4}} \end{align*}

Using (eq:2023-04-15—1b):

12Ki+1−Ki=2 (3(12Ki−1−Ki−2)−2(12Ki−3−Ki−4))=3(Ki−1−2Ki−2)−2(Ki−3−2Ki−4)12Ki−Ki−1=3(Ki−2−2Ki−3)−2(Ki−4−2Ki−5)12Ki=Ki−1+3(Ki−2−2Ki−3)−2(Ki−4−2Ki−5)Ki=2Ki−1+6(Ki−2−2Ki−3)−4(Ki−4−2Ki−5)\begin{align*} \frac{1}{2} K_{i+1} - K_i &= 2 \, \parens{ 3 \parens{\frac{1}{2} K_{i-1} - K_{i-2}} - 2 \parens{\frac{1}{2} K_{i-3} - K_{i-4}} } \\ {} &= 3 \parens{K_{i-1} - 2 K_{i-2}} - 2 \parens{K_{i-3} - 2 K_{i-4}} \\ \frac{1}{2} K_i - K_{i-1} &= 3 \parens{K_{i-2} - 2 K_{i-3}} - 2 \parens{K_{i-4} - 2 K_{i-5}} \\ \frac{1}{2} K_i &= K_{i-1} + 3 \parens{K_{i-2} - 2 K_{i-3}} - 2 \parens{K_{i-4} - 2 K_{i-5}} \\ K_i &= 2 K_{i-1} + 6 \parens{K_{i-2} - 2 K_{i-3}} - 4 \parens{K_{i-4} - 2 K_{i-5}} \end{align*}

If we need the value as Ki mod mK_i \bmod m:

TODO: do the math!