Un petit solveur de sudokus…
Les sudokus, ces petites grilles carrées qui envahissent nos journaux et magazines depuis quelques années maintenant, ont donné naissance à de nombreux logiciels dont l’unique but est leur résolution. Appelés de façon barbare « solveurs », ces programmes sont désormais légion, qu’ils soient en C, en C++, en Python, en Java, et j’en passe. Aujourd’hui, je suis tombé (sans me faire mal) sur une de ces bêtes, mais particulièrement étonnante pour le coup ; un solveur de sudokus en Python… qui tient en quatre lignes !
Voici sans plus tarder l’exploit, dont je ne connais l’auteur :
# -*- coding: utf-8 -*-
def r(a):
i = a.find(‘0’)
if i<0: print a
[m in[(i-j)%9*(i/9^j/9)*(i/27^j/27|i%9/3^j%9/3) or a[j] for j in range(81)]
or r(a[:i]+m+a[i+1:]) for m in `14**7*9`]
En envoyant une chaîne de 81 chiffres à la fonction r, qui correspondent à la grille de sudoku avec 0 à la place des inconnues, cette dernière affiche une chaîne de 81 chiffres où, miracle, les 0 sont remplacés par les bonnes valeurs.
Certes, la méthode est tout ce qu’il y a de plus bourrin, du brute force au sens strict du terme, mais ça a la don de marcher et de ne tenir qu’en quatre lignes.
Comment ça marche ?
Si j’aère un peu le code, et que je l’explique un peu, ça sera sans doute plus clair :
# -*- coding: utf-8 -*-
# On va donc définir une fonction r qui, appelée récursivement, va résoudre
# nos sudokus.
def r(a):
i = a.find(‘0’) # On cherche le premier 0 de la chaîne, donc le premier
# "trou" du sudoku duquel on va chercher la valeur.
if i<0: print a # Si il n’y en a pas, c’est que le sudoku est résolu
# (donc find renvoie -1) ; on l’affiche.
# C’est là que ça devient génial. Savant mélange de compréhension
# et de or, on se retrouve avec quelque chose de très compact mais
# de diablement efficace que je détaille en dessous.
[m in[(i-j)%9*(i/9^j/9)*(i/27^j/27|i%9/3^j%9/3) or a[j] for j in range(81)]
or r(a[:i]+m+a[i+1:]) for m in `14**7*9`]
En fait, on va dans un premier temps parcourir la grille de sudoku pour faire une liste de valeurs impossibles pour la case en cours. Cela se fait par le code suivant :
Pour chaque naturel j de 0 à 80, on ajoute à la liste valeurs_impossibles (i-j)%9*(i/9^j/9)*(i/27^j/27|i%9/3^j%9/3) ou, si cette expression est fausse, a[j]. La liste contient donc les valeurs des cases de la ligne, de la colonne et du carré où se situe i, en plus de valeurs farfelues largement supérieures à 9 qui ne nous intéresse donc pas (le résultat de (i-j)%9*(i/9^j/9)*(i/27^j/27|i%9/3^j%9/3) dans le cas où il est non nul, en fait). On obtient donc une liste de valeurs impossibles pour i.
On regarde pour chaque chiffre m si il est dans la liste valeurs_impossibles. Si ce n’est pas le cas (or), on appelle la fonction r en lui envoyant la nouvelle grille où on a placé m dans la case i.
Enfin, dernier détail, dans le code original on a `14**7*9` et non « 123456789 ». En fait, ça revient au même, puisque 14**7*9 = 948721536, on a donc dans les deux cas une chaîne de tous les chiffres sauf zéro (l’ordre n’a pas d’importance). Seulement, `14**7*9` comporte deux caractère de moins par rapport à « 123456789 », utile quand on veut faire le plus petit solveur 
.
Grâce à la récursivité, on teste ainsi toutes les combinaisons possibles, au détriment de l’optimisation, mais on est sûr de trouver, si elle existe, la solution à notre sudoku (reste à savoir en combien de temps !). Factorisé au maximum, le code tient en quatre lignes, une prouesse permise par la puissance du langage de programmation Python.
