Problem Description

A magic square is a 3×3 grid where all numbers from 1 to 9 appear exactly once, and every row, column, and both diagonals sum to the same value (which is always 15 for a 3×3 magic square with numbers 1-9).

Given a row × col grid of integers, you need to count how many 3×3 subgrids within it form valid magic squares.

Key requirements for a valid magic square subgrid:

• Must be exactly 3×3 in size
• Must contain only the numbers 1 through 9
• Each number from 1 to 9 must appear exactly once (no duplicates)
• All three rows must have the same sum
• All three columns must have the same sum
• Both diagonals must have the same sum
• All these sums must be equal to each other

Important note: While a valid magic square can only contain numbers 1-9, the input grid may contain numbers up to 15. Any 3×3 subgrid containing numbers outside the range 1-9 cannot be a magic square.

The task is to examine all possible 3×3 subgrids in the given grid and return the total count of those that are valid magic squares.

Intuition

Since we need to find all valid magic square subgrids, the most straightforward approach is to check every possible 3×3 subgrid in the given matrix. We can't optimize much here because we need to verify multiple conditions for each potential magic square.

For each 3×3 subgrid, we need to verify several properties:

1. Valid numbers: All values must be between 1 and 9
2. Distinctness: All 9 numbers must be different (which means we need exactly the numbers 1-9)
3. Equal sums: All rows, columns, and diagonals must sum to the same value

The key insight is that if we have the numbers 1 through 9 appearing exactly once, the sum of each row, column, and diagonal in a valid magic square must be 15 (since 1+2+...+9 = 45, and 45/3 = 15 for each row/column).

To check each subgrid efficiently, we can:

• Use a set to track if we have exactly 9 distinct numbers
• Calculate the sum for each row, column, and both diagonals as we iterate through the 3×3 subgrid
• Compare all these sums to ensure they're equal

The enumeration approach works well here because:

• The subgrid size is fixed and small (3×3)
• We need to examine every element in each potential subgrid anyway
• There's no pattern we can exploit to skip checking certain subgrids

By systematically checking each possible top-left corner position (i, j) and validating the 3×3 subgrid starting from that position, we ensure we don't miss any valid magic squares.

Learn more about Math patterns.

Solution Approach

The solution uses an enumeration approach where we check every possible 3×3 subgrid in the matrix.

Main Algorithm Structure:

1. Iterate through each position (i, j) in the grid that could serve as the top-left corner of a 3×3 subgrid
2. For each position, call a helper function check(i, j) to verify if the 3×3 subgrid starting at that position is a magic square
3. Sum up all the valid magic squares found

Implementation Details of the check function:

1. Boundary Check: First verify that a 3×3 subgrid starting at (i, j) doesn't go out of bounds:

   if i + 3 > m or j + 3 > n:
       return 0

2. Data Structures Used:

   • A set s to track distinct numbers and ensure we have exactly 9 different values
   • Arrays row[3] and col[3] to store the sum of each row and column
   • Variables a and b to store the sums of the main diagonal and anti-diagonal

3. Single Pass Validation: Iterate through the 3×3 subgrid once, and for each element at position (x, y):

   • Check if the value v is within the valid range [1, 9]. If not, return 0
   • Add the value to the set s
   • Update the corresponding row sum: row[x - i] += v
   • Update the corresponding column sum: col[y - j] += v
   • If on the main diagonal (x - i == y - j), add to diagonal sum a
   • If on the anti-diagonal (x - i == 2 - (y - j)), add to diagonal sum b

4. Final Validation:

   • Check if we have exactly 9 distinct numbers: len(s) != 9
   • Check if both diagonals have the same sum: a != b
   • Check if all rows equal the diagonal sum: any(x != a for x in row)
   • Check if all columns equal the diagonal sum: any(x != a for x in col)
   • If all conditions are met, return 1; otherwise, return 0

Time Complexity: O(m × n) where m and n are the dimensions of the grid. For each possible top-left corner, we perform a constant amount of work (checking a 3×3 subgrid is O(9) = O(1)).

Space Complexity: O(1) as we only use a fixed amount of extra space regardless of input size (the set can hold at most 9 elements, and the arrays are of fixed size 3).

Example Walkthrough

Let's walk through a small example to illustrate the solution approach.

Consider this 4×5 grid:

grid = [[4, 3, 8, 4, 5],
        [9, 5, 1, 9, 8],
        [2, 7, 6, 2, 3],
        [6, 1, 3, 7, 2]]

We need to check all possible 3×3 subgrids. Since our grid is 4×5, we can have top-left corners at positions where i ≤ 1 and j ≤ 2 (to ensure the 3×3 subgrid fits).

Step 1: Check subgrid starting at (0, 0)

The 3×3 subgrid is:

4 3 8
9 5 1
2 7 6

Let's validate this subgrid:

• Range check: All values are in [1, 9] ✓
• Distinct values: {4, 3, 8, 9, 5, 1, 2, 7, 6} - we have 9 distinct values ✓
• Row sums: Row 0: 4+3+8=15, Row 1: 9+5+1=15, Row 2: 2+7+6=15 ✓
• Column sums: Col 0: 4+9+2=15, Col 1: 3+5+7=15, Col 2: 8+1+6=15 ✓
• Diagonal sums: Main: 4+5+6=15, Anti: 8+5+2=15 ✓

All sums equal 15, so this is a valid magic square! Count = 1.

Step 2: Check subgrid starting at (0, 1)

The 3×3 subgrid is:

3 8 4
5 1 9
7 6 2

Let's validate:

• Range check: All values are in [1, 9] ✓
• Distinct values: {3, 8, 4, 5, 1, 9, 7, 6, 2} - we have 9 distinct values ✓
• Row sums: Row 0: 3+8+4=15, Row 1: 5+1+9=15, Row 2: 7+6+2=15 ✓
• Column sums: Col 0: 3+5+7=15, Col 1: 8+1+6=15, Col 2: 4+9+2=15 ✓
• Diagonal sums: Main: 3+1+2=6, Anti: 4+1+7=12 ✗

The diagonal sums don't match, so this is NOT a magic square.

Step 3: Check subgrid starting at (0, 2)

The 3×3 subgrid is:

8 4 5
1 9 8
6 2 3

Let's validate:

• Distinct values: {8, 4, 5, 1, 9, 8, 6, 2, 3} - we have duplicate 8s ✗

Since we don't have exactly 9 distinct values (8 appears twice), this cannot be a magic square.

Step 4: Check subgrid starting at (1, 0)

The 3×3 subgrid is:

9 5 1
2 7 6
6 1 3

Let's validate:

• Distinct values: {9, 5, 1, 2, 7, 6, 6, 1, 3} - we have duplicate 1s and 6s ✗

This cannot be a magic square due to duplicates.

Step 5: Check subgrid starting at (1, 1)

The 3×3 subgrid is:

5 1 9
7 6 2
1 3 7

Let's validate:

• Distinct values: {5, 1, 9, 7, 6, 2, 1, 3, 7} - we have duplicate 1s and 7s ✗

This cannot be a magic square due to duplicates.

Step 6: Check subgrid starting at (1, 2)

The 3×3 subgrid is:

1 9 8
6 2 3
3 7 2

Let's validate:

• Distinct values: {1, 9, 8, 6, 2, 3, 3, 7, 2} - we have duplicate 2s and 3s ✗

This cannot be a magic square due to duplicates.

Final Result: Out of 6 possible 3×3 subgrids, only 1 is a valid magic square.

The algorithm efficiently checks each condition in a single pass through each 3×3 subgrid, accumulating row sums, column sums, and diagonal sums while simultaneously checking for distinct values and valid range.

Solution Implementation

Time and Space Complexity

Time Complexity: O(m * n)

For each position (i, j) in the grid, we call the check function which examines a 3×3 subgrid. The check function performs:

• A nested loop iterating through 9 cells (3×3), which takes O(9) = O(1) time
• Set operations (add) which are O(1) on average
• Checking conditions for rows, columns, and diagonals, which involves iterating through arrays of size 3, taking O(3) = O(1) time

Since we call check for each of the m * n positions in the grid, and each call takes O(1) time, the overall time complexity is O(m * n).

Space Complexity: O(1)

The space used by the algorithm includes:

• A set s that stores at most 9 unique values: O(9) = O(1)
• Two arrays row and col, each of size 3: O(3) + O(3) = O(6) = O(1)
• A few integer variables (a, b, m, n, etc.): O(1)

The space usage doesn't depend on the input size, so the overall space complexity is O(1).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Incorrect Anti-Diagonal Calculation

One of the most common mistakes is incorrectly identifying which cells belong to the anti-diagonal (top-right to bottom-left).

Incorrect approach:

# Wrong: This checks for bottom-left to top-right
if relative_row + relative_col == 2:
    anti_diagonal_sum += value

Correct approach:

# Correct: For anti-diagonal in a 3x3 grid
if relative_row == 2 - relative_col:
    anti_diagonal_sum += value

The anti-diagonal positions in a 3x3 grid are: (0,2), (1,1), (2,0), which satisfy the equation row + col = 2.

2. Forgetting to Check Value Range

Many solutions forget that while a magic square must contain numbers 1-9, the input grid can contain numbers up to 15.

Pitfall example:

# Missing range check - will incorrectly validate subgrids with numbers > 9
unique_numbers.add(value)
# Continue processing without checking if 1 <= value <= 9

Solution:

# Always check the valid range first
if value < 1 or value > 9:
    return 0
unique_numbers.add(value)

3. Off-by-One Errors in Boundary Checks

A subtle but critical error is using incorrect boundary conditions when checking if a 3x3 subgrid fits within the grid.

Incorrect:

# Wrong: This allows starting positions that would go out of bounds
if row + 2 < rows and col + 2 < cols:
    # Process subgrid

Correct:

# Correct: Ensures the entire 3x3 subgrid fits
if row + 3 > rows or col + 3 > cols:
    return 0

4. Not Verifying All Numbers 1-9 Are Present

Some solutions check for duplicates but forget to ensure all numbers from 1 to 9 are actually present.

Incomplete validation:

# This only checks for 9 unique numbers, not that they're specifically 1-9
if len(unique_numbers) == 9:
    # Assumes it's valid

Complete validation:

# First check range for each value (1-9)
if value < 1 or value > 9:
    return 0
# Then check we have exactly 9 unique numbers
if len(unique_numbers) != 9:
    return 0
# This ensures we have exactly the numbers 1-9 with no duplicates

5. Assuming Magic Constant is Always 15

While it's true that a 3x3 magic square with numbers 1-9 always sums to 15, hardcoding this value can lead to errors if you don't validate all constraints properly.

Risky approach:

# Hardcoding the magic constant
MAGIC_SUM = 15
if row_sum != MAGIC_SUM:
    return 0

Robust approach:

# Calculate the actual sum from the diagonals and use that as reference
if main_diagonal_sum != anti_diagonal_sum:
    return 0
if any(row_sum != main_diagonal_sum for row_sum in row_sums):
    return 0
# This ensures all sums are equal without assuming a specific value