Une grille de sudoku se fabrique, par convention, de façon à n’avoir qu’une seule solution. Avec deux solutions ou plus, il faudrait forcément choisir au hasard quelque part, et ce ne serait plus un puzzle que l’on résout par la seule logique.
Un exemple à deux solutions
La grille ci-dessous est une grille complète dont on a effacé seulement quatre chiffres. Dans les cases vides, les chiffres possibles (les candidats) sont notés.
Les quatre cases ont pour candidats 4 et 9.
- Si la case ligne 2, colonne 5 est 4, la case ligne 2, colonne 8 est 9, la case ligne 3, colonne 5 est 9, et la case ligne 3, colonne 8 est 4.
- Si la case ligne 2, colonne 5 est 9, la case ligne 2, colonne 8 est 4, la case ligne 3, colonne 5 est 4, et la case ligne 3, colonne 8 est 9.
Les deux respectent la règle : il y a donc deux solutions. Il n’y a que quatre cases vides, mais on ne peut en décider aucune.
Quand les quatre cases d’un rectangle, à l’intersection de deux lignes et de deux colonnes, s’étendent sur deux blocs et peuvent échanger les deux mêmes chiffres, la solution n’est pas unique. Quand on fabrique une grille, il faut donc laisser un chiffre dans l’une de ces cases pour que cette forme ne subsiste pas.
Une grille résoluble par des techniques a une solution unique
Les techniques n’avancent qu’avec des affirmations sûres : « seul ce chiffre peut aller dans cette case », « ce chiffre ne peut pas aller dans cette case ».
Si l’on a pu résoudre toute la grille avec des techniques à partir des chiffres de départ, chaque coup était un coup « qu’on ne pouvait que jouer ». S’il existait une autre solution, elle serait en contradiction, quelque part, avec un coup qui ne pouvait pas être autrement. La solution d’une grille résoluble par des techniques est donc unique.
L’app NumberPlace utilise cette propriété pour fabriquer ses grilles. À chaque chiffre effacé, elle vérifie que des techniques suffisent encore, et n’efface que dans ce cas (Comment on fabrique un sudoku). C’est pourquoi toutes les grilles de l’app n’ont qu’une seule solution et se résolvent jusqu’au bout sans rien deviner.
Comment compter le nombre de solutions
Même pour une grille que les techniques ne résolvent pas, on peut vérifier si la solution est unique. Par ordinateur, on place les chiffres dans les cases vides dans l’ordre, en revenant en arrière en cas d’impasse (retour sur trace), et l’on cherche toutes les solutions. Dès qu’on en trouve deux, on sait que la solution n’est pas unique, et l’on peut s’arrêter là (Algorithme de résolution du sudoku).
L’app utilise aussi cette méthode pour vérifier que la solution est unique quand elle recharge, depuis la sauvegarde, une grille jouée en partie.
Ce que cela change pour celui qui résout
Savoir que la solution est unique peut aussi servir à celui qui résout. Par exemple, une « forme échangeable » comme les quatre cases ci-dessus ne devrait pas apparaître dans une grille à solution unique. Les joueurs expérimentés s’en servent parfois à l’envers pour barrer des candidats. Mais c’est un raisonnement qui suppose que « la solution est unique » : on ne peut pas le déduire de la seule règle. Indice, dans l’app, n’utilise pas ce raisonnement : il ne montre la prochaine case qu’avec des techniques qui se déduisent sûrement de la règle.
