1
$\begingroup$

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.

$\endgroup$
7
  • $\begingroup$ You're asking for the number of Hamiltonian paths in the corresponding graph. (Not that it helps.) $\endgroup$
    – Yuval Filmus
    Apr 26, 2012 at 14:56
  • $\begingroup$ With a pawn there are no solutions since you can only move upwards. Same thing with knight because there are no valid moves from $5$. With bishop you cannot get outside the square $2684$ so there are no solutions. With a rook you cannot get $10$ digits without passing through a same digit twice. So the question only makes sense for the queen and the king. If you assume that the queen cannot jump over digits, then they both have the same amount of valid numbers. $\endgroup$
    – Mikko Korhonen
    Apr 26, 2012 at 18:18
  • $\begingroup$ Yuval .. thanks for the insight , would you care to elaborate so perhaps I could go about solving it somehow, maybe pseudo code or formula would really help . m.k I forgot to say that it's about how many valid numbers you can get by mowing 10 times .. for now forget about other pieces, just the king .. say you had a square 1234 pad and a valid number made of four .. so for this two possible valid numbers would be 1234 and 1342, each without re-visiting .. hope that clears things up .. $\endgroup$
    – fissk
    Apr 26, 2012 at 18:21
  • $\begingroup$ I think you are asking for the number of "self-avoiding walks." This is, in general, a hard problem. There is some information at en.wikipedia.org/wiki/Self-avoiding_walk $\endgroup$
    – Gerry Myerson
    Apr 27, 2012 at 1:01
  • $\begingroup$ The requirements have changed , please see the updated version of my question .. it basically need to find all possible permutations of a collection of positions/numbers that a piece is allowed to visit from it's current position while to make 10 digit number $\endgroup$
    – fissk
    Apr 28, 2012 at 10:46

1 Answer 1

Reset to default
3
$\begingroup$

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:

M:=[[1,1,1,1,1,1,1,1,1,1]];  # index 10 represents 0
for n in [2..10] do
  M[n]:=[];
  M[n][1]:=Sum([2,4,5],p->M[n-1][p]);
  M[n][2]:=Sum([1,3,4,5,6],p->M[n-1][p]);
  M[n][3]:=Sum([2,5,6],p->M[n-1][p]);
  M[n][4]:=Sum([1,2,5,7,8],p->M[n-1][p]);
  M[n][5]:=Sum([1,2,3,4,6,7,8,9],p->M[n-1][p]);
  M[n][6]:=Sum([2,3,5,8,9],p->M[n-1][p]);
  M[n][7]:=Sum([4,5,8,10],p->M[n-1][p]);
  M[n][8]:=Sum([4,5,6,7,9,10],p->M[n-1][p]);
  M[n][9]:=Sum([5,6,8,10],p->M[n-1][p]);
  M[n][10]:=Sum([7,8,9],p->M[n-1][p]);
od;

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .