Magic Square – Ratkaise 3×3 palapeli C & Python Esimerkit
Sarah Chen
Mikä on Magic Square?
Maaginen neliö on neliömatriisi, jossa on erityinen numerojärjestely. Nämä numerot on järjestetty siten, että kunkin lävistäjän, rivin ja sarakkeen numeroiden summa pysyy samana. Magic squares -pelit ovat yksinkertaisia logiikkapulmia, joita käytetään virkistysmatematiikassa.
Esimerkki maagisista neliöistä:
Yllä oleva kaavio on esimerkki maagisesta neliöstä, jonka kertaluku on 3. Kunkin lävistäjän, rivin ja sarakkeen summa on 15.
Kuinka Magic Square toimii
Maagiset neliöt ovat n*n matriisia, jotka koostuvat n^2 positiivisesta kokonaisluvusta. Neliömatriisin rivien tai sarakkeiden lukumäärää kutsutaan matriisin järjestykseksi.
Tyypillisesti maagisten neliöiden pulmilla on pariton järjestys ja ne sisältävät kokonaisluvut 1:stä n^2:een. Jokaisen diagonaalin, rivin ja sarakkeen summa on sama. Tätä lukua kutsutaan maagiseksi summaksi tai maagiseksi vakioksi. Yleensä tämä maaginen summa riippuu matriisin järjestyksestä. Maagisten neliöiden kaava kertaluvun n maagiselle summalle on
Otetaan esimerkki maagisesta neliöstä, jossa on kokonaisluvut 3. Joten maaginen summa olisi-
Miksi niitä kutsutaan Magiciksi?
Muinaiset matemaatikot kiehtoivat useiden mielenkiintoisten numeroyhdistelmien luonnetta. Maaginen neliö oli yksi niistä. Varhaisimmat todisteet maagisista neliöistä ovat peräisin Kiinasta vuonna 190 eaa.
Jotkut tutkimukset osoittavat todisteita taikaneliöiden palapelistä muinaisessa Japanissa, Intiassa ja Arabiassa. Joidenkin legendojen perusteella oletettiin, että nämä erityiset numeromuodostelmat liittyivät maagiseen maailmaan. Siksi nämä neliöt nimettiin taikaneliöiksi.
Magic Squaren tyypit
Maagisten neliöiden matematiikasta on erilaisia muunnelmia –
- Normaali Magic Square: Tämän tyyppinen maaginen neliö sisältää ensimmäiset n^2 numeroa.
- Puolimaaginen neliö: Tässä tyypissä vain rivit ja sarake summautuvat maagiseen vakioon.
- Yksinkertainen maaginen neliö: Toisin kuin edellisessä tyypissä, rivit, sarakkeet ja molemmat diagonaalit summautuvat maagiseen vakioon.
- Täydellisin Magic Square: Tämä on tavallinen maaginen neliö, jolla on kaksi erikoisominaisuutta. Tässä matriisin kukin 2 x 2 alineliö muodostaa yhteensä 2(n^2+1). Ja mikä tahansa lukupari, joka on n/2 neliötä erillään ruudukon summasta n^2+1.
Ominaisuuksien perusteella on olemassa monia muita maagisia neliöitä. Mutta aina kun mainitsemme maagisen neliön, oletamme sen olevan pariton, normaali ja yksinkertainen maaginen neliö.
Algoritmi Magic Squaren luomiseksi
Parittoman kertaluvun maagisten neliöiden generointialgoritmi on:
- Ensimmäinen numero tai 1 tallennetaan kohtaan (n/2, n-1), jossa ensimmäinen koordinaatti on rivin sijainti ja toinen koordinaatti on sarakkeen sijainti. Merkitään myöhempiä vaiheita varten tämä paikka muodossa (x, y).
- Seuraavat numerot tallennetaan kohtaan (x-1, y+1). Jos asema ei ole pätevä, otamme huomioon seuraavat ehdot.
- Jos rivin sijainti on -1, se vääntyy arvoon n-1. Vastaavasti, jos laskettu sarakkeen sijainti on n, se vääntyy arvoon 0.
- Rivin sijaintia lisätään 1:llä ja sarakkeen sijaintia vähennetään 2:lla, jos laskettu sijainti sisältää jo numeron.
- Jos rivin sijainti on -1 ja vastaava sarakkeen sijainti on n, uusi sijainti on (0, n-2.
Huomautus: Tämä algoritmi luo vain kelvollisia taikaneliöitä, joiden järjestys on pariton. Pidämme myös tätä maagista neliötä normaalina maagisena neliönä, jossa on ensimmäiset n^2 numeroa. Lisäksi samalle n:n arvolle voi olla useita ratkaisuja.
Otetaan esimerkki ja katsotaan kuinka se toimii. Oletetaan, että haluamme löytää 3. kertaluvun maagisen neliön. Koska se on yksinkertainen ja normaali pariton maaginen neliö, se sisältää kaikki luvut väliltä 1 - 3^2 tai 9.
Kuinka se toimii?
Mukaan meidän algoritmi, vaiheet ovat seuraavat:
Vaihe 1) Ensimmäinen numero tai 1 on kohdassa (3/2, 3-1) tai (1, 2). Sopimuksen mukaan harkitse myöhempiä vaiheita varten x= 1 ja y= 2.
Vaihe 2) Muiden numeroiden sijainti lasketaan seuraavalla tavalla:
Numeron 2 sijainti:
Seuraava numero on kohdassa (x-1, y+1) tai (0, 3), mikä ei ole kelvollinen sijainti. Käyttämällä ehtoa (a) vastaava kelvollinen sijainti olisi (0,0). Joten x = 0, y = 0.
Numeron 3 sijainti:
Numero 3 on kohdassa (x-1, y+1) tai (-1, 1), mikä ei ole kelvollinen sijainti. Käytettäessä ehtoa (a) kelvollinen rivin sijainti olisi n-1 tai 2. Eli numero 3 on kohdassa (2, 1). Seuraavalle numerolle x= 2, y= 1.
Numeron 4 sijainti:
Numeron 4 tulee olla kohdassa (x-1, y+1) tai (1, 2), mikä on kelvollinen sijainti. Mutta se kanta sisältää jo numeron. Ehdon (b) mukaan kelvollinen sijainti olisi (1+1, 2-2) tai (2,0). Seuraavalle luvulle x = 2, y = 0.
Numeron 5 sijainti:
Numeron 5 tulee olla kohdassa (x-1, y+1) tai (1, 1), mikä on kelvollinen sijainti. Seuraavalle luvulle x = 1, y = 1.
Numeron 6 sijainti:
Numeron 6 tulee olla kohdassa (x-1, y+1) tai (0, 2), mikä on kelvollinen sijainti. Seuraavalle luvulle x = 0, y = 2.
Numeron 7 sijainti:
Numeron 7 tulee olla kohdassa (x-1, y+1) tai (-1, 3), mikä ei ole kelvollinen sijainti. Ehdon (c) mukaan kelvollinen sijainti olisi (0, n-2) tai (0, 1). Seuraavalle luvulle x = 0, y = 1.
Numeron 8 sijainti:
Numeron 8 tulee olla kohdassa (x-1, y+1) tai (-1, 2), mikä ei ole kelvollinen sijainti. Käyttämällä ehtoa (a) kelvollinen sijainti olisi (2, 2). Seuraavalle luvulle x= 2, y= 2.
Numeron 9 sijainti:
Numeron 9 tulee olla kohdassa (x-1, y+1) tai (1, 3), mikä ei ole kelvollinen sijainti. Käytettäessä ehtoa (a) kelvollinen sijainti olisi (1, 0).
Pseudokoodi
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++ Code Magic Square
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;
}
Esimerkin tulos:
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 Code 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)
Esimerkin tulos:
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
Monimutkaisuusanalyysi
- Avaruuden monimutkaisuus: Maagisen neliömatriisin ylläpitämiseksi tarvitsemme *n-taulukon. Joten avaruuden kompleksisuus olisi O(n^2).
- Ajan monimutkaisuus: Koodi, jota käytimme taikaneliöiden matematiikan luomiseen, koostuu kahdesta silmukasta. Ulompi silmukka kulkee n kertaa ja sisäsilmukka myös n kertaa. Lopulta aika monimutkaisuus on O(n^2).
