Par Laurent VERHEIRSTRAETEN
Version du 26 mars 2003.
Prologue :
Il n’existe pas de formules toutes faites pour trouver des carrés magiques toutefois, il peut être possible de les fabriquer. Nous prendrons le cas des carrés normaux constitués des N² premiers entiers pour montrer la méthode.
But :
On souhaite pouvoir éviter de « deviner » chaque cellule du carré mais en calculer le maximum à partir du plus petit nombre possible. Pour parler clairement, pour un programme de calcul de carrés magiques qui utilise des boucles imbriquées, chaque boucle correspondant à une case du carré, on cherche à remplacer les boucles par une suite d’opérations permettant de calculer la valeur de la case à partir d’autres cases dont on connaît déjà la valeur.
Principe :
Les conditions nécessaires à la réalisation d’un carré magique peuvent être définies comme étant un système d’équations du premier degré à N² inconnues. En utilisant programme pour résoudre ce système, on pourra alors à partir d’un certains nombre de cases du carré obtenir les autres.
On définit d’abord qu’elle est la taille du carré que l’on désirera obtenir et l’on calcule sa constante magique. Ainsi pour l’ordre 3, nous aurons en appliquant la formule bien connue ;)
(N*(N²+1) 3*(9+1) 30
-------------- = ---------- = --- = 15
2 2 2
Nous considèrerons les cases du carré allant de c1 à c9, c1 étant la première case du carré en haut à gauche et c9 la dernière case du carré en bas à droite.
c1 c2 c3
c4 c5 c6
c7 c8 c9
Le système correspondant au carré magique est défini ainsi :
c1 + c2 + c3 = 15 // Ligne 1
c4 + c5 + c6 = 15 // Ligne 2
c7 + c8 + c9 = 15 // Ligne 3
c1 + c4 + c7 = 15 // Colonne 1
c2 + c5 + c8 = 15 // Colonne 2
c3 + c6 + c9 = 15 // Colonne 3
c1 + c5 + c9 = 15 // Diagonale Gauche / Droite
c3 + c5 + c7 = 15 // Diagonale Droite / Gauche
En utilisant un programme sachant résoudre ce système, on obtiendra les solutions pour les cases pouvant être calculées à partir des autres et des variables dites « indépendantes » qui devront être définies ou deviner dès le début.
Personnellement, j’utilise le logiciel MUpad 2.5 pour faire les calculs. Il a l’avantage d’être gratuit pour une utilisation personnelle. Vous pouvez le télécharger depuis le site web et obtenir une licence d’installation en entrant votre nom et en indiquant votre adresse email. Vous recevrez quelques minutes plus tard votre clé d’installation. Vous pouvez aussi utilisé un logiciel comme Mathématica ou Maple mais ils sont payants. Après résolution, on obtiendra les formules suivantes :
c3 = 15 – c1 – c2
c4 = 20 – c2 – (2*c1)
c5 = 5
c6 = -10 + c2 + ( 2 * c1 )
c7 = -5 + c2 + c1
c8 = 10 – c2
c9 = 10 – c1
c1 et c2 sont des variables indépendantes. On peut observer que ces 2 variables sont utilisées pour calculer les autres. Ainsi en prenant c1 = 4 et c2 = 3, on obtient :
c3 = 15 – 4 – 3 = 8
c4 = 20 – 3 – ( 2 * 4 ) = 9
c5 = 5
c6 = -10 + 3 + ( 2 * 4 ) = 1
c7 = -5 + 3 + 4 = 2
c8 = 10 – 3 = 7
c9 = 10 – 4 = 6
Le carré magique sera donc :
4 3 8
9 5 1
2 7 6
Ce qui prouve qu’avec 2 cases, nous pouvons obtenir les 7 autres. Pour le programme, il ne suffira donc que d’effectuer 2 boucles, d’où l’algorithme possible suivant :
pour c1 allant de 1 à 9 faire
pour c2 allant de 1 à 9 faire
c3 = 15 – c1 – c2
c4 = 20 – c2 – ( 2 * c1 )
c5 = 5
c6 = -10 + c2 + ( 2 * c1 )
c7 = -5 + c2 + c1
c8 = 10 – c2
c9 = 10 – c1
// Afficher le carré
fin pour
fin pour
Exemple avec l’ordre 4 :
c1 c2 c3 c4
c5 c6 c7 c8
c9 c10 c11 c12
c13 c14 c15 c16
La constante magique sera :
(N*(N²+1) 4*(16+1) 68
-------------- = ---------- = --- = 34
2 2 2
Le système d’équations correspondant sera :
c1 + c2 + c3 + c4 = 34 // Ligne 1
c5 + c6 + c7 + c8 = 34 // Ligne 2
c9 + c10 +c11 + c12 = 34 // Ligne 3
c13 + c14 + c15 + c16 = 34 // Ligne 4
c1 + c5 + c9 + c13 = 34 // Colonne 1
c2 + c6 + c10 + c14 = 34 // Colonne 2
c3 + c7 + c11 + c15 = 34 // Colonne 3
c4 + c8 + c12 + c16 =34 // Colonne 4
c1 + c6 + c11 + c16 = 34 // Diagonale Gauche / Droite
c4 + c7 + c10 + c13 = 34 // Diagonale Droite / Gauche
Après résolution on obtiendra :
c4 = 34 - c1 - c2 - c3
c8 = 34 - c5 – c6 - c7
c10 = -34 + c9 - c7 + c5 + c3 + c2 + (2 * c1 );
c11 = 68 - c9 - c6 - c5 - c3 - c2 - (2 * c1)
c12 = -c9 + c7 + c6
c13 = 34 - c1 - c5 - c9
c14 = 68 - c9 + c7 - c6 - c5 - c3 - ( 2 * c2 ) - ( 2 * c1)
c15 = -34 + c9 - c7 + c6 + c5 + c2 + ( 2 * c1)
c16 = -34 + c9 + c5 + c3 + c2 + c1
Les variables indépendantes seront donc c1, c2, c3 , c5 , c6, c7 et c9.
Il suffira donc de 7 cases (boucles) pour obtenir un carré de 16 cases.
Avec les valeurs suivantes :
c1 = 1 ; c2 = 2 ; c3 = 15 ; c5 = 13 ; c6 = 14 ; c7 = 3 ; c9 = 12
c4 = 34 - 1 - 2 - 15 = 16
c8 = 34 - 13 - 14 - 3 = 4
c10 = -34 + 12 - 3 + 13 + 15 + 2 + (2 * 1) = 7
c11 = 68 - 12 - 14 - 13 -15 - 2 - (2 * 1) = 10
c12 = -(12) + 3 + 14 = 5
c13 = 34 - 1 - 13 - 12 = 8
c14 = 68 - 12 + 3 - 14 -13 - 15 - ( 2 * 2) - ( 2 * 1) = 11
c15 = -34 + 12 - 3 + 14 + 13 + 2 + ( 2 * 1) = 6
c16 = -34 + 12 + 13 + 15 + 2 + 1 = 9
Nous obtenons le carré :
1 2 15 16 à partir des valeurs c1 c2 c3 **
13 14 3 4 c5 c6 c7 **
12 7 10 5 c9 ** ** **
8 11 6 9 ** = valeurs calculées ** ** ** **
Remarques :
Il se peut que les variables soient données dans un ordre autre que celui allant de la case haut/gauche à la case bas/droite. dans ce cas il suffit d’effectuer une rotation des variable pour essayer d’obtenir les variables indépendantes en début du carré. Si les variables indépendantes sont placées dans l’ordre et au début du carré vous obtiendrez les carrés dans l’ordre lexicographique. Si une variable indépendante n’est pas placée au début du carré ou si elle est entourées de variables dépendante les carrés ne seront pas générés pas dans l’ordre lexicographique. Dans certains cas, une ou des variables dépendantes se situe au début du carré mais elle fait appel a des variables dépendantes qui si on suit l’ordre des cases n’est pas encore calculer, il peut être préférable plutôt que d’essayer de la déplacer pas rotation de la remplacer par une boucle. Ceci augmentera le temps de calcul mais parfois cela sera la seule solution possible.
Avantages de cette
méthode :
1 er avantage : cette méthode peut s’appliquer à n’importe quel type de carré et de n’importe quel ordre dans la limite du raisonnable bien sûr. Cette méthode ne vous aidera pas à obtenir tous les carrés magiques normaux d’ordre 16 en 1 heure.
2 ème avantage de cette méthode est qu’elle permet de diminuer le nombre de boucles et donc le temps de calcul pour obtenir un carré. Dans le cas d’un carré normal simplement magique, il suffit d’obtenir par boucles environ l’équivalent de 2 lignes pour pouvoir remplir le reste du carré.
3 ème avantage : plus le carré que l’on souhaite obtenir est complexe plus le temps de calcul en sera diminué.
En effet plus vous ajoutez d’équations dans votre système, moins vous obtiendrez de variables indépendantes et donc moins de boucles. Par exemple nous avons vu que nous avions 7 boucles pour obtenir un carré simplement magique d’ordre 4, il n’en faut que 4 pour un carré pandiagonal.
4 ème avantage, les « formules » obtenues permettent d’obtenir tous les carrés magiques d’un même type. Avec les résultats obtenus précédemment vous pouvez construire tous les carrés simplement magiques d’ordre 4.
Inconvénients de cette
méthode :
1 er désavantage : il faut un certain travail de préparation avant d’entrer proprement dit dans la réalisation du programme. Il faut préparer le système d’équations et être très vigilant dans la rédactions des équations. Si vous vous trompez, les solutions générées pourront être fausses et vous n’obtiendrez jamais de bons carrés magiques et le nombres de solutions ne sera pas le bon ! Je vous conseille donc d’écrire un programme qui en entrant l’ordre vous donnera déjà les lignes, les colonnes et les 2 diagonales principales dans un fichier texte. Il ne vous restera plus qu’à faire un copier/coller dans le programme résolvant les équations ou de le modifier si besoin est.
2 ème désavantage : il faut un logiciel de maths pour résoudre les équations. Dès l’ordre 4, ça commence à devenir dur… à moins d’être très bon en maths… mais pour l’ordre 5 et supérieur, bon courage !
3 ème désavantage : il faut effectuer le travail « préparation / résolution d’équations / écriture du code du programme » pour chaque type de carré que l’on souhaite. Bien sûr en utilisant la routine pour les carrés simplement normaux et en affinant les conditions dans le programme, on pourra obtenir des carrés plus rares comme les pandiagonaux mais cela prendra beaucoup plus de temps en calcul que de faire le programme spécifique correspondant aux carrés pandiagonaux.
4 ème désavantage : dans certains cas les solutions des variables dépendantes ne peuvent être calculer dans l’ordre des cases, il faudra soit faire un compromis et remplacer la variable dépendantes par une boucle ou calculer les boucles des variables dans un ordre différent de celui des cases dans le carré. Dans ce cas, il faudra replacer les cases dans le bon ordre lors de la génération de la solution.
Informations pour les
programmeurs :
Les variables contenant les cases du carré devront pouvoir être négative et positive.
Pendant les calculs, il se peut qu’à un moment la valeur de la case soit négative et qu’elle ne prenne une valeur positive qu’à la fin du calcul. Si vous mettez que des variables d’un type obligatoirement positif, les valeurs seront tronqués et donc vous obtiendrez des valeurs fausses et /ou votre programme plantera avec un dépassement de valeurs ou de pile.
Conclusion :
Nous avons vu le principe, les avantages et les inconvénients de cette méthode basée sur la résolution du carré magique en tant que système d’équations. Libre à vous d’essayer cette méthode pour générer des carrés magiques de certains types en l’implémentant dans le langage de votre choix et en effectuant des optimisations. Cette méthode peut être utilisée pour créer des carrés multimagiques. Dans le cas de carrés bimagiques, le sytème se présentera sous la forme d’un système du second degré à n² inconnues.
Même si la mise en œuvre est un peu compliquée, je vous assure que cette méthode vous donnera rapidement des résultats si vous l’implémenter sur des kits de développement de type Delphi, Borland ou Visual C++ ou Visual Basic.
En souhaitant que ce document vous aura fourni une piste d’investigation pour trouver de nombreux carrés magiques…
Laurent VERHEIRSTRAETEN
RETOUR A www.kandaki.com (Téléchargements)