Magisches Quadrat – Löse 3×3 Puzzle mit C & Python Beispiele

Was ist Magic Square?

Ein magisches Quadrat ist eine quadratische Matrix mit einer speziellen Zahlenanordnung. Diese Zahlen sind so angeordnet, dass die Summe der Zahlen auf jeder Diagonale, Zeile und Spalte gleich bleibt. Magische Quadrate-Spiele sind einfache Logikrätsel, die in der Freizeitmathematik verwendet werden.

Beispiel für magische Quadrate:

$magic Square$

Das obige Diagramm ist ein Beispiel für ein magisches Quadrat der Ordnung 3. Die Summe jeder Diagonale, Zeile und Spalte beträgt 15.

So funktioniert Magic Square

Magische Quadrate sind n*n-Matrizen, die aus n^2 positiven Ganzzahlen bestehen. Die Anzahl der Zeilen oder Spalten einer quadratischen Matrix wird als Ordnung der Matrix bezeichnet.

Normalerweise haben magische Quadraträtsel eine ungerade Reihenfolge und enthalten die ganzen Zahlen von 1 bis n^2. Die Summe jeder Diagonale, Zeile und Spalte ist gleich. Diese Zahl wird als magische Summe oder magische Konstante bezeichnet. Im Allgemeinen hängt diese magische Summe von der Reihenfolge der Matrix ab. Die Formel der magischen Quadrate für die magische Summe der Ordnung n lautet:

Nehmen wir ein Beispiel eines magischen Quadrats mit der ganzen Zahl 3. Die magische Summe wäre also:

Warum heißen sie Magie?

Die Mathematiker der Antike waren von der Natur verschiedener interessanter Zahlenkombinationen fasziniert. Das magische Quadrat war eine davon. Die ersten Belege für magische Quadrate stammen aus China im Jahr 190 v. Chr.

Einige Studien belegen, dass es im alten Japan, Indien und Arabien bereits magische Quadrate gab. Aufgrund einiger Legenden wurde angenommen, dass diese speziellen Zahlenformationen mit der magischen Welt in Verbindung standen. Daher wurden diese Quadrate magische Quadrate genannt.

Arten von magischen Quadraten

Es gibt verschiedene Varianten der magischen Quadrate Mathematik –

Normales magisches Quadrat: Diese Art von magischem Quadrat enthält die ersten n^2 Zahlen.
Halbmagisches Quadrat: Bei diesem Typ ergeben nur die Zeilen und die Spalte in der Summe die magische Konstante.
Einfaches magisches Quadrat: Im Gegensatz zum vorherigen Typ summieren sich die Zeilen, Spalten und beiden Diagonalen zur magischen Konstante.
Perfektestes magisches Quadrat: Dies ist ein normales magisches Quadrat mit zwei besonderen Eigenschaften. Hier ergibt jedes 2x2-Unterquadrat der Matrix zusammen 2(n^2+1). Und jedes Zahlenpaar, das n/2 Quadrate vom Gitter entfernt ist, ergibt zusammen n^2+1.

Basierend auf den Eigenschaften gibt es noch viele weitere Arten von magischen Quadraten. Aber wenn wir nur das magische Quadrat erwähnen, nehmen wir an, dass es sich um ein normales und einfaches magisches Quadrat ungerader Ordnung handelt.

Algorithmus zur Erzeugung eines magischen Quadrats

Der Algorithmus zum Erzeugen von magischen Quadraten ungerader Ordnung lautet:

Die erste Zahl oder 1 wird bei (n/2, n-1) gespeichert, wobei die erste Koordinate die Zeilenposition und die zweite Koordinate die Spaltenposition ist. Für spätere Schritte bezeichnen wir diese Position als (x, y).
Die nächsten Zahlen werden bei (x-1, y+1) gespeichert. Wenn die Position ungültig ist, berücksichtigen wir die folgenden Bedingungen.
1. Wenn die Zeilenposition -1 ist, erfolgt ein Warping zu n-1. Wenn die berechnete Spaltenposition gleich n ist, wird sie ebenfalls auf 0 verzerrt.
2. Die Zeilenposition wird um 1 erhöht und die Spaltenposition um 2 dekrementiert, wenn die berechnete Position bereits eine Zahl enthält.
3. Wenn die Zeilenposition -1 und die entsprechende Spaltenposition n ist, ist die neue Position (0, n-2.

Hinweis: Dieser Algorithmus erzeugt nur gültige magische Quadrate ungerader Ordnung. Wir betrachten dieses magische Quadrat auch als normales magisches Quadrat mit den ersten n^2 Zahlen. Darüber hinaus kann es mehrere Lösungen für denselben Wert von n geben.

Nehmen wir ein Beispiel und sehen wir, wie es funktioniert. Nehmen wir an, wir möchten das magische Quadrat der Ordnung 3 finden. Da es ein einfaches und normales magisches Quadrat der ungeraden Ordnung ist, enthält es alle Zahlen von 1 bis 3^2 oder 9.

Wie funktioniert es?

Nach unserem Algorithmus, die Schritte sind die folgenden:

Schritt 1) Die erste Zahl oder 1 steht an der Position (3/2, 3-1) oder (1, 2). Gemäß Konvention gilt für spätere Schritte x = 1 und y = 2.

Schritt 2) Die Position für die restlichen Zahlen wird folgendermaßen berechnet:

Position von Nummer 2:

Die nächste Zahl befindet sich bei (x-1, y+1) oder (0, 3), was keine gültige Position ist. Unter Verwendung der Bedingung (a) wäre die entsprechende gültige Position (0,0). Also, x= 0, y= 0.

Position von Nummer 3:

Nummer 3 befindet sich bei (x-1, y+1) oder (-1, 1), was keine gültige Position ist. Unter Verwendung der Bedingung (a) wäre die gültige Zeilenposition n-1 oder 2. Nummer 3 wäre also bei (2, 1). Für die nächste Zahl ist x= 2, y= 1.

Position von Nummer 4:

Nummer 4 sollte bei (x-1, y+1) oder (1, 2) sein, was eine gültige Position ist. Aber diese Position enthält bereits eine Nummer. Gemäß Bedingung (b) wäre die gültige Position (1+1, 2-2) oder (2,0). Für die nächste Zahl x= 2, y= 0.

Position von Nummer 5:

Nummer 5 sollte bei (x-1, y+1) oder (1, 1) sein, was eine gültige Position ist. Für die nächste Zahl x= 1, y= 1.

Position von Nummer 6:

Nummer 6 sollte bei (x-1, y+1) oder (0, 2) sein, was eine gültige Position ist. Für die nächste Zahl x= 0, y= 2.

Position von Nummer 7:

Nummer 7 sollte bei (x-1, y+1) oder (-1, 3) sein, was keine gültige Position ist. Gemäß Bedingung (c) wäre die gültige Position (0, n-2) oder (0, 1). Für die nächste Zahl x= 0, y= 1.

Position von Nummer 8:

Nummer 8 sollte bei (x-1, y+1) oder (-1, 2) sein, was keine gültige Position ist. Unter Verwendung der Bedingung (a) wäre die gültige Position (2, 2). Für die nächste Zahl x= 2, y= 2.

Position von Nummer 9:

Nummer 9 sollte bei (x-1, y+1) oder (1, 3) sein, was keine gültige Position ist. Unter Verwendung der Bedingung (a) wäre die gültige Position (1, 0).

Pseudocode

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

C++ Code 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

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