Anyone can give me an idea how I approach calculating the following problem. How many possible valid numbers, where a valid number is any number between 0-9, length of 10 digits, excluding # or *, a piece of Chess can trace while travelling across a telephone keypad. Here say I have a King, it can move only as in a real game, in any direction but only a single cell at a time.
So the keypad looks like this:
1 2 3
4 5 6
7 8 9
* 0 #
So the piece makes 10 moves each time and each unique number created by it is a valid number. A piece starts its journey from an initial starting position.
The pieces can move or stay in one place (where moving or staying will both count as a move) as well as revisit the cells (as long as its allowed within their respective moving rights). So for example if a King moves from position 1 a three valid 10-move paths to create a valid number number could be 1236547890 or 1111111111 or 1212121212
All help much appreciated.
Best Answer
I'll consider the "king" case, without the ability to "pass"; the other cases can be resolved similarly. Let $S_{\text{king}}(n,p)$ be the number of $n$-digit numbers with the king ending at $p \in \{0,1,\ldots,9\}$.
We have:
Boundary conditions: $S_{\text{king}}(1,p)=1$ for all $p \in \{0,1,\ldots,9\}$. (I'll assume we can start wherever we want.)
Recurrence relations:
$S_{\text{king}}(n,1)=\sum_{p \in \{2,4,5\}} S_{\text{king}}(n,p)$,
$S_{\text{king}}(n,2)=\sum_{p \in \{1,3,4,5,6\}} S_{\text{king}}(n,p)$,
$S_{\text{king}}(n,3)=\sum_{p \in \{2,5,6\}} S_{\text{king}}(n,p)$,
$S_{\text{king}}(n,4)=\sum_{p \in \{1,2,5,7,8\}} S_{\text{king}}(n,p)$,
$S_{\text{king}}(n,5)=\sum_{p \in \{1,2,3,4,6,7,8,9\}} S_{\text{king}}(n,p)$,
$S_{\text{king}}(n,6)=\sum_{p \in \{2,3,5,8,9\}} S_{\text{king}}(n,p)$,
$S_{\text{king}}(n,7)=\sum_{p \in \{0,4,5,8\}} S_{\text{king}}(n,p)$,
$S_{\text{king}}(n,8)=\sum_{p \in \{0,4,5,6,7,9\}} S_{\text{king}}(n,p)$,
$S_{\text{king}}(n,9)=\sum_{p \in \{0,5,6,8\}} S_{\text{king}}(n,p)$,
$S_{\text{king}}(n,0)=\sum_{p \in \{7,8,9\}} S_{\text{king}}(n,p)$.
This gives:
$$\scriptsize \begin{array}{r|rrrrrrrrrr|r} & p=1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 0 & \text{sum} \\ \hline n=1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 10 \\ 2 & 3 & 5 & 3 & 5 & 8 & 5 & 4 & 6 & 4 & 3 & 46 \\ 3 & 18 & 24 & 18 & 26 & 35 & 26 & 22 & 29 & 22 & 14 & 234 \\ 4 & 85 & 123 & 85 & 128 & 185 & 128 & 104 & 145 & 104 & 73 & 1160 \\ 5 & 436 & 611 & 436 & 642 & 902 & 642 & 531 & 722 & 531 & 353 & 5806 \\ 6 & 2155 & 3058 & 2155 & 3202 & 4551 & 3202 & 2619 & 3601 & 2619 & 1784 & 28946 \\ 7 & 10811 & 15265 & 10811 & 15984 & 22611 & 15984 & 13138 & 17977 & 13138 & 8839 & 144558 \\ 8 & 53860 & 76201 & 53860 & 79802 & 113108 & 79802 & 65411 & 89694 & 65411 & 44253 & 721402 \\ 9 & 269111 & 380432 & 269111 & 398274 & 564041 & 398274 & 326857 & 447787 & 326857 & 220516 & 3601260 \\ 10 & 1342747 & 1898811 & 1342747 & 1988228 & 2816703 & 1988228 & 1630618 & 2234819 & 1630618 & 1101501 & 17975020 \\ \end{array}$$
So there are $17975020$ phone numbers with $10$-digits that can be dialled by a king.
(There are some "sanity checks" we can apply to the above numbers. E.g. $S(n,1)=S(n,3)$ by symmetry.)
The above numbers were computed in GAP using the following code:
In a previous version of the question, there was a condition on the 10-digits being unique. This is a much harder problem, and amounts to counting the number of hamilton paths in various $10$-vertex graphs. Note that finding a hamilton path is an NP-complete problem (ref.). Nevertheless, this enumeration should be achievable using a backtracking algorithm (judging from the above numbers). There's probably not a much better way than this; see these Stackoverflow questions here and here.