J’ai bricolé vite fait un solveur de Sudoku sur le trajet de mes vacances à Berlin : http://pierre.fritsch.free.fr/sudoku

Il est programmé exclusivement en JavaScript.

Pour résoudre, l’algorithme maintient la liste des valeurs possibles pour chaque case, et fait 4 choses en cas de changement :

• Elimination des impossibles ;
• Recherche des absents ;
• Elimination des doublettes ;
• Elimination des triplettes.

Elimination des impossibles

Chaque fois qu’une case est résolue, la valeur correspondante est supprimée dans les autres cases sur la même ligne, la même colonne, et le même carré.

Recherche des absents

Lorsqu’un groupe (ligne, colonne, ou carré) ne contient qu’une seule case susceptible d’accueillir une valeur, alors cette valeur est assignée à la case en question.

Elimination des doublettes

Lorsque, dans un groupe, 2 cases ont chacune seulement 2 valeurs possibles, et si ces valeurs sont identiques, alors ces 2 valeurs sont forcément présentes dans ces 2 cases, et nulle part ailleurs dans le groupe.

Exemple :

-------------------------------------------------------
| 57  | 657 |  1  |  8  |  9  |  4  |  3  | 62  |  62 |
-------------------------------------------------------

Les valeurs 2 et 6 seront nécessairement présentes dans les deux dernières cases, ainsi on peut les éliminer dans la première case :

-------------------------------------------------------
| 57  |  57 |  1  |  8  |  9  |  4  |  3  | 62  |  62 |
-------------------------------------------------------

Elimination des triplettes

Même principe lorsque 3 valeurs apparaissent dans 3 cases.

Exemple :

-------------------------------------------------------
|  1  |  6  | 78  |  5  |  9  | 238 | 23  | 238 |  4  |
-------------------------------------------------------

Les valeurs 2, 3, et 8 apparaîtront forcément dans les sixième, septième, et huitième cases de ce groupe. Ainsi, on peut les éliminer partout ailleurs, ce qui résout la troisième case :

-------------------------------------------------------
|  1  |  6  |  7  |  5  |  9  | 238 | 23  | 238 |  4  |
-------------------------------------------------------