Quel est le nombre minimal d’«indices» — les chiffres déjà inscrits dans la grille de départ — qu’un sudoku doit comporter pour être faisable, c’est-à-dire pour n’avoir qu’une seule solution ? La question peut sembler triviale, mais en mathématiques, c’est une sacrée commande. Certains amateurs avaient déjà remarqué empiriquement qu’aucun sudoku comportant moins de 17 indices n’avait encore été «découvert», mais ce n’était peut-être qu’une question de temps avant qu’un programme ne finisse par en pondre un. La preuve formelle démontrant qu’un sudoku à 16 indices a nécessairement plus d’une solution nous échappait toujours.

Mais ça, c’était en 2011. Le 1er janvier dernier, un mathématicien irlandais du University College de Dublin, Gary McGuire, a publié en ligne ce qui semble bien être la preuve mystérieuse. Comme l’explique ce compte-rendu de la revue Nature, il était en pratique impossible de tester toutes les possibilités, même avec les ordinateurs d’aujourd’hui, vu leur trop grande profusion — le nombre de combinaisons possibles de 16 chiffres de 1 à 9 se compte en milliers de milliards, quantitée multipliée par un nombre tout aussi ahurissant de dispositions possibles dans une grille de 81 cases. Pour contourner cet écueil, M. McGuire a mis au point un algorithme qui consiste à chercher, dans les grilles complétées, ce qu’il appelle des «ensembles inévitables», soit des parties du puzzle qui sont interchangeables et qui peuvent ainsi mener à des solutions multiples. Afin d’éviter cela, les indices de départ doivent chevaucher ces ensembles inévitables de manière à «choisir», en quelque sorte, une seule des solutions multiples.

Cela a permis de ramener le temps de calcul dans des proportions presque «raisonnables» — il a tout de même fallu quelque 7 millions d’«heures CPU» dans un superordinateur pour accoucher d’une conclusion. Résultat : «il n’y a pas de sudoku à 16 indices», comme l’indique le titre de l’article de M. McGuire et al.

À cause des moyens informatiques nécessaires, il faudra encore un certain temps avant que d’autres mathématiciens ne puissent vérifier cette preuve, mais ceux qui ont pris connaissance de l’ouvrage se montrent optimistes pour l’instant.

P.S. J’en profite pour proposer un autre type de puzzle à ceux qui trouvent que le sudoku est trop simple et répétitif : le ken-ken. Même principe que le sudoku : les chiffres ne doivent pas se répéter en lignes et en colonnes. Mais les sous-grilles ont des formes et des nombres de cases variables, et on y trouve seulement un «nombre indice» avec une opération arithmétique (+, –, x et ÷). On remplit les sous-grilles en trouvant les chiffres qui, avec l’opération, donnent le nombre indice. Comme passe-temps, on peut certes trouver mieux, mais c’est déjà pas mal plus intéressant que le sudoku, en ce qui me concerne.

AJOUT (12 janvier 2012) : Je reproduis ici, avec permission, le courriel que m’a envoyé Claude Belisle, professeur de mathématiques à l’Université Laval. M. Belisle dit ne pas avoir lu «en détails» l’article de McGuire et n’avoir qu’un intérêt «plutôt limité» pour le sudoku, mais comme vous le verrez, c’est amplement suffisant pour qu’il amène des éléments très, très intéressants. Le voici, en italique :

«Si je vous présente un problème de sudoku avec seulement quelques indices donnés (i.e. seulement quelques cases remplies),alors exactement un des 3 énoncés suivants est correct:

A. Il existe plusieurs solutions pour ce problème.
B. Il existe une et une seule solution pour ce problème.
C. Il n’existe aucune solution pour ce problème.

Le scénario qui nous intéresse est le scénario B.

Posons : k = le nombre d’indices donnés. Jusqu’à tout récemment, on savait que pour tout k plus grand ou égal à 17, il existe des problèmes de sudoku à k indices ayant une et une seule solution. De plus, on soupçonnait que

Conjecture: pour tout k plus petit ou égal à 16, il n’existe aucun problème de sudoku à k indices ayant une et une seule solution.

McGuire et ses collègues ont démontré que cette conjecture est vraie. D’un point de vue mathématique, leur démonstration n’est pas très intéressante : ils ont tout simplement examiné, par énumération, tous les problèmes à 16 indices et ils ont constaté qu’aucun de ces problèmes n’avait qu’une et une seule solution. C’est donc tout simplement une approche par “la force brute”.

S’il n’y a pas prouesse mathématique, il y a bel et bien prouesse informatique. Le problème avec l’approche par la force brute est que le nombre de grilles sudoku est énorme: 6 670 903 752 021 072 936 960 grilles. Bon, plusieurs grilles sont équivalentes. Par exemple si on prend une grille quelconque et si on y remplace tous les 6 par des 2 et tous les 2 par des 6 alors la nouvelle grille est «équivalente» à la grille initiale. En fait les chiffres 1, 2, 3, 4, 5, 6, 7, 8, 9 pourraient être remplacés par 9 symboles différents. Bref, on peut montrer que le nombre de grilles distinctes est 5 472 730 538. Donc un peu moins que 5,5 milliards de grilles.

L’approche par la force brute est donc la suivante:

1. On fait la liste des 5 472 730 538 grilles sudoku (complétées, i.e. avec les cases toutes remplies).
2. Pour chacune de ces grilles, on fait la liste des problèmes sudoku à 16 indices (obtenus en ne conservant que 16 indices ; on efface le contenu des 81-16 = 65 autres cases). Il y en a en tout 33 594 090 947 249 085 (c’est le nombre de façon de choisir 16 cases parmi 81 cases).
3. Pour chacun de ces  (5 472 730 538) fois (33 594 090 947 249 085) = 183 851 407 423 359 414 572 057 730 problèmes à 16 indices, on vérifie si il y a une et une seule solution.

Du point de vue des mathématiques pures, on pourrait dire qu’il s’agit d’un problème élémentaire. Toutefois, lorsqu’on essaie de mettre en oeuvre cette approche, on se rend vite compte que même avec nos meilleurs ordinateurs, ça prendrait des milliers d’années. La contribution de McGuire est intéressante du point de vue informatique. Bref, il développe une technique permettant d’effectuer l’étape 2 en un temps raisonnable. Enfin, en utilisant plusieurs supers ordinateurs, il réussi par force brute à “démontrer” la conjecture. En tout, ça lui a pris un an.»