Magic Square – Rezolvă puzzle 3×3 folosind C & Python Exemple
Sarah Chen
Ce este Magic Square?
Un pătrat magic este o matrice pătrată cu un aranjament special de numere. Aceste numere sunt aranjate astfel încât suma numerelor de pe fiecare diagonală, rând și coloană să rămână aceeași. Jocurile cu pătrate magice sunt puzzle-uri logice simple folosite în matematica recreativă.
Exemplu de pătrate magice:
Mai sus este un exemplu de pătrat magic de ordinul 3. Suma fiecărei diagonale, rând și coloană este 15.
Cum funcționează Magic Square
Pătratele magice sunt n*n matrice formate din n^2 numere întregi pozitive. Numărul de rânduri sau coloane ale unei matrice pătrate se numește ordinea matricei.
De obicei, puzzle-urile cu pătrate magice au ordine impare și poartă numerele întregi de la 1 la n^2. Suma fiecărei diagonale, rânduri și coloane este aceeași. Acest număr se numește sumă magică sau constantă magică. În general, această sumă magică depinde de ordinea matricei. Formula pătratelor magice pentru suma magică de ordin n este-
Să luăm un exemplu de pătrat magic cu numere întregi 3. Deci, suma magică ar fi-
De ce se numesc Magic?
Matematicienii antici au fost fascinați de natura mai multor combinații interesante de numere. Pătratul magic a fost unul dintre ele. Cele mai vechi dovezi ale pătratelor magice datează din China în 190 î.Hr.
Unele studii arată dovezi ale puzzle-ului pătratelor magice din Japonia antică, India și Arabia. Pe baza unor legende, s-a presupus că acele formațiuni speciale de numere erau legate de lumea magică. Prin urmare, acele pătrate au fost numite pătrate magice.
Tipuri de pătrat magic
Există diferite variante ale matematicii pătratelor magice -
- Pătrat magic normal: Acest tip de pătrat magic conține primele n^2 numere.
- Pătrat semi-magic: În acest tip, doar rândurile și coloana se însumează la constanta magică.
- Pătrat magic simplu: Spre deosebire de tipul anterior, rândurile, coloanele și ambele diagonale se însumează la constanta magică.
- Cel mai perfect pătrat magic: Acesta este un pătrat magic normal cu două proprietăți speciale. Aici, fiecare subpătrat 2 cu 2 al matricei se adună la un total de 2(n^2+1). Și orice pereche de numere care sunt n/2 pătrate în afară de suma grilei la n^2+1.
Pe baza proprietăților, există mai multe tipuri de pătrate magice. Dar ori de câte ori menționăm doar pătratul magic, presupunem că este un pătrat magic normal și simplu de ordin ciudat.
Algoritm pentru generarea unui pătrat magic
Algoritmul pentru generarea de pătrate magice de ordin impar este:
- Primul număr sau 1 va fi stocat la (n/2, n-1), unde prima coordonată este poziția rândului, iar a doua coordonată este poziția coloanei. Pentru pașii următori, să notăm această poziție ca (x, y).
- Următoarele numere vor fi stocate la (x-1, y+1). Dacă postul nu este valid, vom lua în considerare următoarele condiții.
- Dacă poziția rândului este -1, se va deforma la n-1. În mod similar, dacă poziția calculată a coloanei este n, aceasta se va deforma la 0.
- Poziția rândului va fi incrementată cu 1, iar poziția coloanei va fi decrementată cu 2 dacă poziția calculată conține deja un număr.
- Dacă poziția rândului este -1 și poziția coloanei corespunzătoare este n, noua poziție va fi (0, n-2.
Notă: Acest algoritm generează doar pătrate magice valide de ordin impar. De asemenea, considerăm acest pătrat magic un pătrat magic normal cu primele n^2 numere. Mai mult, pot exista mai multe soluții pentru aceeași valoare a lui n.
Să luăm un exemplu și să vedem cum funcționează. Să presupunem că vrem să găsim pătratul magic de ordinul 3. Deoarece va fi un pătrat magic simplu și normal de ordin impar, acesta va conține toate numerele de la 1 la 3^2 sau 9.
Cum functioneaza?
În opinia noastră Algoritmul, pașii vor fi următorii:
Pas 1) Primul număr sau 1 va fi în poziția (3/2, 3-1) sau (1, 2). Prin convenție, luați în considerare x= 1 și y= 2 pentru pașii următori.
Pas 2) Poziția pentru restul numerelor va fi calculată în felul următor:
Poziția numărului 2:
Următorul număr va fi la (x-1, y+1) sau (0, 3), care nu este o poziție validă. Folosind condiția (a), poziția validă corespunzătoare ar fi (0,0). Deci, x= 0, y= 0.
Poziția numărului 3:
Numărul 3 va fi la (x-1, y+1) sau (-1, 1), ceea ce nu este o poziție validă. Folosind condiția (a), poziția validă a rândului ar fi n-1 sau 2. Deci, numărul 3 va fi la (2, 1). Pentru următorul număr, x= 2, y= 1.
Poziția numărului 4:
Numărul 4 ar trebui să fie la (x-1, y+1) sau (1, 2), care este o poziție validă. Dar acea poziție conține deja un număr. Conform condiției (b), poziția valabilă ar fi (1+1, 2-2) sau (2,0). Pentru următorul număr 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 validă. Pentru următorul număr 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 validă. Pentru următorul număr 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 o poziție validă. Conform condiției (c), poziția validă ar fi (0, n-2) sau (0, 1). Pentru următorul număr 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 o poziție validă. Folosind condiția (a), poziția validă ar fi (2, 2). Pentru următorul număr 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 o poziție validă. Folosind condiția (a), poziția validă ar fi (1, 0).
Pseudo cod
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++ Cod Magic Square
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 Cod Magic Square
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
Analiza complexității
- Complexitatea spațială: Pentru a menține matricea pătratului magic, avem nevoie de o matrice*n. Deci, complexitatea spațiului ar fi O(n^2).
- Complexitatea timpului: Codul pe care l-am folosit pentru a genera matematica pătrate magice constă din două bucle. Bucla exterioară rulează de n ori, iar bucla interioară rulează, de asemenea, de n ori. În cele din urmă, complexitatea timpului este O(n^2).