Magic Square – Lös 3×3 pussel med C & Python Exempel

Vad är Magic Square?

En magisk ruta är en kvadratisk matris med ett speciellt talarrangemang. Dessa siffror är ordnade så att summan av talen på varje diagonal, rad och kolumn förblir densamma. Magiska rutor-spel är enkla logiska pussel som används i rekreationsmatematik.

Exempel på magiska rutor:

Ovanstående diagram är ett exempel på en magisk kvadrat av ordning 3. Summan av varje diagonal, rad och kolumn är 15.

Hur Magic Square fungerar

Magiska kvadrater är n*n matriser som består av n^2 positiva heltal. Antalet rader eller kolumner i en kvadratisk matris kallas matrisens ordning.

Vanligtvis har magiska rutor pussel udda ordningsföljder och bär heltal från 1 till n^2. Summan av varje diagonal, rad och kolumn är densamma. Detta tal kallas magisk summa eller magisk konstant. I allmänhet beror denna magiska summa på matrisens ordning. Den magiska kvadratformeln för den magiska summan av ordningen n är-

Låt oss ta ett exempel på en magisk kvadrat med heltal 3. Så den magiska summan skulle vara-

Varför heter de magi?

Forntida matematiker var fascinerade av naturen hos flera intressanta kombinationer av siffror. Den magiska fyrkanten var en av dem. De tidigaste bevisen på magiska rutor går tillbaka till Kina 190 fvt.

Vissa studier visar bevis på pusslet Magic squares i det antika Japan, Indien och Arabien. Baserat på några legender antogs det att dessa speciella formationer av siffror var kopplade till den magiska världen. Därför fick dessa rutor namnet magiska rutor.

Typer av Magic Square

Det finns olika varianter av magiska kvadraters matematik –

Normal Magic Square: Denna typ av magisk kvadrat innehåller de första n^2 talen.
Semi-Magic Square: I denna typ summerar endast raderna och kolumnen den magiska konstanten.
Simple Magic Square: I motsats till den föregående typen summerar raderna, kolumnerna och båda diagonalerna den magiska konstanten.
Most Perfect Magic Square: Detta är en vanlig magisk fyrkant med två speciella egenskaper. Här summerar varje 2 gånger 2 subkvadrat av matrisen till totalt 2(n^2+1). Och alla talpar som är n/2 rutor förutom rutnätssumman till n^2+1.

Baserat på egenskaper finns det många fler typer av magiska rutor. Men när vi bara nämner den magiska kvadraten, antar vi att det är en normal och enkel magisk kvadrat med udda ordning.

Algoritm för att generera Magic Square

Algoritmen för att generera udda magiska rutor är:

Det första numret eller 1:an kommer att lagras vid (n/2, n-1), där den första koordinaten är radpositionen och den andra koordinaten är kolumnpositionen. För senare steg, låt oss beteckna denna position som (x, y).
Nästa nummer kommer att lagras vid (x-1, y+1). Om tjänsten inte är giltig kommer vi att överväga följande villkor.
1. Om radpositionen är -1 kommer den att skeva till n-1. På liknande sätt, om den beräknade kolumnpositionen är n, kommer den att skeva till 0.
2. Radpositionen kommer att ökas med 1, och kolumnpositionen kommer att minskas med 2 om den beräknade positionen redan innehåller ett tal.
3. Om radpositionen är -1 och motsvarande kolumnposition är n, kommer den nya positionen att vara (0, n-2.

Obs: Denna algoritm genererar bara giltiga magiska kvadrater av udda ordning. Vi betraktar också denna magiska ruta som en normal magisk ruta med de första n^2-talen. Dessutom kan det finnas flera lösningar för samma värde på n.

Låt oss ta ett exempel och se hur det fungerar. Låt oss säga att vi vill hitta den magiska kvadraten av ordning 3. Eftersom det blir en enkel och normal magisk kvadrat av udda ordning kommer den att innehålla alla siffror från 1 till 3^2 eller 9.

Hur det fungerar?

Enligt vår algoritm, kommer stegen att vara följande:

Steg 1) Den första siffran eller 1 kommer att vara på (3/2, 3-1) eller (1, 2). Enligt konvention, överväg x= 1 och y= 2 för senare steg.

Steg 2) Positionen för resten av siffrorna kommer att beräknas på följande sätt-

Position nummer 2:

Nästa nummer kommer att vara (x-1, y+1) eller (0, 3), vilket inte är en giltig position. Genom att använda villkor (a) skulle motsvarande giltiga position vara (0,0). Alltså, x= 0, y= 0.

Position nummer 3:

Nummer 3 kommer att vara på (x-1, y+1) eller (-1, 1), vilket inte är en giltig position. Genom att använda villkor (a) skulle den giltiga radpositionen vara n-1 eller 2. Så nummer 3 kommer att vara vid (2, 1). För nästa nummer, x= 2, y= 1.

Position nummer 4:

Nummer 4 ska vara vid (x-1, y+1) eller (1, 2) vilket är en giltig position. Men den positionen innehåller redan en siffra. Enligt villkor (b) skulle den giltiga positionen vara (1+1, 2-2) eller (2,0). För nästa tal är x= 2, y= 0.

Position nummer 5:

Nummer 5 ska vara vid (x-1, y+1) eller (1, 1) vilket är en giltig position. För nästa nummer x= 1, y= 1.

Position nummer 6:

Nummer 6 ska vara vid (x-1, y+1) eller (0, 2) vilket är en giltig position. För nästa nummer x= 0, y= 2.

Position nummer 7:

Nummer 7 ska vara vid (x-1, y+1) eller (-1, 3) vilket inte är en giltig position. Enligt villkor (c) skulle den giltiga positionen vara (0, n-2) eller (0, 1). För nästa tal är x= 0, y= 1.

Position nummer 8:

Nummer 8 ska vara vid (x-1, y+1) eller (-1, 2) vilket inte är en giltig position. Genom att använda villkor (a) skulle den giltiga positionen vara (2, 2). För nästa nummer x= 2, y= 2.

Position nummer 9:

Nummer 9 ska vara vid (x-1, y+1) eller (1, 3) vilket inte är en giltig position. Genom att använda villkor (a) skulle den giltiga positionen vara (1, 0).

Pseudokod

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

Ingång:

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

Utdata från exempel:

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

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)