Magic Square – Lösen Sie 3×3-Rätsel anhand von C- und Python-Beispielen

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, jeder Zeile und jeder Spalte gleich bleibt. Magisches Quadratares Spiele sind einfache Logikrätsel, die in der Freizeitmathematik verwendet werden.

Magisches Quadratares Beispiel:

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

Magisches Quadratares sind n*n Matrizen, die aus n^2 positiven ganzen Zahlen bestehen. Die Anzahl der Zeilen oder Spalten einer quadratischen Matrix wird als Ordnung der Matrix bezeichnet.

Typischerweise handelt es sich um magische Squirrenares Rätsel haben eine ungerade Reihenfolge und enthalten ganze Zahlen von 1 bis n^2. Die Summe aller Diagonalen, Zeilen und Spalten ist gleich. Diese Zahl wird magische Summe oder magische Konstante genannt. Im Allgemeinen hängt diese magische Summe von der Reihenfolge der Matrix ab. Das magische Quadratares Formel für die magische Summe der Ordnung n ist-

Magic Square funktioniert

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

Magic Square funktioniert

Magic Square funktioniert

Warum heißen sie Magie?

Antike Mathematiker waren von der Natur verschiedener interessanter Zahlenkombinationen fasziniert. Das magische Quadrat war eines davon. Der früheste Beweis für magisches Sqares stammt aus dem Jahr 190 v. Chr. in China.

Einige Studien zeigen Hinweise auf den Magic-Squareares Rätsel im alten Japan, Indien und Arabien. Aufgrund einiger Legenden wurde angenommen, dass diese besonderen Zahlenformationen mit der magischen Welt in Zusammenhang stehen. Daher sind diese Sqares wurden Magic Squa genanntares.

Arten von magischen Quadraten

Es gibt verschiedene Varianten von Magic Squaares 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 summiert sich jedes 2 mal 2 große Unterquadrat der Matrix zu einer Gesamtsumme von 2(n^2+1). Und jedes Zahlenpaar, das n/2 sq istares abgesehen von der Gittersumme zu n^2+1.

Basierend auf den Eigenschaften gibt es viele weitere Arten von Magic Squaares. Aber wenn wir nur das magische Quadrat erwähnen, gehen wir davon aus, 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 Ordnungares ist:

  • Die erste Zahl oder 1 wird unter (n/2, n-1) gespeichert, wobei die erste Koordinate die Zeilenposition und die zweite Koordinate die Spaltenposition ist. Für later Schritte, bezeichnen wir diese Position als (x, y).
  • Die nächsten Zahlen werden unter (x-1, y+1) gespeichert. Wenn die Position nicht gültig ist, prüfen wir Folgendeswing Gesundheitsproblemen.
    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 generiert nur gültige Magic Sqares von ungerader Ordnung. Wir betrachten dieses magische Quadrat auch als ein 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, wie es funktioniert. Nehmen wir an, wir möchten das magische Quadrat der Ordnung 3 finden. Da es sich um ein einfaches und normales magisches Quadrat ungerader Ordnung handelt, enthält es alle Zahlen von 1 bis 3^2 oder 9.

Wie funktioniert es?

Nach unserem Algorithmus, die Schritte werden die folgenden seinwing:

Schritt 1) Die erste Zahl oder 1 steht an der Position (3/2, 3-1) oder (1, 2). Betrachten Sie vereinbarungsgemäß x= 1 und y= 2 für later Schritte.

Algorithmus zur Erzeugung eines magischen Quadrats

Schritt 2) Die Position für die restlichen Zahlen wird im Folgenden berechnetwing Benehmen-

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.

Algorithmus zur Erzeugung eines magischen Quadrats

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.

Algorithmus zur Erzeugung eines magischen Quadrats

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.

Algorithmus zur Erzeugung eines magischen Quadrats

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.

Algorithmus zur Erzeugung eines magischen Quadrats

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.

Algorithmus zur Erzeugung eines magischen Quadrats

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.

Algorithmus zur Erzeugung eines magischen Quadrats

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.

Algorithmus zur Erzeugung eines magischen Quadrats

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).

Algorithmus zur Erzeugung eines magischen Quadrats

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 Magic Square

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

Magisches Quadrat des Python-Codes

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

Mitplexity-Analyse

  • Weltraumkomplexität: Um die magische Quadratmatrix aufrechtzuerhalten, benötigen wir ein*n-Array. Also, die Weltraumkommunikationplexity wäre O(n^2).
  • Time Complexität: Der Code, den wir zum Generieren von Magic Sq verwendet habenares Mathe besteht aus zwei Schleifen. Die äußere Schleife läuft n-mal und die innere Schleife läuft ebenfalls n-mal. Letztendlich ist die Zeit gekommenplexität ist O(n^2).