Kako riješiti zagonetku magičnog kvadrata 3×3 u C & Python

Što je čarobni kvadrat?

Magični kvadrat je kvadratna matrica s posebnim rasporedom brojeva. Vrijednosti su postavljene tako da zbroj u svakom retku, svakom stupcu i obje glavne dijagonale ostane isti. Magični kvadrati su jednostavne logičke zagonetke koje se koriste u rekreativnoj matematici.

Primjer magičnih kvadrata:

Gornji dijagram prikazuje magični kvadrat reda 3. Zbroj svake dijagonale, retka i stupca jednak je 15. Sljedeći odjeljak objašnjava kako se dobiva ovaj konstantni zbroj.

Kako funkcioniraju magični kvadrati

Magični kvadrat reda n je matrica dimenzija n x n koja sadrži n² pozitivnih cijelih brojeva. Broj redaka ili stupaca naziva se red matrice.

Tipične zagonetke s magičnim kvadratom imaju neparan redoslijed i koriste cijele brojeve od 1 do n². Budući da svaki redak, stupac i dijagonala moraju dati istu vrijednost, ta se vrijednost naziva magični zbroj ili magična konstanta. Konstanta ovisi samo o n. Formula za magični zbroj reda n je:

Razmotrimo magični kvadrat reda 3. Magični zbroj je tada:

Ova formula objašnjava aritmetiku, ali zagonetka ima dugu kulturnu povijest koja joj daje nezaboravno ime.

Zašto se nazivaju magijom?

Drevni matematičari bili su fascinirani zanimljivim kombinacijama brojeva, a magični kvadrat bio je jedna od njih. Najraniji dokazi datiraju iz Kine oko 190. godine prije Krista.

Studije pokazuju dokaze o magičnim kvadratnim zagonetkama u drevnom Japanu, Indiji i Arabiji. Legende su povezivale ove aranžmane s magičnim svijetom, a ime se zadržalo. Osim folklora, matematičari su također definirali formalne kategorije koje razlikuju jedan kvadrat od drugog.

Vrste magičnog kvadrata

U matematici postoji nekoliko varijanti magičnih kvadrata:

• Normalni magični kvadrat: Sadrži prvih n² prirodnih brojeva.
• Polu-magični kvadrat: Samo retci i stupci zbrajaju se u magičnu konstantu.
• Jednostavan magični kvadrat: Zbroj redaka, stupaca i obje glavne dijagonale daje magičnu konstantu.
• Najsavršeniji magični kvadrat: Normalni magični kvadrat s dva dodatna svojstva. Svaki podkvadrat matrice dimenzija 2 puta 2 daje zbroj od 2(n²+1), a bilo koji par brojeva koji su udaljeni za n/2 polja daje zbroj od n²+1.

Postoje dodatne kategorije na temelju dodatnih svojstava. Kad god se u ovom vodiču koristi izraz "magični kvadrat" bez uvjeta, odnosi se na neparni, normalni, jednostavni magični kvadrat.

Algoritam za generiranje magičnog kvadrata

Klasični algoritam za generiranje magičnog kvadrata neparnog reda, nazvan Sijamska metoda, je sljedeći:

• Prvi broj (1) pohranjen je na poziciji (n/2, n-1), gdje je prva koordinata indeks retka, a druga indeks stupca. Za kasnije korake, ovu poziciju ćemo nazvati (x, y).
• Sljedeći broj se nalazi na (x-1, y+1). Ako ta pozicija nije valjana, primijenite sljedeća pravila:
  1. Ako je indeks retka -1, prelomi ga na n-1. Ako je indeks stupca n, prelomi ga na 0.
  2. Ako izračunata pozicija već sadrži broj, povećajte redak za 1 i smanjite stupac za 2.
  3. Ako je redak -1, a stupac n istovremeno, novi položaj je (0, n-2).

Bilješka: Ovaj algoritam generira samo valjane magične kvadrate neparnog reda. Rezultat je normalni magični kvadrat koji sadrži prvih n² prirodnih brojeva. Za isti n može postojati više valjanih rješenja.

Pravila postaju jasnija kroz mali primjer s redom 3, koji koristi brojeve od 1 do 9.

Kako to funkcionira na kvadratu 3 puta 3

Primjena algoritam gore navedeni koraci su sljedeći:

Korak 1) Prvi broj (1) se postavlja na (3/2, 3-1) ili (1, 2). Za kasnije korake, postavite x = 1 i y = 2.

Korak 2) Položaji preostalih brojeva izračunavaju se na sljedeći način.

Pozicija broja 2:

Sljedeći broj treba ići na (x-1, y+1) ili (0, 3), što nije valjana pozicija. Prema pravilu (a), stupac se prelama na 0, dajući (0, 0). Postavi x = 0, y = 0.

Pozicija broja 3:

Broj 3 treba biti na (x-1, y+1) ili (-1, 1), što nije valjana pozicija. Prema pravilu (a), redak se prelama na n-1 (što je 2). Dakle, broj 3 ide na (2, 1). Postavi x = 2, y = 1.

Pozicija broja 4:

Broj 4 treba biti na (x-1, y+1) ili (1, 2), što je valjano, ali već sadrži 1. Prema pravilu (b), nova pozicija je (1+1, 2-2) ili (2, 0). Postavi x = 2, y = 0.

Pozicija broja 5:

Broj 5 treba biti na (x-1, y+1) ili (1, 1), što je valjana prazna pozicija. Postavi x = 1, y = 1.

Pozicija broja 6:

Broj 6 treba biti na (x-1, y+1) ili (0, 2), što je valjana prazna pozicija. Postavi x = 0, y = 2.

Pozicija broja 7:

Broj 7 trebao bi biti na (x-1, y+1) ili (-1, 3), što nije valjano. Prema pravilu (c), novi položaj je (0, n-2) ili (0, 1). Postavi x = 0, y = 1.

Pozicija broja 8:

Broj 8 trebao bi biti na (x-1, y+1) ili (-1, 2), što nije valjano. Prema pravilu (a), redak se prelama na 2, dajući (2, 2). Postavi x = 2, y = 2.

Pozicija broja 9:

Broj 9 trebao bi biti na (x-1, y+1) ili (1, 3), što nije valjano. Prema pravilu (a), stupac se prelama na 0, dajući (1, 0).

Sa svakom ispunjenom ćelijom, ista logika se izravno prevodi u pseudokod.

Pseudokod za Magični kvadrat

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

Pseudokod se izravno preslikava na kompilirane i interpretirane jezike, što je prikazano u nastavku C++ i Python.

C++ Code za Čarobni trg

Ulazni:

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

Izlaz primjera:

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

The Python Verzija u nastavku koristi identična pravila za retke i stupce.

Python Code za Čarobni trg

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)

Izlaz primjera:

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

Obje implementacije ponašaju se identično, što olakšava usporedbu njihovih troškova.

Analiza složenosti

• Složenost prostora: Magični kvadrat je pohranjen u nizu dimenzija n x n, tako da je prostorna složenost O(n²).
• Složenost vremena: Generator koristi dvije ugniježđene petlje. Vanjska petlja se izvršava n puta, a unutarnja petlja se također izvršava n puta, tako da je ukupna vremenska složenost O(n²).

Pitanja i odgovori