Dix-sept, le nombre d'or au sudoku

Des chercheurs du University College de Dublin ont...

Agrandir

Des chercheurs du University College de Dublin ont prouvé mathématiquement que les sudokus «faisable» comptaient tous 17 indices de départ.

(Québec) Dix-sept. Pas 16, pas 15, 17. C'est le nombre minimal d'«indices», ces nombres divulgués dès le départ, qu'une grille de sudoku doit comporter pour être «faisable», selon une savante étude menée par une équipe de mathématiciens irlandais.

Publié le 1er janvier sur le serveur de prépublication arxiv.org, l'ouvrage a trouvé un écho la fin de semaine dernière sur le site de la revue Nature. On y apprend que des férus de sudokus avaient déjà remarqué qu'aucun casse-tête à 16 indices n'avait jamais été «découvert» malgré des années de création de grilles par ordinateur. L'hypothèse avait été faite qu'il en fallait 17, mais sans une preuve mathématique, cela pouvait tout simplement signifier que les sudokus à 16 indices étaient tout simplement très rares.

Mais la question ne se pose plus : «Nous avons réalisé une recherche exhaustive des possibilités pour trouver un sudoku à 16 indices et n'en avons trouvé aucun, prouvant ainsi que la réponse est 17», écrit un trio de mathématiciens mené par Gary McGuire, du University College de Dublin.

Tour de force

Mine de rien, une telle recherche «exhaustive» est un tour de force. Le nombre de combinaisons possibles de 16 chiffres de 1 à 9 se compte en effet en milliers de milliards, quantité qui se trouve ensuite multipliée par un nombre tout aussi ahurissant de manières de disposer ces 16 chiffres dans une grille de 81 cases. Tester toutes ces possibilités était, en pratique, irréalisable, mais M. McGuire a trouvé une façon de contourner ce problème.

Pour faire un petit ménage dans cette myriade de possibilités, les trois auteurs ont mis au point un algorithme qui «détecte» les parties d'un casse-tête qui sont interchangeables - et qui rendent ainsi un sudoku «infaisable», puisqu'il existe plus d'une solution. Pour éviter les solutions multiples, se sont-ils dit, les indices doivent forcément recouper ces parties interchangeables.

En se concentrant sur cet aspect, tout de même très large, disons-le, M. McGuire a ramené le temps de calcul dont il avait besoin pour faire sa preuve à «seulement» sept millions d'heures-processeur - une grosse bouchée, même pour un superordinateur!

Partager

publicité

publicité

la liste:1710:liste;la boite:91290:box

En vedette

Précédent

publicité

la boite:1608467:box; tpl:300_B73_videos_playlist.tpl:file;

Les plus populaires : Le Soleil

Tous les plus populaires de la section Le Soleil
sur Lapresse.ca
»

CONTRIBUEZ >

Vous avez assisté à un évènement d'intérêt public ?

Envoyez-nous vos textes, photos ou vidéos

Autres contenus populaires

image title
Fermer