Πώς να λύσετε το παζλ 3×3 Magic Square σε C & Python

Τι είναι ένα Μαγικό Τετράγωνο;

Ένα μαγικό τετράγωνο είναι ένας τετραγωνικός πίνακας με μια ειδική διάταξη αριθμών. Οι τιμές τοποθετούνται έτσι ώστε το άθροισμα σε κάθε γραμμή, κάθε στήλη και στις δύο κύριες διαγώνιους να παραμένει το ίδιο. Τα μαγικά τετράγωνα είναι απλά λογικά παζλ που χρησιμοποιούνται στα ψυχαγωγικά μαθηματικά.

Παράδειγμα μαγικών τετραγώνων:

Το παραπάνω διάγραμμα δείχνει ένα μαγικό τετράγωνο τάξης 3. Το άθροισμα κάθε διαγωνίου, γραμμής και στήλης ισούται με 15. Η επόμενη ενότητα εξηγεί πώς παράγεται αυτό το σταθερό άθροισμα.

Πώς λειτουργούν τα μαγικά τετράγωνα

Ένα μαγικό τετράγωνο τάξης n είναι ένας πίνακας n επί n που περιέχει θετικούς ακέραιους αριθμούς n². Ο αριθμός των γραμμών ή των στηλών ονομάζεται τάξη του πίνακα.

Τα τυπικά παζλ μαγικών τετραγώνων έχουν περιττή τάξη και χρησιμοποιούν ακέραιους αριθμούς από 1 έως n². Επειδή κάθε γραμμή, στήλη και διαγώνιος πρέπει να έχει το άθροισμα της ίδιας τιμής, αυτή η τιμή ονομάζεται μαγικό άθροισμα ή μαγική σταθερά. Η σταθερά εξαρτάται μόνο από το n. Ο τύπος για το μαγικό άθροισμα τάξης n είναι:

Θεωρήστε ένα μαγικό τετράγωνο τάξης 3. Το μαγικό άθροισμα τότε είναι:

Αυτός ο τύπος εξηγεί την αριθμητική, αλλά το παζλ έχει μια μακρά πολιτιστική ιστορία που του δίνει το αξιομνημόνευτο όνομά του.

Γιατί ονομάζονται Μαγεία;

Οι αρχαίοι μαθηματικοί γοητεύονταν από ενδιαφέροντες συνδυασμούς αριθμών, και το μαγικό τετράγωνο ήταν ένας από αυτούς. Τα πρώτα στοιχεία χρονολογούνται στην Κίνα γύρω στο 190 π.Χ.

Μελέτες δείχνουν στοιχεία για την ύπαρξη παζλ μαγικών τετραγώνων στην αρχαία Ιαπωνία, την Ινδία και την Αραβία. Οι θρύλοι συνέδεαν αυτές τις διατάξεις με τον μαγικό κόσμο και το όνομα παρέμεινε. Πέρα από τη λαογραφία, οι μαθηματικοί έχουν επίσης ορίσει επίσημες κατηγορίες που διακρίνουν ένα τετράγωνο από ένα άλλο.

Τύποι μαγικού τετραγώνου

Υπάρχουν διάφορες παραλλαγές των μαγικών τετραγώνων στα μαθηματικά:

• Κανονικό μαγικό τετράγωνο: Περιέχει τους πρώτους n² φυσικούς αριθμούς.
• Ημι-μαγικό τετράγωνο: Μόνο οι γραμμές και οι στήλες προστίθενται για να λάβουν τη μαγική σταθερά.
• Απλό μαγικό τετράγωνο: Οι γραμμές, οι στήλες και οι δύο κύριες διαγώνιοι αθροίζονται για να λάβουν τη μαγική σταθερά.
• Το πιο τέλειο μαγικό τετράγωνο: Ένα κανονικό μαγικό τετράγωνο με δύο επιπλέον ιδιότητες. Κάθε υποτετράγωνο 2 επί 2 του πίνακα αθροίζει 2(n²+1), και οποιοδήποτε ζεύγος αριθμών που απέχουν n/2 κελιά αθροίζει n²+1.

Υπάρχουν περισσότερες κατηγορίες με βάση πρόσθετες ιδιότητες. Όποτε ο όρος «μαγικό τετράγωνο» χρησιμοποιείται χωρίς επιφύλαξη σε αυτό το σεμινάριο, αναφέρεται σε ένα απλό, κανονικό, περιττής τάξης μαγικό τετράγωνο.

Αλγόριθμος για τη δημιουργία ενός μαγικού τετραγώνου

Ο κλασικός αλγόριθμος για τη δημιουργία ενός μαγικού τετραγώνου περιττής τάξης, που ονομάζεται σιαμαία μέθοδος, έχει ως εξής:

• Ο πρώτος αριθμός (1) αποθηκεύεται στη θέση (n/2, n-1), όπου η πρώτη συντεταγμένη είναι ο δείκτης γραμμής και η δεύτερη είναι ο δείκτης στήλης. Για μεταγενέστερα βήματα, καλέστε αυτήν τη θέση (x, y).
• Ο επόμενος αριθμός τοποθετείται στο (x-1, y+1). Εάν αυτή η θέση δεν είναι έγκυρη, εφαρμόστε τους ακόλουθους κανόνες:
  1. Εάν ο δείκτης γραμμής είναι -1, τυλίξτε τον σε n-1. Εάν ο δείκτης στήλης είναι n, τυλίξτε τον σε 0.
  2. Εάν η υπολογιζόμενη θέση περιέχει ήδη έναν αριθμό, αυξήστε τη γραμμή κατά 1 και μειώστε τη στήλη κατά 2.
  3. Αν η γραμμή είναι -1 και η στήλη είναι n ταυτόχρονα, η νέα θέση είναι (0, n-2).

Σημείωση: Αυτός ο αλγόριθμος παράγει μόνο έγκυρα μαγικά τετράγωνα περιττής τάξης. Το αποτέλεσμα είναι ένα κανονικό μαγικό τετράγωνο που περιέχει τους πρώτους n² φυσικούς αριθμούς. Μπορεί να υπάρχουν περισσότερες από μία έγκυρες λύσεις για το ίδιο n.

Οι κανόνες γίνονται πιο σαφέστεροι μέσω ενός μικρού παραδείγματος με την τάξη 3, η οποία χρησιμοποιεί τους αριθμούς από το 1 έως το 9.

Πώς λειτουργεί σε ένα τετράγωνο 3 επί 3

Εφαρμογή του αλγόριθμος παραπάνω, τα βήματα είναι:

Βήμα 1) Ο πρώτος αριθμός (1) τοποθετείται στο (3/2, 3-1) ή στο (1, 2). Για τα επόμενα βήματα, ορίστε x = 1 και y = 2.

Βήμα 2) Οι θέσεις των υπόλοιπων αριθμών υπολογίζονται ως εξής.

Θέση αριθμού 2:

Ο επόμενος αριθμός θα πρέπει να πάει στο (x-1, y+1) ή στο (0, 3), το οποίο δεν είναι έγκυρη θέση. Σύμφωνα με τον κανόνα (α), η στήλη αναδιπλώνεται στο 0, δίνοντας (0, 0). Ορίστε x = 0, y = 0.

Θέση αριθμού 3:

Ο αριθμός 3 θα πρέπει να βρίσκεται στο (x-1, y+1) ή στο (-1, 1), το οποίο δεν είναι έγκυρη θέση. Σύμφωνα με τον κανόνα (α), η γραμμή αναδιπλώνεται στο n-1 (το οποίο είναι 2). Έτσι, ο αριθμός 3 πηγαίνει στο (2, 1). Ορίστε x = 2, y = 1.

Θέση αριθμού 4:

Ο αριθμός 4 θα πρέπει να βρίσκεται στο (x-1, y+1) ή στο (1, 2), το οποίο ισχύει αλλά περιέχει ήδη το 1. Σύμφωνα με τον κανόνα (β), η νέα θέση είναι (1+1, 2-2) ή (2, 0). Ορίστε x = 2, y = 0.

Θέση αριθμού 5:

Ο αριθμός 5 θα πρέπει να βρίσκεται στο (x-1, y+1) ή στο (1, 1), το οποίο είναι μια έγκυρη κενή θέση. Ορίστε x = 1, y = 1.

Θέση αριθμού 6:

Ο αριθμός 6 θα πρέπει να βρίσκεται στο (x-1, y+1) ή στο (0, 2), το οποίο είναι μια έγκυρη κενή θέση. Ορίστε x = 0, y = 2.

Θέση αριθμού 7:

Ο αριθμός 7 θα πρέπει να βρίσκεται στο (x-1, y+1) ή στο (-1, 3), κάτι που δεν ισχύει. Σύμφωνα με τον κανόνα (c), η νέα θέση είναι (0, n-2) ή (0, 1). Ορίστε x = 0, y = 1.

Θέση αριθμού 8:

Ο αριθμός 8 θα πρέπει να βρίσκεται στο (x-1, y+1) ή στο (-1, 2), κάτι που δεν ισχύει. Σύμφωνα με τον κανόνα (α), η γραμμή αναδιπλώνεται στο 2, δίνοντας (2, 2). Ορίστε x = 2, y = 2.

Θέση αριθμού 9:

Ο αριθμός 9 θα πρέπει να βρίσκεται στο (x-1, y+1) ή στο (1, 3), κάτι που δεν ισχύει. Σύμφωνα με τον κανόνα (α), η στήλη αναδιπλώνεται στο 0, δίνοντας (1, 0).

Με κάθε κελί που γεμίζει, η ίδια λογική μεταφράζεται απευθείας σε ψευδοκώδικα.

Ψευδοκώδικας για το Μαγικό Τετράγωνο

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++ και Python.

C++ Code για το Μαγικό Τετράγωνο

εισόδου:

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

Έξοδος παραδείγματος:

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

The Python Η παρακάτω έκδοση χρησιμοποιεί πανομοιότυπους κανόνες γραμμών και στηλών.

Python Code για το Μαγικό Τετράγωνο

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)

Έξοδος παραδείγματος:

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

Και οι δύο εφαρμογές συμπεριφέρονται με τον ίδιο τρόπο, γεγονός που καθιστά εύκολη τη σύγκριση του κόστους τους.

Ανάλυση πολυπλοκότητας

• Διαστημική πολυπλοκότητα: Το μαγικό τετράγωνο αποθηκεύεται σε έναν πίνακα n επί n, επομένως η πολυπλοκότητα του χώρου είναι O(n²).
• Χρόνος πολυπλοκότητας: Η γεννήτρια χρησιμοποιεί δύο ένθετους βρόχους. Ο εξωτερικός βρόχος εκτελείται n φορές και ο εσωτερικός βρόχος εκτελείται επίσης n φορές, επομένως η συνολική χρονική πολυπλοκότητα είναι O(n²).

Συχνές Ερωτήσεις