I am working on Project Euler 178 but got stuck in trying to optimize my code. The following text comes from the problem:

Consider the number $ 45656$ .
It can be seen that each pair of consecutive digits of $ 45656$ has a difference of one.
A number for which every pair of consecutive digits has a difference of one is called a step number.
A pandigital number contains every decimal digit from $ 0$ to $ 9$ at least once.
How many pandigital step numbers less than $ 10^{40}$ are there?

I thought of computing the entirety of step numbers with less than $ 40$ digits and subsequently selecting the pandigital ones. The first way to generate these numbers that came to my mind was to define a function

Generate[Ls_] := Module[{F = First[Ls], L = Ls},
                        Which[F == 9,
                              Return[{Prepend[L, F - 1]}],
                              F == 0,                    
                              Return[{Prepend[L, F + 1]}],                       
                              F != 0 && F != 9,                                     
                              Return[{Prepend[L, F + 1], Prepend[L, F - 1]}
                             ]
                       ]

which takes in input a list of lists, for instance {{5}}, and returns a list of lists with a prepended digit that differs by one from the original one, in this case {{4,5},{6,5}}. The first two cases handle the case in which the digit is $ 0$ or $ 9$ . I’ll handle the problem with the first digit being zero later. From here, I thought of nesting this by defining another function

GenMap[Ls_] := Flatten[Map[Generate, Ls], 1]

that should be nested to obtain the result. For instance,

Startingfromfive = Nest[GenMap, {{5}}, 15]; 

would generate the list of digits of the various $ 15$ digit step numbers that end with the digit $ 5$ .

This solution is clearly non optimal and has performance problems, due to the fact that the number of lists that need to be handled grows incredibly fast: Startingfromfive is a list of $ 22001$ lists of $ 15$ elements each. The computation time seems to be growing exponentially, as can be seen from the following plot:

ListPlot[Table[First[Timing[Nest[GenMap, {{5}}, n];]], {n, 1, 20}]]

Nest[GenMap, {{5}}, n] “>

My machine gets up to $ n=25$ in about $ 3$ minutes, showing the unfeasability for $ n=40$ with the aforementioned method. I tried compiling the function, but it doesn’t seem to show a substantial improvement.

Can this code be optimized or do I need to use a completely different approach?