Last Updated: 25 Nov, 2021

Magic Squares In Matrix

Moderate

Problem statement

You are given a matrix ‘MAT’, of size ‘M’ * ‘N’ and has numbers from 1 to 9. Find the number of magic square submatrix present in the matrix. A submatrix is a magic square if that matrix's size is 3 * 3 and consists of distinct numbers from 1 to 9 and having the sum of all the rows, columns, and diagonals equal.

For example:

Let matrix be : 
8 3 4
1 5 9
6 7 2

The sum of the first row is: 15
The sum of the second row is: 15
The sum of the third row is: 15
The sum of the first column is: 15
The sum of the second column is: 15
The sum of the third column is: 15
The sum of both the diagonals is: 15
The matrix consists of distinct numbers from 1 to 9 and has the sum of all the rows, columns, and diagonals equal. So, it is a magic square.

Input Format :

The first line of input contains an integer ‘T’, denoting the number of test cases.

The first line of each test case contains two space-separated integers, ‘M’ and ‘N’, representing the size of the matrices.

The next ‘M’  lines of each test case contain ‘N’ space-separated integers, representing the elements of ‘MAT’.

Output Format :

For each test case, print the count of magic squares present in the matrix.

Print output of each test case in a separate line.

Note :

You do not need to print anything. It has already been taken care of. Just implement the given function.

Constraints :

1 <= T <= 10
1 <= M, N <= 5*10^3
1 <= MAT[i][j] <= 9

Time Limit: 1 sec

Solve now

Approaches

01 Approach

The basic idea is to check every possible submatrix of size 3 * 3 of the matrix whether it is a good square or not. For every submatrix, we find the sum of all the rows, columns, and diagonals and check whether all are equal or not. We also check whether the elements present in the submatrix are distinct or not.

Here is the algorithm :

Base case:
- Check if ‘M’ or ‘N’ is smaller than 3.
  - Return 0.
Create a variable (say, ‘CNT’) to store the number of good squares.
Run a loop from 0 to ‘M’ (say, iterator ‘i’) to traverse the rows.
- Run a loop from 0 to ‘N’ (say, iterator ‘j’) to traverse the columns.
  - Check if the submatrix starting from the (‘i’, ‘j’) index is valid by calling the function isValid.
    - Increment ‘CNT’ by 1.
Return ‘CNT’.

isValid(‘MAT’, ‘M’, ‘N’, ‘i’, ‘j’) (where ‘MAT’ is given matrix, ‘M’ and ‘N’ are dimensions of the matrix, ‘i’ and ‘j’ are the starting index of the matrix)

Base case:
- Check if ‘M’ - ‘i’ or ‘N’ - ‘j’ is smaller than 3 (a good square cannot exist).
  - Return FALSE.
Create a set (say, ‘VAL’) to store the numbers of the submatrix.
Run a loop from ‘i’ to ‘i’ + 3 (say, iterator ‘r’).
- Run a loop from ‘j’ to ‘j’ + 3 (say, iterator ‘c’).
  - Insert ‘MAT[r][c]’ in the set.
Check if the size of ‘VAL’ is not equal to 9.
- Return FALSE.
Create a variable (say, ‘ROW1’) to store the sum of elements of the first row and initialize it with sum of ‘MAT[i][j]’, ‘MAT[i][j + 1]’, and ‘MAT[i][j + 2]’.
Create a variable (say, ‘ROW2’) to store the sum of elements of the second row and initialize it with sum of ‘MAT[i + 1][j]’, ‘MAT[i + 1][j + 1]’, and ‘MAT[i + 1][j + 2]’.
Create a variable (say, ‘ROW3’) to store the sum of elements of the third row and initialize it with sum of ‘MAT[i + 2][j]’, ‘MAT[i + 2][j + 1]’, and ‘MAT[i + 2][j + 2]’.
Check if ‘ROW1’ is not equal to ‘ROW2’ or ‘ROW1’ is not equal to ‘ROW3’.
- Return FALSE.
Similarly, check if the sum of all the columns is equal and is equal to the sum of the row, otherwise return FALSE.
Similarly, check if the sum of all the diagonals is equal and is equal to the sum of the row, otherwise return FALSE.
Return TRUE.

Solve now