Find max unique combinations in a graph

See more:

C#

mathematics

A classic numeric keypad looks like this

<br />
1  2  3<br />
4  5  6<br />
7  8  9<br />
  0<br />

A horse in chess can move horizontally or vertically two fields and then one to the left or right:
Example:
From the number 3 on the keypad the horse can move to 8 or 4
From the number 6 on the keyboard the horse can move to 7, 1 or 0

If you start on the number 1, and pick next number the way a horse moves in chess,

How many unique paths within 10 steps exists?
   A path can visit the same number more than once.

Example path: 1 6 1 6 1 6 1 6 1 8



Ok. So the thing that confuses me is the fact that I have to do 10 steps and they can repeat. If it was a simple case of finding all possible moves I think I could find all combinations.

I identified a connected graph but I think it is redundant to the solution.

any ideas or pseudo code appreciated!

all allowed steps

1, 6, 8<br />
2, 7, 9<br />
3, 4, 8<br />
4, 3, 9, 0<br />
6, 1, 7, 0<br />
7, 2, 6<br />
8, 1, 3<br />
9, 4, 2<br />
0, 4, 6

Choosing this strategy to find legal nodes

public static int Find(int node, int index)
{
    if (index == 0)
    {
        switch (node)
        {
            case 1 : return 6;
            case 2 : return 7;
            case 3 : return 4;
            case 4 : return 3;
            case 6 : return 1;
            case 7 : return 2;
            case 8 : return 1;
            case 9 : return 4;
            case 0 : return 4;
        }
    }
    else if (index == 1)
    {
        switch (node)
        {
            case 1 : return 8;
            case 2 : return 9;
            case 3 : return 8;
            case 4 : return 9;
            case 6 : return 7;
            case 7 : return 6;
            case 8 : return 3;
            case 9 : return 2;
            case 0 : return 6;
        }
    }
    else if (index == 2)
    {
        switch (node)
        {
            case 4 : return 0;
            case 6 : return 0;
        }
    }
    return -1;
}

First variation, but where to go after 1 6 1 6 1 6 1 6 1 6

I need to find all permutations of this pattern with the next node, I think I can move left in the node tree and ignore all right nodes and simply multiply answer with 2 to get the right nodes. But then I have an issue with the 0 node (I think)

HashSet<string> paths = new HashSet<string>();
paths.Add("1 6 1 6 1 6 1 6 1 6");

int start = 1;
//int depth = 1;
int k = start;
for (int j = 0; j < 3; j++)
{
string path = "";
for(int i = 0; i < 10; i++)
{
    int n = k;
    path += string.Format("{0} ", n);
    k = Find(n, j);
}
Console.WriteLine(path);
}