Determine which value represents which direction in a path Important edit: Earlier, there was an incorrect value in Example 1.  It has been fixed.

You are given a two-dimensional array in which each cell contains one of four values.

Examples:

1 2 2 2 2 1        @ . .        X X V
1 3 1 4 1 4        e . @        I C V
2 3 1 3 4 2        H H @        X I V
1 4 4 2 1 3                     V C C
2 2 2 3 2 3                     X X X


The four values represent directional arrows (up, down, left, and right), although you don't know which value represents which direction.

The directional arrows form an unbroken path that includes every cell in the array, although you don't know where the start or end points are.

Write some code that determines which direction each of the four values represents and where the start and end points are.

An acceptable return value for an array that contains the values A, B, C, and D would be something like:

{ up: A, down: C, left: D, right: B, start: [2, 0], end: [4, 2] }


Because you can traverse the path both ways (from start to end and from end to start), there will always be more than one correct solution, and there might be more than two.  Assume that the inputs you receive (as in the above examples) always have at least one correct solution.  In cases where there is more than one correct solution, returning just one of the correct solutions is sufficient.

Shortest code wins.  I'll pick the winner after 7 days or 24 hours without a new submission, whichever comes first.

I'm including solutions to the examples above, but I'd encourage you to only check them once you've written your code:

One:


   { up: 3, down: 1, left: 4, right: 2, start: [0,0], end: [2,5] }


Two:


   { up: '@', down: 'e', left: '.', right: 'H', start: [1,1], end: [0,0] }


Three:


   { up: 'I', down: 'V', left: 'C', right: 'X', start: [0,2], end: [4,2] }
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)