Magic Square – Løs 3×3 puslespill med C & Python Eksempler
Sarah Chen
Hva er Magic Square?
En magisk firkant er en kvadratisk matrise med et spesielt tallarrangement. Disse tallene er ordnet slik at summen av tallene på hver diagonal, rad og kolonne forblir den samme. Magiske kvadrater-spill er enkle logiske gåter som brukes i rekreasjonsmatematikk.
Eksempel på magiske firkanter:
Over gitt diagram er et eksempel på et magisk kvadrat av orden 3. Summen av hver diagonal, rad og kolonne er 15.
Hvordan Magic Square fungerer
Magiske kvadrater er n*n matriser som består av n^2 positive heltall. Antall rader eller kolonner i en kvadratisk matrise kalles rekkefølgen til matrisen.
Vanligvis har magiske ruter odde rekkefølger og har heltall fra 1 til n^2. Summen av hver diagonal, rad og kolonne er den samme. Dette tallet kalles magisk sum eller magisk konstant. Generelt avhenger denne magiske summen av rekkefølgen til matrisen. Den magiske kvadraters formel for den magiske summen av orden n er-
La oss ta et eksempel på et magisk kvadrat med heltall 3. Så den magiske summen vil være-
Hvorfor heter de magi?
Gamle matematikere var fascinert av naturen til flere interessante kombinasjoner av tall. Den magiske firkanten var en av dem. De tidligste bevisene på magiske firkanter dateres tilbake til Kina i 190 fvt.
Noen studier viser bevis på magiske kvadrater i det gamle Japan, India og Arabia. Basert på noen legender, ble det antatt at de spesielle formasjonene av tall var knyttet til den magiske verdenen. Derfor ble disse rutene kalt magiske firkanter.
Typer Magic Square
Det finnes forskjellige varianter av matematikk med magiske kvadrater –
- Normal Magic Square: Denne typen magiske firkanter inneholder de første n^2 tallene.
- Semi-Magic Square: I denne typen summerer bare radene og kolonnen til den magiske konstanten.
- Simple Magic Square: I motsetning til den forrige typen summerer radene, kolonnene og begge diagonalene den magiske konstanten.
- Most Perfect Magic Square: Dette er en vanlig magisk firkant med to spesielle egenskaper. Her summerer hver 2 x 2 underkvadrat av matrisen opp til totalt 2(n^2+1). Og alle tallpar som er n/2 kvadrater bortsett fra rutenettsummen til n^2+1.
Basert på egenskaper finnes det mange flere typer magiske firkanter. Men når vi bare nevner den magiske firkanten, antar vi at den er en normal og enkel magisk firkant i oddetall.
Algoritme for å generere magisk kvadrat
Algoritmen for å generere magiske firkanter i oddetall er:
- Det første tallet eller 1 vil bli lagret ved (n/2, n-1), der den første koordinaten er radposisjonen, og den andre koordinaten er kolonneposisjonen. For senere trinn, la oss betegne denne posisjonen som (x, y).
- De neste tallene vil bli lagret på (x-1, y+1). Hvis stillingen ikke er gyldig, vil vi vurdere følgende forhold.
- Hvis radposisjonen er -1, vil den deformeres til n-1. Tilsvarende, hvis den beregnede kolonneposisjonen er n, vil den deformeres til 0.
- Radposisjonen vil økes med 1, og kolonneposisjonen reduseres med 2 hvis den beregnede posisjonen allerede inneholder et tall.
- Hvis radposisjonen er -1 og den tilsvarende kolonneposisjonen er n, vil den nye posisjonen være (0, n-2.
OBS: Denne algoritmen genererer bare gyldige magiske firkanter av oddetall. Vi anser også denne magiske firkanten som en normal magisk firkant med de første n^2 tallene. Dessuten kan det være flere løsninger for samme verdi av n.
La oss ta et eksempel og se hvordan det fungerer. La oss si at vi ønsker å finne det magiske kvadratet av orden 3. Ettersom det vil være et enkelt og normalt magisk kvadrat av oddetall, vil det inneholde alle tallene fra 1 til 3^2 eller 9.
Hvordan det fungerer?
Ifølge vår algoritme, vil trinnene være følgende:
Trinn 1) Det første tallet eller 1 vil være i (3/2, 3-1) eller (1, 2) posisjon. Ved konvensjon, vurder x= 1 og y= 2 for senere trinn.
Trinn 2) Plasseringen for resten av tallene vil bli beregnet på følgende måte-
Plassering nummer 2:
Det neste tallet vil være på (x-1, y+1) eller (0, 3), som ikke er en gyldig posisjon. Ved å bruke betingelse (a), vil den tilsvarende gyldige posisjonen være (0,0). Så, x= 0, y= 0.
Plassering nummer 3:
Nummer 3 vil være på (x-1, y+1) eller (-1, 1), som ikke er en gyldig posisjon. Ved å bruke betingelse (a), vil den gyldige radposisjonen være n-1 eller 2. Så nummer 3 vil være ved (2, 1). For det neste tallet, x= 2, y= 1.
Plassering nummer 4:
Nummer 4 skal være ved (x-1, y+1) eller (1, 2) som er en gyldig posisjon. Men den posisjonen inneholder allerede et tall. I henhold til betingelse (b) vil den gyldige posisjonen være (1+1, 2-2) eller (2,0). For det neste tallet x= 2, y= 0.
Plassering nummer 5:
Nummer 5 skal være ved (x-1, y+1) eller (1, 1) som er en gyldig posisjon. For det neste tallet x= 1, y= 1.
Plassering nummer 6:
Nummer 6 skal være ved (x-1, y+1) eller (0, 2) som er en gyldig posisjon. For det neste tallet x= 0, y= 2.
Plassering nummer 7:
Nummer 7 skal være på (x-1, y+1) eller (-1, 3) som ikke er en gyldig posisjon. I henhold til betingelse (c), vil den gyldige posisjonen være (0, n-2) eller (0, 1). For det neste tallet x= 0, y= 1.
Plassering nummer 8:
Nummer 8 skal være på (x-1, y+1) eller (-1, 2) som ikke er en gyldig posisjon. Ved å bruke betingelse (a), vil den gyldige posisjonen være (2, 2). For det neste tallet x= 2, y= 2.
Plassering nummer 9:
Nummer 9 skal være ved (x-1, y+1) eller (1, 3) som ikke er en gyldig posisjon. Ved å bruke betingelse (a), vil den gyldige posisjonen være (1, 0).
Pseudokode
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
Inngang:
/*
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;
}
Utgang av eksempel:
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)
Utgang av eksempel:
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
Kompleksitetsanalyse
- Romkompleksitet: For å opprettholde den magiske kvadratmatrisen, krever vi en*n matrise. Så romkompleksiteten vil være O(n^2).
- Tidskompleksitet: Koden som vi brukte til å generere magiske kvadrater matematikk består av to løkker. Den ytre sløyfen går n ganger, og den indre sløyfen går også n ganger. Til syvende og sist er tidskompleksiteten O(n^2).
