Le nombre minimal de cases préremplies pour que le sudoku n'ait qu'une seule solution a été déterminé.
Quel est le nombre minimal de cases d'un sudoku qui doivent être préremplies si l'on veut que le casse-tête n'ait qu'une seule solution ? La réponse est 17 (sur 9 x 9 = 81 cases). On s'en doutait depuis quelque temps, mais Gary McGuire, du Trinity College de Dublin, en Irlande, aidé par Bastian Tugemann et Gilles Civario, l'a prouvé.
La méthode a consisté à effectuer une recherche systématique, par ordinateur, à l'aide d'un algorithme développé par G. McGuire. Plus précisément, la tâche comportait trois étapes. La première était de cataloguer toutes les grilles de sudokus complètement remplies et qui sont vraiment distinctes (c'est-à-dire qu'elles ne se déduisent pas l'une de l'autre en permutant les lignes, en faisant une symétrie, etc.). Il y a ainsi 5 472 730 530 grilles distinctes, parmi les quelque 6,7 x 1021 grilles possibles. Deuxième étape : écrire un programme, nommé checker, qui recherche efficacement, au sein d'une grille complète donnée, les sudokus à 16 cases préremplies et dont la seule solution est la grille donnée. Troisième et dernière étape : passer en revue toutes les grilles complètes à l'aide de ce programme.
Cette recherche exhaustive n'a trouvé aucun sudoku à 16 cases ayant une solution unique, ce qui prouve qu'un sudoku à solution unique doit avoir au moins 17 cases préremplies. On connaissait effectivement de nombreux exemples de sudokus à 17 cases préremplies et dont la solution est unique, et aucun à 16. Mais cela ne signifie pas pour autant que tous les sudokus à 17 cases préremplies ont une solution unique !
