Magic Squares In Grid

class Solution {
public:
    int countMagicSquares(vector<vector<int>>& matrix) {
        int count = 0;
        int rows = matrix.size();
        int cols = matrix[0].size();
        for (int i = 0; i + 2 < rows; i++) {
            for (int j = 0; j + 2 < cols; j++) {
                if (checkMagic(matrix, i, j)) {
                    count++;
                }
            }
        }
        return count;
    }

private:
    bool checkMagic(vector<vector<int>>& matrix, int i, int j) {
        string direct = "2943816729438167";
        string reverse = "7618349276183492";

        string perimeter = "";
        vector<int> indices = {0, 1, 2, 5, 8, 7, 6, 3};
        for (int index : indices) {
            int value = matrix[i + index / 3][j + (index % 3)];
            perimeter += to_string(value);
        }

        return (matrix[i][j] % 2 == 0 && matrix[i + 1][j + 1] == 5 &&
                (direct.find(perimeter) != string::npos ||
                 reverse.find(perimeter) != string::npos));
    }
};

This C++ program identifies and counts Magic Squares within a given 2D grid, specifically focusing on 3x3 subgrids. A Magic Square is characterized by unique numbers where the sum of each row, column, and diagonal equals the same number. Here’s how the solution operates:

• The program traverses the grid, systematically checking each 3x3 subgrid.
• It invokes a helper function checkMagic to determine if the current subgrid forms a Magic Square:
  • The checkMagic function initially constructs a string representation of the square's perimeter. Order matters, requiring two sequences to account for the orientations.
  • The center of this 3x3 grid must be 5 and the corner starting point (matrix[i][j]) must be even. These checks reduce needless permutations.
  • Two hardcoded string templates, direct and reverse, represent the allowable permutations for a valid perimeter sequence.
  • If the perimeter matches any permutation in either direction, the subgrid qualifies as a Magic Square.

This approach efficiently minimizes unnecessary computations by targeting key constraints of a Magic Square directly from its structural properties. This enables only valid configurations to undergo full verification, enhancing performance especially in larger grids.

class Solution {

    public int countMagicSquares(int[][] matrix) {
        int magicCount = 0;
        int rows = matrix.length;
        int cols = matrix[0].length;
        for (int i = 0; i + 2 < rows; i++) {
            for (int j = 0; j + 2 < cols; j++) {
                if (checkMagic(matrix, i, j)) {
                    magicCount++;
                }
            }
        }
        return magicCount;
    }

    private boolean checkMagic(int[][] matrix, int i, int j) {
        String mainPattern = "2943816729438167";
        String reversedPattern = "7618349276183492";

        StringBuilder perimeterValues = new StringBuilder();
        int[] indicesForPerimeter = new int[] { 0, 1, 2, 5, 8, 7, 6, 3 };
        for (int index : indicesForPerimeter) {
            int value = matrix[i + index / 3][j + (index % 3)];
            perimeterValues.append(value);
        }

        String perimeterString = perimeterValues.toString();

        return (
            matrix[i][j] % 2 == 0 &&
            (mainPattern.contains(perimeterString) ||
                reversedPattern.contains(perimeterString)) &&
            matrix[i + 1][j + 1] == 5
        );
    }
}

The provided Java solution involves a method for counting "magic squares" within a 2D matrix. A magic square in this context is a 3x3 sub-grid where the numbers in the square perimeters match specific patterns intended for the solution, and the center of the square must be an odd number, specifically 5.

The method countMagicSquares calculates the number of 3x3 magic squares present in a larger matrix. This process involves iterating through each possible 3x3 sub-grid in the matrix and checking each using the checkMagic helper function.

The checkMagic function confirms whether a given 3x3 grid starting from top-left corner coordinates (i, j) is a magic square based on a few conditions:

• The value at the middle of the grid (i+1, j+1) must be 5.
• The grid's odd-valued perimeter sequence, when viewed accrual from the top-left corner clockwise or counterclockwise, should match pre-defined patterns, identified as mainPattern or reversedPattern in the code. This pattern sequence checks start from the top left and go clockwise or counterclockwise around the border of the 3x3 square.

For developing the perimeter sequence of each grid, the values are appended into a string (perimeterValues) using their absolute values derived from specific ordered indices (indicesForPerimeter). This forms a string sequence from the values in the perimeter of the grid. Evaluate if this sequence appears in either the mainPattern or reversedPattern.

Note: It also checks to ensure every element on the 3x3 grid's perimeter is placed correctly according to the designated patterns if centered with 5, contributing to the definition of a 'magic square.'

In summary, the procedure involves:

1. Looping through each element in the main matrix to consider it as a potential top-left of a 3x3 sub-grid.
2. For each potential top-left origin, check if forming a 3x3 grid with this point as origin can be identified as a magic square using the checkMagic method, which employs string manipulation and pattern matching.

Ensure correct placement of magic squares in larger grid structures efficiently, adhering to specific numerical sequencing rules and central placement conditions.

class Solution:
    def countMagicSquares(self, matrix: List[List[int]]) -> int:
        count = 0
        rows = len(matrix)
        cols = len(matrix[0])
        for i in range(rows - 2):
            for j in range(cols - 2):
                if self._checkMagic(matrix, i, j):
                    count += 1
        return count

    def _checkMagic(self, matrix, x, y):
        seq_str = "2943816729438167"
        reversed_seq = "7618349276183492"
  
        edge_values = []
        edge_pos = [0, 1, 2, 5, 8, 7, 6, 3]
        for pos in edge_pos:
            num = matrix[x + pos // 3][y + pos % 3]
            edge_values.append(str(num))

        converted_seq = "".join(edge_values)
  
        return (
            matrix[x][y] % 2 == 0
            and (
                seq_str.find(converted_seq) != -1
                or reversed_seq.find(converted_seq) != -1
            )
            and matrix[x + 1][y + 1] == 5
        )

The Python script defines a solution for identifying and counting magic squares within a 2D grid. Here, a magic square refers to a 3x3 section of the grid which meets certain numerical properties, specifically, the assignment of numbers such that sums of the 3x3 subgrid's rows, columns, and diagonals are equal.

• The script includes a main method, countMagicSquares, which:

  • Initializes a counter for magic squares.
  • Determines the number of rows and columns in the input matrix.
  • Iterates over possible 3x3 subgrids within the matrix. If a subgrid meets the criteria of being a magic square through the helper method _checkMagic, it increments the count.
  • Returns the total count of magic squares found.

• The helper method _checkMagic specifically checks if a 3x3 section is a magic square:

  • It extracts edge values of the subgrid considering a specific sequence critical for its validation. This is intended to check if the values, when read in a spiral manner from top left to center, match any of two predefined sequences (or their reverse versions) that characterize a normal or mirrored version of a standardized magic square configuration.
  • Additionally, it verifies the centrality and evenness of the top left corner and checks that the center value is 5, which is a fixed requirement in a standard 3x3 magic square.
  • Returns a Boolean indicating whether the subgrid is a magic square based on these criteria.

This solution uses a combination of nested loops to traverse the matrix, string manipulation to assess sequences, and conditional checks to validate subgrid properties against predefined magic square characteristics.