LeetCode 840 - Magic Squares In Grid

https://leetcode.com/problems/magic-squares-in-grid/

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 an grid of integers, how many 3 x 3 "magic square" subgrids are there?  (Each subgrid is contiguous).

Example 1:

Input: [[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:
438
951
276

while this one is not:
384
519
762

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

Note:

1. 1 <= grid.length <= 10
2. 1 <= grid[0].length <= 10
3. 0 <= grid[i][j] <= 15

Let's check every 3x3 grid individually. For each grid, all numbers must be unique and between 1 and 9; plus every row, column, and diagonal must have the same sum.

Extra Credit

We could also include an if grid[r+1][c+1] != 5: continue check into our code, helping us skip over our for r... for c... for loops faster. This is based on the following observations:

• The sum of the grid must be 45, as it is the sum of the distinct values from 1 to 9.
• Each horizontal and vertical line must add up to 15, as the sum of 3 of these lines equals the sum of the whole grid.
• The diagonal lines must also sum to 15, by definition of the problem statement.
• Adding the 12 values from the four lines that cross the center, these 4 lines add up to 60; but they also add up to the entire grid (45), plus 3 times the middle value. This implies the middle value is 5.

    public int numMagicSquaresInside(int[][] grid) {

        int R = grid.length, C = grid[0].length;

        int ans = 0;

        for (int r = 0; r < R-2; ++r)

            for (int c = 0; c < C-2; ++c) {

                if (grid[r+1][c+1] != 5) continue;  // optional skip

                if (magic(grid[r][c], grid[r][c+1], grid[r][c+2],

                          grid[r+1][c], grid[r+1][c+1], grid[r+1][c+2],

                          grid[r+2][c], grid[r+2][c+1], grid[r+2][c+2]))

                    ans++;

            }

        return ans;

    }

    public boolean magic(int... vals) {

        int[] count = new int[16];

        for (int v: vals) count[v]++;

        for (int v = 1; v <= 9; ++v)

            if (count[v] != 1)

                return false;

        return (vals[0] + vals[1] + vals[2] == 15 &&

                vals[3] + vals[4] + vals[5] == 15 &&

                vals[6] + vals[7] + vals[8] == 15 &&

                vals[0] + vals[3] + vals[6] == 15 &&

                vals[1] + vals[4] + vals[7] == 15 &&

                vals[2] + vals[5] + vals[8] == 15 &&

                vals[0] + vals[4] + vals[8] == 15 &&

                vals[2] + vals[4] + vals[6] == 15);

    }

https://leetcode.com/problems/magic-squares-in-grid/discuss/133874/Python-5-and-43816729

One thing to pay attention: A 3 x 3 magic square is a 3 x 3 grid filled with distinct numbers from 1 to 9.
I just find many sumbmission ignoring this condition.

Here I just want share two observatons with this 1-9 condition:

Assume a magic square:
a1,a2,a3
a4,a5,a6
a7,a8,a9

a2 + a5 + a8 = 15
a4 + a5 + a6 = 15
a1 + a5 + a9 = 15
a3 + a5 + a7 = 15

Accumulate all, then we have:
sum(ai) + 3 * a5 = 60
3 * a5 = 15
a5 = 5

The center of magic square must be 5.

Another observation for other 8 numbers:
The even must be in the corner, and the odd must be on the edge.
And it must be in a order like "43816729" （clockwise or anticlockwise)

    def numMagicSquaresInside(self, g):
        def isMagic(i, j):
            s = "".join(str(g[i + x / 3][j + x % 3]) for x in [0, 1, 2, 5, 8, 7, 6, 3])
            return g[i][j] % 2 == 0 and (s in "43816729" * 2 or s in "43816729"[::-1] * 2)
        return sum(isMagic(i, j) for i in range(len(g) - 2) for j in range(len(g[0]) - 2) if g[i + 1][j + 1] == 5)