Méthode pour remplir un sudoku
Méthode générale élémentaire. Sudoku diabolique. Déduction non élémentaire.
La méthode générale élémentaire
La méthode générale élémentaire consiste à opérer itérativement avec les deux étapes suivantes.
Première étape : déterminer les chiffres possibles
Pour chaque case vide, on essaye successivement chaque chiffre {1, 2, 3, 4, 5, 6, 7, 8, 9}.
Un chiffre est possible s’il n’apparaît ni dans la ligne, ni dans la colonne, ni dans le carré 3×3.
Tant que l'on trouve une case ne comportant qu'un seul chiffre possible, on peut la remplir.
Sinon on passe à l’étape 2 ci-dessous.
Deuxième étape : réduire les possibilités
Pour chaque case non encore remplie, on poursuit comme suit :
- Si un chiffre possible pour la case n'est pas possible ailleurs dans la ligne, alors la case peut se réduire à ce chiffre.
- Si un chiffre possible pour la case n'est pas possible ailleurs dans la colonne, alors la case peut se réduire à ce chiffre.
- Si un chiffre possible pour la case n'est pas possible ailleurs dans le carré 3×3, alors la case peut se réduire à ce chiffre.
Si une case a été remplie, on recommence le processus à l’étape 1 en passant en revue toutes les cases non remplies.
En cas d’échec de la méthode générale élémentaire, de blocage complet, on est en présence d’un sudoku diabolique.
Le sudoku diabolique
Il existe deux moyens de résoudre les sudokus diaboliques : essayer un chiffre ou trouver une déduction non élémentaire.
Essayer un chiffre
La méthode générale pour les sudokus diaboliques consiste à essayer un chiffre. On commence par choisir, si possible, une case où il n’y a que deux possibilités. On choisit l’un des deux chiffres en tant qu’hypothèse, en gardant l’autre en mémoire. Dans le cas où, en poursuivant le remplissage de la grille, on se rend compte que la première hypothèse ne convient pas, il faut faire marche arrière et revenir au deuxième chiffre laissé en suspens. Pratiquement, on réalise les essais avec un crayon effaçable.
Il se peut que, même si l’hypothèse était la bonne, le sudoku reste diabolique. Il faut alors essayer des chiffres une deuxième fois dans une autre case, puis peut-être une troisième, etc, après quoi les marches arrière imbriquées peuvent s'avérer diablement compliquées.
Avant de se lancer dans un essai qui peut être coûteux, il est prudent de vérifier que l’on a vraiment épuisé la méthode générale élémentaire. L'application en ligne Résolveur permet d'en avoir la garantie : à l'Étape 2: remplir la grille, si la grille est diabolique, actionner le bouton Remplissage partiel.
Trouver une déduction non élémentaire
Dans certains cas, on peut éviter de faire une hypothèse au moyen d'un raisonnement plus élaboré que la simple application de la méthode générale élémentaire : une déduction non élémentaire qui exploite des particularités de la situation. Voici un exemple proposé par Jean Paul VINCENT :
Dans le carré central, le chiffre 4 se trouve dans la colonne 4, ce qui exclut que le chiffre 4 soit dans la case (1,4). Donc, dans le carré central supérieur, le chiffre 4 se trouve dans la case (2, 5).