Posté par
Frege64 Frege64
Solution:
| 7 | 1 | 8 | 3 | 6 | 4 | 5 | 9 | 2 |
| 3 | 6 | 5 | 7 | 9 | 2 | 4 | 8 | 1 |
| 9 | 4 | 2 | 5 | 1 | 8 | 7 | 6 | 3 |
| 8 | 5 | 9 | 2 | 4 | 1 | 3 | 7 | 6 |
| 6 | 7 | 1 | 9 | 5 | 3 | 8 | 2 | 4 |
| 2 | 3 | 4 | 6 | 8 | 7 | 1 | 5 | 9 |
| 5 | 2 | 7 | 1 | 3 | 6 | 9 | 4 | 8 |
| 1 | 8 | 6 | 4 | 7 | 9 | 2 | 3 | 5 |
| 4 | 9 | 3 | 8 | 2 | 5 | 6 | 1 | 7 |
Initialement, j'ai pensé à trouver une solution par pure déduction.
Sur certaines cases, cela est tout à fait possible, et c'est ainsi que, par exemple, j'ai placé le 3 de L4C7 (car à l'intersection d'une ligne contenant un 2 et d'une colonne contenant un 1 => il restait seulement 3 comme possibilité).
De là, j'ai progressé un peu, mais la seule déduction logique n'aboutissait pas.
La solution finale a été obtenue en exploitant deux caractéristiques de l'exercice:
[ol]
[li] les groupes de chiffres (1,2,3) (4,5,6) et (7,8,9) sont totalement indépendants; résoudre le problème consiste donc à résoudre trois exercices indépendants portant, respectivement, sur chacun des trois groupes;[/li]
[li] Chaque groupe ne comportant que trois chiffres, le nombre de combinaisons est faible et il est facilement possible de tester exhaustivement un choix
quasi quelconque pour voir s'il correspond à une solution possible; je m'en suis rendu compte lorsque, suite à une erreur de déduction sur le groupe (4,5,6) j'ai abouti,
très rapidement, à une imossibilité;[/li]
[/ol]
La mise en oeuvre a donc consisté à:
* Pour chaque groupe
+ pousser la déduction logique aussi loin que possible
+ dans un carré 3x3 "
judicieux" faire une supposition qui permette de finir de remplir la grille (d'ou le choix "
judicieux" de carré 3x3)
+ voir si on aboutit à une impossibilité; si oui: faire le choix opposé à la supposition (c'est binaire dès qu'un des trois chiffres du groupe est déjà renseigné dans le carré 3x3); si non: on a une solution pour ce groupe
* passer au groupe suivant.
Voilà.
C'était amusant, mais moins qu'un "vrai" Sudoku car la résolution fait plus appel à une recherche exhaustive par essai/erreur que à une déduction logique.