Pendant ce temps, chez les Sudokus

Il est 13h, bonjour à tous, bon week-end. Voici les titres de l'actualité de ce dimanche :
- Un week-end de grand froid sur la France. C'est la neige qui a paralysé plusieurs heures des automobilistes sur l'autoroute A26.
- Froid, encore : les températures ressenties sont plus faibles que les températures sous abri. Explications, mais sans équations.
- Froid toujours : nos envoyés spéciaux en province nous montreront comment est la neige dans les différents coins de la France.
- Point sur la fashion week : que nous réservent les créateurs de mode en matière de gants et de bonnets ?
- Science : malgré le froid, trois chercheurs ont réussi à déterminer qu'en dessous de 17 chiffres, un sudoku n'a jamais de solution unique.
- Enfin, nous terminerons par la météo, en rappelant qu'il neige en hiver.

[...]

Ouvrons donc ce sujet science, avec l'exploit du mois dernier : Gary McGuire, mathématicien irlandais, a résolu une énigme datant de plus de dix ans, en découvrant le plus petit sudoku qui existe. Pour cela, il a fallu plus de 7 millions d'heures de calculs sur un superordinateur. Explications.

Il n'existe que trois types de sudokus : ceux qui n'ont qu'une unique solution, ceux qui ont plusieurs solutions et ceux qui n'ont aucune solution. Les premiers sont intéressants, et les autres sont terriblement décevants et ne méritent pas le nom de sudoku (étymologiquement, "chiffre unique").

Marcel Bompré, amateur de sudoku, témoigne : "c'est vrai que c'est décevant quand on ne s'aperçoit qu'au dernier moment que la grille que l'on est en train de remplir possède plusieurs solutions différentes. Surtout qu'il fait froid."

En général, moins un soduku possède de cases pré-remplies, plus sa complétion sera difficile. De tous les sudokus connus, les plus dépouillés ne comportent que 17 chiffres révélés.

Marcel Bompré, amateur de sudoku, témoigne : "un jour, j'ai résolu un sudoku avec seulement 17 chiffres révélés. C'était pas facile. Surtout qu'il fait vraiment froid."

Exemple de sudoku à 17 indices.

Peut-on trouver un sudoku à 16 chiffres ? La question a longtemps été ouverte, jusqu'au 1er janvier 2012. Gary McGuire, aidé de deux collaborateurs, ont regardé attentivement les 6.7 milliers de milliards de milliards de grilles complètes existantes afin de voir s'il était possible de leur retirer plus de 64 chiffres sans les dénaturer. Leur conclusion : il n'existe pas de sudoku à 16 chiffres.

Même pour un ordinateur, vérifier une par une les 6.7×10²¹ grilles existantes reste quelque chose de très long. Heureusement, il est possible de réduire considérablement le nombre de sudokus à inspecter grâce à un théorème appelé "lemme de Burnside" : deux grilles sont équivalentes si l'on peut passer de l'une à l'autre en permutant les chiffres, les colonnes ou les lignes (on ne peut pas vraiment dire que deux sudokus sont différents si on intervertit les 7 et les 5, par exemple)

Équivalence des sudokus :
* permutation des chiffres
* permutation des bandes verticales
* permutation de colonnes au sein d'une même bande
* permutation des bandes horizontales
* permutation de lignes au sein d'une même bande
* inversion des lignes/colonnes

Ces opérations permettent de réduire à 5500 millions le nombre de grilles à inspecter. C'est mieux, mais ça reste long à faire. Il faut donc y aller finement.

La méthode la moins habile pour résoudre le problème est de prendre une par une les grilles complètes et de tester toutes les sous-grilles à 16 indices pour voir s'il en existe des valides. Problème : y a 33 millions de milliards de façons de garder 16 cases parmi 81. En comptant une minute par grille, il faudrait au moins 10000 ans pour arriver à bout du problème.

Les trois compères y sont donc allé un peu différemment, en cherchant les "ensembles inévitables" dans les grilles complètes. On peut illustrer le concept avec le sudoku suivant :

L'un des quatre indices en jaune est inévitable

En retirant les cases jaunes de cette grille, le sudoku aurait deux solutions différentes : il faut en garder au minimum une parmi ces quatre pour une solution unique. En raisonnant de cette façon, on peut en déduire le nombre minimal d'indices amenant à la grille complète en cherchant ces configurations "inévitables". Le reste est une affaire d'informatique : il faut programmer ce principe de manière satisfaisante pour l'appliquer aux 5.4×10⁹ sudokus pleins. C'est ce que les trois chercheurs ont fait, en inventant un nouvel algorithme, qui pourrait d'ailleurs servir dans bien d'autres domaines de l'informatique. Dans les faits, les calculs ont duré presque un an sur le superordinateur Stokes (mais aurait duré 800 ans sur un ordinateur plus classique).

Marcel Bompré, amateur de sudoku, témoigne : "Pfffiou ! C'est long ! Surtout qu'il neige."

La quête d'un sudoku à 16 chiffres est définitivement terminé, mais le travail mathématique ne l'est pas. Tout comme pour la découverte du nombre de Dieu en juillet 2010, l'approche informatique est trop balourde pour être honnête. Il existe sans doute une approche bien plus fine qui pourrait montrer qu'il n'existe pas de sudoku à 16 indices, ni de Rubik's cube que l'on ne peut résoudre en moins de 21 coups.

Rappelons tout de même l'information principale de la journée : il fait froid en hiver.

---

Sources :
* There is no 16-Clue Sudoku: Solving the Sudoku Minimum Number of Clues Problem, l'article de McGuire en prépublication sur arXiv.
* Mathematics of Sudoku I, où Felgenhauer et Jarvis montrent qu'il existe 6.7×10²¹ grilles de sudoku.
* Mathematics of Sudoku II, où Russel et Jarvis montrent qu'il n'existe que 5.4×10⁹ grilles vraiment différentes.

Comments

[Thomas Cabaret]

Bonjour, sujet intéressant, merci



"En général, moins un soduku possède de cases pré-remplies, plus sa complétion sera difficile."

C'est une tendance mais vu d'assez loin.



A mon grand étonnement de "mathématicien" j'ai découvert que le sudoku ca peut être dur, il y a de véritables monstres mathématiques d'une espèce sans commune mesure avec les sudokus soit disant diaboliques des journaux.

C'est le cas par exemple de "Easter Monster":

http://sudoku.com.au/blog/jpgfiles/Easter%20Monster%20jpgs/start_blank.jpg

On notera que la grille initiale avec 21 indices est éloignée du 17 limite.

Voici quelques étapes de la solution:

http://sudoku.com.au/sudokutips.aspx?Go=I29-12-1991&category=sudoku

(avec les "Previous blog pages")



Pour d'autres sudokus extrêmes comme celui ci:

http://en.wikipedia.org/wiki/Sudoku_algorithms



Voir en bas "Exceptionally difficult Sudokus"



On remarquera toujours que ceux-ci sont loins des 17 indices minimaux avec autour de 21 indices.



J'encourage fortement les amateurs à tenter le "Easter Monster" pour bien voir qu'un sudoku ce n'est pas ce qu'on vous fait croire dans la presse :)

[Mr Alabar]

Super article, d'autant plus par ce froid !



Petit oubli cependant : "Il n'existe que trois types de sudokus : ceux [qui] n'ont qu'une unique solution".

[plop]

C'est beau l'informatique, c'est encore plus magnifique quand la forme de l'article permet une critique sur la stupidité des média :)