Quite A Knight

Knight's moves involve translations through $\pm{2 \choose 1}$ , $\pm{2 \choose -1}$ , $\pm{1 \choose 2}$ and $\pm{-1 \choose 2}$ . If we are going to move from $(0,0)$ to $(22,18)$ in the least number of moves, we will only be interested in moves that increase the sum $x+y$ of the coordinates $(x,y)$ of the squares visited. This cuts the number of possible moves in half. Note that this simplification is possible because there exist solutions which only use "positive" moves.

Suppose that we move from $(0,0)$ to $(22,18)$ after a total of $a$ translations by ${2 \choose 1}$ , $b$ translations by ${2 \choose -1}$ , $c$ translations by ${1 \choose 2}$ and $d$ translations by ${-1 \choose 2}$ . Then $2a + 2b + c - d \; = \; 22 \qquad \qquad a - b + 2c + 2d \; = \; 18 \;,$ and hence $(a - c) + 3(b - d) \; = \; 4 \qquad \qquad 3(a + c) + (b + d) \; = \; 40 \;.$ We want $a,b,c,d$ to be nonnegative integers, and for $a+b+c+d$ to be as small as possible. Since $40 \,=\, (a+b+c+d) + 2(a+c)$ , we want $a+c$ to be as large as possible, and hence $b+d$ must be as small as possible. Since $b+d \equiv 1 \pmod{3}$ , the best we can hope for is $b+d=1$ . There are two solutions with $b+d=1$ , namely $a = 7, b = 1, c = 6, d = 0 \qquad \qquad a = 10, b = 0, c = 3, d = 1 \;.$ Either of these solutions involve a total number of $14$ translations. Thus the minimum number of moves from $(0,0)$ to $(22,18)$ is $14$ .

There are $\frac{14!}{7! 6! 1!} \,=\, 24024$ ways of achieving the first type of move, and $\frac{14!}{10! 3! 1!} \,=\, 4004$ ways of achieving the second type of move. Thus there are a total of $28028$ ways of getting from $(0,0)$ to $(22,18)$ in $14$ moves.

The answer is the concatenation of $14$ and $28028$ , namely $\boxed{1428028}$ .