Cum să rezolvi un puzzle cu pătratul magic 3×3 în C și Python

Ce este un Pătrat Magic?

Un pătrat magic este o matrice pătrată cu un aranjament special de numere. Valorile sunt plasate astfel încât suma din fiecare rând, fiecare coloană și ambele diagonale principale să rămână aceeași. Pătratele magice sunt puzzle-uri logice simple folosite în matematica recreativă.

Exemplu de pătrate magice:

Diagrama de mai sus prezintă un pătrat magic de ordinul 3. Suma fiecărei diagonale, rânduri și coloane este egală cu 15. Următoarea secțiune explică modul în care se obține acest total constant.

Cum funcționează pătratele magice

Un pătrat magic de ordinul n este o matrice de ordinul n pe n care conține n² numere întregi pozitive. Numărul de rânduri sau coloane se numește ordinul matricei.

Puzzle-urile tipice cu pătrat magic au o ordine impară și folosesc numere întregi de la 1 la n². Deoarece fiecare rând, coloană și diagonală trebuie să aibă aceeași valoare, acea valoare se numește sumă magică sau constantă magică. Constanta depinde doar de n. Formula pentru suma magică de ordin n este:

Luați în considerare un pătrat magic de ordinul 3. Suma magică este atunci:

Această formulă explică aritmetica, dar puzzle-ul are o lungă istorie culturală, care îi conferă numele memorabil.

De ce sunt numite magie?

Matematicienii antici erau fascinați de combinații interesante de numere, iar pătratul magic era una dintre ele. Cele mai vechi dovezi datează din China, în jurul anului 190 î.Hr.

Studiile arată dovezi ale existenței unor puzzle-uri cu pătrate magice în Japonia, India și Arabia antică. Legendele au legat aceste aranjamente de lumea magică, iar numele a rămas. Dincolo de folclor, matematicienii au definit și categorii formale care disting un pătrat de altul.

Tipuri de pătrat magic

Există mai multe variante ale pătratelor magice în matematică:

• Pătrat magic normal: Conține primele n² numere naturale.
• Pătrat semi-magic: Doar rândurile și coloanele se adună pentru a forma constanta magică.
• Pătrat magic simplu: Rândurile, coloanele și ambele diagonale principale se adună pentru a forma constanta magică.
• Cel mai perfect pătrat magic: Un pătrat magic normal cu două proprietăți suplimentare. Fiecare subpătrat de 2 pe 2 al matricei adună 2(n²+1), iar orice pereche de numere care se află la n/2 celule distanță adună n²+1.

Există mai multe categorii bazate pe proprietăți suplimentare. Ori de câte ori termenul „pătrat magic” este folosit fără rezerve în acest tutorial, se referă la un pătrat magic normal, simplu, de ordin impar.

Algoritm pentru generarea unui pătrat magic

Algoritmul clasic pentru generarea unui pătrat magic de ordin impar, numit metoda siameză, este următorul:

• Primul număr (1) este stocat la poziția (n/2, n-1), unde prima coordonată este indicele rândului, iar a doua este indicele coloanei. Pentru pașii ulterioari, apelați această poziție (x, y).
• Următorul număr este plasat la (x-1, y+1). Dacă acea poziție este invalidă, se aplică următoarele reguli:
  1. Dacă indicele rândului este -1, se încadrează în n-1. Dacă indicele coloanei este n, se încadrează în 0.
  2. Dacă poziția calculată conține deja un număr, se incrementează rândul cu 1 și se decrementează coloana cu 2.
  3. Dacă rândul este -1 și coloana este n în același timp, noua poziție este (0, n-2).

Notă: Acest algoritm generează doar pătrate magice valide de ordin impar. Rezultatul este un pătrat magic normal care conține primele n² numere naturale. Pot exista mai multe soluții valide pentru același n.

Regulile devin mai clare printr-un mic exemplu cu ordinul 3, care folosește numerele de la 1 la 9.

Cum funcționează pe un pătrat de 3 pe 3

Aplicarea Algoritmul mai sus, pașii sunt:

Pas 1) Primul număr (1) este plasat la (3/2, 3-1) sau (1, 2). Pentru pașii următori, se stabilește x = 1 și y = 2.

Pas 2) Pozițiile numerelor rămase se calculează după cum urmează.

Poziția numărului 2:

Următorul număr ar trebui să meargă la (x-1, y+1) sau (0, 3), ceea ce nu este o poziție validă. Conform regulii (a), coloana se încadrează la 0, rezultând (0, 0). Setați x = 0, y = 0.

Poziția numărului 3:

Numărul 3 ar trebui să fie la (x-1, y+1) sau (-1, 1), ceea ce nu este o poziție validă. Conform regulii (a), rândul se încheie la n-1 (care este 2). Deci numărul 3 merge la (2, 1). Setați x = 2, y = 1.

Poziția numărului 4:

Numărul 4 ar trebui să fie la (x-1, y+1) sau (1, 2), ceea ce este valid, dar îl conține deja pe 1. Conform regulii (b), noua poziție este (1+1, 2-2) sau (2, 0). Setați x = 2, y = 0.

Poziția numărului 5:

Numărul 5 ar trebui să fie la (x-1, y+1) sau (1, 1), care este o poziție goală validă. Setați x = 1, y = 1.

Poziția numărului 6:

Numărul 6 ar trebui să fie la (x-1, y+1) sau (0, 2), care este o poziție goală validă. Setați x = 0, y = 2.

Poziția numărului 7:

Numărul 7 ar trebui să fie la (x-1, y+1) sau (-1, 3), ceea ce nu este valid. Conform regulii (c), noua poziție este (0, n-2) sau (0, 1). Setați x = 0, y = 1.

Poziția numărului 8:

Numărul 8 ar trebui să fie la (x-1, y+1) sau (-1, 2), ceea ce nu este valid. Conform regulii (a), rândul se încheie la 2, rezultând (2, 2). Se stabilește x = 2, y = 2.

Poziția numărului 9:

Numărul 9 ar trebui să fie la (x-1, y+1) sau (1, 3), ceea ce nu este valid. Conform regulii (a), coloana se încheie la 0, rezultând (1, 0).

Cu fiecare celulă umplută, aceeași logică se traduce direct în pseudo-cod.

Pseudocod pentru Pătratul Magic

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

Pseudocod-ul se mapează direct pe limbaje compilate și interpretate, așa cum se arată în continuare C++ și Python.

C++ Code pentru Pătratul Magic

Intrare:

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

Ieșirea exemplului:

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 Versiunea de mai jos folosește reguli identice pentru rânduri și coloane.

Python Code pentru Pătratul Magic

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)

Ieșirea exemplului:

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

Ambele implementări se comportă identic, ceea ce face ușoară compararea costurilor lor.

Analiza complexității

• Complexitatea spațială: Pătratul magic este stocat într-un tablou de n pe n, deci complexitatea spațiului este O(n²).
• Complexitatea timpului: Generatorul folosește două bucle imbricate. Bucla exterioară rulează de n ori, iar bucla interioară rulează, de asemenea, de n ori, deci complexitatea totală în timp este O(n²).

Întrebări frecvente