Carrés gréco-latins : construire des carrés magiques par superposition

Les carrés magiques peuvent être construits par des recettes très visuelles : diagonales, symétries, compléments, permutations, déplacements en escalier. Mais il existe une voie plus combinatoire, plus abstraite, et pourtant très naturelle : partir de deux carrés latins, les superposer, puis traduire chaque paire de symboles en nombre.

Cette méthode est liée aux carrés gréco-latins, aussi appelés carrés latins orthogonaux. Elle donne une belle passerelle entre les carrés magiques récréatifs et des objets plus profonds de la combinatoire.

L’idée centrale est simple :

construire un premier carré latin ;
construire un second carré latin compatible avec le premier ;
superposer les deux grilles ;
convertir chaque paire obtenue en un nombre unique ;
vérifier que les lignes, les colonnes et les deux diagonales possèdent la même somme.

La subtilité se cache surtout dans la dernière étape : deux carrés latins orthogonaux donnent naturellement de bonnes lignes et de bonnes colonnes, mais ils ne garantissent pas automatiquement les diagonales d’un carré magique.

Rappel : qu’est-ce qu’un carré latin ?

Un carré latin d’ordre n est une grille n × n remplie avec n symboles, de sorte que chaque symbole apparaît exactement une fois dans chaque ligne et exactement une fois dans chaque colonne.

Par exemple, voici un carré latin d’ordre 5 construit par décalage cyclique :


0	1	2	3	4
1	2	3	4	0
2	3	4	0	1
3	4	0	1	2
4	0	1	2	3

Chaque ligne contient les symboles 0, 1, 2, 3, 4. Chaque colonne aussi.

Ce n’est pas encore un carré magique. C’est une grille d’organisation. Elle dit où placer des symboles, pas encore comment obtenir une somme constante avec les nombres de 1 à n².

Deux carrés latins orthogonaux

Deux carrés latins de même ordre sont dits orthogonaux lorsque leur superposition produit toutes les paires possibles une seule fois.

Si le premier carré contient les symboles A = 0, 1, 2, ..., n-1 et le second les symboles B = 0, 1, 2, ..., n-1, alors la superposition doit faire apparaître les n² couples :

(0,0), (0,1), ..., (0,n-1),
(1,0), (1,1), ..., (1,n-1),
...
(n-1,0), ..., (n-1,n-1)

Aucun couple ne doit manquer. Aucun couple ne doit se répéter.

Historiquement, le nom « gréco-latin » vient de la représentation d’Euler : un carré utilisait des lettres latines, l’autre des lettres grecques. La superposition donnait donc des couples du type Aα, Bβ, Cγ, etc.

De la paire au nombre

Une fois les deux carrés superposés, chaque case contient une paire (A, B). Pour fabriquer un carré numérique contenant les entiers de 1 à n², on peut utiliser la conversion :

nombre = n × A + B + 1

Cette formule est simplement une écriture en base n :

A indique le groupe de n nombres ;
B indique la position dans ce groupe ;
le + 1 permet de passer de 0...n²-1 à 1...n².

Pour n = 5, la paire (0,0) devient 1, la paire (0,1) devient 2, la paire (1,0) devient 6, la paire (4,4) devient 25.

Si les deux carrés sont orthogonaux, les 25 paires sont toutes différentes. On obtient donc les 25 nombres de 1 à 25, chacun une seule fois.

Pourquoi les lignes et les colonnes deviennent magiques

Dans chaque ligne d’un carré latin, les symboles 0, 1, 2, ..., n-1 apparaissent une fois chacun. Leur somme vaut :

0 + 1 + 2 + ... + (n-1) = n(n-1)/2

Dans une ligne du carré final, la partie A contient donc tous les symboles une fois, et la partie B aussi. La somme d’une ligne vaut alors :

n × n(n-1)/2 + n(n-1)/2 + n

Ce qui se simplifie en :

n(n² + 1)/2

C’est exactement la constante magique normale d’un carré d’ordre n contenant les nombres de 1 à n².

Pour n = 5, la constante magique vaut :

5 × (25 + 1) / 2 = 65

Le même raisonnement vaut pour les colonnes.

Ainsi, la superposition de deux carrés latins orthogonaux donne naturellement un carré semi-magique : toutes les lignes et toutes les colonnes ont la bonne somme.

La condition supplémentaire des diagonales

Un carré magique ordinaire exige aussi que les deux diagonales aient la même somme.

Or, un carré latin peut très bien être parfait sur les lignes et les colonnes, mais très mauvais sur une diagonale. Une diagonale peut même répéter plusieurs fois le même symbole.

Pour que la méthode gréco-latine produise un vrai carré magique, il faut donc une condition supplémentaire :

sur chacune des deux grandes diagonales, les symboles du premier carré latin doivent former une permutation complète, et les symboles du second carré latin doivent aussi former une permutation complète.

Autrement dit, chaque grande diagonale doit contenir tous les symboles dans la partie A et tous les symboles dans la partie B.

Cette remarque est importante : l’orthogonalité seule ne suffit pas toujours. Elle assure l’unicité des nombres. Elle assure les lignes et les colonnes. Mais elle ne garantit pas automatiquement les diagonales.

Une construction algébrique pour les ordres impairs premiers

Pour un ordre premier n, on peut construire des carrés latins à l’aide du calcul modulo n.

On numérote les lignes et les colonnes de 0 à n-1. On choisit deux formules linéaires :

A(i, j) = (a × i + b × j) mod n
B(i, j) = (c × i + d × j) mod n

Le premier carré est donné par A, le second par B.

Pour que la construction fonctionne bien, il faut éviter certains choix dégénérés :

les coefficients utilisés ne doivent pas annuler les lignes ou les colonnes ;
les deux carrés doivent être orthogonaux ;
les deux diagonales doivent rester des permutations complètes.

Une condition pratique pour l’orthogonalité est que le déterminant suivant ne soit pas nul modulo n :

a × d - b × c

Pour les diagonales, il faut aussi éviter que les coefficients associés aux deux diagonales s’annulent modulo n.

Cette formulation donne une méthode très compacte : on ne remplit pas la grille case par case ; on choisit une petite mécanique de déplacement, puis toute la grille se déploie.

Exemple complet : un carré magique d’ordre 5

Prenons n = 5, puis les deux carrés latins suivants :

A(i, j) = (i + 2j) mod 5
B(i, j) = (2i + j) mod 5

Le premier carré latin A est :


0	2	4	1	3
1	3	0	2	4
2	4	1	3	0
3	0	2	4	1
4	1	3	0	2

Le second carré latin B est :


0	1	2	3	4
2	3	4	0	1
4	0	1	2	3
1	2	3	4	0
3	4	0	1	2

Ces deux carrés sont orthogonaux : en les superposant, les 25 paires possibles apparaissent une seule fois.

En appliquant la formule nombre = 5 × A + B + 1, on obtient :

					Somme
1	12	23	9	20	65
8	19	5	11	22	65
15	21	7	18	4	65
17	3	14	25	6	65
24	10	16	2	13	65

Les colonnes donnent aussi 65 :

1 + 8 + 15 + 17 + 24 = 65
12 + 19 + 21 + 3 + 10 = 65
23 + 5 + 7 + 14 + 16 = 65
9 + 11 + 18 + 25 + 2 = 65
20 + 22 + 4 + 6 + 13 = 65

Et les deux diagonales :

1 + 19 + 7 + 25 + 13 = 65
20 + 11 + 7 + 3 + 24 = 65

Nous avons donc bien un carré magique normal d’ordre 5.

Pourquoi cet exemple marche

Dans l’exemple précédent, les coefficients ont été choisis pour éviter les répétitions sur les diagonales.

Pour A(i, j) = i + 2j, la grande diagonale principale correspond à j = i, donc :

A(i, i) = 3i mod 5

Comme 3 n’est pas nul modulo 5, les valeurs obtenues parcourent bien 0, 1, 2, 3, 4.

Pour l’autre diagonale, on a j = -i modulo 5, donc :

A(i, -i) = -i mod 5

Là encore, les valeurs parcourent tous les symboles.

Le même raisonnement s’applique au carré B(i, j) = 2i + j.

La magie du carré final vient donc de trois niveaux superposés :

chaque carré est latin ;
les deux carrés sont orthogonaux ;
les deux diagonales restent latines dans les deux couches.

Ce que la méthode donne automatiquement

La méthode gréco-latine est très puissante, mais il faut bien distinguer ce qu’elle garantit et ce qu’elle ne garantit pas.

Propriété	Garantie par deux carrés latins orthogonaux ?
Tous les nombres de `1` à `n²` sont présents une fois	Oui
Toutes les lignes ont la bonne somme	Oui
Toutes les colonnes ont la bonne somme	Oui
La diagonale principale a la bonne somme	Pas toujours
La diagonale secondaire a la bonne somme	Pas toujours
Le carré est pandiagonal ou associé	Non, sauf construction spéciale

C’est pour cette raison qu’un carré gréco-latin n’est pas automatiquement un carré magique complet. Il le devient lorsque les diagonales ont été prises en compte.

Les ordres pairs : un terrain plus délicat

Pour les ordres impairs premiers, la construction modulaire est très confortable. Pour les ordres impairs composés, on peut souvent s’appuyer sur des constructions dérivées, notamment lorsque l’ordre se décompose bien.

Pour les ordres pairs, l’histoire est plus subtile.

Euler savait construire des carrés gréco-latins pour de nombreux ordres, notamment les ordres impairs et les multiples de 4. En revanche, il avait conjecturé que les ordres de la forme 4k + 2 étaient impossibles. Le cas le plus célèbre est celui de l’ordre 6, connu sous le nom du problème des 36 officiers.

Le bilan moderne est plus nuancé :

il n’existe pas de paire de carrés latins orthogonaux d’ordre 2 ;
il n’en existe pas non plus d’ordre 6 ;
pour les autres ordres, il existe des carrés gréco-latins.

L’ordre 6 reste donc une exception célèbre : il existe des carrés magiques d’ordre 6, mais pas par superposition de deux carrés latins orthogonaux d’ordre 6.

Cette distinction est essentielle. Une impossibilité concernant les carrés gréco-latins n’est pas une impossibilité concernant tous les carrés magiques.

Lien avec les transversales

Dans un carré latin, une transversale est un choix de n cases contenant :

une case dans chaque ligne ;
une case dans chaque colonne ;
chaque symbole une seule fois.

Pour construire un second carré latin orthogonal au premier, on peut chercher n transversales disjointes. Chaque transversale devient alors une ligne, une colonne ou une classe du second carré.

Cette approche est particulièrement importante dans les ordres difficiles. Au lieu de remplir directement toute la grille, on cherche des chemins compatibles à l’intérieur du premier carré latin.

C’est une manière de transformer un problème massif en problème de sélection : trouver les bonnes transversales, puis les assembler sans conflit.

Une petite vérification en Python

Voici un court script pour vérifier qu’un carré est latin, que deux carrés sont orthogonaux, puis pour construire le carré numérique final.

def is_latin(square):
    n = len(square)
    expected = set(range(n))

    for row in square:
        if set(row) != expected:
            return False

    for j in range(n):
        col = {square[i][j] for i in range(n)}
        if col != expected:
            return False

    return True


def are_orthogonal(a, b):
    n = len(a)
    pairs = set()

    for i in range(n):
        for j in range(n):
            pairs.add((a[i][j], b[i][j]))

    return len(pairs) == n * n


def greco_latin_to_magic(a, b):
    n = len(a)
    return [[n * a[i][j] + b[i][j] + 1 for j in range(n)] for i in range(n)]


def sums(square):
    n = len(square)
    rows = [sum(row) for row in square]
    cols = [sum(square[i][j] for i in range(n)) for j in range(n)]
    diag_1 = sum(square[i][i] for i in range(n))
    diag_2 = sum(square[i][n - 1 - i] for i in range(n))
    return rows, cols, diag_1, diag_2


n = 5
A = [[(i + 2 * j) % n for j in range(n)] for i in range(n)]
B = [[(2 * i + j) % n for j in range(n)] for i in range(n)]
M = greco_latin_to_magic(A, B)

print("A latin :", is_latin(A))
print("B latin :", is_latin(B))
print("Orthogonaux :", are_orthogonal(A, B))

for row in M:
    print(row)

print(sums(M))

Ce test permet de séparer les trois questions :

les deux carrés sont-ils latins ?
sont-ils orthogonaux ?
le carré numérique final est-il vraiment magique, diagonales comprises ?

À retenir

La construction gréco-latine est l’une des plus belles méthodes de fabrication des carrés magiques, parce qu’elle remplace une grille apparemment mystérieuse par deux structures plus simples.

Un carré magique obtenu de cette manière n’est pas seulement une liste de nombres bien arrangés. C’est une superposition de deux systèmes de coordonnées.

Le premier carré latin contrôle une partie du nombre. Le second carré latin contrôle l’autre partie. L’orthogonalité garantit que chaque couple apparaît une seule fois. Les lignes et les colonnes deviennent automatiquement équilibrées. Les diagonales, elles, demandent une attention supplémentaire.

C’est là que cette méthode devient intéressante : elle montre que la magie d’un carré n’est pas seulement une question de somme. C’est aussi une question de circulation des symboles.

Pour poursuivre

Cette méthode complète naturellement l’article sur les carrés latins et prépare l’étude des carrés gréco-latins alternés, où l’on ne superpose plus seulement deux grilles latines simples, mais des structures alternées capables de produire des carrés plus riches.

Elle s’inscrit aussi dans le panorama général des méthodes de construction des carrés magiques.

Sources et prolongements

Gérard Villemin, « Carrés gréco-latins construction ».
Gérard Villemin, « Carrés magiques : gréco-latins alternés ».
Leonhard Euler, travaux historiques sur les carrés gréco-latins et le problème des 36 officiers.
R. C. Bose, S. S. Shrikhande et E. T. Parker, résultat moderne sur l’existence des carrés gréco-latins hors ordres 2 et 6.