Partage
  • Partager sur Facebook
  • Partager sur Twitter

Problème des 8 dames

Problème des 8 dames méthode en profondeur

Anonyme
    17 octobre 2020 à 17:51:32

    Bonjour/ Bonsoir j'ai un petit soucis je doit faire un programme pour résoudre le problème des 8 dames j'ai déjà une base qui est celle ci:

    from time import time
    L=[3,5,0,4,1,7,2,6]
    def test(L):
        a=True
        for i in range(len(L)):
            for j in range(i+1,len(L)):
                if (abs(L[j]-L[i])/(j-i))==1 or L[i]==L[j]:
                    a=False
        return a
    L=[]
    compt=0
    t1=time()
    for i in range (8):
        for j in range (8):
            for k in range (8):
                for l in range (8):
                    for m in range (8):
                        for n in range (8):
                            for o in range (8):
                                for p in range (8):
                                    L=[i,j,k,l,m,n,o,p]
                                    if test(L):
                                        print(L)
                                        compt+=1
                                        print(compt)
                                    L=[]
    t2=time()
    print (test(L))

    et je doit rendre tout ceci plus efficace en utiliser la méthode en profondeur mais je suis perdu et ne sait pas comment faire merci d'avance pour votre aide

    -
    Edité par Anonyme 17 octobre 2020 à 18:02:59

    • Partager sur Facebook
    • Partager sur Twitter
      17 octobre 2020 à 19:42:23

      for L in itertools.combinations_with_replacement(range(8), 8):

       
      C'est juste pour simplifier les 8 for, après je ne sais pas.

      -
      Edité par thelinekioubeur 17 octobre 2020 à 19:46:28

      • Partager sur Facebook
      • Partager sur Twitter
        17 octobre 2020 à 19:56:56

        Hugo88 a écrit:

         je suis perdu et ne sait pas comment faire merci d'avance pour votre aide

        Le problème des 8 reines a été posé par Gauss en 1842. Imaginez toute la littérature qui a été écrite sur le sujet depuis! Une partie est accessible sur Internet et sans la consulter pas facile de trouver rapidement un algorithme. Et sans algorithme, qu'est ce qu'on va bien pouvoir coder?

        • Partager sur Facebook
        • Partager sur Twitter
        Anonyme
          17 octobre 2020 à 20:57:25

          j'ai bien tenté de trouver des éléments pouvant me mené a la solution, le problème c'est que je n'ai rien trouver sur la méthode en profondeur mis a part son fonctionnement et malheureusement je ne sait pas comment coder cela je me retrouve bloquer a ce stade depuis maintenant 3 semaine c'est pour cela que je fait appelle a vous je ne cherche pas a avoir une solution qui me tombe dans les mains mais comprendre comment faire pourquoi cette ligne pourquoi ceci etc. car si je ne comprend pas cela n'as aucun intérêt c'est donc pour cela que si quelqu'un sait comment faire et qu'il peut m'expliquer je suis preneur merci a tous de votre aide en tout cas.
          • Partager sur Facebook
          • Partager sur Twitter
            17 octobre 2020 à 22:34:11

            Basiquement la méthode en profondeur consiste à poser une dame dans la première colonne, puis une dans la deuxième, et vérifier que ces deux dames ne se voient pas avant de poser une troisième, puis revérifier avec ces trois là et ainsi de suite. Ça permet d'éliminer beaucoup de combinaisons à vérifier.

            Ce n'est pas obligatoire mais ça se fait souvent avec un algorithme récursif.

            • Partager sur Facebook
            • Partager sur Twitter
              18 octobre 2020 à 3:17:14

              Peut-être que je manque quelque chose ...
              Il va de soi quel les 8 dames vont se retrouver sur 8 lignes (ou colonnes) différentes.
              L'idée serait que pour chaque nouvelle dame, je regarde si chaque ligne (ou colonne) est libre. Ça s'est facile.
              C'est moins évident pour les deux diagonales.
              La première diagonale que j'appelle diagonale "ascendante" fait augmenter les deux coordonnées en même temps.
              minimum=min(i, j), maximum=min(8-i, 8-j)
              i+=1, j+=1
              La seconde diagonale que j'appelle diagonale "descendante" fait augmenter une coordonnée pendant que l'autre diminue.
              minimum=min(i, 8-j), maximum=min(8-i, j)
              i+=1, j-=1
              Ça te ferait 3 fonctions de test avec une seule boucle dans chacune.
              La première fonction (ligne ou colonne) pourrait appeler les deux autres à la suite.
              • Partager sur Facebook
              • Partager sur Twitter

              Le Tout est souvent plus grand que la somme de ses parties.

                18 octobre 2020 à 11:10:37

                Hugo88 a écrit:

                malheureusement je ne sait pas comment coder cela je me retrouve bloquer a ce stade depuis maintenant 3 semaine c'est pour cela que je fait appelle .

                En cherchant sur Internet, vous seriez tombé sur ce genre d'article qui vous explique un des algorithmes à utiliser et qui détaille les fonctions à réaliser. Si vous ne commencez pas par là, aucune chance de savoir quoi coder.

                • Partager sur Facebook
                • Partager sur Twitter
                  18 octobre 2020 à 14:23:31

                  J'ai beaucoup de difficulté avec l'éditeur du forum. J'ai fait précéder chaque ligne de  #*  pour ne pas perdre l'indentation.
                  Ces deux fonctions illustrent la façon de parcourir chacune des diagonales.
                  -
                  #*def diagAscendante(i, j):
                  #*    j1 = j - min(i, j)-1
                  #*    for i1 in range(i-min(i,j),min(8,7-j1)):
                  #*        j1+=1
                  #*        print(i1, j1)
                  #*def diagDescendante(i, j):
                  #*    j1=j+min(i,7-j)+1
                  #*    for i1 in range(i-min(i,7-j),min(8,j1)):
                  #*        j1-=1
                  #*        print(i1, j1)
                  #*print("Diagonale ascendante")
                  #*diagAscendante(int(input("i:")), int(input("j:")))
                  #*print("Diagonale descendante")
                  #*diagDescendante(int(input("i:")), int(input("j:")))
                  • Partager sur Facebook
                  • Partager sur Twitter

                  Le Tout est souvent plus grand que la somme de ses parties.

                    19 octobre 2020 à 18:51:55

                    @Hugo88:   ou autres ...
                    J'ai écrit une solution avec le backtracking qui fonctionne bien et donne les 92 solutions attendues.
                    J'ai converti mes fonctions diagAscendante et diagDescendante en générator pour simplifier le code.
                    Cela me prend environ 0.024 secondes sur une machine à 4 GHz.
                    Si toi ou quelqu'un d'autre est intéressé, je vous donnerai la solution dans le format identique à mon dernier message car je n'ai pas réglé mon problème de compatibilité.
                    J'attend une réponse du staff d'OpenClassrooms.
                    Je sais que je pourrais améliorer ma solution en ne choisissant que les dcolonnes restantes pour chaque ligne, mais cela semble nuire au backtracking.
                    Je cherche une solution pour satisfaire les deux.
                    Avec la version actuelle, je fais N*N tests (N=8) alors que je pourrais faire N*(N+1)//2 tests.
                    Pour N=8, je ferais 36 tests au lieu de 64. Ça c'est pour chacune des 92 solutions.
                    Je fais au total 5888 tests au lieu de 3312 tests.
                    Dans les 64-36 (28) tests de trop, je me bloque sur le test sur les colonnes. Je n'ai pas besoin de tester les diagonales.
                    • Partager sur Facebook
                    • Partager sur Twitter

                    Le Tout est souvent plus grand que la somme de ses parties.

                    Anonyme
                      26 octobre 2020 à 15:55:07

                      @PierrotLeFou oui cela m'intéresserai beaucoup si tu acceptait de me fournir se code cela serait top

                      -
                      Edité par Anonyme 26 octobre 2020 à 16:04:20

                      • Partager sur Facebook
                      • Partager sur Twitter
                        26 octobre 2020 à 16:13:15

                        kdo

                        def eight(tableau):
                            if len(tableau) == 8:
                                print(tableau)
                                return
                            for i in range(8):
                                for colonne, ligne in enumerate(tableau):
                                    if ligne == i or abs(ligne - i) == len(tableau) - colonne:
                                        break
                                else:
                                    eight(tableau + [i])
                        
                        
                        eight([])
                        




                        • Partager sur Facebook
                        • Partager sur Twitter
                        Anonyme
                          26 octobre 2020 à 16:55:50

                          Un énorme merci a toi
                          • Partager sur Facebook
                          • Partager sur Twitter
                            27 octobre 2020 à 1:00:06

                            @thelinekioubeur:
                            Chapeau! Je l'ai testé et ça donne bien 92 solutions.
                            Je ne connais pas l'acronyme kdo
                            Je dirais que tu m'as mis KO ...
                            • Partager sur Facebook
                            • Partager sur Twitter

                            Le Tout est souvent plus grand que la somme de ses parties.

                              3 avril 2021 à 2:00:14

                              thelinekioubeur a écrit:

                              kdo

                              def eight(tableau):
                                  if len(tableau) == 8:
                                      print(tableau)
                                      return
                                  for i in range(8):
                                      for colonne, ligne in enumerate(tableau):
                                          if ligne == i or abs(ligne - i) == len(tableau) - colonne:
                                              break
                                      else:
                                          eight(tableau + [i])
                              
                              
                              eight([])
                              




                              Je me ré-intéressais à la résolution récursive du problème des N-queens et je tombe sur ce joli code, à la fois concis et clair (la seule difficulté pouvant être, si on ne connait pas, l'instruction for/else). Ce code ne semble pas répandu (rien de proche sur rosetta, ce que je trouve de moins éloigné est ce post sur SO et qui est moins sobre) et mériterait d'être mieux connu.

                              Le seul point est qu'il est un peu lent mais la vitesse n'était pas un objectif je suppose. Petite proposition d'accélération du code et de légère simplification :

                              from time import perf_counter
                              
                              def queens(tableau, n, cpt):
                                  if len(tableau) == n:
                                      cpt[0]+=1
                                      return
                                  for i in range(n):
                                      for colonne, ligne in enumerate(tableau):
                                          if ligne == i or abs(ligne - i) == len(tableau) - colonne:
                                              break
                                      else:
                                          queens(tableau + [i], n, cpt)
                              
                              def queens_var(tableau, n, cpt):
                                  if len(tableau) == n:
                                      cpt[0]+=1
                                      return
                                  for i in set(range(n))-set(tableau):
                                      if all(abs(ligne - i) != len(tableau) - colonne for colonne, ligne in enumerate(tableau)):
                                          queens_var(tableau + [i], n, cpt)
                              
                              cpt1=[0]
                              n=13
                              
                              begin_perf = perf_counter()
                              
                              queens([], n,cpt1)
                              
                              delta = perf_counter() - begin_perf
                              
                              print(f"Temps d'exécution : {delta:.2f}s")
                              
                              
                              cpt2=[0]
                              
                              begin_perf = perf_counter()
                              
                              queens_var([], n,cpt2)
                              
                              delta = perf_counter() - begin_perf
                              
                              print(f"Temps d'exécution : {delta:.2f}s")
                              
                              
                              print(cpt1[0], cpt2[0])
                              
                              mps d'exécution : 46.44s
                              Temps d'exécution : 28.37s
                              73712 73712
                              






                              • Partager sur Facebook
                              • Partager sur Twitter

                              Problème des 8 dames

                              × Après avoir cliqué sur "Répondre" vous serez invité à vous connecter pour que votre message soit publié.
                              × Attention, ce sujet est très ancien. Le déterrer n'est pas forcément approprié. Nous te conseillons de créer un nouveau sujet pour poser ta question.
                              • Editeur
                              • Markdown