Magic Square – Risolvi il puzzle 3×3 usando C & Python Esempi
Sara Chen
Cos'è il quadrato magico?
Un quadrato magico è una matrice quadrata con una disposizione speciale dei numeri. Questi numeri sono disposti in modo che la somma dei numeri su ogni diagonale, riga e colonna rimanga la stessa. I giochi di quadrati magici sono semplici puzzle logici utilizzati nella matematica ricreativa.
Esempio di quadrati magici:
Il diagramma sopra riportato è un esempio di un quadrato magico di ordine 3. La somma di ciascuna diagonale, riga e colonna è 15.
Come funziona il Quadrato Magico
I quadrati magici sono matrici n*n composte da n^2 numeri interi positivi. Il numero di righe o colonne di una matrice quadrata è chiamato ordine della matrice.
In genere, i puzzle dei quadrati magici hanno ordini dispari e contengono gli interi da 1 a n^2. La somma di ogni diagonale, riga e colonna è la stessa. Questo numero è chiamato somma magica o costante magica. In genere, questa somma magica dipende dall'ordine della matrice. La formula dei quadrati magici per la somma magica di ordine n è-
Prendiamo l'esempio di un quadrato magico con numeri interi 3. Quindi, la somma magica sarebbe:
Perché si chiamano Magic?
Gli antichi matematici erano affascinati dalla natura di diverse interessanti combinazioni di numeri. Il quadrato magico era una di queste. La prima testimonianza di quadrati magici risale alla Cina nel 190 a.C.
Alcuni studi mostrano prove del puzzle dei quadrati magici nell'antico Giappone, India e Arabia. Sulla base di alcune leggende, si presumeva che quelle speciali formazioni di numeri fossero collegate al mondo magico. Quindi, quei quadrati furono chiamati quadrati magici.
Tipi di quadrato magico
Esistono diverse varianti della matematica dei quadrati magici:
- Quadrato magico normale: Questo tipo di quadrato magico contiene i primi n^2 numeri.
- Quadrato semi-magico: In questo tipo, solo le righe e la colonna si sommano alla costante magica.
- Quadrato magico semplice: A differenza del tipo precedente, le righe, le colonne ed entrambe le diagonali si sommano alla costante magica.
- Il quadrato magico più perfetto: Questo è un normale quadrato magico con due proprietà speciali. Qui, ogni sottoquadrato 2 per 2 della matrice si somma a un totale di 2(n^2+1). E qualsiasi coppia di numeri che si trovi a n/2 quadrati di distanza dalla griglia somma a n^2+1.
In base alle proprietà, ci sono molti altri tipi di quadrati magici. Ma ogni volta che menzioniamo semplicemente il quadrato magico, diamo per scontato che sia un quadrato magico normale e semplice di ordine dispari.
Algoritmo per generare il quadrato magico
L'algoritmo per generare quadrati magici di ordine dispari è:
- Il primo numero o 1 verrà memorizzato in (n/2, n-1), dove la prima coordinata è la posizione della riga e la seconda coordinata è la posizione della colonna. Per i passaggi successivi, denotiamo questa posizione come (x, y).
- I numeri successivi saranno memorizzati in (x-1, y+1). Se la posizione non è valida, allora considereremo le seguenti condizioni.
- Se la posizione della riga è -1, si deformerà a n-1. Allo stesso modo, se la posizione della colonna calcolata è n, verrà deformata a 0.
- La posizione della riga verrà incrementata di 1 e la posizione della colonna verrà diminuita di 2 se la posizione calcolata contiene già un numero.
- Se la posizione della riga è -1 e la posizione della colonna corrispondente è n, la nuova posizione sarà (0, n-2.
Nota: Questo algoritmo genera solo quadrati magici validi di ordine dispari. Consideriamo anche questo quadrato magico un quadrato magico normale con i primi n^2 numeri. Inoltre, possono esserci più soluzioni per lo stesso valore di n.
Facciamo un esempio e vediamo come funziona. Diciamo che vogliamo trovare il quadrato magico di ordine 3. Poiché sarà un semplice e normale quadrato magico di ordine dispari, conterrà tutti i numeri da 1 a 3^2 o 9.
Come funziona?
Secondo le nostre algoritmo, i passaggi saranno i seguenti:
Passo 1) Il primo numero o 1 sarà nella posizione (3/2, 3-1) o (1, 2). Per convenzione, considera x= 1 e y= 2 per i passaggi successivi.
Passo 2) La posizione per il resto dei numeri verrà calcolata nel modo seguente:
Posizione del numero 2:
Il numero successivo sarà in (x-1, y+1) o (0, 3), che non è una posizione valida. Utilizzando la condizione (a), la posizione valida corrispondente sarebbe (0,0). Quindi x= 0, y= 0.
Posizione del numero 3:
Il numero 3 sarà in (x-1, y+1) o (-1, 1), che non è una posizione valida. Utilizzando la condizione (a), la posizione della riga valida sarebbe n-1 o 2. Quindi, il numero 3 sarà in (2, 1). Per il numero successivo, x= 2, y= 1.
Posizione del numero 4:
Il numero 4 dovrebbe essere in (x-1, y+1) o (1, 2) che è una posizione valida. Ma quella posizione contiene già un numero. Secondo la condizione (b), la posizione valida sarebbe (1+1, 2-2) o (2,0). Per il numero successivo x= 2, y= 0.
Posizione del numero 5:
Il numero 5 dovrebbe essere in (x-1, y+1) o (1, 1) che è una posizione valida. Per il numero successivo x= 1, y= 1.
Posizione del numero 6:
Il numero 6 dovrebbe essere in (x-1, y+1) o (0, 2) che è una posizione valida. Per il numero successivo x= 0, y= 2.
Posizione del numero 7:
Il numero 7 dovrebbe essere in (x-1, y+1) o (-1, 3) che non è una posizione valida. Secondo la condizione (c), la posizione valida sarebbe (0, n-2) o (0, 1). Per il numero successivo x= 0, y= 1.
Posizione del numero 8:
Il numero 8 dovrebbe essere in (x-1, y+1) o (-1, 2) che non è una posizione valida. Utilizzando la condizione (a), la posizione valida sarebbe (2, 2). Per il numero successivo x= 2, y= 2.
Posizione del numero 9:
Il numero 9 dovrebbe essere in (x-1, y+1) o (1, 3) che non è una posizione valida. Utilizzando la condizione (a), la posizione valida sarebbe (1, 0).
Pseudo-codice
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++ Codice Quadrato Magico
Ingresso:
/*
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;
}
Output dell'esempio:
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 Codice Quadrato Magico
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)
Output dell'esempio:
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
Analisi della complessità
- Complessità spaziale: Per mantenere la matrice del quadrato magico, abbiamo bisogno di un array an*n. Quindi, la complessità dello spazio sarebbe O(n^2).
- Complessità temporale: Il codice che abbiamo usato per generare la matematica dei quadrati magici è costituito da due cicli. Il ciclo esterno viene eseguito per n volte, e anche quello interno viene eseguito per n volte. In definitiva, la complessità temporale è O(n^2).
