Solveur Sudoku

Le Sudoku est un jeu de logique consistant à remplir une grille 9x9 avec les chiffres de 1 à 9. Chaque chiffre doit apparaître une et une seule fois dans chaque ligne, chaque colonne et chacun des 9 blocs 3x3

Des variantes existent avec d'autres tailles ou avec des symboles (lettres, icônes). La structure mathématique reste identique : il s'agit d'un problème de satisfaction de contraintes où chaque symbole doit respecter des règles d'unicité locale.

La grille peut être remplie en copiant-collant une suite de 81 caractères (chiffres ou symboles), ou en saisissant directement les valeurs dans les cases.

Les chiffres $ 1 $ à $ 9 $ sont acceptés. Pour les variantes de type Wordoku, des lettres peuvent également être utilisées, à condition que 9 symboles distincts soient employés.

Le programme résout le Sudoku 9x9 comme un humain le ferait, en combinant les déductions logiques.

— Calcul des candidats : pour chaque case vide, dCode détermine l'ensemble des valeurs possibles compatibles avec les contraintes de ligne, colonne et bloc.

— Seule valeur possible : si une case ne possède qu'un seul candidat, cette valeur est validée.

— Seule case possible : si, pour un chiffre donné, une seule case d'une ligne, colonne ou bloc peut l'accueillir, cette valeur est validée.

Dans une grille classique 9x9, un bloc (appelé aussi région ou groupe ou secteur ou sous-grille) est un carré 3x3. Il y a 9 blocs au total.

dCode calcule toutes les solutions du sudoku, et pas seulement la première. Pour vérifier un sudoku maison, le solveur pourra confirmer qu'il existe une seule et unique solution.

La forme moderne du Sudoku a été publiée en 1979 par Howard Garns dans le magazine américain Dell sous le nom Number Place.

Le jeu a ensuite été popularisé au Japon dans les années 1980 par l'entreprise Nikoli, qui lui a donné le nom Sudoku, contraction de Sūji wa dokushin ni kagiru, signifiant les chiffres doivent rester uniques.

Une seule ligne peut être constituée de $ 9! $ (factorielle de 9) façons différentes, idem pour les colonnes, mais le sudoku entier a un nombre de possibilités bien inférieur à $ 9!^9 $, car certaines permutations peuvent conduire à des grilles identiques. Le nombre total de grilles est de $ 9! \times 72^2 \times 2^7 \times 27704267971 = 6670903752021072936960 $ combinaisons (résultat démontré en 2005).

Pour qu'un sudoku n'ait qu'une seule solution, il doit avoir au moins 17 cases préremplies sur les 81 totales. Gary McGuire et son équipe ont prouvé cela ici en utilisant un algorithme pour effectuer une recherche systématique par ordinateur. Ils ont d'abord catalogué les 5 472 730 530 grilles de sudokus distinctes. Ensuite, ils ont créé un programme pour vérifier si des sudokus avec 16 cases préremplies avaient une solution unique. Leur recherche exhaustive n'a trouvé aucun sudoku avec seulement 16 cases préremplies ayant une solution unique, confirmant ainsi le nombre minimal de 17 cases préremplies nécessaire.

En conservant les règles du sudoku NxN qui demandent d'utiliser les N caractères sur chaque ligne et chaque colonne, alors il est impossible de les respecter si le sudoku n'est pas carré.

Certaines variantes du sudoku carré utilisent cependant des blocs intérieurs non carrés (voir sudoku 6x6, sudoku 7x7 ou sudoku 8x8)