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

La méthode LUX de Conway pour les carrés magiques est, en mathématiques, un algorithme inventé par John Horton Conway pour créer des carrés magiques d'ordre $4n+2$, où $n\in \mathbb {N} ^{\star }$.

Méthode

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 1^re 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

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

Sources

• (en) Eric W. Weisstein, « Magic Square », sur MathWorld.
• (en) Martin Erickson, Aha! Solutions, Mathematical Association of America, coll. « Spectrum », 2009, 220 p. (ISBN 978-0-88385-829-5), p. 98-99 [lire en ligne].

Référence

(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).