Magic Squares In Grid

To count the number of 3 x 3 magic squares inside the given grid, we can iterate through all possible 3 x 3 subgrids and check if each subgrid is a magic square. A 3 x 3 grid is a magic square if it meets the following criteria:

  1. All the numbers in the grid are distinct and lie between 1 and 9.
  2. The sum of the numbers in each row, each column, and both diagonals is the same.

Here’s the code:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution:
    def numMagicSquaresInside(self, grid: List[List[int]]) -> int:
        def is_magic(x: int, y: int) -> bool:
            nums = {grid[x + i][y + j] for i in range(3) for j in range(3)}
            if nums != set(range(1, 10)):
                return False

            s = sum(grid[x][y : y + 3]) # Sum of the first row
            return all(
                sum(grid[x + i][y + j] for j in range(3)) == s
                and sum(grid[x + j][y + i] for j in range(3)) == s
                for i in range(3)
            ) and sum(grid[x + i][y + i] for i in range(3)) == s \
            and sum(grid[x + i][y + 2 - i] for i in range(3)) == s

        rows, cols = len(grid), len(grid[0])
        count = 0
        for i in range(rows - 2):
            for j in range(cols - 2):
                if is_magic(i, j):
                    count += 1
        return count

This code iterates through all possible 3 x 3 subgrids and uses the is_magic function to check if each subgrid is a magic square. The function verifies the constraints for a magic square and returns True or False. The main function counts the number of magic squares and returns the final count.