Outil pour créer ou résoudre des carrés latins, une grille carrée de NxN avec N symboles distincts répartis sans répétition dans chaque ligne et colonne, idéale pour les amateurs de logique et de puzzles similaires au sudoku.
Carré Latin - dCode
Catégorie(s) : Jeux de Nombres
dCode est gratuit et ses outils sont une aide précieuse dans les jeux, les maths, les énigmes, les géocaches, et les problèmes à résoudre au quotidien !
Une suggestion ? un problème ? une idée ? Écrire à dCode !
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.
Exemple : Un carré latin 3x3 :
1 | 2 | 3 |
3 | 1 | 2 |
2 | 3 | 1 |
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,
Exemple :
- | - | - |
- | - | - |
- | - | - |
2- Remplir la première ligne avec N symboles
Exemple :
A | B | C |
- | - | - |
- | - | - |
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)
Exemple :
A | B | C |
C | A | B |
- | - | - |
4- Répéter l'étape 3 jusqu'à atteindre la dernière ligne de la grille.
Exemple :
A | B | C |
C | A | B |
B | C | A |
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.
Il existe des variantes de carrés latins avec des contraintes supplémentaires, telles que les carrés latins diagonaux où chaque symbole doit également être unique sur les deux grandes diagonales de la grille.
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é.
dCode se réserve la propriété du code source pour "Carré Latin". Sauf code licence open source explicite (indiqué Creative Commons / gratuit), l'algorithme pour "Carré Latin", l'applet ou snippet (convertisseur, solveur, chiffrement / déchiffrement, encodage / décodage, encryptage / décryptage, traducteur) ou les fonctions liées à "Carré Latin" (calculer, convertir, résoudre, décrypter / encrypter, déchiffrer / chiffrer, décoder / encoder, traduire) codés en langage informatique (Python, Java, C#, PHP, Javascript, Matlab, etc.) ou les données, en téléchargement, script, ou les accès API à "Carré Latin" ne sont pas publics, idem pour un usage hors ligne, PC, mobile, tablette, appli iPhone ou Android !
Rappel : dCode est gratuit.
Le copier-coller de la page "Carré Latin" ou de ses résultats est autorisée (même pour un usage commercial) tant que vous créditez dCode !
L'exportation des résultats sous forme de fichier .csv ou .txt est gratuite en cliquant sur l'icone export
Citer comme source bibliographique :
Carré Latin sur dCode.fr [site web en ligne], consulté le 03/12/2024,