Shortest path of the king

Observation 1

This is barely a shortest-path problem. Yes, you could BFS over $64$ squares, but that's like bringing a tank to a pillow fight.

Let the start be $(x_1,y_1)$ and the target be $(x_2,y_2)$, where the letter is the $x$-coordinate and the digit is the $y$-coordinate.

In one king move, both coordinates can change by at most $1$: $|\Delta x| \le 1, \qquad |\Delta y| \le 1.$

So if $dx = |x_2-x_1|, \qquad dy = |y_2-y_1|,$ then any path needs at least $\max(dx,dy)$ moves, because a single move cannot reduce either difference by more than $1$.

Observation 2

That lower bound is also achievable.

• While both $dx>0$ and $dy>0$, move diagonally toward the target.
• After one coordinate matches, move straight along the remaining coordinate.

So the minimum number of moves is exactly $\max(dx,dy).$

In metric-speak, $d_\infty((x_1,y_1),(x_2,y_2)) = \max(|x_2-x_1|, |y_2-y_1|).$ Fancy name, tiny implementation.

Greedy construction

Maintain the current square $(x,y)$.

At each step:

• if $x < x_2$, append R and do $x \leftarrow x+1$
• if $x > x_2$, append L and do $x \leftarrow x-1$
• if $y < y_2$, append U and do $y \leftarrow y+1$
• if $y > y_2$, append D and do $y \leftarrow y-1$

The move string you build is automatically one of: L, R, U, D, LU, LD, RU, RD.

Why does this work? Because every iteration decreases each nonzero coordinate difference by exactly $1$. Therefore the value $D = \max(|x-x_2|, |y-y_2|)$ drops by exactly $1$ each time, until it becomes $0$.

So after exactly the optimal number of steps, you're done. Clean, greedy, no nonsense.

Complexity

Let $D = \max(|x_2-x_1|, |y_2-y_1|).$

The simulation runs for exactly $D$ moves, so the complexity is $O(D) = O(\max(dx,dy)),$ which is at most $7$ on an $8 \times 8$ board. Memory usage is $O(1)$ besides the output itself.