Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
You're asking for the number of Hamiltonian paths in the corresponding graph. (Not that it helps.) –  Yuval Filmus Apr 26 '12 at 14:56
    
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. –  Mikko Korhonen Apr 26 '12 at 18:18
    
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 .. –  fissk Apr 26 '12 at 18:21
    
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 –  Gerry Myerson Apr 27 '12 at 1:01
    
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 –  fissk Apr 28 '12 at 10:46

1 Answer 1

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.