Hoe los je een 3x3 magisch vierkant puzzel op in C&O? Python

Wat is een magisch vierkant?

Een magisch vierkant is een vierkante matrix met een speciale rangschikking van getallen. De waarden zijn zo geplaatst dat de som in elke rij, elke kolom en beide hoofddiagonalen gelijk blijft. Magische vierkanten zijn eenvoudige logische puzzels die gebruikt worden in de recreatieve wiskunde.

Voorbeeld van magische vierkanten:

Het bovenstaande diagram toont een magisch vierkant van orde 3. De som van elke diagonaal, rij en kolom is gelijk aan 15. In het volgende gedeelte wordt uitgelegd hoe deze constante som tot stand komt.

Hoe werken magische vierkanten?

Een magisch vierkant van orde n is een n x n matrix die n² positieve gehele getallen bevat. Het aantal rijen of kolommen wordt de orde van de matrix genoemd.

Typische magische vierkantpuzzels hebben een oneven volgorde en gebruiken de getallen van 1 tot en met n². Omdat elke rij, kolom en diagonaal dezelfde waarde moet opleveren, wordt die waarde de magische som of magische constante genoemd. De constante hangt alleen af ​​van n. De formule voor de magische som van orde n is:

Beschouw een magisch vierkant van orde 3. De magische som is dan:

Deze formule verklaart de rekenkunde, maar de puzzel heeft een lange culturele geschiedenis die hem zijn gedenkwaardige naam heeft gegeven.

Waarom worden ze magisch genoemd?

Oude wiskundigen waren gefascineerd door interessante getallencombinaties, en het magische vierkant was er daar één van. Het vroegste bewijs hiervoor dateert uit China, rond 190 v.Chr.

Studies tonen aan dat er in het oude Japan, India en Arabië al magische vierkanten bestonden. Legendes verbonden deze patronen met de magische wereld, en de naam is blijven hangen. Naast de folklore hebben wiskundigen ook formele categorieën gedefinieerd die het ene vierkant van het andere onderscheiden.

Soorten magisch vierkant

In de wiskunde bestaan ​​verschillende varianten van magische vierkanten:

• Normaal magisch vierkant: Bevat de eerste n² natuurlijke getallen.
• Semi-magisch vierkant: Alleen de rijen en de kolommen tellen op tot de magische constante.
• Eenvoudig magisch vierkant: De rijen, kolommen en beide hoofddiagonalen tellen op tot de magische constante.
• Meest perfecte magische vierkant: Een gewoon magisch vierkant met twee extra eigenschappen. Elk 2x2 deelvierkant van de matrix telt op tot 2(n²+1), en elk paar getallen dat n/2 cellen van elkaar verwijderd is, telt op tot n²+1.

Er bestaan ​​meer categorieën op basis van aanvullende eigenschappen. Wanneer in deze handleiding de term 'magisch vierkant' zonder verdere specificatie wordt gebruikt, verwijst deze naar een oneven, normaal, eenvoudig magisch vierkant.

Algoritme voor het genereren van een magisch vierkant

Het klassieke algoritme voor het genereren van een magisch vierkant van oneven orde, de zogenaamde Siamese methode, is als volgt:

• Het eerste getal (1) wordt opgeslagen op positie (n/2, n-1), waarbij de eerste coördinaat de rij-index is en de tweede de kolom-index. Voor latere stappen noemen we deze positie (x, y).
• Het volgende getal wordt geplaatst op (x-1, y+1). Als die positie ongeldig is, pas dan de volgende regels toe:
  1. Als de rij-index -1 is, ga dan naar n-1. Als de kolom-index n is, ga dan naar 0.
  2. Als de berekende positie al een getal bevat, verhoog dan de rij met 1 en verlaag de kolom met 2.
  3. Als de rij -1 is en de kolom tegelijkertijd n, is de nieuwe positie (0, n-2).

Let op: Dit algoritme genereert alleen geldige magische vierkanten van oneven orde. Het resultaat is een normaal magisch vierkant dat de eerste n² natuurlijke getallen bevat. Er kunnen meerdere geldige oplossingen zijn voor dezelfde n.

De regels worden duidelijker aan de hand van een klein voorbeeld met orde 3, waarbij de getallen 1 tot en met 9 worden gebruikt.

Hoe het werkt op een vierkant van 3 bij 3.

Het toepassen van de algoritme De bovenstaande stappen zijn:

Stap 1) Het eerste getal (1) wordt geplaatst op (3/2, 3-1) of (1, 2). Voor de volgende stappen stellen we x = 1 en y = 2.

Stap 2) De posities van de resterende getallen worden als volgt berekend.

Positie van nummer 2:

Het volgende getal zou naar (x-1, y+1) of (0, 3) moeten gaan, wat geen geldige positie is. Volgens regel (a) springt de kolom terug naar 0, wat (0, 0) oplevert. Stel x = 0, y = 0.

Positie van nummer 3:

Nummer 3 zou op (x-1, y+1) of (-1, 1) moeten staan, wat geen geldige positie is. Volgens regel (a) springt de rij terug naar n-1 (wat 2 is). Dus nummer 3 komt op (2, 1). Stel x = 2, y = 1.

Positie van nummer 4:

Nummer 4 zou op (x-1, y+1) of (1, 2) moeten staan, wat geldig is maar al 1 bevat. Volgens regel (b) is de nieuwe positie (1+1, 2-2) of (2, 0). Stel x = 2, y = 0.

Positie van nummer 5:

Nummer 5 moet zich op (x-1, y+1) of (1, 1) bevinden, wat een geldige lege positie is. Stel x = 1, y = 1.

Positie van nummer 6:

Nummer 6 moet zich op (x-1, y+1) of (0, 2) bevinden, wat een geldige lege positie is. Stel x = 0, y = 2.

Positie van nummer 7:

Nummer 7 zou op (x-1, y+1) of (-1, 3) moeten staan, wat niet geldig is. Volgens regel (c) is de nieuwe positie (0, n-2) of (0, 1). Stel x = 0, y = 1.

Positie van nummer 8:

Nummer 8 zou op (x-1, y+1) of (-1, 2) moeten staan, wat niet geldig is. Volgens regel (a) springt de rij terug naar 2, wat (2, 2) oplevert. Stel x = 2, y = 2.

Positie van nummer 9:

Nummer 9 zou op (x-1, y+1) of (1, 3) moeten staan, wat niet geldig is. Volgens regel (a) springt de kolom terug naar 0, wat (1, 0) oplevert.

Als elke cel is ingevuld, vertaalt dezelfde logica zich direct naar pseudocode.

Pseudocode voor een magisch vierkant

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

De pseudocode komt rechtstreeks overeen met gecompileerde en geïnterpreteerde talen, zoals hierna wordt getoond in C++ en Python.

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

De Python De onderstaande versie gebruikt identieke rij- en kolomregels.

Python Code voor een 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

Beide implementaties gedragen zich identiek, waardoor het eenvoudig is om hun kosten te vergelijken.

Complexiteitsanalyse

• Ruimtecomplexiteit: Het magische vierkant wordt opgeslagen in een n bij n matrix, dus de ruimtecomplexiteit is O(n²).
• Tijdscomplexiteit: De generator maakt gebruik van twee geneste lussen. De buitenste lus wordt n keer uitgevoerd en de binnenste lus ook n keer, dus de totale tijdscomplexiteit is O(n²).

Veelgestelde vragen