C# latin squares or shuffling a 2D array

Another problem in "Problems for Computer Solution" by Fred Gruenberger and George Jaffray concerns Latin Squares. Latin Squares are essentially two dimensional array that is shuffled in both dimensions.

I believe an example is now in order:

If you start with a set of numbers:
    1,2,3
Then shuffle them:
    3,1,2
You then have an array shuffled in a single dimension, but if you have a two dimensional array where your set of numbers:
    1,2,3
is repeated for each row:
    1,2,3
    1,2,3
    1,2,3

A possible suffling of this two dimensional array could look like this:
    3,1,2
    1,2,3
    2,3,1

The numbers are now shuffled so that each row and column is different from every other row and column and - here is the most important part - no member of the set is repeated in a row or column.

One possible way to progammatically generate a Latin Square is to use this trick - Use the first row not only as data but as the rule on how to place the values for all the rest of the rows.

I believe another example is now in order:

If you start with our shuffled set of numbers:
    3,1,2

Now look at the data and say:
In the first row the 2 is in the 3rd column.
In the second row the 2 is in the 1st column.
In the third row the 2 is in the 2nd column.

3rd column, 1st column, 2nd column - thats our first row! 3,1,2!

Now rotate the first row by taking the first value and placing at the end - 1,2,3 - and do the same thing to the original data. So, lets look at the data and say:
In the first row the 3 is in the 1st column.
In the second row the 3 is in the 2nd column.
In the third row the 3 is in the 3rd column.

Rotate one last time - 2,3,1 - and do the same thing to the original data. So, lets look at the data and say one last time:
In the first row the 1 is in the 2nd column.
In the second row the 1 is in the 3rd column.
In the third row the 1 is in the 1st column.

So using the rules above we generated:
    3,1,2
    2,3,1
    1,2,3

Here is a 9x9 array shuffled using the above trick:
    3,2,6,5,9,4,1,7,8
    5,6,7,8,4,2,3,1,9
    8,7,1,9,2,6,5,3,4
    9,1,3,4,6,7,8,5,2
    4,3,5,2,7,1,9,8,6
    2,5,8,6,1,3,4,9,7
    6,8,9,7,3,5,2,4,1
    7,9,4,1,5,8,6,2,3
    1,4,2,3,8,9,7,6,5

And, here is the code that can generate Latin Squares using the above trick:

using System;
using System.Collections;

class LatinSquare
{
    static void Main()
    {
        var LatinSquare = new int[9, 9];
        var Pattern = new int[] {1,2,3,4,5,6,7,8,9};

        Pattern = Shuffle(Pattern);
        
        //Use the first row as a pattern for the rest 
        //of the Latin Square
        for (int i = 0; i < 9; i++)
        {
            {LatinSquare[i,0] = Pattern[i];
        } 
            
        for (int x = 0; x < 9; x++)
        {
            for (int y = 1; y < 9; y++)
            {
                LatinSquare[Pattern[y] - 1, y] = 
                    LatinSquare[LatinSquare[x, 0] - 1, 0];
            }

            Pattern = RotatePattern(Pattern);
        }

        PrintLatinSquare(LatinSquare);

        Console.Read();
    }

    private static T[] Shuffle(T[] OriginalArray)
    {
        var matrix = new SortedList();
        var r = new Random();

        for (int x = 0; x <= OriginalArray.GetUpperBound(0); x++)
        {
            int i = r.Next();

            if (!matrix.ContainsKey(i)) 
            {
                matrix.Add(i, OriginalArray[x]);
            }
        }

        var OutputArray = new T[OriginalArray.Length];

        var counter = 0;
        foreach (DictionaryEntry entry in matrix)
        {
            OutputArray[counter++] = (T)entry.Value;
        }

        return OutputArray;
    }

    private static int[] RotatePattern(int[] Pattern)
    {
        int temp = Pattern[0];

        ;for (int y = 0; y < 9 - 1; y++)
        {
            Pattern[y] = Pattern[y + 1];
        }

        Pattern[9 - 1] = temp;

        return Pattern;
    }

    private static void PrintLatinSquare(int[,] LatinSquare)
    {
        //Print out the Latin Square
        for (int i = 0; i < 9; i++)
        {
            for (int j = 0; j < 9; j++)
            {
                Console.Write(LatinSquare[j, i].ToString().PadLeft(3));
            }
            Console.WriteLine();
        }
    }
}

The code also available here!