Magisch Vierkant – Los de 3×3-puzzel op met C & Python Voorbeelden
Sara Chen
Wat is Magisch Vierkant?
Een magisch vierkant is een vierkante matrix met een speciale nummerindeling. Deze nummers zijn zo gerangschikt dat de som van de nummers op elke diagonaal, rij en kolom hetzelfde blijft. Magische vierkantenspellen zijn eenvoudige logische puzzels die worden gebruikt in recreatieve wiskunde.
Voorbeeld van magische vierkanten:
Bovenstaand diagram is een voorbeeld van een magisch vierkant van orde 3. De som van elke diagonaal, rij en kolom is 15.
Hoe Magisch Vierkant werkt
Magische vierkanten zijn n*n matrices die bestaan uit n^2 positieve gehele getallen. Het aantal rijen of kolommen van een vierkante matrix wordt de orde van de matrix genoemd.
Magische vierkantenpuzzels hebben doorgaans oneven volgordes en dragen de gehele getallen van 1 tot n^2. De som van elke diagonaal, rij en kolom is hetzelfde. Dit getal wordt magische som of magische constante genoemd. Over het algemeen hangt deze magische som af van de volgorde van de matrix. De formule voor magische vierkanten voor de magische som van orde n is-
Laten we een voorbeeld nemen van een magisch vierkant met gehele getallen 3. De magische som zou dus zijn:
Waarom worden ze Magie genoemd?
Oude wiskundigen waren gefascineerd door de aard van verschillende interessante combinaties van getallen. Het magische vierkant was er daar één van. Het vroegste bewijs van magische vierkanten dateert uit China in 190 v.Chr.
Sommige studies tonen bewijs van de Magic squares-puzzel in het oude Japan, India en Arabië. Op basis van sommige legendes werd aangenomen dat die speciale formaties van getallen verbonden waren met de magische wereld. Daarom werden die vierkanten magische vierkanten genoemd.
Soorten magisch vierkant
Er zijn verschillende varianten van magische vierkantenwiskunde –
- Normaal magisch vierkant: Dit type magisch vierkant bevat de eerste n^2 getallen.
- Semi-magisch vierkant: Bij dit type vormen alleen de rijen en de kolom de magische constante.
- Eenvoudig magisch vierkant: In tegenstelling tot het vorige type vormen de rijen, kolommen en beide diagonalen samen de magische constante.
- Meest perfecte magische vierkant: Dit is een normaal magisch vierkant met twee speciale eigenschappen. Hier telt elk 2 bij 2 subvierkant van de matrix op tot een totaal van 2(n^2+1). En elk paar getallen dat n/2 vierkanten van het raster verwijderd is, telt op tot n^2+1.
Gebaseerd op eigenschappen zijn er nog veel meer soorten magische vierkanten. Maar wanneer we alleen het magische vierkant noemen, gaan we ervan uit dat het een oneven-orde normaal en eenvoudig magisch vierkant is.
Algoritme om magisch vierkant te genereren
Het algoritme voor het genereren van magische vierkanten van oneven orde is:
- Het eerste getal of 1 wordt opgeslagen op (n/2, n-1), waarbij de eerste coördinaat de rijpositie is en de tweede coördinaat de kolompositie. Voor latere stappen, laten we deze positie aanduiden als (x, y).
- De volgende getallen worden opgeslagen op (x-1, y+1). Als de positie niet geldig is, dan zullen we de volgende voorwaarden overwegen.
- Als de rijpositie -1 is, zal deze kromtrekken naar n-1. Op dezelfde manier, als de berekende kolompositie n is, zal deze naar 0 vervormen.
- De rijpositie wordt met 1 verhoogd en de kolompositie met 2 verlaagd als de berekende positie al een getal bevat.
- Als de rijpositie -1 is en de corresponderende kolompositie n is, is de nieuwe positie (0, n-2.
Opmerking: Dit algoritme genereert alleen geldige magische vierkanten van oneven orde. We beschouwen dit magische vierkant ook als een normaal magisch vierkant met de eerste n^2 getallen. Bovendien kunnen er meerdere oplossingen zijn voor dezelfde waarde van n.
Laten we een voorbeeld nemen en kijken hoe het werkt. Stel dat we het magisch vierkant van orde 3 willen vinden. Omdat het een eenvoudig en normaal magisch vierkant van oneven orde zal zijn, zal het alle getallen van 1 tot 3^2 of 9 bevatten.
Hoe werkt het?
Volgens onze algoritme, dan zijn de stappen als volgt:
Stap 1) Het eerste getal of 1 zal op de (3/2, 3-1) of (1, 2) positie staan. Volgens conventie, beschouw x= 1 en y= 2 voor latere stappen.
Stap 2) De positie van de overige getallen wordt op de volgende manier berekend:
Positie van nummer 2:
Het volgende getal bevindt zich op (x-1, y+1) of (0, 3), wat geen geldige positie is. Door voorwaarde (a) te gebruiken, zou de overeenkomstige geldige positie (0,0) zijn. Dus x= 0, y= 0.
Positie van nummer 3:
Nummer 3 bevindt zich op (x-1, y+1) of (-1, 1), wat geen geldige positie is. Door voorwaarde (a) te gebruiken, zou de geldige rijpositie n-1 of 2 zijn. Nummer 3 zal dus op (2, 1) staan. Voor het volgende getal, x= 2, y= 1.
Positie van nummer 4:
Nummer 4 moet op (x-1, y+1) of (1, 2) staan, wat een geldige positie is. Maar die positie bevat al een nummer. Volgens voorwaarde (b) zou de geldige positie (1+1, 2-2) of (2,0) zijn. Voor het volgende getal x= 2, y= 0.
Positie van nummer 5:
Nummer 5 moet op (x-1, y+1) of (1, 1) staan, wat een geldige positie is. Voor het volgende getal x= 1, y= 1.
Positie van nummer 6:
Nummer 6 moet op (x-1, y+1) of (0, 2) staan, wat een geldige positie is. Voor het volgende getal x= 0, y= 2.
Positie van nummer 7:
Nummer 7 moet op (x-1, y+1) of (-1, 3) staan, wat geen geldige positie is. Volgens voorwaarde (c) zou de geldige positie (0, n-2) of (0, 1) zijn. Voor het volgende getal x= 0, y= 1.
Positie van nummer 8:
Nummer 8 moet op (x-1, y+1) of (-1, 2) staan, wat geen geldige positie is. Door voorwaarde (a) te gebruiken, zou de geldige positie (2, 2) zijn. Voor het volgende getal x= 2, y= 2.
Positie van nummer 9:
Nummer 9 moet op (x-1, y+1) of (1, 3) staan, wat geen geldige positie is. Door voorwaarde (a) te gebruiken, zou de geldige positie (1, 0) zijn.
Pseudo-code
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 Magisch Vierkant
Input:
/*
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;
}
Uitvoer van voorbeeld:
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 Magisch Vierkant
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)
Uitvoer van voorbeeld:
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
Complexiteitsanalyse
- Ruimtecomplexiteit: Om de magische vierkantmatrix te behouden, hebben we een*n array nodig. De ruimtecomplexiteit zou dus O(n^2) zijn.
- Tijdscomplexiteit: De code die we gebruikten om magische vierkanten te genereren, bestaat uit twee lussen. De buitenste lus loopt n keer, en de binnenste lus loopt ook n keer. Uiteindelijk is de tijdcomplexiteit O(n^2).
