Check whether a Matrix is a Latin Square or not in C++

In this tutorial, we will see how to determine if a given matrix is a Latin square or not, let’s learn how to easily check is a matrix is a Latin square in C++.

Determining if the given matrix is a Latin square in C++

What is a Latin square?
A matrix in which each row and each column doesn’t contain any duplicates is called a Latin Square.
In other words, each column and each row should only consist of unique elements. Observe the example below for a better understanding.

1 2 3 4
1 2 3 3 
3 4 2 1
4 2 1 3

The above matrix is not a Latin square, observe the second row.
The second row has elements 1,2,3,3. You can see that the element 3 is repeated since now the row contains duplicates (3 is the duplicate element here).
So we can conclude that the above matrix is not a Latin square.

Now observe the below matrix which is a Latin square.

1 2 3 4
2 3 4 1
3 4 1 2
4 1 2 3

The above matrix is a Latin square because no matter which row or column you choose, it only consists of unique elements.
For example, let’s choose the second row it contains 2,3,4,1, none of the elements are repeated.
The same goes for the third column it contains 3,4,1,2, again all elements here are unique.
Hence we can conclude that the above matrix is a Latin square.

How to detect if the given matrix is a Latin square or not in C++?
You might have observed that the key to detecting if a matrix is a Latin square or not is, whether it’s rows and columns contains duplicate elements or not.
In other words if we prove that no row or column in the matrix contains duplicates then we can prove that the matrix is a Latin square.

Using set data structure to detect if any row or column has duplicates in it

In C++, we have a data structure called a set, which helps a lot when it comes to dealing with duplicates. A set is a data structure that does not allow any duplicate elements to be inserted in it.
Learn more about sets in C++ here: https://codespeedy.com/unordered-sets-in-cpp/

So if the row of a matrix contains n elements, then if we insert all those elements into a set. Then the size of the set is equal to n only if the row we are inserting doesn’t contain any duplicates. For example.

unordered_set<int> myset;

int n=4;

for(int i=0;i<n;i++){
    myset.insert(1);
    myset.insert(2);
    myset.insert(3);
    myset.insert(3);
}

In the above snippet of code, observe that we are inserting 3 twice into the set. But since the set only contains unique elements it discards one duplicate 3. So even if we are inserting 2 3’s the set only contains one 3.
If we print the elements in the set, it will look like

The set contains
1
2
3

Code for checking if the matrix is a Latin square

As we will be needing a set for each row and column we will be using a vector of sets rather than a single one.

#include <bits/stdc++.h>
using namespace std;

int main() {
  
  int n=0; 
  cout<<"Enter value of n"<<endl;
  cin>>n;
  
  int matrix[n][n];
  memset(matrix,0,sizeof(matrix));
  
  //vector of sets for row
  //and for columns
  vector<set<int> >  rowSet(n);
  vector<set<int> >  colSet(n);
  
  cout<<"Enter the matrix"<<endl;
  for(int i=0;i<n;i++){
      for(int j=0;j<n;j++){
          //insert elements into the
          //matrix
          cin>>matrix[i][j];
          
          //At the same time insert
          //the elements into rowSet
          //and the column set
          rowSet[i].insert(matrix[i][j]);
          colSet[j].insert(matrix[i][j]);
      }
  } 
  //Initially set the variable
  //is latin to true.
  bool isLatin=true;
  
  for(int i=0;i<n;i++){
      
      //if the size of any rowSet 
      //or columnSet is not equal to n
      //then there is a duplicate
      //element in that row or column
      
      if(rowSet[i].size()!=n || colSet[i].size()!=n){
          
          //In such case we set
          //set our boolean variable
          //to false.

          isLatin=false;
      }
  }
  
  if(isLatin==true){
      cout<<"The matrix is a latin square"<<endl;
  }
  else{
      cout<<"The matrix is not a latin square"<<endl;
  }
}

Output

Enter value of n
4
Enter the matrix
1 2 3 4
2 3 4 1
3 4 1 2
4 1 2 3

The matrix is a latin square

Also read: Matrix Inversion in C++

Leave a Reply

Your email address will not be published. Required fields are marked *