Sådan løser du 3×3 magiske firkanter i C & Python

Hvad er en magisk firkant?

Et magisk kvadrat er en kvadratmatrix med en særlig opstilling af tal. Værdierne er placeret således, at summen i hver række, hver kolonne og begge hoveddiagonaler forbliver den samme. Magiske kvadrater er simple logiske gåder, der bruges i rekreativ matematik.

Eksempel på magiske firkanter:

Diagrammet ovenfor viser et magisk kvadrat af orden 3. Summen af ​​hver diagonal, række og kolonne er lig med 15. I næste afsnit forklares, hvordan denne konstante total frembringes.

Hvordan magiske firkanter fungerer

Et magisk kvadrat af orden n er en n gange n matrix, der indeholder n² positive heltal. Antallet af rækker eller kolonner kaldes matrixens orden.

Typiske magiske kvadratgåder har en ulige rækkefølge og bruger heltal fra 1 til n². Fordi hver række, kolonne og diagonal skal summere til den samme værdi, kaldes denne værdi den magiske sum eller magiske konstant. Konstanten afhænger kun af n. Formlen for den magiske sum af orden n er:

Betragt et magisk kvadrat af orden 3. Den magiske sum er da:

Denne formel forklarer regnestykket, men puslespillet har en lang kulturhistorie, der giver det sit mindeværdige navn.

Hvorfor kaldes de magi?

Gamle matematikere var fascinerede af interessante talkombinationer, og det magiske kvadrat var en af ​​dem. De tidligste beviser stammer fra Kina omkring 190 f.Kr.

Studier viser tegn på magiske firkantgåder i det gamle Japan, Indien og Arabien. Legender forbandt disse arrangementer med den magiske verden, og navnet stod fast. Ud over folklore har matematikere også defineret formelle kategorier, der adskiller et firkant fra et andet.

Typer af Magic Square

Der findes flere varianter af magiske firkanter i matematik:

• Normal Magic Square: Indeholder de første n² naturlige tal.
• Semi-Magic Square: Kun rækkerne og kolonnerne summerer sig til den magiske konstant.
• Simple Magic Square: Rækkerne, kolonnerne og begge hoveddiagonaler lægges sammen til den magiske konstant.
• Mest perfekte magiske kvadrat: Et normalt magisk kvadrat med to ekstra egenskaber. Hvert 2 gange 2 underkvadrat i matricen summerer sig til 2(n²+1), og ethvert par af tal, der er n/2 celler fra hinanden, summerer sig til n²+1.

Der findes flere kategorier baseret på yderligere egenskaber. Når udtrykket "magisk kvadrat" bruges uden forbehold i denne vejledning, refererer det til et ulige, normalt, simpelt magisk kvadrat.

Algoritme til at generere et magisk kvadrat

Den klassiske algoritme til at generere et magisk kvadrat af ulige orden, kaldet den siamesiske metode, er som følger:

• Det første tal (1) gemmes på position (n/2, n-1), hvor den første koordinat er rækkeindekset og den anden er kolonneindekset. For senere trin, kald denne position (x, y).
• Det næste tal placeres ved (x-1, y+1). Hvis denne position er ugyldig, skal følgende regler anvendes:
  1. Hvis rækkeindekset er -1, ombrydes det til n-1. Hvis kolonneindekset er n, ombrydes det til 0.
  2. Hvis den beregnede position allerede indeholder et tal, skal du øge rækken med 1 og formindske kolonnen med 2.
  3. Hvis rækken er -1 og kolonnen samtidig er n, er den nye position (0, n-2).

Bemærk: Denne algoritme genererer kun gyldige magiske kvadrater af ulige orden. Resultatet er et normalt magisk kvadrat, der indeholder de første n² naturlige tal. Der kan være mere end én gyldig løsning for det samme n.

Reglerne bliver tydeligere gennem et lille eksempel med rækkefølge 3, som bruger tallene 1 til 9.

Sådan fungerer det på en 3 x 3 firkant

Anvendelse af algoritme ovenfor er trinnene:

Trin 1) Det første tal (1) placeres ved (3/2, 3-1) eller (1, 2). For senere trin, sæt x = 1 og y = 2.

Trin 2) Positionerne for de resterende tal beregnes som følger.

Position nummer 2:

Det næste tal skal gå til (x-1, y+1) eller (0, 3), hvilket ikke er en gyldig position. Ved at følge regel (a) ombrydes kolonnen til 0, hvilket giver (0, 0). Sæt x = 0, y = 0.

Position nummer 3:

Tallet 3 skal være ved (x-1, y+1) eller (-1, 1), hvilket ikke er en gyldig position. Ved at følge regel (a) ombrydes rækken til n-1 (som er 2). Så tallet 3 går til (2, 1). Sæt x = 2, y = 1.

Position nummer 4:

Tallet 4 skal være ved (x-1, y+1) eller (1, 2), hvilket er gyldigt, men allerede indeholder 1. Ifølge regel (b) er den nye position (1+1, 2-2) eller (2, 0). Sæt x = 2, y = 0.

Position nummer 5:

Tallet 5 skal være ved (x-1, y+1) eller (1, 1), hvilket er en gyldig tom position. Sæt x = 1, y = 1.

Position nummer 6:

Tallet 6 skal være ved (x-1, y+1) eller (0, 2), hvilket er en gyldig tom position. Sæt x = 0, y = 2.

Position nummer 7:

Tallet 7 skal være ved (x-1, y+1) eller (-1, 3), hvilket ikke er gyldigt. Ifølge regel (c) er den nye position (0, n-2) eller (0, 1). Sæt x = 0, y = 1.

Position nummer 8:

Tallet 8 skal være ved (x-1, y+1) eller (-1, 2), hvilket ikke er gyldigt. Ved at følge regel (a) ombrydes rækken til 2, hvilket giver (2, 2). Sæt x = 2, y = 2.

Position nummer 9:

Tallet 9 skal være ved (x-1, y+1) eller (1, 3), hvilket ikke er gyldigt. Ved regel (a) ombrydes kolonnen til 0, hvilket giver (1, 0).

Når hver celle er udfyldt, oversættes den samme logik direkte til pseudokode.

Pseudokode til 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 knyttes direkte til kompilerede og fortolkede sprog, vist nedenfor C++ og Python.

C++ Code til Magisk Firkant

Input:

/*
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 af 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

Python Versionen nedenfor bruger identiske række- og kolonneregler.

Python Code til 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)

Output af 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 implementeringer opfører sig identisk, hvilket gør det nemt at sammenligne deres omkostninger.

Kompleksitetsanalyse

• Rumkompleksitet: Det magiske kvadrat er gemt i et n gange n array, så rumkompleksiteten er O(n²).
• Tidskompleksitet: Generatoren bruger to indbyggede løkker. Den ydre løkke kører n gange, og den indre løkke kører også n gange, så den samlede tidskompleksitet er O(n²).

Ofte Stillede Spørgsmål