Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

Python Discussion :

Backtracking / Résolution sudoku


Sujet :

Python

  1. #1
    Nouveau Candidat au Club
    Backtracking / Résolution sudoku
    Bonjour,

    dans un projet pour mes cours, je doit réaliser un solveur de sudoku grâce a une fonction récursive. Ce dernier ce décline en deux étapes. La premier est un solveur pour grille simple, qui ne fait pas appel a du backtracking, celui la est réussi.
    Le second lui, me pose plus de problème. Le prof me demande de faire appel a du backtracking afin de pouvoir revenir sur mes pas lorsqu'une case a plusieurs possibilité.

    voici comment il souhaite qu'on s'y prenne :



    voici ou j'en suis pour l'instant (j'importe une bibliothèque "sudolib" qui répertorie toutes les fonction utilisée) :
    Code :Sélectionner tout -Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    from sudolib import *
     
    grille2=[[0,0,0,1,5,0,3,0,0],[0,0,1,0,0,0,7,9,5],[0,5,6,0,0,4,0,0,0],[9,0,3,0,8,0,0,0,0],[0,2,0,0,0,0,0,8,0],[0,0,0,0,3,0,1,0,4],[0,0,0,9,0,0,4,3,0],[8,9,2,0,0,0,6,0,0],[0,0,4,0,2,6,0,0,0]]
     
    def sudoku2(grille) :
        if reste(grille) == 0 : # Teste d'arret
            affiche2(grille)    # si il ne reste pas de case vide la fonction s'arrete, affiche la grille et return True
            return True
        else :
     
            case = repere(grille) # definit la case à remplire
            if len(possibles(grille,case[0],case[1])) == 0 : #si la case n'a pas de solution retourn False
                return False
            else :
                poss = possibles(grille,case[0],case[1]) # cree la liste des possibilités pour une case donnée
     
                while len(poss) != 0  : # tant qu'il reste des possibilités
                    grille[case[0]][case[1]] = possibles(grille,case[0],case[1])[0] # la case prend la premiere valeur possible
                    test = sudoku2(grille) # verifie si le sudoku est possible pour la nouvelle grille
                    if not bool(test) :
                        poss.pop(0)  # si le test est faux la premiere possibilite est retire et la grille "nettoye"
                        grille[case[0]][case[1]] = 0
                    elif bool(test) :
                        poss=[]# si le sudoku est possible toutes les valeures sont retire pour pouvoir sortir de la grille
     
                return sudoku2(grille) # ré-execute la fonction avec la nouvelle grille pour enclache la recursivite
     
     
    sudoku2(grille2)


    voici ma bibliothèque :

    Code :Sélectionner tout -Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    87
    88
    89
    90
    91
    92
    93
    94
    95
    96
    97
    98
    99
    100
    101
    102
    103
    104
    105
    106
    107
    108
    109
    110
    111
    112
    113
    114
    115
    116
    117
    118
    119
    120
    121
    122
    123
    124
    125
    126
    127
    128
    129
    130
    131
    132
    def affiche (grille):
        """affiche sous forme matricielle
    0 7 0 0 0 9 4 0 1
    9 6 0 1 0 0 5 0 7
    0 0 0 5 0 0 0 9 0
    0 0 1 0 0 0 7 6 2
    0 2 4 0 0 0 3 1 0
    5 3 7 0 0 0 8 0 0
    0 1 0 0 0 6 0 0 0
    4 0 2 0 0 1 0 7 6
    7 0 6 2 0 0 0 8 0
    """
        for i in range(9):
            ligne=""
            for j in range (9) :
                ligne += str(grille[i][j])
            # A compléter
            print(ligne)
     
    def affiche2 (grille):
        """affiche sous forme matricielle mis en forme avec des bordures
    ----------------------
    |  7   |    9 |4   1 |
    |9 6   |1     |5   7 |
    |      |5     |  9   |
    ----------------------
    |    1 |      |7 6 2 |
    |  2 4 |      |3 1   |
    |5 3 7 |      |8     |
    ----------------------
    |  1   |    6 |      |
    |4   2 |    1 |  7 6 |
    |7   6 |2     |  8   |
    ----------------------
    """
     
        # A compléter à l'aide des caractères  - et | ainsi que de la division euclidienne %
        for i in range (9) :
            if i%3 == 0 :
                print("-------------------------")
            ligne=""
            for j in range (9) :
                if  j%3 ==0:
                    ligne+="| "
                if grille[i][j] == 0 :
                    ligne+= "  "
                else :
                    ligne+= str(grille[i][j])+" "
            ligne+="|"
            print(ligne)
        print("-------------------------")
     
     
    def ligne(grille,i):
        """retourne la liste des chiffres présents sur la ligne autres que 0
        print(ligne(grille,0))
        >>>[7, 9, 1, 4]"""
        ligne=[]
        for j in range(9) :
            if grille[i][j] != 0:
                ligne.append(grille[i][j])
        # A compléter
        return ligne
     
     
     
     
    def colonne(grille,j):
        """retourne la liste des chiffres présents sur la colonne autre que 0
        print(colonne(grille,0))
        >>>[9, 5, 4, 7]"""
        colonne=[]
        for i in range (9):
            if grille[i][j] != 0 :
                colonne.append(grille[i][j])
        # A compléter
        return colonne
    ##print(colonne(grille,3))
     
     
    def bloc(grille,i,j):
        bloc=[]
        """retourne la liste des chiffres autre que 0 présents sur le bloc contenant (i,j)
        print(bloc(grille,3,2))
        >>>[1, 2, 4, 5, 3, 7]"""
        for k in range (9) :
            for l in range(9) :
                if grille[k][l] != 0 and k//3 == i//3 and l//3 == j//3:
                    bloc.append(grille[k][l])
        # A compléter
        return bloc
    ##print(bloc(grille,4,1))
     
     
    def possibles(grille,i,j):
        """retourne la liste des chiffres possibles pour la case de coordonnées (i,j)
        print(possibles(grille,0,0))
        >>>[2, 3, 8]"""
        poss=[]
        for g in range(1,10):
            if (g not in bloc(grille,i,j)) and (g not in ligne(grille,i)) and (g not in colonne(grille,j)) :
                poss.append(g)
        # A compléter
        return poss
    ##print(possibles(grille,5,7),bloc(grille,5,7))
        # A compléter
     
    def reste(grille):
        """retourne le nombre de cases restant à remplir"""
        n=0
        for i in range (len(grille)) :
                n+=grille[i].count(0)
        # A compléter
        return n
     
     
    def repere(grille):
        """ retourne sous forme de tuple le couple (i,j), coordonnées de la case ayant le moins de valeurs possibles
    print(repere(grille))
    >>> (3, 0)
    """
        min=(0,0)
        minCombi = 9
        for i in range (9) :
            for j in range (9) :
                if grille[i][j] == 0:
                    poss = possibles(grille,i,j)
                    if len(poss)<minCombi :
                        minCombi = len(poss)
                        min=(i,j)
     
        return min




    Cela fait beaucoup de code (dont surement pas mal d'inutile mais c'est ce qu'on nous demande de faire)
    J'espère que quelqu'un comprendra mon problème et saura me dire pourquoi mon backtracking ne fonctionne pas

    Merci d'avance !

    Tom

  2. #2
    Expert éminent sénior
    Salut,

    Citation Envoyé par Tom_Co Voir le message
    J'espère que quelqu'un comprendra mon problème et saura me dire pourquoi mon backtracking ne fonctionne pas
    Pourquoi ne pas chercher sur Internet avec les mots clefs "python sudoku backtracking" et en essayant de comprendre comment ces codes marchent essayer de mettre au point le votre?

    - W
    Architectures post-modernes.
    Python sur DVP c'est aussi des FAQs, des cours et tutoriels

  3. #3
    Nouveau Candidat au Club
    Citation Envoyé par wiztricks Voir le message
    Salut,



    Pourquoi ne pas chercher sur Internet avec les mots clefs "python sudoku backtracking" et en essayant de comprendre comment ces codes marchent essayer de mettre au point le votre?

    - W
    salut, d'abord merci de ta réponses. J'ai déjà cherchez plusieurs solution en ligne et je n'en ai malheureusement compris aucune. je suis donc venue ici pour avoir des éclaircissement.
    De plus je ne cherche pas forcement avoir des réponses toutes faite mais juste que quelqu'un puisse pointer ce qui ne va pas et me proposer des solution ou des démarches a suivre.

    Encore merci

    Tom

  4. #4
    Expert éminent sénior
    Citation Envoyé par Tom_Co Voir le message
    De plus je ne cherche pas forcement avoir des réponses toutes faite mais juste que quelqu'un puisse pointer ce qui ne va pas et me proposer des solution ou des démarches a suivre.
    Comprendre comment est fait le code des autres est une démarche à suivre...

    Après pour corriger son code, il faut commencer par exposer le problème, réduire le code pour permettre de le reproduire facilement, et faire des théories qu'on cherche à valider/infirmer. Par exemple si vous pensez que çà ne marche pas parce que telle valeur n'est pas "à jour" un "print" permet de...

    - W
    Architectures post-modernes.
    Python sur DVP c'est aussi des FAQs, des cours et tutoriels

  5. #5
    Nouveau Candidat au Club
    Citation Envoyé par wiztricks Voir le message
    Comprendre comment est fait le code des autres est une démarche à suivre...

    Après pour corriger son code, il faut commencer par exposer le problème, réduire le code pour permettre de le reproduire facilement, et faire des théories qu'on cherche à valider/infirmer. Par exemple si vous pensez que çà ne marche pas parce que telle valeur n'est pas "à jour" un "print" permet de...

    - W
    D'accord merci pour ta réponse, je vais voir comment mettre ça en pratique.

    Merci encore,
    Tom

  6. #6
    Nouveau Candidat au Club
    Toujours pas
    Re-bonjour, après de nombreuses recherches et tentatives de modification/compréhension, je n'ai toujours pas trouver comment adapté le backtracking au la structure de l'algorithme demande.

    En effet, j'ai bien compris le principe mais les nombreuses solutions sur internet proposent un remplissage de la grille de gauche a droite et de haute en bas. Or, dans mon cas je dois remplir la grille en déterminant les cases ayant le moins de possibilités.

    J'espère que quelqu'un pourra m'aider rapidement

    Merci d'avance !

    Tom

  7. #7
    Expert éminent sénior
    Salut,

    Citation Envoyé par Tom_Co Voir le message
    En effet, j'ai bien compris le principe mais les nombreuses solutions sur internet proposent un remplissage de la grille de gauche a droite et de haute en bas. Or, dans mon cas je dois remplir la grille en déterminant les cases ayant le moins de possibilités.
    Çà change juste le choix de la case à jouer, pour le reste, c'est pareil.

    Prenez le code que je trouve ici, le moteur est:
    Code :Sélectionner tout -Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    def solve(bo):
        find = find_empty(bo)
        if not find:
            return True
        else:
            row, col = find
        for i in range(1,10):
            if valid(bo, i, (row, col)):
                bo[row][col] = i
                if solve(bo):
                    return True
                bo[row][col] = 0
        return False

    la case à jouer suivante est retournée par find_empty...

    Si on veut que çà retourne la case qui a le moins de possibilités plutôt que la première case vide... çà ne change pas grand chose sinon que çà serait mieux (dans ce cas) de tester les possibilités plutôt que tous les entiers dans 1..9.

    - W
    Architectures post-modernes.
    Python sur DVP c'est aussi des FAQs, des cours et tutoriels

  8. #8
    Nouveau Candidat au Club
    Salut ! Encore merci pour ta réponse si rapide.

    Malheureusement elle ne m’aide pas beaucoup car même en replacement la case de l’exemple par la case que je souhaite, l’algorithme n’a pas la structure qui m’ait imposé pour le projet. C’est la qu’est mon problème, je n’arrive pas à adapté le principe de backtracking à la structure demande. J’espère avoir été assez claire et j’espère que quelqu’un saura m’aider ^^

    Encore merci !

  9. #9
    Expert éminent sénior
    Citation Envoyé par Tom_Co Voir le message
    C’est la qu’est mon problème, je n’arrive pas à adapté le principe de backtracking à la structure demande.
    Je vous ai suggéré de partir d'un code existant (et des explications qui vont avec) et de l'adapter... Vous revenez avec une question qui n'a ni queue ni tête...

    Citation Envoyé par Tom_Co Voir le message
    J’espère avoir été assez claire et j’espère que quelqu’un saura m’aider
    La récursivité est compliquée... Ça pompe pas mal d'énergie mentale de se plonger dans code (passablement pourri, vous débutez, ce n'est pas votre faute, mais désolé, la gamelle est loin d'être appétissante...) et vous avez pu constater que dans d'autres forums, pas grand monde ne s'est aventuré à vous répondre.

    De toutes façons, ne vous prenez pas martel en tête, le professeur vous donnera une solution que vous pourrez étudier à souhait... D'ici là, si vous voulez progresser, il faudrait travailler un peu plus efficacement plutôt que de tourner en rond en attendant une aide hypothétique.

    - W
    Architectures post-modernes.
    Python sur DVP c'est aussi des FAQs, des cours et tutoriels

  10. #10
    Nouveau Candidat au Club
    D’accord merci beaucoup pour votre aide !

###raw>template_hook.ano_emploi###