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

Programmation multimédia/Jeux Python Discussion :

créer une grille de sudoku


Sujet :

Programmation multimédia/Jeux Python

  1. #1
    Futur Membre du Club
    Homme Profil pro
    Étudiant
    Inscrit en
    mai 2019
    Messages
    8
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : mai 2019
    Messages : 8
    Points : 5
    Points
    5
    Par défaut créer une grille de sudoku
    Bonjour à tous, j'essaie de coder un programme permettant de générer une grille de sudoku avec une UNIQUE solution. J'ai fais des recherches sur le forum mais je ne trouve pas de solution satisfaisante. J'ai codé un algorithme de résolution par backtracking mais je ne comprends pas comment l'utiliser pour générer la grille avec solution unique, comme il est dit sur internet.
    En effet j'ai réussi à faire ceci :
    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
    def creation(nbrdechiffre): #probleme solution non unique
        i,j=0,0
        gr=creerGrille(9,9)
        L=[]
        k=0
        K=[]
        for z in range (7):
            K.append(random.randint(1,9))
            print(K)
        while len (L) != nbrdechiffre:
            i=random.randint(0,8)
            j=random.randint(0,8)
     
            if [i,j] not in L:
     
                L.append([i,j]) #liste des indices
     
            for k in range (len(L)):
                d=L[k][0]
                b=L[k][1]
                y=random.randint(0,6)
                t=K[y]
                gr[d][b]= t
     
                while nbroccurences(gr,gr[d][b],d,b)!= 0:  #nombre d’occurrence est une fonction qui compte l'occurrence d'un chiffre dans la ligne colonne, sous grille
                    gr[d][b]=random.randint(1,9)
        print (resolution(gr))
        while resolution(gr) == False:
            print(gr)
            gr=creation(nbrdechiffre)
     
     
        return gr
    voici mon algo de résolution
    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
    def absent_de_la_ligne( k , grille, i): #valeur à vérifier, grille , numéro de ligne
        for j in range(0,9):
            if grille[i][j] == k :
                return False
        return True
     
     
    def absent_de_la_colonne( k , grille , j): #valeur à vérifier, grille , numéro de colonne
        for i in range(0,9):
            if grille[i][j] == k :
                return False
        return True
     
    def absent_du_bloc ( k , grille , i , j): #valeur à vérifier, grille , numéro de colonne, ligne
        ibis = i - (i%3)
        jbis = j - (j%3)
        for u in range(ibis,ibis+3):
            for v in range(jbis,jbis+3):
                if grille[u][v] == k :
                    return False
        return True
     
    def backtracking ( grille , position ):
        if (position == 81): #critère d'arret
            return True
        i = position//9 #à expliquer diapo
        j = position%9
        if grille[i][j] != 0 :
            return backtracking( grille , position +1)
        for k in range (1,10):
            if (absent_de_la_ligne( k , grille, i) and absent_de_la_colonne( k , grille , j) and absent_du_bloc ( k , grille , i , j)):
                grille[i][j] = k
                if (backtracking ( grille , position+1)):
                    return True
        grille[i][j] = 0  # cas non solvable
        return False			
     
    def solution ( grille ):
        sol=creerGrille(9,9)
        for i in range (9):
            for j in range(9):
                sol[i][j]=grille[i][j]
        positions=0
        res = backtracking(sol,positions)
        return res,sol

  2. #2
    Modérateur

    Homme Profil pro
    Architecte technique
    Inscrit en
    juin 2008
    Messages
    14 326
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Architecte technique
    Secteur : Industrie

    Informations forums :
    Inscription : juin 2008
    Messages : 14 326
    Points : 24 234
    Points
    24 234
    Par défaut
    Salut,

    Citation Envoyé par aabdoulay Voir le message
    j'essaie de coder un programme permettant de générer une grille de sudoku avec une UNIQUE solution.
    Pour faire cela, il faut un algorithme... Et la rubrique algorithme est là pour vous en suggérer un.

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

  3. #3
    Futur Membre du Club
    Homme Profil pro
    Étudiant
    Inscrit en
    mai 2019
    Messages
    8
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : mai 2019
    Messages : 8
    Points : 5
    Points
    5
    Par défaut
    dois je reposter dans l'autre section?
    j'ai déjà parcouru les posts, mais je ne comprends pas la méthode de création liée au backtracking
    edit: en fait, ce que je ne comprends pas, c'est la méthode pour compter le nombre de solution d'un sudoku. Je ne vois pas comment modifier le programme backtracking en ajoutant un compteur, puisqu'il s'arrete quand il trouve une solution.

  4. #4
    Modérateur

    Homme Profil pro
    Architecte technique
    Inscrit en
    juin 2008
    Messages
    14 326
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Architecte technique
    Secteur : Industrie

    Informations forums :
    Inscription : juin 2008
    Messages : 14 326
    Points : 24 234
    Points
    24 234
    Par défaut
    Citation Envoyé par aabdoulay Voir le message
    edit: en fait, ce que je ne comprends pas, c'est la méthode pour compter le nombre de solution d'un sudoku. Je ne vois pas comment modifier le programme backtracking en ajoutant un compteur, puisqu'il s'arrete quand il trouve une solution.
    On dirait que vous avez du code qui implémente un algo. (que vous avez récupéré on ne sait où) que vous voudriez le modifier pour qu'il retourne un nombre de solutions plutôt que la première solution trouvée...
    Comme on ne sait pas comment a été construit l'algo. pas évident qu'il sache énumérer toutes les solutions possibles... En tout cas c'est pas en lisant le code qu'on peut le savoir.

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

Discussions similaires

  1. afficher une grille de sudoku Swing
    Par herbert8 dans le forum AWT/Swing
    Réponses: 3
    Dernier message: 03/10/2007, 00h42
  2. Comment résoudre une grille de Sudoku ?
    Par tarik_12 dans le forum Pascal
    Réponses: 1
    Dernier message: 25/04/2007, 20h31
  3. [VB6]Afficher une grille de Sudoku
    Par epaminondas dans le forum VB 6 et antérieur
    Réponses: 7
    Dernier message: 07/03/2006, 17h36
  4. Comment créer une Grille numérotée ?
    Par bassim dans le forum Composants VCL
    Réponses: 6
    Dernier message: 18/09/2005, 03h00
  5. Créer une grille avec centage
    Par lil_jam63 dans le forum Algorithmes et structures de données
    Réponses: 10
    Dernier message: 16/08/2004, 16h21

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo