Méthode LUX de Conway pour les carrés magiques

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

En mathématiques, la méthode LUX de Conway pour les carrés magiques est un algorithme pour la création de carrés magiques d'ordre 4n + 2, où n \in \N et n \ge 1.

Méthode[modifier | modifier le code]

On commence par créer un tableau de 2n+1 cases de côté, en le remplissant comme suit, de haut en bas :

  • n+1 lignes de L.
  • 1 ligne de U.
  • n-1 ligne(s) de X.

Puis, on échange le U au milieu de sa ligne avec le L qui le surplombe.

Chaque lettre représentera, dans le carré magique final d'ordre 4n+2, un bloc carré de 4 cases.

On construit ensuite le tableau final, puis on le parcourt en suivant les cases du tableau « LUX » selon la méthode dite de Siam, permettant de créer de carrés magiques d'ordre impair (or, 2n+1 est impair) :

  • On commence par le milieu de la 1re ligne. Puis, à chaque itération, en revenant par le bas ou la gauche du carré quand les bords haut ou droit sont dépassés :
  • Si la case juste en haut à droite est libre, on s'y déplace.
  • Sinon, on se déplace dans la case juste au-dessous de la case actuelle.

On effectue donc ces déplacements sur le tableau « LUX ». À chaque arrivée dans une case de celui-ci, on se reporte ensuite au carré magique final, en repérant les 4 cases correspondant à la case unique de « LUX ». On remplit ensuite ces 4 cases avec les entiers croissants, suivant directement les 4 entiers placés dans le bloc de 4 cases précédent. À noter que le tout premier nombre placé dans le carré magique est 1. L'ordre croissant des 4 entiers remplissant un bloc de 4 cases est déterminé par la lettre présente dans « LUX », en relation avec les schémas de construction suivants :

\mathrm{L}: \quad \begin{smallmatrix}4&&1\\&\swarrow&\\2&\rightarrow&3\end{smallmatrix} \qquad \mathrm{U}: \quad \begin{smallmatrix}1&&4\\\downarrow&&\uparrow\\2&\rightarrow&3\end{smallmatrix} \qquad \mathrm{X}:\quad \begin{smallmatrix}1&&4\\&\searrow\!\!\!\!\!\!\nearrow&\\3&&2\end{smallmatrix}

Exemple[modifier | modifier le code]

Prenons par exemple n = 2. Le tableau « LUX » est de côté 5 :

L L L L L
L L L L L
L L U L L
U U L U U
X X X X X

On peut ainsi construire un carré magique d'ordre 10 :

68 65 96 93 4 1 32 29 60 57
66 67 94 95 2 3 30 31 58 59
92 89 20 17 28 25 56 53 64 61
90 91 18 19 26 27 54 55 62 63
16 13 24 21 49 52 80 77 88 85
14 15 22 23 50 51 78 79 86 87
37 40 45 48 76 73 81 84 9 12
38 39 46 47 74 75 82 83 10 11
41 44 69 72 97 100 5 8 33 36
43 42 71 70 99 98 7 6 35 34

Référence[modifier | modifier le code]

(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Conway's LUX method for magic squares » (voir la liste des auteurs).