A 3 x 3 magic square is a 3 x 3 grid filled with distinct numbers from 1 to 9 such that each row, column, and both diagonals all have the same sum.
Given a row x col grid of integers, how many 3 x 3 "magic square" subgrids are there?  (Each subgrid is contiguous).
 
Example 1:

Input: grid = [[4,3,8,4],[9,5,1,9],[2,7,6,2]]
Output: 1
Explanation: 
The following subgrid is a 3 x 3 magic square:

while this one is not:

In total, there is only one magic square inside the given grid.

Example 2:
Input: grid = [[8]]
Output: 0

Example 3:
Input: grid = [[4,4],[3,3]]
Output: 0

Example 4:
Input: grid = [[4,7,8],[9,5,1],[2,3,6]]
Output: 0

 
Constraints:

row == grid.length
col == grid[i].length
1 <= row, col <= 10
0 <= grid[i][j] <= 15

Source: leetcode | Difficulty: MEDIUM_HARD
Tags: Matrices

Data structures

Mathematics

Starter code: class Solution:
    def numMagicSquaresInside(self, grid: List[List[int]]) -> int:
        

Solutions:
class Solution:

	def numMagicSquaresInside(self, grid: List[List[int]]) -> int:
		if len(grid) < 3 or len(grid[0]) < 3:
			return 0
		rows = len(grid)
		cols = len(grid[0])
		magic_squares = 0
		for i in range(rows - 2):
			for j in range(cols - 2):
				window = [tmp[j:j + 3] for tmp in grid[i:i + 3]]
				if self.isMagicSquare(window):
					magic_squares += 1
		return magic_squares

	def isMagicSquare(self, square: List[List[int]]) -> bool:
		target = square[0][0] + square[0][1] + square[0][2]
		seen = {}
		print(square)
		for row in square:
			tmp = 0
			for i in row:
				tmp += i
				if i in seen or i > 9 or i < 1:
					return False
				else:
					seen[i] = 1
			if tmp != target:
				return False
		for i in range(3):
			tmp = 0
			for row in square:
				tmp += row[i]
			if tmp != target:
				return False
		tmp = 0
		for i in range(3):
			tmp += square[i][i]
		if tmp != target:
			return False
		tmp = 0
		for i in range(3):
			tmp += square[i][2 - i]
		if tmp != target:
			return False
		return True


class Solution:

	def isMagicSquare(self, grid):
		flat = [num for row in grid for num in row]
		if sorted(flat) != [1, 2, 3, 4, 5, 6, 7, 8, 9]:
			return False
		row_sums = [sum(row) for row in grid]
		col_sums = [sum([row[i] for row in grid]) for i in range(3)]
		diag_sums = [sum([grid[i][i] for i in range(3)]), grid[0][2] + grid[1][1] + grid[2][0]]
		row_sums.extend(col_sums)
		row_sums.extend(diag_sums)
		return len(set(row_sums)) == 1

	def numMagicSquaresInside(self, grid: List[List[int]]) -> int:
		cnt = 0
		for i in range(len(grid) - 2):
			for j in range(len(grid) - 2):
				temp_grid = [grid[i + k][j:j + 3] for k in range(3)]
				if self.isMagicSquare(temp_grid):
					cnt += 1
		return cnt