 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 19i 29i 39i 49i 59i 69i 79i 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 2727 x 933 nota pour la division entière cet algorithme de mon crû utilise la technique du backtracking 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 asettext 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 p43ghz pour le multithreading 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 01 09042006 création par jibux 02 15042006 ajout d info et liens merci nemo 03 13062006 simplification formule box x merci lessapregor todo mettre à jour les fichiers sources suite simplification les fichiers sources de cette application fichier attaché taille sudokujpg 3043 ko data2jpg 2901 ko les fichiers sources de cette application 101 ko  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 cassetê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 estil de ton crû estce le seul astu une idée du nombre d itérations maximales nécessaires pour résoudre un problème estil optimal pas d autre remarque notamment pour la forme c est ras   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 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 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 933 lessapregor wanadoofr résoudre un sudoku avec python bonjour effectivement merci pour cette simplification 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 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 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  python  