Searching for a series of nodes in an isometric graph, Depth First is not finding some possible paths

Question

I have a 4x4 undirected graph, with links/paths between each node vertically,horizontally and diagonally. In my example I've simplified the contents of these nodes to integers. Given a series of numbers of any length, I want to determine if a path exists on the board that consists of these numbers. No node can be used twice. For example searching 789, 548 and 734 on the graph below would return true, but 111, 7343 and 98989 would return false.

I currently have what is essentially a depth first search, but I realized it is missing some paths. In the above example, 12234 could be missed. If the search starts at 1, moves diagonally to 2, and left to 2, there is nowhere else to go. The search then backtracks, marking the rightmost 2 as visited and blocking the only correct path.

The improvement I've been able to come up with is to add additional state to each node to record the depth at which they were visited. That would eliminate this case, and certainly make it more correct. But this is still a problem for 27979 on the graph above. If the search starts at the left-most 2, goes down and right to 7, up-right to 9, up-left to 7, it will again block the correct path.

It seems like I'm using the wrong kind of search here, but what's the right one?

Answer 1

It seems I've come up with a solution, which I'll share in case someone else comes across this is the future.

On each search I build a tree with bidirectional links, so that at each place the path can go multiple ways it branches, like a breadth-first search. This differs in that each branch of the tree can use the nodes of any other unconnected branch. As each node is added to the tree I follow the links back to root and check the node against each link to eliminate the possibility of cyclical paths and allow reuse of nodes from other paths. Once the a branch has reached the depth desired, I backtrack to root to record the path.