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
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?
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.
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.
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.
Le Tout est souvent plus grand que la somme de ses parties.
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.
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:")))
Le Tout est souvent plus grand que la somme de ses parties.
@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.
Le Tout est souvent plus grand que la somme de ses parties.
Problème des 8 dames
× Après avoir cliqué sur "Répondre" vous serez invité à vous connecter pour que votre message soit publié.
Le Tout est souvent plus grand que la somme de ses parties.
Le Tout est souvent plus grand que la somme de ses parties.
Le Tout est souvent plus grand que la somme de ses parties.