Magic Square – Resolva quebra-cabeças 3×3 usando C & Python Exemplos
Sarah Chen
O que é o Quadrado Mágico?
Um quadrado mágico é uma matriz quadrada com um arranjo numérico especial. Esses números são organizados de forma que a soma dos números em cada diagonal, linha e coluna permaneça a mesma. Os jogos de quadrados mágicos são quebra-cabeças lógicos simples usados em matemática recreativa.
Exemplo de quadrados mágicos:
O diagrama acima é um exemplo de quadrado mágico de ordem 3. A soma de cada diagonal, linha e coluna é 15.
Como funciona o Quadrado Mágico
Quadrados mágicos são matrizes n*n que consistem em n^2 inteiros positivos. O número de linhas ou colunas de uma matriz quadrada é chamado de ordem da matriz.
Normalmente, os quebra-cabeças de quadrados mágicos têm ordens ímpares e contêm números inteiros de 1 a n ^ 2. A soma de cada diagonal, linha e coluna é a mesma. Este número é chamado de soma mágica ou constante mágica. Geralmente, esta soma mágica depende da ordem da matriz. A fórmula dos quadrados mágicos para a soma mágica de ordem n é-
Vamos dar um exemplo de quadrado mágico com números inteiros 3. Então, a soma mágica seria-
Por que eles são chamados de Magia?
Os matemáticos antigos eram fascinados pela natureza de diversas combinações interessantes de números. O quadrado mágico era um deles. A evidência mais antiga de quadrados mágicos remonta à China em 190 aC.
Alguns estudos mostram evidências do quebra-cabeça dos quadrados mágicos no antigo Japão, Índia e Arábia. Com base em algumas lendas, presumia-se que essas formações especiais de números estavam ligadas ao mundo mágico. Conseqüentemente, esses quadrados foram chamados de quadrados mágicos.
Tipos de Quadrado Mágico
Existem diferentes variantes da matemática dos quadrados mágicos –
- Quadrado Mágico Normal: Este tipo de quadrado mágico contém os primeiros n ^ 2 números.
- Quadrado Semi-Mágico: Neste tipo, apenas as linhas e a coluna somam a constante mágica.
- Quadrado Mágico Simples: Em contraste com o tipo anterior, as linhas, colunas e ambas as diagonais somam a constante mágica.
- Quadrado Mágico Mais Perfeito: Este é um quadrado mágico normal com duas propriedades especiais. Aqui, cada subquadrado 2 por 2 da matriz soma um total de 2 (n ^ 2 + 1). E qualquer par de números que estejam n/2 quadrados separados da grade soma n ^ 2 + 1.
Com base nas propriedades, existem muitos outros tipos de quadrados mágicos. Mas sempre que mencionamos apenas o quadrado mágico, assumimos que é um quadrado mágico normal e simples de ordem ímpar.
Algoritmo para gerar quadrado mágico
O algoritmo para gerar quadrados mágicos de ordem ímpar é:
- O primeiro número ou 1 será armazenado em (n/2, n-1), onde a primeira coordenada é a posição da linha e a segunda coordenada é a posição da coluna. Para etapas posteriores, vamos denotar esta posição como (x, y).
- Os próximos números serão armazenados em (x-1, y+1). Se a posição não for válida, consideraremos as seguintes condições.
- Se a posição da linha for -1, ela será distorcida para n-1. Da mesma forma, se a posição calculada da coluna for n, ela será distorcida para 0.
- A posição da linha será incrementada em 1 e a posição da coluna será diminuída em 2 se a posição calculada já contiver um número.
- Se a posição da linha for -1 e a posição da coluna correspondente for n, a nova posição será (0, n-2.
Nota: Este algoritmo gera apenas quadrados mágicos válidos de ordem ímpar. Também consideramos este quadrado mágico um quadrado mágico normal com os primeiros n ^ 2 números. Além disso, pode haver múltiplas soluções para o mesmo valor de n.
Vamos dar um exemplo e ver como funciona. Digamos que queremos encontrar o quadrado mágico de ordem 3. Como será um quadrado mágico simples e normal de ordem ímpar, conterá todos os números de 1 a 3 ^ 2 ou 9.
Como funciona?
De acordo com o nosso algoritmo, os passos serão os seguintes:
Passo 1) O primeiro número ou 1 estará na posição (3/2, 3-1) ou (1, 2). Por convenção, considere x= 1 e y= 2 para etapas posteriores.
Passo 2) A posição para o restante dos números será calculada da seguinte maneira-
Posição do número 2:
O próximo número estará em (x-1, y+1) ou (0, 3), o que não é uma posição válida. Usando a condição (a), a posição válida correspondente seria (0,0). Então, x = 0, y = 0.
Posição do número 3:
O número 3 estará em (x-1, y+1) ou (-1, 1), o que não é uma posição válida. Usando a condição (a), a posição válida da linha seria n-1 ou 2. Portanto, o número 3 estará em (2, 1). Para o próximo número, x= 2, y= 1.
Posição do número 4:
O número 4 deve estar em (x-1, y+1) ou (1, 2), que é uma posição válida. Mas essa posição já contém um número. De acordo com a condição (b), a posição válida seria (1+1, 2-2) ou (2,0). Para o próximo número 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 válida. Para o próximo número 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 válida. Para o próximo número x= 0, y= 2.
Posição do número 7:
O número 7 deve estar em (x-1, y+1) ou (-1, 3), o que não é uma posição válida. De acordo com a condição (c), a posição válida seria (0, n-2) ou (0, 1). Para o próximo número x= 0, y= 1.
Posição do número 8:
O número 8 deve estar em (x-1, y+1) ou (-1, 2), o que não é uma posição válida. Usando a condição (a), a posição válida seria (2, 2). Para o próximo número x= 2, y= 2.
Posição do número 9:
O número 9 deve estar em (x-1, y+1) ou (1, 3), o que não é uma posição válida. Usando a condição (a), a posição válida seria (1, 0).
Pseudo-código
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
C++ Código 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
Python Código 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
Análise de Complexidade
- Complexidade do espaço: Para manter a matriz quadrada mágica, precisamos de um array*n. Portanto, a complexidade do espaço seria O(n^2).
- Complexidade de tempo: O código que usamos para gerar a matemática dos quadrados mágicos consiste em dois loops. O loop externo é executado n vezes e o loop interno também é executado n vezes. Em última análise, a complexidade do tempo é O (n ^ 2).
