Résoudre un SuDoku avec Python
Vous connaissez sûrement ce passe temps qui fait fureur en ce moment, je veux bien sur parler du SuDoku.
Pour ceux qui ne connaîtraient pas, une petite recherche dans google vous retournera 68 millions de pages !
Si vous avez échappé à l’épidémie, ce lien vous expliquera les règles du jeu. Pour plus de renseignements wikipedia est votre ami.
Je vous propose de réaliser un programme en python pour trouver la solution des grilles de SuDoku qu’on trouve un peu partout.
Éléments abordés dans ce document
En plus des différents sujets abordés dans les tutoriels précédents, voici les nouvelles notions que nous allons découvrir :
Au travail
Avant toutes choses, il va falloir choisir le mode de représentation de la grille.
81 cases numérotées de 0 à 80
9 lignes, 9 colonnes et 9 boîtes numérotées de 0 à 8
Puis on va définir 3 fonctions pour retrouver les valeurs stockées dans les lignes, colonnes et boîtes :
lig[x]=[9i,9i+1,9i+2,9i+3,9i+4,9i+5,9i+6,9i+7,9i+8]
(avec i=x/9)
col[x]=[i,i+9,i+18,i+27,i+36,i+45,i+54,i+63,i+72]
(avec i=x%9)
box[x]=[i,i+1,i+2,i+9,i+10,i+11,i+18,i+19,i+20]
(avec i=(x/27)*27+(x%9/3)*3
nota : / pour la division entière
Cet algorithme de mon crû utilise la technique du back-tracking. Il cherchera toutes les solutions possibles en partant de la première case et en testant toutes les valeurs possibles par ordre croissant. En cas de blocage, on retourne en arrière et on prend la valeur suivante etc ...
Cette méthode très simple me permet d’expliquer à un enfant comment les ordinateurs peuvent faire pour trouver des solutions. Il suffit pour cela d’une feuille de papier et d’un crayon et suivre la recette décrite plus bas en la faisant tourner à la main.
Il est clair qu’elle n’est certainement pas la plus rapide.
On utilise grille qui contient le problème à résoudre et grilleTemp qui contient la solution en cours de calcul.
lig(i) retourne l’ensemble des valeurs déjà utilisées pour la ligne i (idem pour col() et box() )
valMinSup([],x) retourne la plus petite valeur possible supérieure à x en éliminant les valeurs présentes dans la liste
Ceci donne en pseudo code :
grilleTemp = grille
i = 0
Boucler
si grille(i) est vide
nouvelleValeur = valMinSup(lig(i)+col(i)+box(i), grilleTemp(i))
si nouvelleValeur correcte
grilleTemp(i) = nouvelleValeur
i += 1
sinon
grilleTemp(i) = 0
tantQue i>0 et grille(--i) non vide
sinon
i += 1
si i < 0
fin du programme sans avoir trouvé de solution
si i > 80
fin du programme, la solution est dans grilleTemp
C’est tout, en fait le programme est vraiment très simple. Nous pouvons maintenant utililser nos outils favoris (eric et QT Designer) pour créer ce programme.
QT Designer nous permet de créer ceci :
Pour le code, pas de difficulté particulière hormis la petite astuce qui permet d’adresser toutes les cases de la grille dans une boucle.
for i in range(81):
a=getattr(self, "lineEdit%d" % i)
a.setText('')
Par contre, la fonction qui cherche la solution est une candidate idéale pour un thread. En effet si la recherche est un peu longue, l’application se fige. Lors de mes tests, la grille la plus simple a été trouvée après 242 tests tandis que la plus compliquée en a nécessitée 229 425, soit 11 secondes de calcul sur mon P4-3GHz.
Pour le multi-threading, j’ai suivi les recommandations de cet article (en anglais).
Le point important à ne pas oublier avec les threads, c’est qu’il n’est pas possible d’échanger des données directement avec le programme principal. Il faut passer par la fonction customEvent(), sinon, c’est le segfault assuré.
Historique des modifications
Version | Date | Commentaire |
---|---|---|
0.1 | 09/04/2006 | Création par Jibux |
0.2 | 15/04/2006 | Ajout d’info et liens (merci [Nemo]) |
0.3 | 13/06/2006 | Simplification formule box[x] (merci lessap.regor) |
TODO : mettre à jour les fichiers sources suite simplification.
Fichier attaché | Taille |
---|---|
sudoku.jpg | 30.43 Ko |
data-2.jpg | 29.01 Ko |
Les fichiers sources de cette application | 10.1 Ko |
Commentaires
Résoudre un SuDoku avec Python
Résoudre un SuDoku avec Python
Et pour la génération de labyrinthe, cela me rappelle un programme que j’ai réalisé il y a une bonne vingtaine d’années qui se trouve ici
Résoudre un SuDoku avec Python
Bonjour,
Pourquoi pas, mais il faudrait connaître une méthode pour faire cela.
La difficulté principale étant que la grille proposée ne doit admettre qu’une solution.
Résoudre un SuDoku avec Python
A quand la génération d’un Sudoku avec Python ? Le programme décrit ici serait un complément intérêssant pour trouver les solutions de la grille générée.
La génération me semble un problème encore plus difficile que la résolution, c’est un peu comme le problème de génération d’un labyrinthe, la résolution est plus "simple" que la génération.
Résoudre un SuDoku avec Python
Bonjour,
effectivement.
Merci pour cette simplification
Résoudre un SuDoku avec Python
Bonjour
Il me semble que le 2eme terme de i pour box(x) peut être plus simple tout en donnant le même résultat : (x%9/3)*3
lessap.regor@wanadoo.fr
> Résoudre un SuDoku avec Python
Merci pour ces précisions.
Je trouve que ce que tu as rajouté à ton article le complète bien et permet de mieux préciser le contexte d’écriture.
> Résoudre un SuDoku avec Python
Merci pour tes remarques.
J’ai rajouté des informations à mon article en tenant compte de tes questions.
Voici mes réponses :
> Résoudre un SuDoku avec Python
Pour une fois je ne me contenterai pas du traditionnel RAS :o)
Tout d’abord, je fais partie des rares excentriques qui ne connaissent pas encore le Sudoku (j’ai pigé que c’est un casse-tête) ou plutôt qui n’en connaissent pas les règles : il serait peut-être utile d’intégrer un court rappel des règles du jeu ou, à défaut, un lien vers une page les exposant, non ?
Mon autre interrogation porte sur l’algorithme de résolution :
Pas d’autre remarque (notamment pour la forme, c’est RAS).