Une question ouverte depuis des annees
Depuis la popularisation du Sudoku, une question fascinait les mathematiciens : quel est le nombre minimum d'indices necessaires pour qu'une grille de Sudoku ait une solution unique ? Des milliers de grilles a 17 indices avaient ete trouvees, mais personne n'avait jamais reussi a en construire une a 16 indices avec une solution unique.
La preuve de Gary McGuire
En janvier 2012, le mathematicien irlandais Gary McGuire et son equipe de l'University College Dublin publient la preuve tant attendue : il n'existe aucune grille de Sudoku a 16 indices ayant une solution unique. Le minimum est donc bien de 17.
La preuve a necessite :
- 7 millions d'heures de calcul sur un cluster de processeurs
- L'analyse exhaustive de toutes les configurations possibles a 16 indices
- Des algorithmes d'optimisation sophistiques pour reduire l'espace de recherche
6 670 903 752 021 072 936 960 grilles possibles
Pour mettre cette decouverte en perspective, il existe exactement 6,67 x 10^21 grilles de Sudoku valides (soit environ 6,67 milliards de milliards). C'est un nombre astronomique, pourtant chacune de ces grilles respecte les memes contraintes elementaires definies par Howard Garns en 1979.
Impact sur la creation de grilles
Cette decouverte a un impact pratique : les createurs de grilles savent desormais qu'une grille a 17 indices represente le defi ultime. C'est le minimum absolu pour un puzzle resoluble. Les grilles a 17 indices sont extremement rares et d'une difficulte redoutable — un exercice reserve aux joueurs les plus experimentes.