Come risolvere il puzzle del quadrato magico 3×3 in C & Python

Cos'è un quadrato magico?

Un quadrato magico è una matrice quadrata con una particolare disposizione dei numeri. I valori sono posizionati in modo tale che la somma in ogni riga, in ogni colonna e in entrambe le diagonali principali rimanga invariata. I quadrati magici sono semplici rompicapo logici utilizzati nella matematica ricreativa.

Esempio di quadrati magici:

Il diagramma qui sopra mostra un quadrato magico di ordine 3. La somma di ogni diagonale, riga e colonna è pari a 15. La sezione successiva spiega come si ottiene questo totale costante.

Come funzionano i quadrati magici

Un quadrato magico di ordine n è una matrice n x n contenente n² numeri interi positivi. Il numero di righe o colonne è chiamato ordine della matrice.

I tipici puzzle del quadrato magico hanno un ordine dispari e utilizzano i numeri interi da 1 a n². Poiché la somma di ogni riga, colonna e diagonale deve essere uguale, tale valore viene chiamato somma magica o costante magica. La costante dipende solo da n. La formula per la somma magica di ordine n è:

Consideriamo un quadrato magico di ordine 3. La somma magica è quindi:

Questa formula spiega il calcolo aritmetico, ma l'enigma ha una lunga storia culturale che gli conferisce il suo nome memorabile.

Perché vengono chiamati magici?

Gli antichi matematici erano affascinati dalle combinazioni interessanti di numeri, e il quadrato magico era una di queste. Le prime testimonianze risalgono alla Cina intorno al 190 a.C.

Gli studi dimostrano l'esistenza di puzzle a forma di quadrato magico nell'antico Giappone, in India e in Arabia. Le leggende collegavano queste configurazioni al mondo magico, e il nome è rimasto. Oltre al folklore, anche i matematici hanno definito categorie formali che distinguono un quadrato dall'altro.

Tipi di quadrato magico

In matematica esistono diverse varianti dei quadrati magici:

• Quadrato magico normale: Contiene i primi n² numeri naturali.
• Quadrato semi-magico: Solo la somma delle righe e delle colonne corrisponde alla costante magica.
• Quadrato magico semplice: La somma di righe, colonne ed entrambe le diagonali principali corrisponde alla costante magica.
• Il quadrato magico più perfetto: Un normale quadrato magico con due proprietà aggiuntive. Ogni sotto-quadrato 2x2 della matrice somma a 2(n²+1), e qualsiasi coppia di numeri distanti n/2 celle somma a n²+1.

Esistono ulteriori categorie basate su proprietà aggiuntive. Ogni qualvolta in questo tutorial si usa il termine "quadrato magico" senza specificazioni, ci si riferisce a un quadrato magico semplice, normale e di ordine dispari.

Algoritmo per generare un quadrato magico

L'algoritmo classico per generare un quadrato magico di ordine dispari, chiamato metodo siamese, è il seguente:

• Il primo numero (1) è memorizzato nella posizione (n/2, n-1), dove la prima coordinata è l'indice di riga e la seconda è l'indice di colonna. Per i passaggi successivi, chiameremo questa posizione (x, y).
• Il numero successivo viene posizionato in (x-1, y+1). Se tale posizione non è valida, applicare le seguenti regole:
  1. Se l'indice di riga è -1, il valore va a capo a n-1. Se l'indice di colonna è n, il valore va a capo a 0.
  2. Se la posizione calcolata contiene già un numero, incrementa la riga di 1 e decrementa la colonna di 2.
  3. Se la riga è -1 e la colonna è n allo stesso tempo, la nuova posizione è (0, n-2).

Nota: Questo algoritmo genera solo quadrati magici validi di ordine dispari. Il risultato è un normale quadrato magico contenente i primi n² numeri naturali. Per lo stesso n possono esserci più soluzioni valide.

Le regole diventano più chiare attraverso un piccolo esempio con l'ordine 3, che utilizza i numeri da 1 a 9.

Come funziona su un quadrato 3x3

Applicare il algoritmo Sopra, i passaggi sono:

Passo 1) Il primo numero (1) è posizionato in (3/2, 3-1) o (1, 2). Per i passaggi successivi, poniamo x = 1 e y = 2.

Passo 2) Le posizioni dei numeri rimanenti vengono calcolate come segue.

Posizione del numero 2:

Il numero successivo dovrebbe andare a (x-1, y+1) o (0, 3), che non è una posizione valida. Per la regola (a), la colonna va a capo a 0, dando (0, 0). Imposta x = 0, y = 0.

Posizione del numero 3:

Il numero 3 dovrebbe trovarsi in (x-1, y+1) o (-1, 1), che non è una posizione valida. Per la regola (a), la riga si avvolge fino a n-1 (che è 2). Quindi il numero 3 va in (2, 1). Impostiamo x = 2, y = 1.

Posizione del numero 4:

Il numero 4 dovrebbe trovarsi in (x-1, y+1) o (1, 2), che è valido ma contiene già 1. Per la regola (b), la nuova posizione è (1+1, 2-2) o (2, 0). Impostiamo x = 2, y = 0.

Posizione del numero 5:

Il numero 5 dovrebbe trovarsi in (x-1, y+1) o (1, 1), che è una posizione vuota valida. Imposta x = 1, y = 1.

Posizione del numero 6:

Il numero 6 dovrebbe trovarsi in (x-1, y+1) o (0, 2), che è una posizione vuota valida. Imposta x = 0, y = 2.

Posizione del numero 7:

Il numero 7 dovrebbe trovarsi in (x-1, y+1) o (-1, 3), il che non è valido. Per la regola (c), la nuova posizione è (0, n-2) o (0, 1). Imposta x = 0, y = 1.

Posizione del numero 8:

Il numero 8 dovrebbe trovarsi in (x-1, y+1) o (-1, 2), il che non è valido. Per la regola (a), la riga va a capo a 2, dando (2, 2). Impostiamo x = 2, y = 2.

Posizione del numero 9:

Il numero 9 dovrebbe trovarsi in (x-1, y+1) o (1, 3), il che non è valido. Per la regola (a), la colonna si chiude a 0, dando (1, 0).

Man mano che ogni cella viene riempita, la stessa logica si traduce direttamente in pseudocodice.

Pseudonimo per Quadrato Magico

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

Lo pseudocodice mappa direttamente sui linguaggi compilati e interpretati, mostrato di seguito in C++ and Python.

C++ Code per il 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

Migliori Python La versione seguente utilizza le stesse regole per righe e colonne.

Python Code per il 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

Entrambe le implementazioni si comportano in modo identico, il che semplifica il confronto dei costi.

Analisi della complessità

• Complessità spaziale: Il quadrato magico è memorizzato in una matrice n x n, quindi la complessità spaziale è O(n²).
• Complessità temporale: Il generatore utilizza due cicli annidati. Il ciclo esterno viene eseguito n volte e anche il ciclo interno viene eseguito n volte, quindi la complessità temporale complessiva è O(n²).

DOMANDE FREQUENTI