Encyclopédie du sudoku · Mathématiques et informatique

Les mathématiques du sudoku

Mis à jour le 2026-10-05

Un carré latin avec des blocs

Dans un carré latin, chaque symbole apparaît une fois dans chaque ligne et chaque colonne. Un sudoku rempli est un carré latin de taille 9 avec une condition supplémentaire : chacun des neuf blocs de 3×3 contient lui aussi chaque chiffre une fois.

Sources: Wikipedia: Latin square

Combien de grilles existent

Bertram Felgenhauer et Frazer Jarvis ont dénombré les grilles de 9×9 entièrement remplies en 2005 : il en existe 6 670 903 752 021 072 936 960, soit environ 6,67 × 10²¹. Beaucoup sont une même grille sous une autre forme. Si l'on compte deux grilles comme une seule lorsqu'on peut transformer l'une en l'autre en renommant les chiffres, en effectuant une rotation ou une réflexion, ou en réordonnant les lignes et les colonnes de manière à conserver une grille valide, il reste 5 472 730 538 grilles essentiellement différentes, un nombre calculé par Ed Russell et Frazer Jarvis.

Sources: Felgenhauer and Jarvis, Enumerating possible Sudoku grids (2005), OEIS A107739: number of Sudoku grids, Wikipedia: Mathematics of Sudoku

Le minimum de 17 indices

Aucun sudoku standard de 9×9 avec 16 chiffres donnés ou moins ne possède exactement une solution. Gary McGuire, Bastian Tugemann et Gilles Civario l'ont montré grâce à une recherche informatique exhaustive et ont annoncé le résultat en janvier 2012. Dix-sept est un minimum, pas une garantie : de nombreuses grilles avec 17 chiffres donnés ont encore plusieurs solutions.

Sources: McGuire, Tugemann and Civario, There is no 16-Clue Sudoku (arXiv 1201.0749)

Le sudoku comme coloration de graphe

Dessinez un sommet pour chacune des 81 cellules et reliez deux sommets dès que leurs cellules partagent une ligne, une colonne ou un bloc. Ce graphe du sudoku possède 810 arêtes, et chaque sommet a exactement 20 voisins. Résoudre le jeu consiste à étendre les couleurs fixées par les chiffres donnés de façon que des sommets reliés n'aient jamais la même couleur. Il faut au moins neuf couleurs, car chaque ligne, colonne et bloc forme un groupe de neuf sommets tous reliés entre eux, et toute grille entièrement remplie montre que neuf couleurs suffisent.

Sources: Wikipedia: Sudoku graph

Difficile en général, rapide pour le 9×9

Pour les grilles de sudoku dont la taille peut croître sans limite (n²×n² avec des blocs de n×n), déterminer si une grille partiellement remplie peut être complétée est un problème NP-complet, un résultat publié par Takayuki Yato et Takahiro Seta en 2003. Les programmes informatiques efficaces résolvent généralement les grilles ordinaires de 9×9 en une fraction de seconde, même si le temps dépend du programme, de l'ordinateur et de la grille.

Sources: Wikipedia: Mathematics of Sudoku, Wikipedia: Sudoku solving algorithms, Peter Norvig: Solving Every Sudoku Puzzle

Voir aussi

Sources

Tous les articles →