Sudoku : déterminer le nombre minimum de "dévoilés"

Le projet sur le Sudoku de l'université des technologies de Graz vient de débuter. L'objectif est de déterminer le nombre minimum de dévoilés (les cases préremplies) pour garantir une solution unique dans une grille de Sudoku. Pour l'instant, seuls les linuxiens peuvent participer. Une application pour Windows et Mac devrait arriver dans les jours à venir.

Un sondage est actuellement organisé sur le forum pour désigner le plus beau logo (voir les 10 images qui défilent ci-dessus)

INSCRIPTION - URL du projet : http://dist2.ist.tugraz.at/sudoku/

Le sudoku est un jeu en forme de grille défini en 1979 et inspiré du carré latin ainsi que du problème des 36 officiers du mathématicien suisse Leonhard Euler. Le but du jeu est de remplir cette grille avec des chiffres allant de 1 à 9 en respectant certaines contraintes, quelques chiffres étant déjà disposés dans la grille. Une question intéressante consiste à se demander quel est le nombre minimum de dévoilés suffisants pour que le Sudoku n'admette toujours qu'une seule solution.

Étonnamment, jusqu'ici, aucune meilleure limite inférieure n'a été obtenue par le raisonnement mathématique. Des recherches ont déjà montré qu'il est possible de construire au moins 41.000 grilles de Sudoku avec 17 dévoilés. Ainsi, aujourd'hui, on peut déjà dire que le nombre minimum de dévoilés pour garantir une solution unique est compris entre 8 et 17.

Un projet s'intéresse déjà au cas d'une grille avec 16 dévoilés, mais il existe 5.472.730.538 solutions (en prenant en compte la symétrie, le réétiquetage, etc.), ainsi cette approche pourrait prendre énormément de temps.

La méthode de travail du projet de l'université de Graz est toute autre. On part d'une grille à 8 dévoilés puis on analyse les 92.248 solutions, si on ne trouve aucune solution unique, on continue en analysant toutes les solutions dans une grille admettant 9 dévoilés, et ainsi de suite jusqu'à 16. Dès l'instant où un utilisateur découvre une solution unique, le projet s'arrête puisque le nombre minimal de dévoilés sera alors déterminé. Si aucune solution unique n'est découverte jusqu'à 16, on pourra dire que 17 est le nombre minimum de dévoilés pour garantir une solution unique.

Voir la description détaillée du projet