Le Sudoku dans sa forme la plus répandue consiste à compléter une grille de 9×9 cases avec les chiffres de 1 à 9, de sorte à ce que chaque chiffre apparaisse exactement une fois dans chaque bloc.
Chaque case appartient à 3 blocs qui sont :
Nous nous proposons ici de résoudre des grilles de Sudoku en Python sur calculatrices Casio Graph 90/35+E II, fx-9750/9860GIII et fx-CG50.
Chaque case appartient à 3 blocs qui sont :
- la ligne
- la colonne
- l'un des 9 carrés juxtaposés de 3×3 cases
Nous nous proposons ici de résoudre des grilles de Sudoku en Python sur calculatrices Casio Graph 90/35+E II, fx-9750/9860GIII et fx-CG50.
Mais comment résout-on un Sudoku ?
Une première méthode naïve est d'inscrire les 9 chiffres possibles dans chaque case vide, puis de procéder par élimination en rayant de chaque case ainsi complétée les chiffres apparaissant déjà dans chacun des 3 blocs concernés :
Sur les grilles les plus simples comme la précédente, cette règle permet d'induire 352 déductions et suffit à remplir l'ensemble de la grille.
Une première méthode naïve est d'inscrire les 9 chiffres possibles dans chaque case vide, puis de procéder par élimination en rayant de chaque case ainsi complétée les chiffres apparaissant déjà dans chacun des 3 blocs concernés :- sur la même ligne
- sur la même colonne
- dans le même carré
Après 297 déductions qui n'ont permis de remplir que 4 cases nous voilà avec une grille non remplie sur laquelle on ne peut pourtant plus rien déduire.
Rajoutons donc quelques stratégies :
On peut même aller encore plus loin et constater que la toute première méthode naïve n'est qu'un cas particulier de cette stratégie étendue que nous venons de formuler, si bien que tout ce qui a été évoqué jusqu'ici peut être vérifié via un unique appel de fonction.
- Nous pouvons citer la méthode des paires exclusives : si 2 cases non résolues d'un même bloc n'admettent plus qu'une même paire de 2 chiffres $mathjax$\left(a_1, a_2\right)$mathjax$, alors ces 2 chiffres sont impossibles sur toutes les autres cases du bloc.
- De là nous pouvons passer à la méthode des triplets exclusifs : si 3 cases non résolues d'un même bloc n'admettent plus que tout ou partie d'un même triplet de 3 chiffres $mathjax$\left(a_1, a_2, a_3\right)$mathjax$, alors ces 3 chiffres sont impossibles sur toutes les autres cases du bloc.
- La même stratégie peut être formulée pour les quadruplets et même généralisée jusqu'aux N-uplets de dimension $mathjax$N=8$mathjax$.
$mathjax$\left(a_1,a_2,a_3, ..., a_N\right)$mathjax$
, alors ces N chiffres sont impossibles sur toutes les autres cases du bloc.On peut même aller encore plus loin et constater que la toute première méthode naïve n'est qu'un cas particulier de cette stratégie étendue que nous venons de formuler, si bien que tout ce qui a été évoqué jusqu'ici peut être vérifié via un unique appel de fonction.
En fait il existe d'autres stratégies, et plus les grilles se compliqueront plus il sera nécessaire d'en invoquer plusieurs.
Une autre stratégie devenant pertinente une fois que les précédentes ne donnent plus rien, est de procéder par essais-erreur et retour arrière (backtracking) :
Avec tout ceci nous arrivons à conclure cette fois-ci. 9 paris, ici tous justes, nous permettent de pousser jusqu'à 467 déductions et remplir toute la grille.
Une autre stratégie devenant pertinente une fois que les précédentes ne donnent plus rien, est de procéder par essais-erreur et retour arrière (backtracking) :
- on sauvegarde l'état de la grille
- on choisit une case non encore déduite parmi celles offrant le moins de possibilités
- on fait alors un pari : on y inscrit l'une des valeurs possibles et on l'utilise pour reprendre les déductions précédentes
- si ces déductions nous conduisent à une impasse (case avec plus aucune valeur possible), alors c'est que le pari que nous avons fait n'était pas bon - on revient en arrière pour parier une autre valeur sur la case en question
- si ces déductions s'achèvent sur une grille inachevée, on recommence : nouvelle sauvegarde avec choix d'une nouvelle case pour des paris supplémentaires
Notre script Python est-il bien capable de s'en sortir dans tous les cas ? Pour le vérifier, attaquons-nous à "Al Escargot", réputée pour être la grille de Sudoku la plus difficile.Le site spécialisé Parfum-Echecs estime sa difficulté à 40 étoiles. Pour référence chaque étoile nécessite au minimum autour de 50 coups, et les Sudoku de la presse ne dépassent jamais les 7 étoiles (au minimum dans les 350 coups). Ici avec 40 étoiles, dans le meilleur des cas nous en sommes déjà à 2000 coups.
Les performances sont toutefois en-deça de l'estimation puisque nous avons ici 3729 coups, répartis en :
- 3654 déductions de valeurs de cases
- 75 paris
