# 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