carré eulérien

Imaginez deux grilles carrées de même taille, remplies avec deux séries de symboles. Dans chacune, chaque symbole apparaît une fois par ligne et une fois par colonne. On pose ensuite les grilles l’une sur l’autre : chaque case reçoit un couple de symboles.

La superposition forme un carré eulérien si aucun couple ne se répète. Dans une grille d’ordre 3, les neuf cases doivent donc présenter les neuf associations possibles entre les trois symboles de chaque série.

Un carré eulérien d’ordre n, aussi appelé carré gréco-latin, est la superposition de deux carrés latins d’ordre n. Chaque carré emploie n symboles et place chacun d’eux exactement une fois dans chaque ligne et chaque colonne. Dans chaque cellule, le premier symbole vient du premier carré et le second du second carré.

La condition décisive est que les n² couples obtenus soient tous distincts. Les deux carrés latins sont alors dits orthogonaux. L’appellation « gréco-latin » vient des premiers exemples, qui distinguaient les deux séries par des lettres grecques et latines. Les symboles choisis n’ont toutefois aucune incidence sur la propriété.

Si les deux carrés latins sont en outre diagonaux, c’est-à-dire si chaque symbole apparaît une fois sur chacune de leurs deux grandes diagonales, leur superposition est dite diagonale. Des carrés eulériens existent pour tous les ordres, sauf 2 et 6.

Prenons deux carrés latins d’ordre 3. Le premier contient les lignes 1–2–3, 2–3–1 et 3–1–2. Le second contient les lignes A–B–C, C–A–B et B–C–A. Chaque chiffre et chaque lettre apparaît une fois par ligne et par colonne.

1. Superposons les premières cases : 1 et A donnent le couple (1, A).
2. Faisons de même cellule par cellule. La première ligne devient (1, A), (2, B), (3, C).
3. Les deux autres lignes deviennent (2, C), (3, A), (1, B), puis (3, B), (1, C), (2, A).

Le résultat contient 3² = 9 couples. Pour le contrôler, fixons un chiffre : 1 est associé une fois à A, une fois à B et une fois à C. Le même contrôle réussit pour 2 et 3 ; aucun des neuf couples possibles ne manque ni ne se répète. Les trois grilles rendent cette superposition vérifiable cellule par cellule.

Pour construire un petit exemple, commencez par deux carrés latins de même ordre. Superposez-les, puis barrez chaque couple déjà rencontré. Si une répétition apparaît, modifiez la structure de l’un des carrés ou permutez ses lignes ou ses colonnes par rapport à l’autre avant de recommencer le contrôle. Une simple permutation de ses symboles ne change pas le motif des répétitions.

Pour vérifier une grille donnée, contrôlez d’abord séparément la propriété latine des deux composantes. Comptez ensuite les couples : il doit y en avoir n² distincts. Ce second test est indispensable, car deux carrés peuvent être latins sans être orthogonaux.

Pour organiser deux facteurs ayant chacun n modalités, un carré eulérien répartit chaque association une seule fois dans la grille. Si seul l’un des deux facteurs doit être équilibré, un carré latin suffit ; l’orthogonalité répond au besoin supplémentaire de distinguer tous les couples.

Un carré latin ne contient qu’une série de n symboles. Le carré eulérien en superpose deux et exige que leurs n² couples soient distincts. Une grille 3 × 3 remplie par 1, 2 et 3 peut donc être latine sans constituer à elle seule un carré eulérien.

Un sudoku impose aussi l’unicité des symboles dans des régions supplémentaires, généralement des blocs. Ce découpage ne définit pas un carré eulérien : le critère à tester ici est la non-répétition des couples issus de deux carrés latins.

Ordres impossibles. Il n’existe aucun carré eulérien d’ordre 2 ni d’ordre 6. Chercher plus longtemps ou changer les symboles ne lève pas ce blocage ; il faut choisir un autre ordre.

Deux carrés latins ne suffisent pas. Si un même couple apparaît deux fois, certaines autres associations sont nécessairement absentes. Les composantes restent éventuellement latines, mais elles ne sont pas orthogonales et leur superposition n’est pas eulérienne.

Diagonal ne signifie pas seulement « lisible en diagonale ». Pour employer cette variante, chacun des deux carrés latins superposés doit avoir chaque symbole exactement une fois sur chacune de ses deux grandes diagonales. Sans ce double contrôle, le carré eulérien ne peut pas être qualifié de diagonal.

Le carré latin permet d’étudier séparément la règle qui organise chaque composante avant d’aborder leur orthogonalité.

Le sudoku montre une autre manière d’imposer des contraintes d’unicité à une grille et aide à distinguer les structures.