Skip to Content

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 :

  •  Les threads « avec QThread, QCustomEvent(), setData(), postEvent() »
  •  Une astuce pour adresser toutes les cases de la grille « avec getAttr() »

    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.

    Zip - 10 ko
    Les fichiers sources de cette application
  • Fichier attachéTaille
    sudoku.jpg30.43 Ko
    data-2.jpg29.01 Ko
    Les fichiers sources de cette application10.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 :

  •  OUI : il est de mon crû, mais en utilisant une technique très classique. Pour la petite histoire je l’ai utilisé pour la première fois sans la connaître, il y a maintenant pas mal d’années (ça ne nous rajeuni pas !).
  •  NON : il y en a sûrement, je pense, presque autant qu’on veut bien en imaginer !
  •  NON : il y a théoriquement 9^81 possibilités. Mais la méthode de calcul élimine toutes les solutions impossibles dès qu’elle les trouvent.
  •  NON : il faudrait par exemple commencer par les cases qui ont le moins de possibilités. Mais comme je l’ai rajouté dans l’article le but était de faire comprendre à mon fils comment une machine peut faire pour trouver des solutions.
  • > 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 :

  •  est-il de ton crû ?
  •  est-ce le seul ?
  •  as-tu une idée du nombre d’itérations maximales nécessaires pour résoudre un problème ?
  •  est-il optimal ?
    Pas d’autre remarque (notamment pour la forme, c’est RAS).