Les mathématiques cachées derrière le sudoku
Le sudoku se présente comme un jeu simple : remplir une grille avec des chiffres sans répétition. Pourtant, derrière cette façade minimaliste se cachent des questions mathématiques profondes qui ont passionné les chercheurs du monde entier. Combinatoire, théorie des graphes, complexité algorithmique… Le sudoku est un véritable terrain de jeu pour les mathématiciens.
Combien de grilles de sudoku existent ?
La première question qui vient à l’esprit est celle du dénombrement. Combien de grilles complètes de sudoku 9×9 valides existe-t-il ? La réponse, trouvée en 2005 par Bertram Felgenhauer et Frazer Jarvis, est exactement 6 670 903 752 021 072 936 960, soit environ 6,67 × 1021.
Ce nombre astronomique - plus de six sextillions - explique pourquoi vous ne tomberez probablement jamais deux fois sur la même grille. Toutefois, si l’on élimine les grilles équivalentes par symétrie (rotations, réflexions, permutations de chiffres et échanges de lignes/colonnes), le nombre de grilles essentiellement différentes se réduit à environ 5,47 milliards.
La méthode de calcul
Le dénombrement exact a nécessité une combinaison de techniques mathématiques et informatiques. Les chercheurs ont d’abord rempli la bande supérieure (les trois premières régions), en dénombrant toutes les configurations possibles. Puis, par des algorithmes de comptage sophistiqués, ils ont calculé le nombre de façons de compléter les six régions restantes pour chaque configuration de départ.
Le problème du nombre minimum d’indices
Quel est le nombre minimum d’indices (cases préremplies) nécessaire pour qu’une grille de sudoku ait une solution unique ? Cette question a résisté pendant des années avant d’être résolue en 2012 par Gary McGuire, Bastian Tugemann et Gilles Civario de l’University College Dublin.
La réponse est 17. Il est impossible de créer une grille de sudoku à solution unique avec seulement 16 indices. La démonstration a nécessité plus d’un an de calcul informatique sur un cluster de processeurs, vérifiant exhaustivement que toute grille à 16 indices possède nécessairement plusieurs solutions.
Il existe environ 49 000 grilles à 17 indices connues, chacune étant un petit bijou de minimalisme logique. Si vous êtes curieux de voir à quoi ressemble une telle grille, imaginez un sudoku 9×9 avec seulement 17 chiffres visibles - et pourtant une seule solution possible.
Le sudoku est NP-complet
En théorie de la complexité, le sudoku généralisé (sur des grilles de taille n×n) a été prouvé NP-complet. Cela signifie qu’il fait partie de la classe de problèmes les plus difficiles à résoudre de manière générale, au même titre que le problème du voyageur de commerce ou la satisfaisabilité booléenne. D’autres jeux de logique possèdent des propriétés mathématiques tout aussi fascinantes, comme le démineur dont les probabilités et fondements mathématiques relèvent également de la NP-complétude.
Que signifie NP-complet ?
Un problème NP-complet possède deux propriétés :
- Vérifiable en temps polynomial : donnée une solution proposée, on peut vérifier rapidement si elle est correcte
- Au moins aussi difficile que tout problème NP : si l’on trouvait un algorithme rapide pour le sudoku généralisé, on résoudrait du même coup tous les problèmes NP
En pratique, pour les grilles standard 9×9, les algorithmes modernes résolvent les sudokus en une fraction de seconde. C’est pour les grilles de taille croissante que la difficulté explose exponentiellement.
Satisfaction de contraintes
En informatique, le sudoku se modélise naturellement comme un problème de satisfaction de contraintes (CSP). Chaque case est une variable qui peut prendre les valeurs 1 à 9, et les règles du sudoku définissent les contraintes d’inégalité entre variables.
Les solveurs de CSP utilisent des techniques comme la propagation de contraintes (qui correspond aux techniques humaines de scanning et d’élimination) combinée au backtracking (retour en arrière lorsqu’une impasse est atteinte). Les techniques humaines avancées comme le X-Wing ou le Swordfish sont en réalité des formes spécifiques de propagation de contraintes.
Coloration de graphes
Le sudoku peut également se formuler comme un problème de coloration de graphe. Chaque case représente un sommet, et deux sommets sont reliés par une arête s’ils partagent une ligne, une colonne ou une région. Résoudre le sudoku revient alors à colorier ce graphe avec 9 couleurs de sorte que deux sommets adjacents n’aient jamais la même couleur.
Le graphe du sudoku 9×9 possède 81 sommets et un nombre chromatique de 9. Cette reformulation permet d’appliquer au sudoku tout l’arsenal de la théorie des graphes, et réciproquement, le sudoku sert d’illustration pédagogique pour enseigner la coloration de graphes aux étudiants.
Les symétries du sudoku
Le groupe de symétries du sudoku - les transformations qui envoient une grille valide sur une autre grille valide - est étonnamment riche. Il comprend :
- Les permutations des trois bandes horizontales et des trois bandes verticales
- Les permutations des lignes au sein de chaque bande et des colonnes au sein de chaque pile
- Les permutations des 9 chiffres entre eux
- La transposition (miroir par la diagonale)
Le groupe total contient 3 359 232 éléments. C’est ce groupe qui permet de réduire les 6,67 sextillions de grilles à seulement 5,47 milliards de classes d’équivalence.
Le sudoku comme objet de recherche
Le sudoku continue d’inspirer la recherche mathématique contemporaine. Des questions ouvertes demeurent, notamment sur les propriétés statistiques des grilles, l’efficacité optimale des algorithmes de génération, et les liens avec d’autres structures combinatoires.
Pour ceux que l’histoire du sudoku intéresse, la dimension mathématique remonte aux travaux d’Euler sur les carrés latins au XVIIIe siècle. Et si vous souhaitez appliquer ces connaissances théoriques à la pratique, nos articles sur les techniques avancées vous montreront comment les principes d’élimination et de propagation se traduisent en stratégies concrètes.
La prochaine fois que vous résoudrez un sudoku en ligne, rappelez-vous que vous manipulez un objet mathématique d’une richesse insoupçonnée, à l’intersection de la combinatoire, de la théorie des graphes et de l’informatique théorique.
