LATIN SQUARE” and its implementation

Problem

Understand Latin Square and its implementation

Understanding the latin square
“A Latin square is an n × n array filled with n different Latin letters, each occurring exactly once in each row and exactly once in each column” – Wikipedia. You can find the detail explanation of the properties of this Square here on Wikipedia

In this article we will build a square to match the definition. As the definition suggest Latin square is square in which the row elements do not repeat and the column elements do no repeat.
This article talks about how to fill numbers.Leonhard Euler however initially proposed it to be filled with Latin characters and thus the name.

So we can ask the question is a Latin square unique for a given dimension.NO, the possibilities are many in fact it is not easily computable.One such calculation by van Lint and Wilson is shown in the Wikipedia article. Our interest is to simply build one such Latin square with numbers.

Latin Square have had various application. One such is they can be used as error correcting codes. Perhaps the most well know application is the game of Sudoku. Sudoku is a special case of Latin square where in the additional property is that for a 9×9 square 3×3 sub squares must contain all the 9 numbers. KenKen puzzles are also a variant of Latin square. They are also used to formulate statistical experiments. Dating services can use Latin squares to Organize meeting between n number of boys and girls (marriage problem). Most popular is scheduling of round-robin tournaments.


IMPLEMENTATION:
Following is a C++ program that displays the for a ‘N’ order dimension, Latin squares of the order N,N-1…1
Firstly the Logic.
Step 1. Generate a array randomly. Lets call this Original
for Eg : Original[ 1 , 2 , 4 , 3 ]
We keep the first digit as it is. From this digit find the index from which we can extract the value and place it accordingly
index = (1 – 1) =0
value[0] = 1
So,
place 1 at (1-1) = 0 index of row 0
place 1 at (2-1) = 1 index of row 1
place 1 at (4-1) = 3 index of row 2
place 1 at (3-1) = 2 index of row 3
partial square looks like ( B – not yet found) – You can see the output to match this derivation
1 B B B
B 1 B B
B B B 1
B B 1 B
Step 2: Now rotate the Original array by one position to the left 2 4 3 1
NOTE : However the index and value are with reference to the original array
Let us derive
First digit – 2 . Index needed = (2-1) = 1
Original[1] = 2 (notice it is not 4 , we are still using values from original array)
So,
place 2 at (2-1) = 1 index of row 0
place 2 at (4-1) = 3 index of row 1
place 2 at (3-1) = 2 index of row 2
place 2 at (1-1) = 0 index of row 3
Now square looks like
1 2 B B
B 1 B 2
B B 2 1
2 B 1 B
You can derive further. So this can be implemented by two function shuffle and rotate. Shuffle will use a random generator function to generate the initial permutation and then use rotate method to do the one shift rotate for n times
Here is a code in cpp-

#include <iostream>
#include <stdlib.h>
#include <iomanip>
 
using namespace std;
 
void shuffle(int array1[], int size)
{
     int i, temp, random, last;
 
     for (i = 0; i < size; i++)
           array1[i] = i + 1;
 
     for (last = size; last > 1; last--)
     {
           random = rand() % last;
           temp = array1[random];
           array1[random] = array1[last - 1];
           array1[last - 1] = temp;
     }
}
 
void rotate(int array2[], int size)
{
     int temp, i;
 
     temp = array2[0];
     for (i = 0; i < size - 1; i++)
           {array2[i] = array2[i+1];}
     array2[size - 1] = temp;
}
 
int main()
{
     int sequence[10],jumbled[10];
     int square[10][10];
     int position, value, i, j, size;
 
     srand((unsigned)time(NULL));
     cout<<"Enter the Dimension of Square you need \n";
     cin>>size;   
      
     while (size != 0)
     {
           shuffle(jumbled, size);
           for (i = 0; i < size; i++){
                 sequence[i] = jumbled[i];}
 
           for (i = 0; i < size; i++)
           {
                 position = sequence[0];
                 value = jumbled[position - 1];
 
                 for (j = 0; j < size; j++){
                       square[j][sequence[j] - 1] = value;}
 
                 rotate(sequence, size);
           }
           cout << endl;
           cout << "A Latin Square of Order " << size << " is: " << endl << endl;
        
           for (i = 0; i < size; i++)
           {
                 for (j = 0; j < size; j++)
         {
                       cout << setw(5) << square[i][j];
                 }
         cout << endl;
           }
         size--;
     }
     return 0;
}

OUTPUT:
Used in explanation
laptop:~/code$ ./a.out
Enter the Dimension of Square you need
4
A Latin Square of Order 4 is:
1 2 4 3
4 1 3 2
3 4 2 1
2 3 1 4
A Latin Square of Order 3 is:
2 1 3
1 3 2
3 2 1
A Latin Square of Order 2 is:
1 2
2 1
A Latin Square of Order 1 is:
1
laptop:~/code$ ./a.out
Enter the Dimension of Square you need
4
A Latin Square of Order 4 is:
1 3 4 2
3 2 1 4
2 4 3 1
4 1 2 3
A Latin Square of Order 3 is:
3 1 2
2 3 1
1 2 3
A Latin Square of Order 2 is:
1 2
2 1
A Latin Square of Order 1 is:
1
A detail explanation about Latin squares is found here at cut the knot site.
Also you can refer to code of a simple Latin square using C here

 Reference
http://chinmaylokesh.wordpress.com/category/data-structures/matrix/
http://www.tylo42.com/latin_square