Jak rozwiązać łamigłówkę z magicznym kwadratem 3×3 w języku C i Python

Czym jest kwadrat magiczny?

Magiczny kwadrat to macierz kwadratowa ze specjalnym układem liczb. Wartości są rozmieszczone tak, aby suma w każdym wierszu, każdej kolumnie i obu głównych przekątnych była taka sama. Magiczne kwadraty to proste łamigłówki logiczne stosowane w matematyce rekreacyjnej.

Przykład kwadratów magicznych:

Powyższy diagram przedstawia magiczny kwadrat rzędu 3. Suma każdej przekątnej, każdego wiersza i każdej kolumny jest równa 15. W następnej sekcji wyjaśniono, w jaki sposób powstaje ta stała suma.

Jak działają kwadraty magiczne

Magiczny kwadrat rzędu n to macierz nxn zawierająca n² dodatnich liczb całkowitych. Liczba wierszy lub kolumn nazywana jest rzędem macierzy.

Typowe łamigłówki z magicznymi kwadratami mają nieparzystą kolejność i wykorzystują liczby całkowite od 1 do n². Ponieważ każdy wiersz, kolumna i przekątna muszą sumować się do tej samej wartości, wartość ta nazywana jest sumą magiczną lub stałą magiczną. Stała ta zależy tylko od n. Wzór na sumę magiczną rzędu n to:

Rozważmy kwadrat magiczny rzędu 3. Suma magiczna wynosi zatem:

Wzór ten wyjaśnia arytmetykę, ale łamigłówka ta ma długą historię kulturową, która dała jej niezapomnianą nazwę.

Dlaczego nazywa się je magicznymi?

Starożytni matematycy fascynowali się ciekawymi kombinacjami liczb, a magiczny kwadrat był jednym z nich. Najwcześniejsze dowody na to pochodzą z Chin, około 190 r. p.n.e.

Badania wskazują na istnienie łamigłówek z kwadratami magicznymi w starożytnej Japonii, Indiach i Arabii. Legendy wiązały te układy ze światem magii i nazwa ta przyjęła się. Poza folklorem, matematycy zdefiniowali również kategorie formalne, które odróżniają poszczególne kwadraty.

Rodzaje kwadratu magicznego

W matematyce występują różne odmiany kwadratów magicznych:

• Normalny magiczny kwadrat: Zawiera pierwsze n² liczb naturalnych.
• Kwadrat półmagiczny: Tylko wiersze i kolumny sumują się do magicznej stałej.
• Prosty magiczny kwadrat: Wiersze, kolumny i obie główne przekątne sumują się do stałej magicznej.
• Najdoskonalszy magiczny kwadrat: Zwykły kwadrat magiczny z dwiema dodatkowymi właściwościami. Każdy podkwadrat macierzy 2x2 sumuje się do 2(n²+1), a każda para liczb oddzielona o n/2 komórki sumuje się do n²+1.

Istnieje więcej kategorii opartych na dodatkowych właściwościach. Ilekroć w tym samouczku termin „kwadrat magiczny” jest używany bez zastrzeżeń, odnosi się on do kwadratu magicznego o nieparzystym rzędzie, normalnego i prostego.

Algorytm generowania kwadratu magicznego

Klasyczny algorytm generowania kwadratu magicznego nieparzystego rzędu, zwany metodą syjamską, wygląda następująco:

• Pierwsza liczba (1) jest przechowywana w pozycji (n/2, n-1), gdzie pierwsza współrzędna to indeks wiersza, a druga indeks kolumny. W dalszych krokach nazwij tę pozycję (x, y).
• Następna liczba jest umieszczona w punkcie (x-1, y+1). Jeśli ta pozycja jest nieprawidłowa, zastosuj następujące zasady:
  1. Jeśli indeks wiersza to -1, zaokrąglij go do n-1. Jeśli indeks kolumny to n, zaokrąglij go do 0.
  2. Jeśli obliczona pozycja zawiera już liczbę, zwiększ wiersz o 1 i zmniejsz kolumnę o 2.
  3. Jeżeli wiersz ma wartość -1 i jednocześnie kolumna ma wartość n, to nowa pozycja będzie wynosić (0, n-2).

Uwaga: Ten algorytm generuje tylko poprawne kwadraty magiczne nieparzystego rzędu. Rezultatem jest normalny kwadrat magiczny zawierający pierwsze n² liczb naturalnych. Dla tego samego n może istnieć więcej niż jedno poprawne rozwiązanie.

Zasady staną się jaśniejsze na krótkim przykładzie z rzędem 3, w którym wykorzystano liczby od 1 do 9.

Jak to działa na kwadracie 3 na 3

Stosowanie algorytm powyżej kroki są następujące:

Krok 1) Pierwszą liczbę (1) umieszczamy w (3/2, 3-1) lub (1, 2). W dalszych krokach ustaw x = 1, a y = 2.

Krok 2) Pozycje pozostałych liczb oblicza się w następujący sposób.

Pozycja numeru 2:

Następna liczba powinna znaleźć się w przedziale (x-1, y+1) lub (0, 3), co nie jest prawidłową pozycją. Zgodnie z regułą (a), kolumna zawija się do 0, dając (0, 0). Ustaw x = 0, y = 0.

Pozycja numeru 3:

Liczba 3 powinna znajdować się w (x-1, y+1) lub (-1, 1), co nie jest prawidłową pozycją. Zgodnie z regułą (a), wiersz zawija się do n-1 (czyli 2). Zatem liczba 3 trafia do (2, 1). Ustaw x = 2, y = 1.

Pozycja numeru 4:

Liczba 4 powinna znajdować się w punkcie (x-1, y+1) lub (1, 2), co jest poprawne, ale zawiera już 1. Zgodnie z regułą (b), nowa pozycja to (1+1, 2-2) lub (2, 0). Ustaw x = 2, y = 0.

Pozycja numeru 5:

Liczba 5 powinna znajdować się w (x-1, y+1) lub (1, 1), co jest prawidłową pozycją pustą. Ustaw x = 1, y = 1.

Pozycja numeru 6:

Liczba 6 powinna znajdować się w (x-1, y+1) lub (0, 2), co jest prawidłową pozycją pustą. Ustaw x = 0, y = 2.

Pozycja numeru 7:

Liczba 7 powinna znajdować się w punkcie (x-1, y+1) lub (-1, 3), co jest nieprawidłowe. Zgodnie z regułą (c), nowa pozycja to (0, n-2) lub (0, 1). Ustaw x = 0, y = 1.

Pozycja numeru 8:

Liczba 8 powinna znajdować się w punkcie (x-1, y+1) lub (-1, 2), co jest nieprawidłowe. Zgodnie z regułą (a), wiersz zawija się do 2, dając (2, 2). Ustaw x = 2, y = 2.

Pozycja numeru 9:

Liczba 9 powinna znajdować się w punkcie (x-1, y+1) lub (1, 3), co jest nieprawidłowe. Zgodnie z regułą (a) kolumna zawija się do 0, dając (1, 0).

Przy wypełnianiu każdej komórki ta sama logika jest bezpośrednio tłumaczona na pseudokod.

Pseudokod dla Magicznego Kwadratu

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 jest mapowany bezpośrednio na języki kompilowane i interpretowane, co pokazano poniżej. C++ oraz Python.

C++ Code dla Magicznego Kwadratu

Wejście:

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

Dane wyjściowe przykładu:

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 Wersja poniżej używa identycznych reguł dotyczących wierszy i kolumn.

Python Code dla Magicznego Kwadratu

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)

Dane wyjściowe przykładu:

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

Oba rozwiązania działają identycznie, co ułatwia porównanie ich kosztów.

Analiza złożoności

• Złożoność przestrzeni: Magiczny kwadrat jest przechowywany w tablicy n na n, więc złożoność przestrzenna wynosi O(n²).
• Złożoność czasowa: Generator wykorzystuje dwie zagnieżdżone pętle. Pętla zewnętrzna wykonuje się n razy, a pętla wewnętrzna również n razy, więc całkowita złożoność czasowa wynosi O(n²).

FAQ