What are my chances in a Most Excellent Adventure? Most Excellent Adventure is a home brew roleplaying game system based on the Bill & Ted Films, plays gnarly air guitar riff. 
In this game system, when you draw from your dice pool you need to connect the results as a phone number on your phone pad:

Here one person has rolled 4, 2, 8, 3, 8, and 2, dialling 3-2-2-4-8-8. The other 7, 4, 6, 3, 9, and 4, only dialling 4-4-7 or 3-6-9. And the longest number wins.
How do I work out my chance for success (or chance of a certain phone number length) from this system?
I've tried enumerating the chance of getting a two digit number depending on which number you rolled first (each of the first ones is $1/10$) and I get:


*

*$4/10$

*$6/10$

*$4/10$

*$6/10$

*$9/10$

*$6/10$

*$5/10$

*$7/10$

*$5/10$

*$4/10$


But then, how do I follow each different 'route' of probabilities? I could imagine drawing a probability tree with ten branches and up to 12 levels, but that seems excessive. I could draw up a table (with blanks for non-telephonable combinations), but that would get hard to follow after the first table or so).
I've tried to consider combinatrics, but I've gotten myself confused over nPr and nCr notation and not getting the right numbers in there. Is there an easier way to calculate the probabilities? 
 A: It is remarkable, though maybe not trivial, that for almost every connected set of phone keys, there exists a Eulerian path through the digits (that is you can walk from digit to adjacent digit and reach all digits exactly once). By simply repeating multiple digits, you can thus dial a number (almost) whenever the set of keys is connected.
There are few exception to the rule above: 


*

*If you have $4, 6, 8, 0$ but neither $2, 5, 7, 9$, there is no Eulerian path. You can win only if you have two $8$s.

*If you have $1, 3, 5$ and at least one of $7,8,9$, but none of $2,4,6$, a similar situation occurs. You may need (at least) two $5$s.

*The previous case rotated by 90° or 180° or 270° around the $5$ key.


In summary: If the set of keys is connected, you have almost won. However, for a precise analysis, I am afraid tha a computer based enumeration of all possibilities is the only way to go.
A: I'm not sure that this qualifies as a complete answer to the question, but it will certainly provide some useful ideas and information.
I wrote a program to solve this using the following brute force technique.


*

*Create a Possibe_Next_Key integer set for each of the digits 0 to 9 E.g. For 1 this is {1,2,4,5} those being the allowable next key presses following a 1

*Make a Next_Key_Possible boolean array based on the Possibe_Next_Key sets. This is a 2D array of the form [From_Key,To_Key]=true|false E.g. Possible_Next_Key[0][5]=false because there is no direct link from the 0 to the 5 key

*Iterate through all $10^{6}$ permutations, finding the longest ordered sequence of connected numbers, checking for uniqueness against previous permutations, and so updating a dictionary containing the following:- {UniqueSet, Longest_Key_Sequence, Number_Of Permutations}

*Finally - total up the Number_Of_Permutations for each Longest_Key_Sequence 


And the results I get are as follows:
Ways of getting a maximum key-sequence of 1 key = 0
Ways of getting a maximum key-sequence of 2 keys = 6300
Ways of getting a maximum key-sequence of 3 keys = 76640
Ways of getting a maximum key-sequence of 4 keys = 119340
Ways of getting a maximum key-sequence of 5 keys = 168024
Ways of getting a maximum key-sequence of 6 keys = 629696
Note - their sum is $10^{6}$
So if $P_{n}$ is the probability that the longest phone number that can be dialed with a roll of 6 10-faced dice is n (following the rules of the game) then
$P_{1}$ = 0
$P_{2}$ = 0.0063
$P_{3}$ = 0.07664
$P_{4}$ = 0.11934
$P_{5}$ = 0.168024
$P_{6}$ = 0.629696
Assuming my program is correct, which I believe it to be.
