Hur man löser 3×3 magiska rutor-pussel i C & Python

Vad är en magisk kvadrat?

En magisk kvadrat är en kvadratmatris med en speciell ordning av tal. Värdena är placerade så att summan i varje rad, varje kolumn och båda huvuddiagonalerna förblir densamma. Magiska kvadrater är enkla logiska pussel som används i rekreationsmatematik.

Exempel på magiska rutor:

Diagrammet ovan visar en magisk kvadrat av ordning 3. Summan av varje diagonal, rad och kolumn är lika med 15. Nästa avsnitt förklarar hur denna konstanta summa produceras.

Hur magiska rutor fungerar

En magisk kvadrat av ordning n är en n gånger n-matris som innehåller n² positiva heltal. Antalet rader eller kolumner kallas matrisens ordning.

Typiska magiska kvadratpussel har en udda ordning och använder heltal från 1 till n². Eftersom varje rad, kolumn och diagonal måste summera till samma värde kallas det värdet för den magiska summan eller magiska konstanten. Konstanten beror endast på n. Formeln för den magiska summan av ordning n är:

Betrakta en magisk kvadrat av ordning 3. Den magiska summan är då:

Denna formel förklarar aritmetiken, men pusslet har en lång kulturhistoria som ger det dess minnesvärda namn.

Varför kallas de magi?

Forntida matematiker fascinerades av intressanta talkombinationer, och den magiska kvadraten var en av dem. De tidigaste bevisen går tillbaka till Kina omkring 190 f.Kr.

Studier visar bevis på magiska kvadratpussel i forntida Japan, Indien och Arabien. Legender kopplade dessa arrangemang till den magiska världen, och namnet fastnade. Utöver folklore har matematiker också definierat formella kategorier som skiljer en kvadrat från en annan.

Typer av Magic Square

Det finns flera varianter av magiska kvadrater i matematik:

• Normal Magic Square: Innehåller de första n² naturliga talen.
• Semi-Magic Square: Endast raderna och kolumnerna summerar sig till den magiska konstanten.
• Simple Magic Square: Raderna, kolumnerna och båda huvuddiagonalerna summeras till den magiska konstanten.
• Most Perfect Magic Square: En normal magisk kvadrat med två extra egenskaper. Varje 2 gånger 2 delkvadrat i matrisen adderar till 2(n²+1), och alla par av tal som är n/2 celler ifrån varandra summerar till n²+1.

Fler kategorier finns baserade på ytterligare egenskaper. När termen "magisk kvadrat" används utan förbehåll i den här handledningen hänvisar den till en normal, enkel magisk kvadrat av udda ordning.

Algoritm för att generera en magisk kvadrat

Den klassiska algoritmen för att generera en magisk kvadrat av udda ordning, kallad den siamesiska metoden, är följande:

• Det första talet (1) lagras vid position (n/2, n-1), där den första koordinaten är radindex och den andra är kolumnindex. För senare steg, anropa denna position (x, y).
• Nästa tal placeras vid (x-1, y+1). Om den positionen är ogiltig, tillämpa följande regler:
  1. Om radindexet är -1, radbryt det till n-1. Om kolumnindexet är n, radbryt det till 0.
  2. Om den beräknade positionen redan innehåller ett tal, öka raden med 1 och minska kolumnen med 2.
  3. Om raden är -1 och kolumnen samtidigt är n, är den nya positionen (0, n-2).

Obs: Denna algoritm genererar endast giltiga magiska kvadrater av udda ordning. Resultatet är en normal magisk kvadrat som innehåller de första n² naturliga talen. Det kan finnas mer än en giltig lösning för samma n.

Reglerna blir tydligare genom ett litet exempel med ordning 3, som använder siffrorna 1 till 9.

Hur det fungerar på en 3 x 3-kvadrat

Applicera algoritm ovan är stegen:

Steg 1) Det första talet (1) placeras vid (3/2, 3-1) eller (1, 2). För senare steg, sätt x = 1 och y = 2.

Steg 2) Positionerna för de återstående talen beräknas enligt följande.

Position nummer 2:

Nästa tal ska gå till (x-1, y+1) eller (0, 3), vilket inte är en giltig position. Enligt regel (a) radbryts kolumnen till 0, vilket ger (0, 0). Sätt x = 0, y = 0.

Position nummer 3:

Tal 3 ska vara vid (x-1, y+1) eller (-1, 1), vilket inte är en giltig position. Enligt regel (a) radbryts raden till n-1 (vilket är 2). Så tal 3 går till (2, 1). Sätt x = 2, y = 1.

Position nummer 4:

Tal 4 ska vara vid (x-1, y+1) eller (1, 2), vilket är giltigt men redan innehåller 1. Enligt regel (b) är den nya positionen (1+1, 2-2) eller (2, 0). Sätt x = 2, y = 0.

Position nummer 5:

Nummer 5 ska vara vid (x-1, y+1) eller (1, 1), vilket är en giltig tom position. Sätt x = 1, y = 1.

Position nummer 6:

Nummer 6 ska vara vid (x-1, y+1) eller (0, 2), vilket är en giltig tom position. Sätt x = 0, y = 2.

Position nummer 7:

Talet 7 ska vara vid (x-1, y+1) eller (-1, 3), vilket inte är giltigt. Enligt regel (c) är den nya positionen (0, n-2) eller (0, 1). Sätt x = 0, y = 1.

Position nummer 8:

Talet 8 ska vara vid (x-1, y+1) eller (-1, 2), vilket inte är giltigt. Enligt regel (a) radbryts raden till 2, vilket ger (2, 2). Sätt x = 2, y = 2.

Position nummer 9:

Talet 9 ska vara vid (x-1, y+1) eller (1, 3), vilket inte är giltigt. Enligt regel (a) radbryts kolumnen till 0, vilket ger (1, 0).

Med varje cell som är fylld översätts samma logik direkt till pseudokod.

Pseudokod för Magic Square

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

Pseudokoden mappas direkt till kompilerade och tolkade språk, vilket visas härnäst i C++ och Python.

C++ Code för Magiska torget

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

Ocuco-landskapet Python Versionen nedan använder identiska rad- och kolumnregler.

Python Code för Magiska torget

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)

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

Båda implementeringarna beter sig identiskt, vilket gör det enkelt att jämföra deras kostnader.

Komplexitetsanalys

• Rymdkomplexitet: Den magiska kvadraten lagras i en n gånger n-matris, så rumskomplexiteten är O(n²).
• Tidskomplexitet: Generatorn använder två kapslade loopar. Den yttre loopen körs n gånger, och den inre loopen körs också n gånger, så den totala tidskomplexiteten är O(n²).

Vanliga frågor