Hvordan løse 3×3 magiske firkanter i C & Python

Hva er et magisk kvadrat?

Et magisk kvadrat er en kvadratmatrise med en spesiell plassering av tall. Verdiene er plassert slik at summen i hver rad, hver kolonne og begge hoveddiagonalene forblir den samme. Magiske kvadrater er enkle logiske oppgaver som brukes i rekreasjonsmatematikk.

Eksempel på magiske firkanter:

Diagrammet ovenfor viser et magisk kvadrat av orden 3. Summen av hver diagonal, rad og kolonne er lik 15. Neste avsnitt forklarer hvordan denne konstante summen produseres.

Hvordan magiske firkanter fungerer

Et magisk kvadrat av orden n er en n ganger n-matrise som inneholder n² positive heltall. Antall rader eller kolonner kalles matrisens orden.

Typiske magiske firkantpuslespill har en odderekkefølge og bruker heltall fra 1 til n². Fordi hver rad, kolonne og diagonal må summere seg til samme verdi, kalles denne verdien den magiske summen eller magiske konstanten. Konstanten avhenger bare av n. Formelen for den magiske summen av orden n er:

Tenk deg et magisk kvadrat av orden 3. Den magiske summen er da:

Denne formelen forklarer regnestykket, men puslespillet har en lang kulturhistorie som gir det sitt minneverdige navn.

Hvorfor kalles de magi?

Gamle matematikere var fascinert av interessante tallkombinasjoner, og det magiske kvadratet var en av dem. De tidligste bevisene stammer fra Kina rundt 190 f.Kr.

Studier viser bevis på magiske firkantgåter i det gamle Japan, India og Arabia. Legender knyttet disse arrangementene til den magiske verden, og navnet ble værende. Utover folklore har matematikere også definert formelle kategorier som skiller en firkant fra en annen.

Typer Magic Square

Det finnes flere varianter av magiske firkanter i matematikk:

• Normal Magic Square: Inneholder de første n² naturlige tallene.
• Semi-Magic Square: Bare radene og kolonnene summerer seg til den magiske konstanten.
• Simple Magic Square: Radene, kolonnene og begge hoveddiagonalene summerer seg til den magiske konstanten.
• Most Perfect Magic Square: Et normalt magisk kvadrat med to ekstra egenskaper. Hvert 2 x 2 underkvadrat i matrisen summerer seg til 2(n²+1), og ethvert tallpar som er n/2 celler fra hverandre summerer seg til n²+1.

Flere kategorier finnes basert på tilleggsegenskaper. Når begrepet «magisk kvadrat» brukes uten forbehold i denne veiledningen, refererer det til et normalt, enkelt magisk kvadrat av odde orden.

Algoritme for å generere et magisk kvadrat

Den klassiske algoritmen for å generere et magisk kvadrat av odde orden, kalt den siamesiske metoden, er som følger:

• Det første tallet (1) lagres i posisjon (n/2, n-1), hvor den første koordinaten er radindeksen og den andre er kolonneindeksen. For senere trinn, kall denne posisjonen (x, y).
• Det neste tallet plasseres ved (x-1, y+1). Hvis den posisjonen er ugyldig, bruk følgende regler:
  1. Hvis radindeksen er -1, brytes den til n-1. Hvis kolonneindeksen er n, brytes den til 0.
  2. Hvis den beregnede posisjonen allerede inneholder et tall, øk raden med 1 og reduser kolonnen med 2.
  3. Hvis raden er -1 og kolonnen er n samtidig, er den nye posisjonen (0, n-2).

OBS: Denne algoritmen genererer bare gyldige magiske kvadrater av oddeorden. Resultatet er et normalt magisk kvadrat som inneholder de første n² naturlige tallene. Det kan være mer enn én gyldig løsning for samme n.

Reglene blir tydeligere gjennom et lite eksempel med rekkefølge 3, som bruker tallene 1 til 9.

Slik fungerer det på en 3 x 3-kvadrat

Bruk av algoritme ovenfor er trinnene:

Trinn 1) Det første tallet (1) plasseres ved (3/2, 3-1) eller (1, 2). For senere trinn, sett x = 1 og y = 2.

Trinn 2) Plasseringen av de resterende tallene beregnes som følger.

Plassering nummer 2:

Det neste tallet skal gå til (x-1, y+1) eller (0, 3), som ikke er en gyldig posisjon. I henhold til regel (a) brytes kolonnen til 0, noe som gir (0, 0). Sett x = 0, y = 0.

Plassering nummer 3:

Tallet 3 skal være på (x-1, y+1) eller (-1, 1), som ikke er en gyldig posisjon. I henhold til regel (a) brytes raden til n-1 (som er 2). Så tallet 3 går til (2, 1). Sett x = 2, y = 1.

Plassering nummer 4:

Tallet 4 skal være ved (x-1, y+1) eller (1, 2), som er gyldig, men allerede inneholder 1. I henhold til regel (b) er den nye posisjonen (1+1, 2-2) eller (2, 0). Sett x = 2, y = 0.

Plassering nummer 5:

Tallet 5 skal være på (x-1, y+1) eller (1, 1), som er en gyldig tom posisjon. Sett x = 1, y = 1.

Plassering nummer 6:

Tallet 6 skal være på (x-1, y+1) eller (0, 2), som er en gyldig tom posisjon. Sett x = 0, y = 2.

Plassering nummer 7:

Tallet 7 skal være ved (x-1, y+1) eller (-1, 3), noe som ikke er gyldig. I henhold til regel (c) er den nye posisjonen (0, n-2) eller (0, 1). Sett x = 0, y = 1.

Plassering nummer 8:

Tallet 8 skal være ved (x-1, y+1) eller (-1, 2), noe som ikke er gyldig. I henhold til regel (a) brytes raden til 2, noe som gir (2, 2). Sett x = 2, y = 2.

Plassering nummer 9:

Tallet 9 skal være ved (x-1, y+1) eller (1, 3), noe som ikke er gyldig. I henhold til regel (a) brytes kolonnen til 0, noe som gir (1, 0).

Når hver celle er fylt, oversettes den samme logikken direkte til pseudokode.

Pseudokode for Magic Square

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

Pseudokoden kartlegges direkte på kompilerte og tolkede språk, vist nedenfor C++ og Python.

C++ Code for Magisk firkant

Inngang:

/*
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;
}

Utgang av eksempel:

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

Ocuco Python Versjonen nedenfor bruker identiske rad- og kolonneregler.

Python Code for Magisk firkant

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)

Utgang av eksempel:

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

Begge implementeringene oppfører seg identisk, noe som gjør det enkelt å sammenligne kostnadene.

Kompleksitetsanalyse

• Romkompleksitet: Det magiske kvadratet lagres i en n ganger n-matrise, så romkompleksiteten er O(n²).
• Tidskompleksitet: Generatoren bruker to nestede løkker. Den ytre løkken går n ganger, og den indre løkken går også n ganger, så den totale tidskompleksiteten er O(n²).

Spørsmål og svar