Jak vyřešit magický čtverec 3×3 v jazyce C & Python

Co je to magický čtverec?

Magický čtverec je čtvercová matice se speciálním uspořádáním čísel. Hodnoty jsou umístěny tak, aby součet v každém řádku, každém sloupci a obou hlavních diagonálách zůstal stejný. Magické čtverce jsou jednoduché logické hádanky používané v rekreační matematice.

Příklad magických čtverců:

Výše uvedený diagram znázorňuje magický čtverec řádu 3. Součet všech úhlopříček, řádků a sloupců se rovná 15. Následující část vysvětluje, jak se tento konstantní součet získá.

Jak fungují magické čtverce

Magický čtverec řádu n je matice o rozměrech n krát n obsahující n² kladných celých čísel. Počet řádků nebo sloupců se nazývá řád matice.

Typické magické čtverce mají lichý řád a používají celá čísla od 1 do n². Protože každý řádek, sloupec a diagonála musí dávat stejnou hodnotu, nazývá se tato hodnota magický součet nebo magická konstanta. Konstanta závisí pouze na n. Vzorec pro magický součet řádu n je:

Uvažujme magický čtverec řádu 3. Magický součet je pak:

Tento vzorec vysvětluje aritmetiku, ale hádanka má dlouhou kulturní historii, která jí dala její památné jméno.

Proč se jim říká magie?

Starověcí matematici byli fascinováni zajímavými kombinacemi čísel a magický čtverec byl jednou z nich. Nejstarší důkazy pocházejí z Číny kolem roku 190 př. n. l.

Studie ukazují důkazy o magických čtvercích ve starověkém Japonsku, Indii a Arábii. Legendy spojovaly tato uspořádání s magickým světem a název se uchytil. Kromě folklóru matematici také definovali formální kategorie, které odlišují jeden čtverec od druhého.

Typy magického čtverce

V matematice existuje několik variant magických čtverců:

• Normální magický čtverec: Obsahuje prvních n² přirozených čísel.
• Semi-Magic Square: Magickou konstantu dávají pouze řádky a sloupce.
• Jednoduchý kouzelný čtverec: Řádky, sloupce a obě hlavní diagonály se sčítají do magické konstanty.
• Nejdokonalejší magický čtverec: Normální magický čtverec se dvěma vlastnostmi navíc. Každý dílčí čtverec matice o rozměrech 2 krát 2 se součtem rovná 2(n²+1) a jakákoli dvojice čísel vzdálených od sebe o n/2 políčka se součtem rovná n²+1.

Existují i ​​další kategorie založené na dalších vlastnostech. Kdykoli je v tomto tutoriálu použit termín „magický čtverec“ bez upřesnění, vztahuje se k lichému, normálnímu, jednoduchému magickému čtverci.

Algoritmus pro generování magického čtverce

Klasický algoritmus pro generování magického čtverce lichého řádu, nazývaný siamská metoda, je následující:

• První číslo (1) je uloženo na pozici (n/2, n-1), kde první souřadnice je index řádku a druhá index sloupce. Pro pozdější kroky tuto pozici nazýváme (x, y).
• Další číslo je umístěno na pozici (x-1, y+1). Pokud je tato pozice neplatná, použijte následující pravidla:
  1. Pokud je index řádku -1, zalomí se na n-1. Pokud je index sloupce n, zalomí se na 0.
  2. Pokud vypočítaná pozice již obsahuje číslo, zvětšete řádek o 1 a snižte sloupec o 2.
  3. Pokud je řádek -1 a sloupec zároveň n-tý, nová pozice je (0, n-2).

Poznámka: Tento algoritmus generuje pouze platné magické čtverce lichého řádu. Výsledkem je normální magický čtverec obsahující prvních n² přirozených čísel. Pro stejné n může existovat více než jedno platné řešení.

Pravidla se vyjasní na malém příkladu s řádem 3, který používá čísla 1 až 9.

Jak to funguje na čtverci 3 x 3

Použití algoritmus výše uvedené kroky jsou:

Krok 1) První číslo (1) se umístí na (3/2, 3-1) nebo (1, 2). Pro další kroky nastavte x = 1 a y = 2.

Krok 2) Pozice zbývajících čísel se vypočítají následovně.

Pozice čísla 2:

Další číslo by mělo jít na (x-1, y+1) nebo (0, 3), což není platná pozice. Podle pravidla (a) se sloupec zalomí na 0, čímž dostaneme (0, 0). Nastavíme x = 0, y = 0.

Pozice čísla 3:

Číslo 3 by mělo být na (x-1, y+1) nebo (-1, 1), což není platná pozice. Podle pravidla (a) se řádek zalomí na n-1 (což je 2). Číslo 3 tedy přejde na (2, 1). Nastavme x = 2, y = 1.

Pozice čísla 4:

Číslo 4 by mělo být v bodě (x-1, y+1) nebo (1, 2), což je platné, ale již obsahuje 1. Podle pravidla (b) je nová pozice (1+1, 2-2) nebo (2, 0). Nastavte x = 2, y = 0.

Pozice čísla 5:

Číslo 5 by mělo být na (x-1, y+1) nebo (1, 1), což je platná prázdná pozice. Nastavte x = 1, y = 1.

Pozice čísla 6:

Číslo 6 by mělo být na (x-1, y+1) nebo (0, 2), což je platná prázdná pozice. Nastavte x = 0, y = 2.

Pozice čísla 7:

Číslo 7 by mělo být v bodě (x-1, y+1) nebo (-1, 3), což není platné. Podle pravidla (c) je nová pozice (0, n-2) nebo (0, 1). Nastavte x = 0, y = 1.

Pozice čísla 8:

Číslo 8 by mělo být v bodě (x-1, y+1) nebo (-1, 2), což není platné. Podle pravidla (a) se řádek zalomí do čísla 2, čímž dostaneme (2, 2). Nastavme x = 2, y = 2.

Pozice čísla 9:

Číslo 9 by mělo být v bodě (x-1, y+1) nebo (1, 3), což není platné. Podle pravidla (a) se sloupec zalomí do 0, čímž dostaneme (1, 0).

S každou vyplněnou buňkou se stejná logika přímo překládá do pseudokódu.

Pseudokód pro Magický čtverec

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

Pseudokód se mapuje přímo na kompilované a interpretované jazyky, jak je ukázáno dále v C++ a Python.

C++ Code pro Magické náměstí

Vstup:

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

Výstup příkladu:

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

Jedno Python Níže uvedená verze používá shodná pravidla pro řádky a sloupce.

Python Code pro Magické náměstí

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)

Výstup příkladu:

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

Obě implementace se chovají identicky, což usnadňuje porovnání jejich nákladů.

Analýza složitosti

• Prostorová složitost: Magický čtverec je uložen v poli n krát n, takže prostorová složitost je O(n²).
• Časová složitost: Generátor používá dvě vnořené smyčky. Vnější smyčka se spustí n-krát a vnitřní smyčka se také spustí n-krát, takže celková časová složitost je O(n²).

Nejčastější dotazy