Magic Squares In Grid
Problem
A 3x3 magic square has distinct values 1-9 with all rows, columns, and diagonals summing to 15. Count how many 3x3 magic squares appear inside the given grid.
grid = [[4,3,8,4],[9,5,1,9],[2,7,6,2]]1def numMagicSquaresInside(grid):
rows, cols = len(grid), len(grid[0])
def magic(r, c):
vals = [grid[r + i][c + j] for i in range(3) for j in range(3)]
if sorted(vals) != list(range(1, 10)): return False
rs = [sum(grid[r + i][c:c + 3]) for i in range(3)]
cs = [sum(grid[r + i][c + j] for i in range(3)) for j in range(3)]
d1 = grid[r][c] + grid[r + 1][c + 1] + grid[r + 2][c + 2]
d2 = grid[r][c + 2] + grid[r + 1][c + 1] + grid[r + 2][c]
return all(x == 15 for x in rs + cs + [d1, d2])
return sum(magic(r, c) for r in range(rows - 2) for c in range(cols - 2))
function numMagicSquaresInside(grid) {
const R = grid.length, C = grid[0].length;
const magic = (r, c) => {
const seen = new Set();
for (let i = 0; i < 3; i++) for (let j = 0; j < 3; j++) {
const v = grid[r + i][c + j];
if (v < 1 || v > 9 || seen.has(v)) return false;
seen.add(v);
}
for (let i = 0; i < 3; i++) if (grid[r + i][c] + grid[r + i][c + 1] + grid[r + i][c + 2] !== 15) return false;
for (let j = 0; j < 3; j++) if (grid[r][c + j] + grid[r + 1][c + j] + grid[r + 2][c + j] !== 15) return false;
if (grid[r][c] + grid[r + 1][c + 1] + grid[r + 2][c + 2] !== 15) return false;
if (grid[r][c + 2] + grid[r + 1][c + 1] + grid[r + 2][c] !== 15) return false;
return true;
};
let count = 0;
for (let r = 0; r <= R - 3; r++) for (let c = 0; c <= C - 3; c++) if (magic(r, c)) count++;
return count;
}
class Solution {
public int numMagicSquaresInside(int[][] grid) {
int R = grid.length, C = grid[0].length, count = 0;
for (int r = 0; r <= R - 3; r++)
for (int c = 0; c <= C - 3; c++)
if (magic(grid, r, c)) count++;
return count;
}
boolean magic(int[][] g, int r, int c) {
boolean[] seen = new boolean[10];
for (int i = 0; i < 3; i++) for (int j = 0; j < 3; j++) {
int v = g[r + i][c + j];
if (v < 1 || v > 9 || seen[v]) return false;
seen[v] = true;
}
for (int i = 0; i < 3; i++) if (g[r + i][c] + g[r + i][c + 1] + g[r + i][c + 2] != 15) return false;
for (int j = 0; j < 3; j++) if (g[r][c + j] + g[r + 1][c + j] + g[r + 2][c + j] != 15) return false;
if (g[r][c] + g[r + 1][c + 1] + g[r + 2][c + 2] != 15) return false;
if (g[r][c + 2] + g[r + 1][c + 1] + g[r + 2][c] != 15) return false;
return true;
}
}
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
bool magic(vector<vector<int>>& g, int r, int c) {
vector<bool> seen(10, false);
for (int i = 0; i < 3; i++) for (int j = 0; j < 3; j++) {
int v = g[r + i][c + j];
if (v < 1 || v > 9 || seen[v]) return false;
seen[v] = true;
}
for (int i = 0; i < 3; i++) if (g[r + i][c] + g[r + i][c + 1] + g[r + i][c + 2] != 15) return false;
for (int j = 0; j < 3; j++) if (g[r][c + j] + g[r + 1][c + j] + g[r + 2][c + j] != 15) return false;
if (g[r][c] + g[r + 1][c + 1] + g[r + 2][c + 2] != 15) return false;
if (g[r][c + 2] + g[r + 1][c + 1] + g[r + 2][c] != 15) return false;
return true;
}
int numMagicSquaresInside(vector<vector<int>>& grid) {
int R = grid.size(), C = grid[0].size(), count = 0;
for (int r = 0; r <= R - 3; r++) for (int c = 0; c <= C - 3; c++)
if (magic(grid, r, c)) count++;
return count;
}
};
Explanation
A magic square is a strict little pattern, so the plan is to slide a 3x3 window over every possible top-left corner in the grid and check whether that window is magic.
For a 3x3 block to be magic it must satisfy two things. First, the nine numbers must be exactly the digits 1 through 9, each used once. Second, every row, every column, and both diagonals must add up to 15.
The helper magic(r, c) grabs the nine values starting at (r, c), checks that sorted(vals) equals [1..9], then verifies the three row sums rs, the three column sums cs, and the two diagonals d1 and d2 are all 15.
The outer loops only go up to rows - 2 and cols - 2 so the 3x3 window always stays inside the grid, and we count how many windows pass the test.
Example: in [[4,3,8,4],[9,5,1,9],[2,7,6,2]] the block at corner (0,0) holds 4 3 8 / 9 5 1 / 2 7 6, which uses 1-9 and every line sums to 15, so the answer is 1.