Magic Square – Résolvez un puzzle 3 × 3 en utilisant C & Python Exemples
Sarah Chen
Qu'est-ce que le Carré Magique ?
Un carré magique est une matrice carrée avec une disposition numérique spéciale. Ces nombres sont disposés de manière à ce que la somme des nombres sur chaque diagonale, ligne et colonne reste la même. Les jeux de carrés magiques sont de simples énigmes logiques utilisées en mathématiques récréatives.
Exemple de carrés magiques :
Le diagramme ci-dessus est un exemple de carré magique d’ordre 3. La somme de chaque diagonale, ligne et colonne est de 15.
Comment fonctionne Carré Magique
Les carrés magiques sont des matrices n*n constituées de n^2 entiers positifs. Le nombre de lignes ou de colonnes d’une matrice carrée est appelé l’ordre de la matrice.
En règle générale, les puzzles de carrés magiques ont des ordres impairs et portent les nombres entiers de 1 à n^2. La somme de chaque diagonale, ligne et colonne est la même. Ce nombre est appelé somme magique ou constante magique. Généralement, cette somme magique dépend de l’ordre de la matrice. La formule des carrés magiques pour la somme magique d'ordre n est-
Prenons l'exemple d'un carré magique avec des entiers 3. Ainsi, la somme magique serait-
Pourquoi s'appelle-t-on Magic ?
Les mathématiciens de l’Antiquité étaient fascinés par la nature de plusieurs combinaisons intéressantes de nombres. Le carré magique en faisait partie. Les premières preuves de carrés magiques remontent à la Chine en 190 avant notre ère.
Certaines études montrent des preuves de l'existence du puzzle des carrés magiques dans l'ancien Japon, en Inde et en Arabie. Sur la base de certaines légendes, on supposait que ces formations spéciales de nombres étaient liées au monde magique. Par conséquent, ces carrés ont été appelés carrés magiques.
Types de carrés magiques
Il existe différentes variantes mathématiques des carrés magiques –
- Carré magique normal : Ce type de carré magique contient les n^2 premiers nombres.
- Carré semi-magique : Dans ce type, seules les lignes et la colonne totalisent la constante magique.
- Carré magique simple : Contrairement au type précédent, les lignes, les colonnes et les deux diagonales totalisent la constante magique.
- Le carré magique le plus parfait : Il s’agit d’un carré magique normal doté de deux propriétés spéciales. Ici, chaque sous-carré 2 x 2 de la matrice totalise 2 (n ^ 2 + 1). Et toute paire de nombres distants de n/2 carrés de la grille totalise n^2+1.
En fonction des propriétés, il existe de nombreux autres types de carrés magiques. Mais chaque fois que nous mentionnons simplement le carré magique, nous supposons qu’il s’agit d’un carré magique simple et normal d’ordre impair.
Algorithme pour générer un carré magique
L'algorithme pour générer des carrés magiques d'ordre impair est le suivant :
- Le premier nombre ou 1 sera stocké à (n/2, n-1), où la première coordonnée est la position de la ligne et la deuxième coordonnée est la position de la colonne. Pour les étapes ultérieures, notons cette position par (x, y).
- Les prochains nombres seront stockés à (x-1, y+1). Si le poste n'est pas valide, nous considérerons les conditions suivantes.
- Si la position de la ligne est -1, elle se déformera en n-1. De même, si la position calculée de la colonne est n, elle passera à 0.
- La position de la ligne sera incrémentée de 1 et la position de la colonne sera décrémentée de 2 si la position calculée contient déjà un nombre.
- Si la position de la ligne est -1 et la position de la colonne correspondante est n, la nouvelle position sera (0, n-2.
Remarque : Cet algorithme génère uniquement des carrés magiques valides d'ordre impair. Nous considérons également ce carré magique comme un carré magique normal avec les n^2 premiers nombres. De plus, il peut y avoir plusieurs solutions pour la même valeur de n.
Prenons un exemple et voyons comment cela fonctionne. Disons que nous voulons trouver le carré magique d'ordre 3. Comme ce sera un carré magique simple et normal d'ordre impair, il contiendra tous les nombres de 1 à 3^2 ou 9.
Comment cela fonctionne?
Selon nos algorithme, les étapes seront les suivantes :
Étape 1) Le premier chiffre ou 1 sera à la position (3/2, 3-1) ou (1, 2). Par convention, considérons x= 1 et y= 2 pour les étapes ultérieures.
Étape 2) La position du reste des nombres sera calculée de la manière suivante :
Position du numéro 2 :
Le numéro suivant sera à (x-1, y+1) ou (0, 3), ce qui n'est pas une position valide. En utilisant la condition (a), la position valide correspondante serait (0,0). Donc, x= 0, y= 0.
Position du numéro 3 :
Le numéro 3 sera à (x-1, y+1) ou (-1, 1), ce qui n'est pas une position valide. En utilisant la condition (a), la position de ligne valide serait n-1 ou 2. Ainsi, le numéro 3 sera à (2, 1). Pour le nombre suivant, x= 2, y= 1.
Position du numéro 4 :
Le numéro 4 doit être à (x-1, y+1) ou (1, 2), ce qui est une position valide. Mais cette position contient déjà un chiffre. Selon la condition (b), la position valide serait (1+1, 2-2) ou (2,0). Pour le nombre suivant x= 2, y= 0.
Position du numéro 5 :
Le numéro 5 doit être à (x-1, y+1) ou (1, 1), ce qui est une position valide. Pour le nombre suivant x= 1, y= 1.
Position du numéro 6 :
Le numéro 6 doit être à (x-1, y+1) ou (0, 2), ce qui est une position valide. Pour le nombre suivant x= 0, y= 2.
Position du numéro 7 :
Le numéro 7 doit être à (x-1, y+1) ou (-1, 3), ce qui n'est pas une position valide. Selon la condition (c), la position valide serait (0, n-2) ou (0, 1). Pour le nombre suivant x= 0, y= 1.
Position du numéro 8 :
Le numéro 8 doit être à (x-1, y+1) ou (-1, 2), ce qui n'est pas une position valide. En utilisant la condition (a), la position valide serait (2, 2). Pour le nombre suivant x= 2, y= 2.
Position du numéro 9 :
Le numéro 9 doit être à (x-1, y+1) ou (1, 3), ce qui n'est pas une position valide. En utilisant la condition (a), la position valide serait (1, 0).
Pseudo-code
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 Carré Magique
Entrées :
/*
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;
}
Sortie de l'exemple :
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 Carré Magique
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)
Sortie de l'exemple :
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
Analyse de complexité
- Complexité de l'espace: Pour conserver la matrice du carré magique, nous avons besoin d’un tableau*n. Ainsi, la complexité spatiale serait O(n^2).
- Complexité temporelle: Le code que nous avons utilisé pour générer les mathématiques des carrés magiques se compose de deux boucles. La boucle externe s'exécute n fois et la boucle interne s'exécute également n fois. En fin de compte, la complexité temporelle est O(n^2).