Determine which value represents which direction in a path
C#

EDIT: Fixed a division and formatting. And added the helper class.

This is the golfed code, 807 chars 

class M{public int c,x,y,u;}
void G(string[] z){
M K;int[]x={0,0,-1,1},y={-1,1,0,0},I={0,0,0,0};
string[]T={"Up","Down","Left","Right"};
int X,Y,R,n=0,H=z.Length,W=z[0].Length;W-=W/2;var D= string.Join(" ", z).Where(c=&gt;c!=' ').Select(c=&gt;new M(){c=c,x=n%W,y=n++/W}).ToList();n=0;var S=D.GroupBy(k=&gt;k.c).ToDictionary(k=&gt;k.Key,k =&gt;n++);
for(;I[0]&lt;4;I[0]++)for(I[1]=0;I[1]&lt;4;I[1]++)for(I[2]=0;I[2]&lt;4;I[2]++)for(I[3]=0;I[3]&lt;4;I[3]++){
if ((1&lt;&lt;I[0]|1&lt;&lt;I[1]|1&lt;&lt;I[2]|1&lt;&lt;I[3])!=15)continue;
foreach (var Q in D){D.ForEach(p=&gt;p.u=-1);R=1;K=Q;j:if((X=K.x+x[n=I[S[K.c]]])&gt;=0&amp;&amp;X&lt;W&amp;&amp;(Y=K.y+y[n])&gt;=0&amp;&amp;Y&lt;H&amp;&amp;(K=D[X+Y*W]).u&lt;0){
K.u=1;if(++R==D.Count){Console.WriteLine("{4} Start({0}:{1}) End({2}:{3})",Q.x,Q.y,K.x,K.y,string.Join(", ",S.Select(k=&gt;string.Format("{1}: '{0}'",(char)k.Key,T[I[k.Value]])).ToArray()));return;}goto j;}}}
}    


Results for the three test cases:


  Down: '1', Right: '2', Up: '3', Left: '4' Start(0:0) End(5:2)
  Up: '@', Left: '.', Down: 'e', Right: 'H' Start(1:1) End(0:0)
  Right: 'X', Down: 'V', Up: 'I', Left: 'C' Start(0:2) End(2:4)


This is the raw code without "golf", almost 4,000 characters:

class Program
{
    static string[] input1 =  { "1 2 2 2 2 1",
               "1 3 4 4 1 4",       
               "2 3 1 3 4 2",
               "1 4 4 2 1 3",       
               "2 2 2 3 2 3"};

    static string[] input2 =  { "@ . .",
                                "e . @",       
                                "H H @",
               };

    static string[] input3 =  { "0 0 1",
                                "0 0 1",       
                                "3 2 2",
               };

    static void Main(string[] args)
    {
        Resolve(input1);
        Resolve(input2);
        Resolve(input3);
        Console.ReadLine();
    }


    class N { public int c; public int x, y, i, u; }

    static void Resolve(string[] input)
    {
        int[] ox = { -1, 1, 0, 0 }, oy = { 0, 0, -1, 1 }, I = { 0, 0, 0, 0 };
        string[] TXT = { "Left", "Right", "Up", "Down" };
        int X, Y, R, n = 0, H = input.Length, W = input[0].Length;
        W -= W / 2;
        N K = null;
        var data = string.Join(" ", input).Where(c =&gt; c != ' ').Select(c =&gt; new N() { c = c, x = (n % W), y = (n / W), i = n++, u = -1 }).ToList();
        n = 0;
       var S = data.GroupBy(k =&gt; k.c).ToDictionary(k =&gt; k.Key, k =&gt; n++);

        for (; I[0] &lt; 4; I[0]++)
            for (I[1] = 0; I[1] &lt; 4; I[1]++)
                for (I[2] = 0; I[2] &lt; 4; I[2]++)
                    for (I[3] = 0; I[3] &lt; 4; I[3]++)
                    {
                        if (((1 &lt;&lt; I[0]) | (1 &lt;&lt; I[1]) | (1 &lt;&lt; I[2]) | (1 &lt;&lt; I[3])) != 15) continue;
                        foreach(var Q in data)
                        {
                            data.ForEach(p =&gt; p.u = -1);
                            R = 0;
                            K = Q;
                            while (K != null)
                            {
                                n = I[S[K.c]];
                                X = K.x + ox[n];
                                Y = K.y + oy[n];
                                if (X &gt;= 0 &amp;&amp; X &lt; W &amp;&amp; Y &gt;= 0 &amp;&amp; Y &lt; H)
                                {
                                    n = X + Y * W;
                                    if (data[n].u &lt; 0)
                                    {
                                         data[n].u = K.i;
                                         K = data[n];
                                        R++;
                                        if (R == data.Count - 1)
                                        {
                                            Console.WriteLine();
                                            Console.WriteLine("Start({0}:{1}) End({2}:{3})", Q.x, Q.y, K.x, K.y);
                                            Console.WriteLine(string.Join(", ", S.Select(k =&gt; string.Format("'{0}': {1}", (char)k.Key, TXT[I[k.Value]])).ToArray()));
                                            Action&lt;N&gt; Write = null;
                                            Write = (k) =&gt;
                                             {
                                                 if (k.u != -1)
                                                 {
                                                     Write(data[k.u]);
                                                 }
                                                 Console.Write(string.Format("({0}:{1}){2}", k.x, k.y, k == K ? "\n" : " =&gt; "));
                                             };

                                            Write(K);
                                            return;
                                        }
                                        continue;
                                    }
                                }
                                K = null;
                            }
                        }
                    }
        Console.WriteLine("Solution not found");
    }
 }
}


These are the results for the three examples:


  Solution not found
  
  Start(1:1) End(0:0) '@': Up, '.': Left, 'e': Down, 'H': Right 
  
  (1:1) => (0:1) => (0:2) => (1:2) => (2:2) => (2:1) => (2:0) => (1:0) => (0:0)
  
  Start(0:0) End(1:1) '0': Right, '1': Down, '3': Up, '2': Left 
  
  (0:0) => (1:0) => (2:0) => (2:1) => (2:2) => (1:2) => (0:2) => (0:1) => (1:1)