Orthogonal path search algorithm between two ten-digit numbers

Question

Let S be a set of ten-digit numbers. For any two numbers v and w in S , I would like to know if there is a sequence of numbers v = u_0, u_1, ..., u_k = w such that:

• every u_i is in S
• for each i = 1, ..., k, the numbers u_ {i-1} and u_i differ in exactly one position

As a plus, it would be even better to find an algorithm for finding the shortest such sequence.

Ideally, I would prefer a solution to C (or pseudo-code), but I really really appreciate any suggestions on this! Thanks!

Answer 1

Generate a graph from the elements S: u and v are adjacent if they differ in exactly one coordinate.

Now, given u, do a breadth-first search until you hit v.

Answer 2

I would convert S to a graph of node objects, where each node object contains links to neighboring nodes. (In some programming languages, read “links” as “pointers.”) Agency is defined by your condition 2 in the sequence, so any path through the resulting graph is a sequence that meets two conditions.

From there, this is a simple problem of checking the connectivity of two vertices in your graph. The simplest solution is a breadth -first search . (This particular algorithm also detects the shortest path (s).)