Shortest list from a two dimensional array

Question

This question is more about an algorithm than actual code, but example code would be appreciated.

Let's say I have a two-dimensional array such as this:

    A  B  C  D  E
   --------------
1 | 0  2  3  4  5
2 | 1  2  4  5  6
3 | 1  3  4  5  6
4 | 2  3  4  5  6
5 | 1  2  3  4  5

I am trying to find the shortest list that would include a value from each row. Currently, I am going row by row and column by column, adding each value to a SortedSet and then checking the length of the set against the shortest set found so far. For example:

Adding cells {1A, 2A, 3A, 4A, 5A} would add the values {0, 1, 1, 2, 1} which would result in a sorted set {0, 1, 2}. {1B, 2A, 3A, 4A, 5A} would add the values {2, 1, 1, 2, 1} which would result in a sorted set {1, 2}, which is shorter than the previous set.

Obviously, adding {1D, 2C, 3C, 4C, 5D} or {1E, 2D, 3D, 4D, 5E} would be the shortest sets, having only one item each, and I could use either one.

I don't have to include every number in the array. I just need to find the shortest set while including at least one number from every row.

Keep in mind that this is just an example array, and the arrays that I'm using are much, much larger. The smallest is 495x28. Brute force will take a VERY long time (28^495 passes). Is there a shortcut that someone knows, to find this in the least number of passes? I have C# code, but it's kind of long.

Edit:

Posting current code, as per request:

// Set an array of counters, Add enough to create largest initial array
int ListsCount = MatrixResults.Count();
int[] Counters = new int[ListsCount];
SortedSet<long> CurrentSet = new SortedSet<long>();
for (long X = 0; X < ListsCount; X++)
{
    Counters[X] = 0;
    CurrentSet.Add(X);
}

while (true)
{
    // Compile sequence list from MatrixResults[]
    SortedSet<long> ThisSet = new SortedSet<long>();
    for (int X = 0; X < Count4; X ++)
    {
        ThisSet.Add(MatrixResults[X][Counters[X]]);
    }

    // if Sequence Length less than current low, set ThisSet as Current
    if (ThisSet.Count() < CurrentSet.Count())
    {
        CurrentSet.Clear();
        long[] TSI = ThisSet.ToArray();
        for (int Y = 0; Y < ThisSet.Count(); Y ++)
        {
            CurrentSet.Add(TSI[Y]);
        }
    }

    // Increment Counters
    int Index = 0;
    bool EndReached = false;
    while (true)
    {
        Counters[Index]++;
        if (Counters[Index] < MatrixResults[Index].Count()) break;
        Counters[Index] = 0;
        Index++;
        if (Index >= ListsCount)
        {
            EndReached = true;
            break;
        }
        Counters[Index]++;
    }

    // If all counters are fully incremented, then break
    if (EndReached) break;
}