Déterminer le plus petit nombre de cases qui doivent être dévoilées pour garantir une grille de Sudoku admettant une seule et unique solution.

INSCRIPTION

Télécharger BOINC (tutorial)

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

• Début du projet : 4 Septembre 2007
• Université des technologies de Graz (Autriche)

Le Sudoku est un casse-tête très connu, ainsi vous pouver taper le mot Sudoku sur google pour avoir accès à une description et à de nombreux logiciels,... Une donnée importante à prendre en compte en ce qui concerne le Sudoku, est qu'il existe toujours une solution, et cette solution se doit d'être unique ! Ecrire un programme qui trouve cette solution n'est pas très difficile, vous pouvez vous même trouver de nombreux programmes de ce type sur internet. Environ 25 à 30 cases sont dévoilées dans les grilles de Sudoku de difficulté moyenne (dans les journaux, etc.). Généralement, un Sudoku devient plus compliqué, lorsque l'on réduit le nombre de chiffres dévoilés. Mais attention, ceci n'est pas une règle universelle : il existe également des grilles de Sudoku difficiles avec beaucoup de cases déjà remplies, et faciles avec seulement quelques cases dévoilées.

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. Sans trop raisonner on peut déjà admettre que 8 est une limite basse. Partez du principe que seulement 7 chiffres sont donnés, alors dans n'importe quel cas de figure, il vous sera possible d'interchanger toutes les occurrences de deux chiffres non donnés, et ainsi vous aurez toujours au moins deux solutions différentes. Étonnamment, jusqu'ici aucune meilleure limite inférieure n'a été obtenue par le raisonnement mathématique. Tout les grilles de Sudoku minimales connues avec une solution unique admettent 17 cases dévoilées, voir http://people.csse.uwa.edu.au/gordon/sudokumin.php pour avoir accès à une collection de plus de 41.000 puzzles de ce type (collection qui s'agrandie encore).

Ainsi, la fourchette actuelle du plus petit nombre d'indices (cases déjà remplies) qu'une grille de Sudoku (avec une solution unique) peut admettre varie de 8 à 17. Le but de notre projet est de resserrer cet intervalle. Pour cela, nous avons commencé avec 92.248 grilles de Sudoku avec 8 chiffres dévoilés (chiffres de 1 à 8, représentant toutes les possibilités en prenant en compte la symétrie, le réétiquetage, etc.) puis nous continuerons en ajoutant 1 case remplie de plus à chaque fois, pour vérifier la singularité de la solution. (Une description mathématique plus détaillée de notre approche sera publiée d'ici peu)

Pendant la première phase d'évaluation de notre programme nous avons pu prouver qu'au moins 11 cases doivent être préremplies. Ainsi la fourchette actuelle se réduit entre 11 et 17. L'utilisation du calcul partagé fera augmenter étape par étape la limite inférieure, jusqu'à ce qu'un utilisateur trouve un nouvel exemple minimal ou si nous pouvons prouver qu'aucun exemple de ce type n'existe jusqu'à 16 nombres dévoilées.

Quelques remarques:

• Une autre approche consiste à regarder si 17 est la bonne réponse. Il suffit pour cela de résoudre toutes les grilles de Sudoku avec 16 cases dévoilées, voir http://www.math.ie/checker.html. Malheureusement, il existe beaucoup trop de grilles de ce type (5.472.730.538 solutions, en prenant en compte la symétrie, etc voir http://www.afjarvis.staff.shef.ac.uk/sudoku/sudgroup.html), ainsi cette approche pourrait prendre énormement de temps.
• Quelques analyses mathématiques du Sudoku peuvent être trouvées sur cette page.
• Pour finir, ne loupez pas cette page internet : http://avmtech.net/comics/foxtrot/ft061015.gif :)