Contenu | Rechercher | Menus

Annonce

DVD, clés USB et t-shirts Ubuntu-fr disponibles sur la boutique En Vente Libre

Si vous avez des soucis pour rester connecté, déconnectez-vous puis reconnectez-vous depuis ce lien en cochant la case
Me connecter automatiquement lors de mes prochaines visites.

À propos de l'équipe du forum.

#1 Le 11/10/2014, à 12:24

toitoinebzh

Résoudre des Sudoku - Python + Tkinter

Bonjour à tous,

je vous présente un petit programme que je viens de développer et qui a été une bonne occasion pour me remettre à Python et apprendre Tkinter

c'est un programme qui permet d'entrer un tableau sudoku puis d'afficher la solution

au final, le fichier se compose de deux fichiers, un gère la résolution du sudoku, l'autre gère l'interface

tout d'abord le fichier fcts_sudoku.py

#!/usr/bin/env python
#-*- coding:utf-8 -*-
"""
Programme Sudoku
fait le 11/10/2014
Python 2.7.6 
"""

import numpy as np
#import time

# ============================================================================
# Classes
# ============================================================================
class Sudoku():
    """
    Permet de définir et résoudre un sudoku
    """

    def __init__(self, data):
        """
        initialise le sudoku
        """
        self.tableau = data # tableau initiale - celui à résoudre
        self.solution = np.zeros((9, 9)) # initialisation - tableau solution
        self.iteration = 0 # nb d'itérations avant résultat final

#        self.solve()
    def __repr__(self):
        """
        permet d'affichier le tableau initiale et la solution
        """
        print "\nTableau initiale\n"
        affiche_tab(self.tableau)
        print "\nSolution\n"
        affiche_tab(self.solution)
        print "\nNb d'itérations :", self.iteration
        return ""

    def ligne(self, i):
        """
        liste des nb dans une ligne
        """
        return self.solution[i, :]

    def colonne(self, j):
        """
        liste des nb dans une colonne
        """
        return self.solution[:, j]

    def pos_carre(self, i, j):
        """
        retourne la position d'un sous tableau sudoku
        """
        return 3*(i//3), 3*(j//3)

    def carre(self, i, j):
        """
        retourne l'ensemble de nb d'un sous tableau
        """
        pos_i, pos_j = self.pos_carre(i, j)
        sous_tableau = self.solution[pos_i:pos_i+3, pos_j:pos_j+3]
        return sous_tableau

    def presence_valeur(self, i, j, val):
        """
        test booleen pour savoir si un chiffre est déjà dans le tableau
        """
        return (val in self.ligne(i)) \
                or (val in self.colonne(j)) \
                or (val in self.carre(i, j))

    def case_vide(self, i, j):
        """
        test pour savoir si la case est rempli ou non
        """
        return self.tableau[i, j] == 0

    def avance(self, i, j, val):
        """
        détermine les indices de la case suivante pour la recherche
        """
        # on avance
        j = j+1
        val = 1
        if j > 9:
            i = i+1
            j = 1
        return i, j, val

    def recule(self, i, j, val):
        """
        détermine les indices de la case précédente pour la recherche
        """
        # on recule
        j = j-1
        if j < 0:
            j = 8
            i = i-1
        # on efface la valeur precedente
        # puis on teste la valeur suivante
        val = self.solution[i, j]+1
        if self.case_vide(i, j):
            self.solution[i, j] = 0
        else:
            i, j, val = self.recule(i, j, val)
        return i, j, val


    def deplacement(self, i, j, val):
        """
        gère le suivi de la case de recherche
        """
        if val < 10:
#            print "en avant"
            return self.avance(i, j, val)
        else:
#            print "en arrière"
            return self.recule(i, j, val)

    def solve(self):
        """
        resolution récursive du sudoku
        ne gère pas les sudoku sans solution
        """
        self.solution = np.copy(self.tableau)
        # on parcours tout le self.tableau
        i = 0
        while i < 9:
            j = 0
            val = 1
            while j < 9:
                # on teste toutes les valeurs
                if self.case_vide(i, j) and val < 10:
                    if self.presence_valeur(i, j, val):
                        val = val+1
                    else:
                        self.solution[i, j] = val
                        self.iteration = self.iteration + 1
#                        affiche_tab(self.solution)
#                        time.sleep(0.1)
                        i, j, val = self.deplacement(i, j, val)
                else:
                    i, j, val = self.deplacement(i, j, val)
            i = i + 1

# ============================================================================
# Fonctions
# ============================================================================
def affiche_tab(tableau):
    """
     affiche le sudoku en console
     """
    i, j = 0, 0
    for i in range(9):
        if i%3 == 0:
            print "-------------------------"
        for j in range(9):
            if j%3 == 0:
                print "|",
            if tableau[i, j] == 0:
                print "_",
            else:
                print tableau[i, j],
        print "|"
    print "-------------------------"
    
# ============================================================================
# Programme
# ============================================================================

if __name__ == '__main__':

#    tab_inconnu = [[0,0,0,0,0,0,0,0,0],
#                   [0,0,0,0,0,0,0,0,0],
#                   [0,0,0,0,0,0,0,0,0],
#                   [0,0,0,0,0,0,0,0,0],
#                   [0,0,0,0,0,0,0,0,0],
#                   [0,0,0,0,0,0,0,0,0],
#                   [0,0,0,0,0,0,0,0,0],
#                   [0,0,0,0,0,0,0,0,0],
#                   [0,0,0,0,0,0,0,0,0]]

#    tab_inconnu = [[3,0,0,0,7,6,8,0,0],
#                   [0,6,5,0,4,3,0,7,0],
#                   [9,0,0,8,0,0,0,0,3],
#                   [0,0,2,6,0,0,0,8,0],
#                   [0,3,9,0,8,0,2,6,0],
#                   [0,8,0,0,0,7,5,0,0],
#                   [5,0,0,0,0,2,0,0,7],
#                   [0,4,0,7,1,0,9,5,0],
#                   [0,0,6,5,9,0,0,0,8]]

    tab_inconnu = [[0,2,0,1,0,0,0,0,0],
                   [0,0,5,0,2,0,4,0,0],
                   [1,3,0,0,4,8,0,0,0],
                   [0,6,0,0,8,0,0,0,1],
                   [0,1,0,2,0,4,0,9,0],
                   [4,0,0,0,7,0,0,2,0],
                   [0,0,0,8,9,0,0,5,2],
                   [0,0,9,0,1,0,6,0,0],
                   [0,0,0,0,0,6,0,7,0]]

    tab_inconnu = np.array(tab_inconnu)
    mSudok = Sudoku(tab_inconnu)
#    start_time = time.time()
    mSudok.solve()
#    elapsed_time = time.time() - start_time
    print mSudok
#    print elapsed_time

puis le fichier Jeu.py


#!/usr/bin/env python
#-*- coding:utf-8 -*-

"""
Résoud des sudokus - interface
Python 2.7.6
"""

from fcts_sudoku import Sudoku
import Tkinter
import numpy as np

# ============================================================================
# Classes
# ============================================================================
class Interface():
    """
    Définit l'interface du jeu sudoku
    """
    
    def __init__(self):
        """
        initialisation
        """
        # fenetre
        self.fenetre=Tkinter.Tk()
        self.fenetre.title("Résolveur de Sudoku")
        self.fenetre.wm_attributes("-topmost", 1) # toujours au dessus
        
        # boutons
        self.bResoudre=Tkinter.Button(self.fenetre, text = 'Résoudre', command = self.fResoudre)
        self.bResoudre.grid(column=0,row=10,columnspan=3)
        self.bRelancer=Tkinter.Button(self.fenetre, text = 'Nouveau', command = self.fNouveau)
        self.bRelancer.grid(column=3,row=10,columnspan=3)
        self.bQuitter=Tkinter.Button(self.fenetre, text = 'Quitter', command = self.fQuitter )
        self.bQuitter.grid(column=6,row=10,columnspan=3)
        
        # creation des 9x9 cases
        self.fcreation_entree()
    
    def start(self):
        """
        lance le jeu
        """
        self.fenetre.mainloop()
                
    def fcreation_entree(self):
        """
        initialisation des entrees (Entry) et ajout a la fenetre
        """
        self.entree = []
        for i in range(9):
            self.entree+=[[]]
            for j in range(9):
                self.entree[i]+=[Tkinter.StringVar()]
        for i in range(9):
            for j in range(9):
                Tkinter.Entry(self.fenetre, textvariable = self.entree[i][j],width=3,font="18",justify='center').grid(column=i,row=j)
                self.entree[i][j].set( "")
                
    def fQuitter(self):
        """
        quitter l'application
        """
        self.fenetre.destroy()
        return
    
    def fResoudre(self):
        """
        résoud le sudoku et affiche la solution
        ne gère pas les sudoku sans solution
        """
        # on recupere les valeurs
        tableau = np.zeros((9, 9))
        for i in range(9):
            for j in range(9):
                val=self.entree[i][j].get()
                if isValid(val):
                    val=int(val)
                else:
                    val=0
                tableau[i,j]=val
        # on resoud le sudoku
        mSudok = Sudoku(tableau)
        mSudok.solve()
        
        # on affiche la solution
        for i in range(9):
            for j in range(9):
                self.entree[i][j].set( str(int(mSudok.solution[i, j])))
        return
    
    def fNouveau(self):
        """
        on reinitialise le tableau d'entrees (Entry)
        """
        for i in range(9):
            for j in range(9):
                self.entree[i][j].set( "")
        return
# ============================================================================
# Fonctions
# ============================================================================
def isValid(val):
    """
    test la valeur dans les cases
    - vrai si nombre entier entre 1 et 10
    - faux sinon
    """
    try:
        val=int(val)
        if val>0 and val<10:
            return True
        else:
            return False
    except:
        return False
# ============================================================================
# Programme
# ============================================================================

if __name__ == '__main__':
    Jeu=Interface()
    Jeu.start()

pour lancer le jeu, il suffit de lancer le fichier Jeu.py
-- soit en ligne de commande
         

python Jeu.py

-- soit en interface graphique,
   clic droit sur le fichier Jeu.py > Propriétés > Permissions > Autoriser ce fichier à être exécuté ...

tout fonctionne bien, par contre je ne gère par les sudokus sans solution, l'interface peut être améliorée... je pense que je vais en rester là

si vous avez des critiques sur ma manière de programmer, je suis intéressé, étant plutôt autodidacte en programmation et python

source de la dernière version dispo ici > https://framagit.org/anto1ne/sudokusolver

Dernière modification par toitoinebzh (Le 29/10/2021, à 16:43)

Hors ligne

#2 Le 11/10/2014, à 12:43

Braun

Re : Résoudre des Sudoku - Python + Tkinter

Bonjour,
Question Sudoku, j'ai un faible pour (g)prolog.

Hors ligne

#3 Le 11/10/2014, à 18:50

ElGatoNegro

Re : Résoudre des Sudoku - Python + Tkinter

Salut,
après un :

sudo apt-get install python-numpy python-tk

ça fonctionne bien.
Désolé de ne pouvoir critiquer (dans le bon sens du terme) ton code, je n'y connais pas grand chose...
Mais peut-être pourrais-tu vérifier la présence des modules nécessaires, au lancement?
@+


"Écart est le palindrome de Tracé" (Alain Damasio)

Hors ligne

#4 Le 11/10/2014, à 20:53

toitoinebzh

Re : Résoudre des Sudoku - Python + Tkinter

merci du retour smile

en effet, il faut ces deux modules, j'utilise numpy et tkinter, pour la résolution et l'affichage
ces modules sont très répandues, je ne me suis pas posé la question de la présence ou non de ces modules

concernant prolog, je n'ai jamais entendu parler de ce langage, d'après wikipedia, ce langage a en effet  l'air d'être bien adapté pour résoudre ce genre de problème

Hors ligne

#5 Le 12/10/2014, à 05:55

pingouinux

Re : Résoudre des Sudoku - Python + Tkinter

Bonjour,
J'ai commencé à regarder tes scripts, et voici deux remarques :

  • Si j'ai bien compris, les indices i et j varient entre 0 et 8 (inclus).
    Dans avance, cette ligne

            if j > 9:

    ne devrait-elle pas être

            if j > 8:
  • Ces cas n'étant pas testés, n'y a-t-il pas de risque d'appeler avance avec i,j==8,8, ou recule avec i,j==0,0 ?

Hors ligne

#6 Le 12/10/2014, à 09:53

toitoinebzh

Re : Résoudre des Sudoku - Python + Tkinter

pingouinux a écrit :

Bonjour,
J'ai commencé à regarder tes scripts, et voici deux remarques :

  • Si j'ai bien compris, les indices i et j varient entre 0 et 8 (inclus).
    Dans avance, cette ligne

            if j > 9:

    ne devrait-elle pas être

            if j > 8:
  • Ces cas n'étant pas testés, n'y a-t-il pas de risque d'appeler avance avec i,j==8,8, ou recule avec i,j==0,0 ?

merci pour ces remarques,

pour la première remarque, la ligne if j>9 est juste, l'indice j varie entre 0 et 8, j'avance d'une case en incrémentant ce j, d'où la ligne précédente j=j+1
par contre il faut faire attention au cas où on sort du tableau soit j=9, dans ce cas, je passe à la ligne suivante j=1, et i=i+1

le cas i,j==8,8 avec avance ne pose pas de problème, avance va changer i en 9
ma boucle while i <9 termine le programme,

pour la seconde remarque, je n'ai en effet pas pris en compte le cas où i,j==(position de la première case vide)  avec recule, c'est une amélioration à réaliser,

en effet je suppose par défaut que les sudokus que l'on cherche à résoudre ont une solution, je ne gère pas les sudokus sans solution avec ce programme

Hors ligne

#7 Le 27/10/2021, à 13:36

Qsoftware

Re : Résoudre des Sudoku - Python + Tkinter

Bonjour,

J'étais à la recherche d'un moyen pour résoudre un sudoku et je suis tombé ici. J'ai alors immédiatement pris le code-source.
Et j'ai trouvé dommage que personne depuis l'ai remis au goût du jour en python3. Alors je l'ai fait. 

Le code-source en python3 est disponible ici :

https://gitlab.com/GitQsoftware/resoud_sudoku

Jeune en développement, j'ai trouvé alors dommage que les cases ne sont pas séparées comme sur une vrai grille de sudoku : Alors je vais aussi me lancer dedans.

Bonne journée et merci wink


-- Rien de mieux que Xubuntu --

Hors ligne

#8 Le 27/10/2021, à 19:02

toitoinebzh

Re : Résoudre des Sudoku - Python + Tkinter

salut Qsoftware,

bravo pour ce travail, j'avais oublié que j'avais lancé cette discussion
ton script fonctionne bien chez moi, c'est une bonne nouvelle smile

dommage que l'on a pas discuté plus tôt, j'avais déjà fait le passage en python3 il y a a peu près 2 ans, je n'ai pas donné de nouvelles ici, mon code source est dispo ici, il doit être similaire au tien
https://framagit.org/anto1ne/sudokusolver

à l'époque où j'avais codé ce jeu, l'interface graphique était mon point faible, j'ai pas mal progressé depuis mais j'ai quitté tkinter au profit de pyqt (plus joli)

fais toi plaisir à développer une interface à ton goût, ton code est bien structuré, la partie intelligence du jeu est séparée de la partie interface graphique, cela devrait te faciliter la tache
pour ajouter un espace entre chaque carré, je pense qu'il faut regarder du coté de la fonction fcreation_entree

en amélioration possible, il y a aussi la vérification du tableau avant de lancer la résolution, si on entre un tableau qui n'a pas de solution (par exemple 2 case 1 dans le même carré, le jeu plante, ce bug existe aussi de mon coté)

au passage, joli icône tu l'as trouvé où ?

Dernière modification par toitoinebzh (Le 27/10/2021, à 19:13)

Hors ligne

#9 Le 28/10/2021, à 08:03

Qsoftware

Re : Résoudre des Sudoku - Python + Tkinter

Bonjour toitoinebzh,
Merci pour ces idées d’amélioration. Je pense aussi refaire l'interface graphique en Pyqt5 : Je développe depuis un 1 an seulement et est appris Tkinter. Mais depuis quelques semaines, je me mets à Pyqt.

Pour l'icône, je l'ai trouvée sur le site web flaticon.com qui propose des icônes gratuites en créditant le créateur de celle-ci.


Je reviendrai sur ce forum au fil de mes améliorations pour t'en faire part.


Bonne journée cool


-- Rien de mieux que Xubuntu --

Hors ligne

#10 Le 28/10/2021, à 18:29

toitoinebzh

Re : Résoudre des Sudoku - Python + Tkinter

merci pour le lien
n'hésites pas à donner des nouvelles wink

Hors ligne

#11 Le 28/10/2021, à 21:05

Nuliel

Re : Résoudre des Sudoku - Python + Tkinter

Bonjour,
Pour info il y a plein de méthodes ultra efficaces pour résoudre un sudoku, surtout lorsqu'on passe à des sudoku plus grand que 9x9, ça peut être très utile! C'est un domaine très intéressant


[ poster un retour de commande ] [ poster une photo ]
Thinkpad x220, Dell latitude E7270 (i7 6600U, 16 Go de RAM, ...), Thinkstation E32 modifié: i5-4570, GTX 1060 6 Gb, 16 Gb de RAM, ...
Mon nouveau blog: nuliel.fr

Hors ligne

#12 Le 29/10/2021, à 21:51

beuguissime

Re : Résoudre des Sudoku - Python + Tkinter

Salut Nulliel,
Si tu as des liens vers des ressources en ligne discutant des techniques de résolution des sudoku, je veux bien. Pour le jour où je serai en manque de maths/d'algorithmique wink

Dernière modification par beuguissime (Le 29/10/2021, à 21:54)

Hors ligne

#13 Le 29/10/2021, à 22:27

Nuliel

Re : Résoudre des Sudoku - Python + Tkinter

Je t'ai envoyé un MP

http://hodoku.sourceforge.net/en/tech_intersections.php contient pas mal d'exemples de techniques pour résoudre un sudoku.

Dernière modification par Nuliel (Le 29/10/2021, à 22:29)


[ poster un retour de commande ] [ poster une photo ]
Thinkpad x220, Dell latitude E7270 (i7 6600U, 16 Go de RAM, ...), Thinkstation E32 modifié: i5-4570, GTX 1060 6 Gb, 16 Gb de RAM, ...
Mon nouveau blog: nuliel.fr

Hors ligne