Quel est le nombre minimum d'indices qu'un Sudoku peut avoir ?
Dernière mise à jour
Un Sudoku valide - avec exactement une solution - nécessite au moins 17 chiffres donnés. C'est un résultat mathématique prouvé. Tout puzzle avec 16 indices ou moins a soit plusieurs solutions, soit aucune.
La preuve de 2012
En 2012, Gary McGuire, Bastian Tugemann et Gilles Civario de l'University College Dublin ont publié une preuve qu'aucun Sudoku valide à 16 indices n'existe. Leur travail était principalement computationnel : ils ont exploré l'espace complet des grilles possibles à 16 indices et vérifié qu'aucune ne produisait une solution unique. La recherche a nécessité environ 7 millions d'heures-cœur de calcul.
Auparavant, on croyait largement que 17 était le minimum et des milliers de puzzles à 17 indices avaient été trouvés expérimentalement. L'équipe de McGuire a fourni la première preuve rigoureuse que 16 est impossible.
À quoi ressemblent les puzzles 17-Clue
Les puzzles à 17 indices sont extrêmement clairsemés - 17 chiffres donnés dans 81 cellules, laissant 64 vides. Ils font partie des puzzles les plus difficiles à résoudre et nécessitent généralement des techniques avancées. Trouver des puzzles valides à 17 indices a lui-même nécessité des décennies d'efforts computationnels. Au moment de la rédaction, plus de 49 000 puzzles de Sudoku à 17 indices essentiellement différents sont connus.
Ce que cela signifie pour la conception de puzzles
Les puzzles publiés destinés aux solveurs humains descendent rarement en dessous de 22 indices. Les puzzles de difficulté Expert et Maître utilisent généralement 22-27 chiffres donnés, tandis que les puzzles Faciles en utilisent 36-45. Le minimum de 17 indices est une limite théorique - En pratique, la solvabilité avec une bonne technique et un chemin de résolution agréable importent bien plus que le nombre d'indices seul.