Blog

While teaching programming in C++ to a student from USA, I encountered an assignment given to him based on the array in which it was asked to produce a latin square of English alphabets. Basically a latin square consists of sets of the numbers/characters arranged in such a way that no orthogonal (row or column) contains the same number/character twice. So naturally it can be implemented with the help of a two-dimensional array having equal number of rows and columns. The challange is to generate a random set of alphabets so that the same alphabet should not be present in same row and column. For example if the size of the square is 2 then a latin square can be any one of the following:

AB
BA

OR

BA
AB

Similarly if the size is 3 then it can be any one of the following:

CBA
ACB
BAC

OR

ABC
CAB
BCA

OR

BAC
CBA
ACB

In order to implement this program, I used the rand() function to generate a random number like below:

ch = rand() % SIZE + 1; //Randon number between 1 to SIZE

In order to make this rand() function working I called the function srand(time(0)); in the very beginning of the main function.

Then to make sure that every alphabet added to the array is unique in its row as well as in its column, I used two variables found_in_row and found_in_column. When a alphabet is found either in current row or in current column then the alphabets in current row are filled up again with another set of random alphabets. This process is done till the randomly generated alphabet becomes unique in current row and column. Using this type of iteration, a latin square of a given size is generated with English alphabets. Here is the complete code for reference:

#include<iostream>
#include<time.h>
using namespace std;

int main()
{
    srand(time(0));
    const int SIZE = 3;
    char arr[SIZE][SIZE];
    char ch;
    bool found_in_row, found_in_column;
    for (int i = 0; i < SIZE; i++)
    {
        col:
        for (int j = 0; j < SIZE; j++)
        {
            while (true)
            {
                found_in_row = false;
                found_in_column = false;
                ch = rand() % SIZE + 1; // 1-3

                for (int k = 0; k < j; k++) // row
                {
                    if (arr[i][k] == (ch + 64))
                    {
                        found_in_row = true;
                        break;
                    }
                }

                for (int k = 0; k < i; k++) //column
                {
                    if (arr[k][j] == (ch + 64))
                    {
                        found_in_column = true;
                        break;
                    }
                }
                if(found_in_column || found_in_row) goto col;
                if (found_in_row == false && found_in_column==false ) break;
            }
            arr[i][j] = ch + 64;
        }
    }
    
    for (int i = 0; i < SIZE; i++)
    {
        for (int j = 0; j < SIZE; j++)
        {
            cout << arr[i][j];
        }
        cout << endl;
    }
    
    return 0;
}