Wie man das 3×3 magische Quadrat-Rätsel in C löst & Python

Was ist ein magisches Quadrat?

Ein magisches Quadrat ist eine quadratische Matrix mit einer speziellen Anordnung der Zahlen. Die Werte sind so angeordnet, dass die Summe in jeder Zeile, jeder Spalte und auf beiden Hauptdiagonalen immer gleich ist. Magische Quadrate sind einfache Logikrätsel, die in der Unterhaltungsmathematik verwendet werden.

Beispiel für magische Quadrate:

Das obige Diagramm zeigt ein magisches Quadrat der Ordnung 3. Die Summe jeder Diagonale, Zeile und Spalte beträgt 15. Im nächsten Abschnitt wird erklärt, wie diese konstante Summe zustande kommt.

Wie magische Quadrate funktionieren

Ein magisches Quadrat der Ordnung n ist eine n×n-Matrix, die n² positive ganze Zahlen enthält. Die Anzahl der Zeilen oder Spalten wird als Ordnung der Matrix bezeichnet.

Typische magische Quadrate haben eine ungerade Ordnung und verwenden die ganzen Zahlen von 1 bis n². Da die Summe jeder Zeile, Spalte und Diagonale immer gleich sein muss, wird dieser Wert als magische Summe oder magische Konstante bezeichnet. Die Konstante hängt nur von n ab. Die Formel für die magische Summe der Ordnung n lautet:

Betrachten wir ein magisches Quadrat der Ordnung 3. Die magische Summe lautet dann:

Diese Formel erklärt die Rechenaufgabe, aber das Rätsel hat eine lange Kulturgeschichte, die ihm seinen einprägsamen Namen gibt.

Warum werden sie Magie genannt?

Antike Mathematiker waren fasziniert von interessanten Zahlenkombinationen, und das magische Quadrat war eine davon. Die frühesten Belege stammen aus China um 190 v. Chr.

Studien belegen die Existenz magischer Quadrate im alten Japan, Indien und Arabien. Legenden verbanden diese Anordnungen mit der magischen Welt, und der Name blieb erhalten. Neben der Folklore haben Mathematiker auch formale Kategorien definiert, die die einzelnen Quadrate voneinander unterscheiden.

Arten von magischen Quadraten

In der Mathematik gibt es verschiedene Varianten von magischen Quadraten:

• Normales magisches Quadrat: Enthält die ersten n² natürlichen Zahlen.
• Halbmagisches Quadrat: Nur die Zeilen und Spalten ergeben zusammen die magische Konstante.
• Einfaches magisches Quadrat: Die Zeilen, Spalten und beide Hauptdiagonalen ergeben zusammen die magische Konstante.
• Perfektestes magisches Quadrat: Ein normales magisches Quadrat mit zwei zusätzlichen Eigenschaften. Jedes 2x2-Teilquadrat der Matrix ergibt in der Summe 2(n²+1), und jedes Zahlenpaar, das n/2 Zellen voneinander entfernt ist, ergibt in der Summe n²+1.

Es gibt weitere Kategorien, die auf zusätzlichen Eigenschaften basieren. Wenn in diesem Tutorial der Begriff „magisches Quadrat“ ohne weitere Erläuterung verwendet wird, bezieht er sich auf ein normales, einfaches magisches Quadrat ungerader Ordnung.

Algorithmus zur Erzeugung eines magischen Quadrats

Der klassische Algorithmus zur Erzeugung eines magischen Quadrats ungerader Ordnung, die sogenannte Siamese-Methode, lautet wie folgt:

• Die erste Zahl (1) wird an Position (n/2, n-1) gespeichert, wobei die erste Koordinate den Zeilenindex und die zweite den Spaltenindex angibt. Im Folgenden bezeichnen wir diese Position als (x, y).
• Die nächste Zahl wird an Position (x-1, y+1) platziert. Ist diese Position ungültig, gelten folgende Regeln:
  1. Ist der Zeilenindex -1, wird er auf n-1 erhöht. Ist der Spaltenindex n, wird er auf 0 erhöht.
  2. Falls die berechnete Position bereits eine Zahl enthält, wird die Zeile um 1 erhöht und die Spalte um 2 verringert.
  3. Wenn die Zeile -1 und die Spalte gleichzeitig n ist, ist die neue Position (0, n-2).

Hinweis: Dieser Algorithmus erzeugt nur gültige magische Quadrate ungerader Ordnung. Das Ergebnis ist ein normales magisches Quadrat, das die ersten n² natürlichen Zahlen enthält. Für dasselbe n können mehrere gültige Lösungen existieren.

Die Regeln werden durch ein kleines Beispiel mit der Ordnung 3, bei dem die Zahlen 1 bis 9 verwendet werden, deutlicher.

So funktioniert es auf einem 3x3-Quadrat

Anwendung der Algorithmus Die oben genannten Schritte sind:

Schritt 1) Die erste Zahl (1) wird an der Position (3/2, 3-1) oder (1, 2) platziert. Für die folgenden Schritte setze x = 1 und y = 2.

Schritt 2) Die Positionen der übrigen Zahlen werden wie folgt berechnet.

Position von Nummer 2:

Die nächste Zahl müsste an die Position (x-1, y+1) oder (0, 3) gesetzt werden, was jedoch keine gültige Position ist. Gemäß Regel (a) wird die Spalte zu 0 umgebrochen, wodurch sich (0, 0) ergibt. Setze x = 0 und y = 0.

Position von Nummer 3:

Nummer 3 müsste an Position (x-1, y+1) oder (-1, 1) stehen, was aber keine gültige Position ist. Nach Regel (a) springt die Zeile zu n-1 (also 2). Daher landet Nummer 3 an Position (2, 1). Setze x = 2 und y = 1.

Position von Nummer 4:

Die Zahl 4 sollte an der Position (x-1, y+1) oder (1, 2) stehen, was zwar gültig ist, aber bereits die 1 enthält. Nach Regel (b) ist die neue Position (1+1, 2-2) oder (2, 0). Setze x = 2 und y = 0.

Position von Nummer 5:

Die Zahl 5 sollte an der Position (x-1, y+1) oder (1, 1) stehen, da es sich um eine gültige, leere Position handelt. Setze x = 1 und y = 1.

Position von Nummer 6:

Die Zahl 6 sollte an der Position (x-1, y+1) oder (0, 2) stehen, da es sich um eine gültige, leere Position handelt. Setze x = 0 und y = 2.

Position von Nummer 7:

Die Zahl 7 müsste an der Position (x-1, y+1) oder (-1, 3) stehen, was nicht zulässig ist. Gemäß Regel (c) ist die neue Position (0, n-2) oder (0, 1). Setze x = 0 und y = 1.

Position von Nummer 8:

Die Zahl 8 müsste bei (x-1, y+1) oder (-1, 2) liegen, was nicht zulässig ist. Nach Regel (a) wird die Zeile zu 2 umgebrochen, was (2, 2) ergibt. Setze x = 2 und y = 2.

Position von Nummer 9:

Die Zahl 9 müsste bei (x-1, y+1) oder (1, 3) liegen, was ungültig ist. Gemäß Regel (a) wird die Spalte auf 0 umgebrochen, was (1, 0) ergibt.

Wenn alle Zellen ausgefüllt sind, lässt sich dieselbe Logik direkt in Pseudocode übersetzen.

Pseudocode für ein magisches Quadrat

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

Der Pseudocode lässt sich direkt auf kompilierte und interpretierte Sprachen übertragen, die im Folgenden dargestellt werden. C++ und Python.

C++ Code für magisches Quadrat

Eingang:

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

Ausgabe des Beispiels:

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

Das Python Die untenstehende Version verwendet identische Zeilen- und Spaltenregeln.

Python Code für magisches Quadrat

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)

Ausgabe des Beispiels:

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

Beide Implementierungen verhalten sich identisch, sodass sich ihre Kosten leicht vergleichen lassen.

Komplexitätsanalyse

• Raumkomplexität: Das magische Quadrat wird in einem n mal n-Array gespeichert, daher beträgt die Speicherkomplexität O(n²).
• Zeitliche Komplexität: Der Generator verwendet zwei verschachtelte Schleifen. Die äußere Schleife wird n-mal durchlaufen, und die innere Schleife wird ebenfalls n-mal durchlaufen, sodass die Gesamtzeitkomplexität O(n²) beträgt.

Häufig gestellte Fragen