Comment résoudre un carré magique 3×3 en C et Python

Qu'est-ce qu'un carré magique ?

Un carré magique est une matrice carrée dont les nombres sont agencés d'une manière particulière. Les valeurs sont placées de sorte que la somme de chaque ligne, de chaque colonne et des deux diagonales principales reste la même. Les carrés magiques sont des énigmes logiques simples utilisées en mathématiques récréatives.

Exemple de carrés magiques :

Le diagramme ci-dessus représente un carré magique d'ordre 3. La somme de chaque diagonale, ligne et colonne est égale à 15. La section suivante explique comment ce total constant est obtenu.

Comment fonctionnent les carrés magiques ?

Un carré magique d'ordre n est une matrice n x n contenant n² entiers positifs. Le nombre de lignes ou de colonnes est appelé l'ordre de la matrice.

Les carrés magiques classiques ont un ordre impair et utilisent les entiers de 1 à n². Puisque la somme de chaque ligne, colonne et diagonale doit être identique, cette valeur est appelée somme magique ou constante magique. Cette constante ne dépend que de n. La formule de la somme magique d'ordre n est :

Considérons un carré magique d'ordre 3. La somme magique est alors :

Cette formule explique le calcul, mais le casse-tête possède une longue histoire culturelle qui lui donne son nom mémorable.

Pourquoi les appelle-t-on magie ?

Les mathématiciens de l'Antiquité étaient fascinés par les combinaisons de nombres intéressantes, et le carré magique en était une. Les premières traces remontent à la Chine, vers 190 avant notre ère.

Des études ont mis en évidence l'existence de carrés magiques dans le Japon, l'Inde et l'Arabie antiques. Des légendes associaient ces configurations au monde de la magie, et le nom est resté. Au-delà du folklore, les mathématiciens ont également défini des catégories formelles permettant de distinguer un carré d'un autre.

Types de carrés magiques

Il existe plusieurs variantes de carrés magiques en mathématiques :

• Carré magique normal : Contient les n² premiers nombres naturels.
• Carré semi-magique : Seules les lignes et les colonnes s'additionnent pour donner la constante magique.
• Carré magique simple : La somme des lignes, des colonnes et des deux diagonales principales est égale à la constante magique.
• Le carré magique le plus parfait : Un carré magique normal avec deux propriétés supplémentaires. Chaque sous-carré 2x2 de la matrice a une somme égale à 2(n²+1), et toute paire de nombres séparés par n/2 cellules a une somme égale à n²+1.

Il existe d'autres catégories, basées sur des propriétés supplémentaires. Dans ce tutoriel, lorsque le terme « carré magique » est utilisé sans autre précision, il désigne un carré magique simple, normal et d'ordre impair.

Algorithme pour générer un carré magique

L'algorithme classique pour générer un carré magique d'ordre impair, appelé méthode siamoise, est le suivant :

• Le premier nombre (1) est stocké à la position (n/2, n-1), où la première coordonnée correspond à l'indice de ligne et la seconde à l'indice de colonne. Pour la suite, nous appellerons cette position (x, y).
• Le nombre suivant est placé à la position (x-1, y+1). Si cette position est invalide, appliquez les règles suivantes :
  1. Si l'indice de ligne est -1, revenez à n-1. Si l'indice de colonne est n, revenez à 0.
  2. Si la position calculée contient déjà un nombre, incrémentez la ligne de 1 et décrémentez la colonne de 2.
  3. Si la ligne est -1 et la colonne est n en même temps, la nouvelle position est (0, n-2).

À noter: Cet algorithme ne génère que des carrés magiques valides d'ordre impair. Le résultat est un carré magique normal contenant les n² premiers nombres naturels. Il peut exister plusieurs solutions valides pour une même valeur de n.

Les règles deviennent plus claires grâce à un petit exemple avec l'ordre 3, qui utilise les nombres de 1 à 9.

Comment ça fonctionne sur un carré de 3 par 3

Application de algorithme Ci-dessus, les étapes sont les suivantes :

Étape 1) Le premier nombre (1) est placé en (3/2, 3-1) ou (1, 2). Pour les étapes suivantes, définissez x = 1 et y = 2.

Étape 2) Les positions des nombres restants sont calculées comme suit.

Position du numéro 2 :

Le nombre suivant devrait être (x-1, y+1) ou (0, 3), ce qui n'est pas une position valide. D'après la règle (a), la colonne revient à 0, ce qui donne (0, 0). On pose donc x = 0 et y = 0.

Position du numéro 3 :

Le nombre 3 devrait se trouver en (x-1, y+1) ou (-1, 1), ce qui n'est pas une position valide. D'après la règle (a), la ligne se répète jusqu'à n-1 (soit 2). Le nombre 3 se trouve donc en (2, 1). On pose x = 2 et y = 1.

Position du numéro 4 :

Le nombre 4 devrait se trouver en (x-1, y+1) ou (1, 2), ce qui est valide mais contient déjà 1. D'après la règle (b), la nouvelle position est (1+1, 2-2) ou (2, 0). On pose x = 2 et y = 0.

Position du numéro 5 :

Le nombre 5 devrait se trouver en (x-1, y+1) ou (1, 1), qui est une position vide valide. Définissez x = 1, y = 1.

Position du numéro 6 :

Le nombre 6 devrait se trouver en (x-1, y+1) ou (0, 2), qui est une position vide valide. Définissez x = 0, y = 2.

Position du numéro 7 :

Le nombre 7 devrait se trouver en (x-1, y+1) ou (-1, 3), ce qui est incorrect. D'après la règle (c), sa nouvelle position est (0, n-2) ou (0, 1). On pose donc x = 0 et y = 1.

Position du numéro 8 :

Le nombre 8 devrait se trouver aux coordonnées (x-1, y+1) ou (-1, 2), ce qui n'est pas valide. D'après la règle (a), la ligne se termine par 2, ce qui donne (2, 2). On pose donc x = 2 et y = 2.

Position du numéro 9 :

Le chiffre 9 devrait se trouver aux coordonnées (x-1, y+1) ou (1, 3), ce qui n'est pas valide. D'après la règle (a), la colonne revient à 0, ce qui donne (1, 0).

Une fois chaque cellule remplie, la même logique se traduit directement en pseudo-code.

Pseudo-code du carré magique

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

Le pseudo-code correspond directement aux langages compilés et interprétés, présentés ci-après dans C++ et Python.

C++ Code pour le 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

Le Python La version ci-dessous utilise des règles de lignes et de colonnes identiques.

Python Code pour le 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

Les deux implémentations se comportent de manière identique, ce qui facilite la comparaison de leur coût.

Analyse de complexité

• Complexité de l'espace: Le carré magique est stocké dans un tableau n par n, donc la complexité spatiale est O(n²).
• Complexité temporelle: Le générateur utilise deux boucles imbriquées. La boucle externe s'exécute n fois, et la boucle interne s'exécute également n fois, donc la complexité temporelle globale est O(n²).

FAQ