Contar cuadrados mágicos en una cuadrícula

Dada una Grid de enteros. La tarea es encontrar el número total de subcuadrículas Magic Square de 3 x 3 (contiguas) en la cuadrícula dada. Un cuadrado mágico es una cuadrícula de 3 x 3 llena de todos los números distintos del 1 al 9, de modo que cada fila, columna y ambas diagonales tienen la misma suma.
Ejemplos:
 

Entrada: G = { { 4, 3, 8, 4 }, { 9, 5, 1, 9 }, { 2, 7, 6, 2 } } 
Salida: 1 
Explicación: La siguiente subcuadrícula es un cuadrado mágico de 3 x 3 : [ 4 3 8, 9 5 1, 2 7 6 ]
Entrada : G = { { 1, 2, 3, 4, 5 }, { 6, 7, 8, 9, 10 }, { 10, 11, 12, 13, 14 }, { 15, 16, 17, 18, 19 } } 
Salida: 0

Enfoque: Revisemos cada subcuadrícula de 3 x 3 individualmente. Para cada cuadrícula, todos los números deben ser únicos y entre (1 y 9) también todas las filas , columnas y ambas diagonales deben tener la misma suma.
Observe también el hecho de que una subcuadrícula es un Cuadrado Mágico si su elemento central es 5. Porque al sumar los 12 valores de las cuatro líneas que cruzan el centro, suman 60, pero también suman la cuadrícula completa (45), más 3 veces el valor medio. Esto implica que el valor medio es 5. Por lo tanto, podemos verificar esta condición que nos ayuda a omitir varias subcuadrículas. 
Puedes obtener más información sobre Magic_square aquí o aquí .
El procedimiento para verificar que una subcuadrícula sea un Cuadrado Mágico es el siguiente: 
 

• El elemento del medio debe ser 5.
• La suma de la cuadrícula debe ser 45 y contiene todos los valores distintos del 1 al 9.
• Cada horizontal (fila) y vertical (columna) debe sumar 15.
• Ambas líneas diagonales también deben sumar 15.

A continuación se muestra la implementación del enfoque anterior: 
 

// CPP program to count magic squares
#include <bits/stdc++.h>
using namespace std;
 
const int R = 3;
const int C = 4;
 
// function to check is subgrid is Magic Square
int magic(int a, int b, int c, int d, int e,
                int f, int g, int h, int i)
{
    set<int> s1 = { a, b, c, d, e, f, g, h, i },
             s2 = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
 
    // Elements of grid must contain all numbers from 1 to
    // 9, sum of all rows, columns and diagonals must be
    // same, i.e., 15.
    if (s1 == s2 && (a + b + c) == 15 && (d + e + f) == 15 &&
       (g + h + i) == 15 && (a + d + g) == 15 &&                    
       (b + e + h) == 15 && (c + f + i) == 15 &&
       (a + e + i) == 15 && (c + e + g) == 15)
       return true;
    return false;   
}
 
// Function to count total Magic square subgrids
int CountMagicSquare(int Grid[R][C])
{
    int ans = 0;
 
    for (int i = 0; i < R - 2; i++)
        for (int j = 0; j < C - 2; j++) {
 
            // if condition true skip check
            if (Grid[i + 1][j + 1] != 5)
                continue;
 
            // check for magic square subgrid
            if (magic(Grid[i][j], Grid[i][j + 1],
                Grid[i][j + 2], Grid[i + 1][j],
                Grid[i + 1][j + 1], Grid[i + 1][j + 2],
                Grid[i + 2][j], Grid[i + 2][j + 1],
                Grid[i + 2][j + 2]))
 
                ans += 1;
          cout<<"ans = "<<ans<<endl;
        }
 
    // return total magic square
    return ans;
}
 
// Driver program
int main()
{
    int G[R][C] = { { 4, 3, 8, 4 },
                    { 9, 5, 1, 9 },
                    { 2, 7, 6, 2 } };
 
    // function call to print required answer
    cout << CountMagicSquare(G);
 
    return 0;
}
 
// This code is written by Sanjit_Prasad

# Python3 program to count magic squares
R = 3
C = 4
 
# function to check is subgrid is Magic Square
def magic(a, b, c, d, e, f, g, h, i):
 
    s1 = set([a, b, c, d, e, f, g, h, i])
    s2 = set([1, 2, 3, 4, 5, 6, 7, 8, 9])
 
    # Elements of grid must contain all numbers
    # from 1 to 9, sum of all rows, columns and
    # diagonals must be same, i.e., 15.
    if (s1 == s2 and (a + b + c) == 15 and
       (d + e + f) == 15 and (g + h + i) == 15 and
       (a + d + g) == 15 and (b + e + h) == 15 and
       (c + f + i) == 15 and (a + e + i) == 15 and
       (c + e + g) == 15):
        return True
         
    return false    
 
# Function to count total Magic square subgrids
def CountMagicSquare(Grid):
 
    ans = 0
 
    for i in range(0, R - 2):
        for j in range(0, C - 2):
 
            # if condition true skip check
            if Grid[i + 1][j + 1] != 5:
                continue
 
            # check for magic square subgrid
            if (magic(Grid[i][j], Grid[i][j + 1],
                  Grid[i][j + 2], Grid[i + 1][j],
                  Grid[i + 1][j + 1], Grid[i + 1][j + 2],
                  Grid[i + 2][j], Grid[i + 2][j + 1],
                  Grid[i + 2][j + 2]) == True):
 
                ans += 1
 
    # return total magic square
    return ans
 
# Driver Code
if __name__ == "__main__":
 
    G = [[4, 3, 8, 4],
         [9, 5, 1, 9],
         [2, 7, 6, 2]]
 
    # Function call to print required answer
    print(CountMagicSquare(G))
     
# This code is contributed by Rituraj Jain

// C# program to count magic squares
using System;
using System.Collections.Generic;
 
class GFg {
    const int R = 3;
    const int C = 4;
 
    // function to check is subgrid is Magic Square
    static int magic(int a, int b, int c, int d, int e,
                     int f, int g, int h, int i)
    {
        HashSet<int> s1 = new HashSet<int>() {
            a, b, c, d, e, f, g, h, i
        };
        HashSet<int> s2 = new HashSet<int>() {
            1, 2, 3, 4, 5, 6, 7, 8, 9
        };
 
        // Elements of grid must contain all numbers from 1
        // to 9, sum of all rows, columns and diagonals must
        // be same, i.e., 15.
        if (s1.SetEquals(s2) && (a + b + c) == 15
            && (d + e + f) == 15 && (g + h + i) == 15
            && (a + d + g) == 15 && (b + e + h) == 15
            && (c + f + i) == 15 && (a + e + i) == 15
            && (c + e + g) == 15)
            return 1;
        return 0;
    }
 
    // Function to count total Magic square subgrids
    static int CountMagicSquare(int[, ] Grid)
    {
        int ans = 0;
 
        for (int i = 0; i < R - 2; i++)
            for (int j = 0; j < C - 2; j++) {
 
                // if condition true skip check
                if (Grid[i + 1, j + 1] != 5)
                    continue;
 
                // check for magic square subgrid
                if (magic(Grid[i, j], Grid[i, j + 1],
                          Grid[i, j + 2], Grid[i + 1, j],
                          Grid[i + 1, j + 1],
                          Grid[i + 1, j + 2],
                          Grid[i + 2, j],
                          Grid[i + 2, j + 1],
                          Grid[i + 2, j + 2])
                    != 0)
 
                    ans += 1;
            }
 
        // return total magic square
        return ans;
    }
 
    // Driver program
    public static void Main()
    {
        int[, ] G = { { 4, 3, 8, 4 },
                      { 9, 5, 1, 9 },
                      { 2, 7, 6, 2 } };
 
        // function call to print required answer
        Console.WriteLine(CountMagicSquare(G));
    }
}
 
// This code is contributed by ukasp.

<script>
 
// JavaScript program to count magic squares
var R = 3;
var C = 4;
 
function eqSet(as, bs) {
    if (as.size !== bs.size) return false;
    for (var a of as) if (!bs.has(a)) return false;
    return true;
}
 
// function to check is subgrid is Magic Square
function magic(a, b, c, d, e, f, g, h, i)
{
    var s1 = new Set([a, b, c, d, e, f, g, h, i]);
    var s2 = new Set([ 1, 2, 3, 4, 5, 6, 7, 8, 9 ]);
 
    // Elements of grid must contain all numbers from 1 to
    // 9, sum of all rows, columns and diagonals must be
    // same, i.e., 15.
    if (eqSet(s1, s2) && (a + b + c) == 15 && (d + e + f) == 15 &&
       (g + h + i) == 15 && (a + d + g) == 15 &&                    
       (b + e + h) == 15 && (c + f + i) == 15 &&
       (a + e + i) == 15 && (c + e + g) == 15)
       return true;
    return false;   
}
 
// Function to count total Magic square subgrids
function CountMagicSquare(Grid)
{
    var ans = 0;
 
    for (var i = 0; i < R - 2; i++)
        for (var j = 0; j < C - 2; j++) {
 
            // if condition true skip check
            if (Grid[i + 1][j + 1] != 5)
                continue;
 
            // check for magic square subgrid
            if (magic(Grid[i][j], Grid[i][j + 1],
                Grid[i][j + 2], Grid[i + 1][j],
                Grid[i + 1][j + 1], Grid[i + 1][j + 2],
                Grid[i + 2][j], Grid[i + 2][j + 1],
                Grid[i + 2][j + 2]))
                ans += 1;
        }
 
    // return total magic square
    return ans;
}
 
// Driver program
var G = [[4, 3, 8, 4 ],
                [ 9, 5, 1, 9 ],
                [ 2, 7, 6, 2 ]];
// function call to print required answer
document.write( CountMagicSquare(G));
 
 
</script>

1

Complejidad temporal: O(R * C)

Espacio Auxiliar: O(1)