Dieu et le Sudoku

Vous connaissez le nombre de Dieu ?

Sous cette appellation étrange se cache un minmax soit un maximum du minimum.
Houlà ! C'est compliqué ?
Pas du tout...

En 2010 deux mathématiciens et un programmeur ont établi le nombre de Dieu au Rubik's Cube.

Celui-ci est de 20 et cela veut dire concrètement que quelque soit la position de départ vous aurez toujours la possibilité de résoudre le cube infernal en 20 coups ou moins. 20 est le maximum des coups minimum pour résoudre le casse-tête.

Et le Sudoku donc ?

En fait le problème est un peu différent, et il s'agit d'un nombre de Dieu un peu particulier puisque la question que s'est posé Gary McGuire, Bastian Tugemann et Gilles Civario était de découvrir le nombre d'indices minimum possibles pour qu'une grille de Sudoku soit valide et résolvable. (une grille valide n'admettant qu'une solution unique)

Dans la plupart des publications, ainsi que dans la collection du passionné Gordon Royle, mathématicien australien, ont ne trouve que des modèles à 17 indices au mieux.

Alors le Sudoku à 16 indices existe t-il ?

Si l'on prend les combinaisons possibles, un Sudoku composé d'une matrice de 9 sur 9 en comporte ... environ 6 671 milliards de milliards de grilles.

Pour simplifier la chose, on peut considérer que certaines combinaisons sont en fait équivalentes.

Par exemple si l'on échange les emplacements des 1 et des 9 nous obtiendrons deux grilles différentes mais à l'usage ce sera le même jeu.
De même on peut éliminer les rotations et les symétries et tout ça pour la grille mais aussi pour les lignes et les colonnes et autres sous ensembles.

Du coup, on se retrouve avec 5 472 730 538 modèles originaux.

Avec un ordinateur on pourrait toutes les analyser. Disons que cela prendrait du temps...

Les chercheurs ont donc simplifié en travaillant sur les indices inévitables et les trois chercheurs ont fait tourner un superordinateur Stokes sur l'équivalent de 7,1 millions d'heures de calcul afin de vérifier au cas par cas qu'aucune grille n'était résolvable avec 16 indices seulement sur les 5 472 730 538 grilles.

Tout ça ne vaut pas bien sûr une belle démonstration. Qui reste à faire...

▶ Le nombre de Dieu au Rubik'Cube (english)
▶ Article et Grilles de Gordon Royle (english)
▶ Réduire le nombre de grilles possibles (english)
▶ Téléchargez l'étude en pdf sur arxiv.org (36 pages, english)