Quelle est la limite inférieure d'une grille de Sudoku ?

Le texte présenté ci dessous est une traduction d'un article publié dans l'édition du 12 mars du journal en ligne International Science Grid this Week.

	Quel est le nombre minimal de cases qui doivent être dévoilées pour résoudre une grille de Sudoku ? Le projet BOINC Sudoku tente de le découvrir. Image présentée avec l'aimable autorisation du projet Sudoku

Il existe deux façons de résoudre une grille de Sudoku : à la main, où en programmant une fonction informatique qui fera le travail à votre place.

Le projet Sudoku a trouvé une troisième voie : utiliser le calcul distribué volontaire pour découvrir la grille de Sudoku ultime.

La résolution d'une grille de Sudoku "classique" (avec 25 ou 30 cases dévoilées au début du jeu) est relativement aisée. Mais que se passe t-il si vous débutez le jeu avec moitié moins de cases dévoilées.

Est-il possible de résoudre une grille de Sudoku débutant avec seulement 10 chiffres dévoilés ? Et qu'en est-il avec 5 cases dévoilées ? Quel est le plancher en dessous duquel il est impossible de descendre si l'on veut toujours garantir une seule et unique solution à la grille.

Dans l'état actuel des connaissances, toutes les grilles de Sudoku dites "minimales" garantissant une unique solution débutent avec 17 cases dévoilées. En outre, toutes les grilles présentant moins de 8 cases dévoilées au début du jeu n'aboutiront jamais à une solution unique. Ainsi, la grille minimale demanderait entre 8 et 17 cases dévoilées.

Un nouveau projet de calcul distribué sur BOINC, Sudoku, se donne pour objectif de réduire cet interval. Mais il ambitionne également de découvrir la disposition initiale d'une grille de Sudoku offrant le plus petit nombre de cases dévoilées et n'aboutissant qu'à une seule et unique solution.

Les scientifiques impliqués dans ce projet indiquent que les premiers tests ont déjà permis de réduire l'interval qui est maintenant compris entre 11 et 17 cases dévoilées ; l'étape suivante consiste à utiliser le calcul volontaire pour petit à petit relever la borne inférieure de cet interval. Ensuite, soit un utilisateur découvrira une grille de Sudoku avec la disposition initale des cases permettant d'aboutir à une solution unique, soit le projet aura aidé à démontrer qu'il n'existe aucun exemple de ce type jusqu'aux grilles offrant 16 cases dévoilées.

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