Como resolver o quebra-cabeça quadrado mágico 3x3 em C & Python

O que é um quadrado mágico?

Um quadrado mágico é uma matriz quadrada com uma disposição especial de números. Os valores são colocados de forma que a soma em cada linha, cada coluna e ambas as diagonais principais permaneça a mesma. Os quadrados mágicos são quebra-cabeças lógicos simples usados ​​em matemática recreativa.

Exemplo de quadrados mágicos:

O diagrama acima mostra um quadrado mágico de ordem 3. A soma de cada diagonal, linha e coluna é igual a 15. A próxima seção explica como esse total constante é obtido.

Como funcionam os quadrados mágicos

Um quadrado mágico de ordem n é uma matriz n por n contendo n² inteiros positivos. O número de linhas ou colunas é chamado de ordem da matriz.

Os quebra-cabeças de quadrados mágicos típicos têm uma ordem ímpar e usam os números inteiros de 1 a n². Como a soma de cada linha, coluna e diagonal deve ser a mesma, esse valor é chamado de soma mágica ou constante mágica. A constante depende apenas de n. A fórmula para a soma mágica de ordem n é:

Considere um quadrado mágico de ordem 3. A soma mágica, então, é:

Essa fórmula explica a aritmética, mas o enigma tem uma longa história cultural que lhe confere seu nome memorável.

Por que são chamadas de mágicas?

Os matemáticos da antiguidade eram fascinados por combinações interessantes de números, e o quadrado mágico era uma delas. As primeiras evidências datam da China, por volta de 190 a.C.

Estudos mostram evidências de quebra-cabeças de quadrados mágicos no Japão antigo, na Índia e na Arábia. Lendas ligavam esses arranjos ao mundo mágico, e o nome permaneceu. Além do folclore, matemáticos também definiram categorias formais que distinguem um quadrado do outro.

Tipos de Quadrado Mágico

Existem diversas variantes de quadrados mágicos na matemática:

• Quadrado Mágico Normal: Contém os primeiros n² números naturais.
• Quadrado Semi-Mágico: Apenas as linhas e as colunas somam a constante mágica.
• Quadrado Mágico Simples: As linhas, colunas e ambas as diagonais principais somam a constante mágica.
• Quadrado Mágico Mais Perfeito: Um quadrado mágico normal com duas propriedades extras. Cada subquadrado 2 por 2 da matriz soma 2(n²+1), e qualquer par de números que estejam a n/2 células de distância soma n²+1.

Existem outras categorias baseadas em propriedades adicionais. Sempre que o termo "quadrado mágico" for usado sem qualificação neste tutorial, ele se referirá a um quadrado mágico simples, normal e de ordem ímpar.

Algoritmo para gerar um quadrado mágico

O algoritmo clássico para gerar um quadrado mágico de ordem ímpar, chamado método siamês, é o seguinte:

• O primeiro número (1) é armazenado na posição (n/2, n-1), onde a primeira coordenada é o índice da linha e a segunda é o índice da coluna. Para etapas posteriores, chamemos esta posição de (x, y).
• O próximo número é colocado em (x-1, y+1). Se essa posição for inválida, aplique as seguintes regras:
  1. Se o índice da linha for -1, arredonde para n-1. Se o índice da coluna for n, arredonde para 0.
  2. Se a posição calculada já contiver um número, incremente a linha em 1 e decremente a coluna em 2.
  3. Se a linha for -1 e a coluna for n ao mesmo tempo, a nova posição será (0, n-2).

Observação: Este algoritmo gera apenas quadrados mágicos válidos de ordem ímpar. O resultado é um quadrado mágico normal contendo os primeiros n² números naturais. Pode haver mais de uma solução válida para o mesmo n.

As regras ficam mais claras através de um pequeno exemplo com a ordem 3, que usa os números de 1 a 9.

Como funciona em um quadrado de 3 por 3

Aplicando o algoritmo Acima, os passos são:

Passo 1) O primeiro número (1) é colocado em (3/2, 3-1) ou (1, 2). Para etapas posteriores, defina x = 1 e y = 2.

Passo 2) As posições dos números restantes são calculadas da seguinte forma.

Posição do número 2:

O próximo número deveria ir para (x-1, y+1) ou (0, 3), que não é uma posição válida. Pela regra (a), a coluna retorna a 0, resultando em (0, 0). Defina x = 0, y = 0.

Posição do número 3:

O número 3 deveria estar em (x-1, y+1) ou (-1, 1), o que não é uma posição válida. Pela regra (a), a linha retorna a n-1 (que é 2). Portanto, o número 3 vai para (2, 1). Defina x = 2, y = 1.

Posição do número 4:

O número 4 deveria estar em (x-1, y+1) ou (1, 2), o que é válido, mas já contém 1. Pela regra (b), a nova posição é (1+1, 2-2) ou (2, 0). Defina x = 2, y = 0.

Posição do número 5:

O número 5 deve estar em (x-1, y+1) ou (1, 1), que é uma posição vazia válida. Defina x = 1, y = 1.

Posição do número 6:

O número 6 deve estar em (x-1, y+1) ou (0, 2), que é uma posição vazia válida. Defina x = 0, y = 2.

Posição do número 7:

O número 7 deveria estar em (x-1, y+1) ou (-1, 3), o que não é válido. Pela regra (c), a nova posição é (0, n-2) ou (0, 1). Defina x = 0, y = 1.

Posição do número 8:

O número 8 deveria estar em (x-1, y+1) ou (-1, 2), o que não é válido. Pela regra (a), a linha retorna a 2, resultando em (2, 2). Defina x = 2, y = 2.

Posição do número 9:

O número 9 deveria estar em (x-1, y+1) ou (1, 3), o que não é válido. Pela regra (a), a coluna volta para 0, resultando em (1, 0).

A cada célula preenchida, a mesma lógica se traduz diretamente em pseudocódigo.

Pseudocódigo para Quadrado Mágico

Begin
    Declare an array of size n*n
    Initialize the array to 0
    Set row = n/2
    Set column = n-1
    For all number i: from 1 to n*n
        If the row = -1 and column = n
            row = 0
            column = n-2
        Else
            If row = -1
                row = n-1
            If column = n
                column = 0
        If the position already contains a number
            decrement column by 2
            increment row by 1
            continue until the position is not 0
        Else
            put the number i into the calculated position
            increment i
        Increment column value
        Decrement row value
End

O pseudocódigo mapeia diretamente para linguagens compiladas e interpretadas, mostradas a seguir em C++ e Python.

C++ Code para o Quadrado Mágico

Entrada:

/*
A C/C++ program for generating odd order magic squares
*/
#include <bits/stdc++.h>
using namespace std;

void GenerateMagicSquare(int n)
{
    int magic[n][n];
    //initializing the array
    for(int i=0; i<n; i++)
        for(int j=0; j<n; j++)
            magic[i][j] = 0;
    //setting row and column value
    int i = n / 2;
    int j = n - 1;
    for (int k = 1; k <= n * n;)
    {
        //checking condition (c)
        if (i == -1 && j == n)
        {
            j = n - 2;
            i = 0;
        }
        else
        {
            //checking condition (a)
            if (j == n)
                j = 0;
            if (i < 0)
                i = n - 1;
        }
        //checking condition (b)
        if (magic[i][j])
        {
            j -= 2;
            i++;
            continue;
        }
        else
        {
            //placing the number into the array
            magic[i][j] = k;
            k++;
        }
        //for the next number setting (i-1, j+1)
        j++;
        i--;
    }
    //printing the matrix
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
            cout << magic[i][j] << "  ";
        cout << endl;
    }
}
int main()
{
    //This code works for only odd numbers
    int n = 7;
    cout<<"The magic sum is " << n*(n*n+1)/2 <<endl;
    GenerateMagicSquare(n);
    return 0;
}

Saída do exemplo:

The magic sum is 175

20  12  4  45  37  29  28
11  3  44  36  35  27  19
2  43  42  34  26  18  10
49  41  33  25  17  9  1
40  32  24  16  8  7  48
31  23  15  14  6  47  39
22  21  13  5  46  38  30

O Python A versão abaixo usa regras idênticas para linhas e colunas.

Python Code para o Quadrado Mágico

def GenerateMagicSquare(n):
    #initializing the array
    magic = [[0 for x in range(n)]
                for y in range(n)]
    #setting row and column value
    i = n // 2
    j = n - 1
    k = 1
    while k <= (n * n):
        #checking condition (c)
        if i == -1 and j == n:
            j = n - 2
            i = 0
        else:
            #checking condition (a)
            if j == n:
                j = 0
            if i < 0:
                i = n - 1
        #checking conditon (b)
        if magic[i][j]:
            j = j - 2
            i = i + 1
            continue
        else:
            #placing the number into the array
            magic[i][j] = k
            k = k + 1
        #for the next number setting (i-1, j+1)
        j = j + 1
        i = i - 1
    #printing the matrix
    for i in range(0, n):
        for j in range(0, n):
            print('%2d ' % (magic[i][j]),end='')
            if j == n - 1:
                print()
#This code works for only odd numbers
n = 7
print("The magic sum is ",n * (n * n + 1) // 2, "\n")
GenerateMagicSquare(n)

Saída do exemplo:

The magic sum is  175

20 12  4 45 37 29 28
11  3 44 36 35 27 19
 2 43 42 34 26 18 10
49 41 33 25 17  9  1
40 32 24 16  8  7 48
31 23 15 14  6 47 39
22 21 13  5 46 38 30

Ambas as implementações se comportam de maneira idêntica, facilitando a comparação de seus custos.

Análise de Complexidade

• Complexidade do espaço: O quadrado mágico é armazenado em uma matriz n por n, portanto a complexidade de espaço é O(n²).
• Complexidade de tempo: O gerador usa dois loops aninhados. O loop externo é executado n vezes e o loop interno também é executado n vezes, portanto a complexidade de tempo geral é O(n²).

Perguntas Frequentes