carré latin

Imaginez une grille de quatre lignes et quatre colonnes à remplir avec quatre symboles : A, B, C et D. Dans chaque ligne, chacun doit apparaître une fois. La même règle vaut dans chaque colonne. Répéter un A oblige donc à déplacer ou remplacer l'un des deux A.

La grille achevée est un carré latin d'ordre 4. Le mot « carré » décrit sa forme ; « latin » n'impose ni lettres ni nombres particuliers. Seule compte la répartition régulière des quatre symboles.

Un carré latin d'ordre n est une grille de n lignes et n colonnes remplie avec un ensemble de n symboles. Pour chaque symbole, chaque ligne contient exactement une occurrence et chaque colonne contient exactement une occurrence. Les symboles peuvent être des lettres, des nombres ou d'autres marques : leurs noms n'interviennent pas dans la propriété.

Si les lignes et les colonnes sont numérotées de 0 à n − 1, une construction cyclique consiste à placer dans la case de ligne i et de colonne j le symbole numéroté par le reste de i + j dans la division par n. Elle s'écrit : $L_{i,j}=(i+j)nL\_\{i,j\}=(i+j)\backslash bmod\; n$. Quand j parcourt une ligne, ou quand i parcourt une colonne, tous les restes de 0 à n − 1 apparaissent une fois.

Cette construction donne un carré latin pour tout entier n au moins égal à 1, mais tous les carrés latins ne sont pas nécessairement présentés sous cette forme. Une table de multiplication d'un groupe fini est un carré latin. Plus généralement, tout carré latin peut être lu comme la table d'une opération de quasigroupe après avoir étiqueté ses lignes, ses colonnes et ses symboles par le même ensemble.

Construisons un carré latin d'ordre 4. Les données sont quatre lignes, quatre colonnes et les symboles A, B, C et D, associés respectivement aux restes 0, 1, 2 et 3. La case de ligne i et de colonne j reçoit le reste de i + j dans la division par 4.

1. Plaçons A, B, C, D sur la première ligne : les sommes 0 + j donnent successivement les restes 0, 1, 2, 3.

2. Décalons ce motif d'une place vers la gauche à chaque nouvelle ligne. Les quatre lignes deviennent A B C D, puis B C D A, puis C D A B, puis D A B C. La construction cyclique complète est ainsi entièrement déterminée.

3. Contrôlons une colonne, par exemple la troisième : elle contient C, D, A, B. Chacun des quatre symboles y apparaît exactement une fois. Le même contrôle réussit pour les trois autres colonnes.

4. Le tableau obtenu est donc un carré latin d'ordre 4. Un contrôle refaisable consiste à compter, pour chaque lettre, quatre occurrences au total : une dans chacune des quatre lignes et une dans chacune des quatre colonnes.

Pour vérifier une grille candidate, choisissez un symbole et parcourez d'abord toutes les lignes, puis toutes les colonnes. Si une ligne ou une colonne contient ce symbole deux fois, la grille n'est pas latine. Répétez ce contrôle pour chacun des symboles : il convient mieux qu'une simple inspection globale, qui peut masquer une répétition.

Pour construire rapidement un exemple, la règle cyclique est une alternative sûre aux essais successifs. Écrivez les n symboles dans la première ligne, puis effectuez le même décalage circulaire à chaque ligne suivante. Le retour du premier symbole après le dernier rend le motif observable.

Dans un sudoku, le contrôle latin porte sur les neuf lignes et les neuf colonnes. Il ne suffit toutefois pas pour valider la grille : il faut aussi contrôler les neuf régions de 3 × 3. Le critère des régions indique quand employer les règles complètes du sudoku plutôt que celles du seul carré latin.

Un carré latin et un sudoku. Un carré latin impose une occurrence de chaque symbole par ligne et par colonne. Un sudoku ajoute la même contrainte dans chacune de ses régions. Une grille 9 × 9 peut donc être latine tout en répétant un chiffre dans une région de 3 × 3 : elle n'est alors pas un sudoku valide.

Un carré latin et un carré magique. Le carré latin porte sur la fréquence des symboles dans les lignes et les colonnes. Le carré magique porte sur l'égalité de sommes numériques. Remplacer A, B, C, D par 1, 2, 3, 4 dans l'exemple donne toujours 10 par ligne et colonne, mais les deux diagonales valent 8 et 16 : ce n'est pas un carré magique.

L'ordre 1 n'est pas exclu. Une grille réduite à une seule case et à un seul symbole satisfait la définition. Son apparence triviale ne justifie pas de fixer arbitrairement n à 2 ou davantage.

Le comptage global ne suffit pas. Dans une grille d'ordre 4, quatre A au total ne garantissent rien s'ils occupent deux fois la même ligne. Il faut contrôler séparément l'unicité dans chacune des quatre lignes et chacune des quatre colonnes.

La forme cyclique n'est pas la définition. Le décalage régulier construit le carré de l'exemple, mais la propriété latine exige seulement une occurrence par ligne et par colonne. Face à un motif non cyclique, il faut donc appliquer ce test plutôt que rechercher un décalage.

Une table latine n'est pas forcément une table de groupe. Elle définit une opération de quasigroupe, car chaque équation où un seul facteur est inconnu possède une solution unique. Pour obtenir un groupe, il faut en plus une opération associative, un élément neutre et des inverses.

Le glossaire consacré au sudoku montre comment les contraintes de régions s'ajoutent à celles des lignes et des colonnes.

L'article Cheminement combinatoire prolonge l'étude des configurations discrètes et des méthodes de dénombrement.

L'article Les débuts des groupes replace les structures algébriques évoquées par les tables de multiplication dans leur histoire mathématique.