Carré Latin

Un carré latin est un carré de taille $ n \times n $ rempli avec exactement $ n $ symboles distincts (lettres, chiffres, nombres) de manière à ce que chaque symboles n'apparaissent qu'une seule fois par ligne et par colonne.

Il existe plusieurs méthode de génération des carrés latin. Voici la plus courte à expliquer :

1- Prendre une grille de NxN vide,

2- Remplir la première ligne avec N symboles

3- Remplir la ligne suivante en décalant tous les symboles de 1 case vers la droite (et revenir au début de la ligne si nécessaire)

4- Répéter l'étape 3 jusqu'à atteindre la dernière ligne de la grille.

Et voilà. Le carré est ainsi valide mais toujours identique, pour en obtenir d'autres :

5- Permuter aléatoirement 2 lignes

6- Permuter aléatoirement 2 colonnes

7- Répéter les étapes 5 et 6 autant de fois que désiré, le résultat est toujours un carré latin.

L'algorithme de résolution consiste à noter, pour chaque case non remplie, la liste des symboles possibles en respectant les règles (interdiction de 2 symboles identiques sur une même ligne ou une même colonne), si un seul symboles parmi les N est possible alors remplir la case avec ce symbole.

Le nom de carré latin vient de Leonard Euler qui a étudié ces grilles et qui utilisait comme symboles des lettres latines.

La variante la plus connue est le sudoku, qui reprend les mêmes bases, mais ajoute une contrainte sur les blocs de 3x3 (et parfois d'autres contraintes pour les sudoku irréguliers).

Le ken-ken (kendoku) est aussi un carré latin avec des contraintes de calculs mathématiques.

Le carré magique est une variante mathématique lointaine qui reprend le fait que la sommes des lignes et des colonnes est toujours identiques, mais il ne se limite pas à N symboles distincts.

Le nombre de carrés latins possibles augmente rapidement avec la taille de $ N $. Pour $ N = 3 $, il existe 12 carrés latins différents, pour $ N = 4 $, il y en a 576, puis 161280 pour 5, 812851200 pour 6 etc. pour des tailles plus grandes, ce nombre devient exponentiel, voir ici

Aucune formule directe pour trouver ces nombres n'est connue à ce jour.

Les premières traces écrites de travaux sur ces grilles datent de 1700, mais le principe lui-même était connu bien avant, peut-être même de l'antiquité.