Le Sudoku est un jeu très à la mode: le principe est de remplir une grille de 81 cases avec les chiffres de 1 à 9 de façon à ce qu'aucun chiffre ne se répète dans aucune ligne, aucune colonne et aucune région (carré 3x3).
Pour remplir les cases vides, on procède donc par élimination. On n'écrit le chiffre que lorsqu'on en est sûr. On remplit la grille de proche en proche.
Il y a 4 niveaux de difficulté selon le nombre de cases données initialement:
Le sudoku ci-dessous est facile:
|
Pour la résolution, on peut commencer ici par la 6ème ligne: il ne manque que 3 valeurs: 1, 3 et 7. La case (6,5) (ligne 6, colonne 5) ne peut accepter que le 3 car les chiffres 1 à 7 sont déjà dans la colonne. De même: case (6,7) vaut 1, case (6,9) vaut 7. Etc...
Pour résoudre, on remplit donc les cases qui ne peuvent avoir qu'une seule valeur possible (on n'écrit un chiffre que quand on en est sûr).
Si on est bloqué (il ne reste donc des cases vides qui peuvent avoir plusieurs valeurs possibles), on regarde si une de ces valeurs possibles n'apparaît qu'une seule fois dans les possibilités des autres cases vides de la ligne, colonne et région. Par exemple la valeur 7 dans les 3 régions du bas: il apparaît dans la région (3,1) à la 3ème ligne (case (9,1)), et dans la région (3,3) à la 1ère ligne. Il ne peut donc apparaître dans la région (3,2) qu'à la 2ème ligne (cases (8,5) ou (8,6)). Mais comme il est déjà dans la colonne 5, le 7 ne peut donc être que dans la case (8,6).
Et ainsi de suite de proche en proche... Mais si on est vraiment bloqué, on est amené à fixer arbitrairement la valeur d'une case vide, c'est ce qui s'appelle une hypothèse (rassurez-vous, ça n'arrive que dans le niveau diabolique). Si on arrive à une impossibilité lors de la résolution, on doit alors gommer tout ce qu'on a rempli depuis l'hypothèse et en poser une autre.
Bon allez, voici la solution de la grille ci-dessus.
Le site www.websudoku.com propose des millions de grilles à tous les niveaux de difficulté. On peut ainsi s'en imprimer une petite réserve...
Pour les petits curieux comme moi, je leur propose un programme de résolution maison, avec le source en C, l'exécutable (pour fenêtre MS-DOS de Windows, ou Terminal de Mac OS X), et sa documentation. Ce programme permet de résoudre ou créer des grilles de tous niveaux, et de les imprimer.
Mise à jour: