Docteur Mops
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)

À suivre dans la rédaction...

Commentaires (7)

Default
Rodenbach
Rodenbach

j'aurai appris plein de choses (dont une qui n'est pas des moindres, grâce au calembour vaseux de Bruno. Je me demande quand même quel est le nombre de dieu des moyens mnémotechniques de retenir les codes des départements en partant du principe que certaines astuces permettent de retenir plusieurs départements d'un coup, et qu'à un certain stade de remplissage de la "grille", on peut déduire les chiffres des départements restants sans moyen mnémotechnique.)

Bruno des Montagnes

Faire rentrer 17 chiffres dans une grille de 9* 9.. ben.. fastoche... Charente facile, non ??? ;-)

evavy
evavy

20 mouvements ?

Zut alors, je ne suis pas Dieu.

Il y a des jours comme ça, où l'on découvre que l'on est peu de chose.

Mais effectivement, ça fait plutôt du bien.

Cirth
Cirth

Merci pour la news, ça change tout en étant très interessant

bonobo
bonobo

Pareil que mes camarades ci-dessus.

Yzarc
Yzarc

Effectivement, très intéressant ce genre de news.

666Raziel
666Raziel

J'adore ce genre de news !