Les Huits Dames

Bonjour,

Je dois faire un programme qui affiche les 92 solutions possibles des "Huits dames" : c'est à dire que sur une grille de 8 par 8, pour être valide, la solution doit permettre d'avoir 8 pions sur la grille, sans qu'aucun puisse être en ligne, en diagonale ou en colonne d'un autre pion.

J'ai testé quelque chose :
Code:

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 flag = False test3=0 DATA =[ ['a8','b8','c8','d8','e8','f8','g8','h8'], ['a7','b7','c7','d7','e7','f7','g7','h7'], ['a6','b6','c6','d6','e6','f6','g6','h6'], ['a5','b5','c5','d5','e5','f5','g5','h5'], ['a4','b4','c4','d4','e4','f4','g4','h4'], ['a3','b3','c3','d3','e3','f3','g3','h3'], ['a2','b2','c2','d2','e2','f2','g2','h2'], ['a1','b1','c1','d1','e1','f1','g1','h1'],] while 1: #Pas encore mis de condition ici.. for i in range(0,8): for j in range(0,8): flag = True DATA[i][j]='1' for test in range(0,8): #Test Colonne if DATA[i][test]=='1' and test!= j: DATA[i][j]='0' for test2 in range(0,8):#Test Ligne if DATA[test2][j]=='1' and test2!= i: DATA[i][j]='0' while i+test3!=7 and j+test3!=7 and flag == True: #Test Diago Bas/Droite test3 += 1 if DATA[i+test3][j+test3]=='1': DATA[i][j]='0' test3=0 flag = False test3=0 while i+test3!=0 and j+test3!=0 and flag == True :#Test Diago Haut/Gauche test3 -= 1 if DATA[i+test3][j+test3]=='1': DATA[i][j]='0' flag = False test3=0 print(DATA) #La il me faudrait une condition qui affiche que les solutions avec 8 Pions présents sur la grille.
Donc en gros, mon programme mets un pion sur la première ligne/colonne, puis essaye de mettre sur les autres colonnes de la premiere ligne, sauf que mes condition l'en empêche, puis il passe à la deuxième ligne etc.
Ce qui fait que j'ai une solution a 7 pions au final.

Maintenant il faudrait que j'arrive a faire partir mon programme d'une autre cellule que la ligne[0]/colonne[0].
Je ne vois pas bien comment m'y prendre.

Puis ensuite, il y a encore plein d'autre solution a testé, comme par exemple, au lieu de commencer par la ligne 0 puis passer a la 1, il faudrait passer directement a la 2, etc.

Je sais pas si c'est bien clair, mais si vous avez compris le principe, j'aimerais bien quelques idées pour avancer.

Salut,

Citation:

Envoyé par bromy

Je sais pas si c'est bien clair, mais si vous avez compris le principe, j'aimerais bien quelques idées pour avancer.

Un algo. est un algo, le programmer est autre chose.
L'article sur Wikipedia vous donne une idée des algo. possibles.
Vous y trouverez des pointeurs vers des documents qui expliquent comment réaliser certains d'entre eux.

Ce n'est qu’après avoir choisi l'algo. et réfléchi a comment le réaliser en Python que vous pourrez commencer a coder sans être paume après avoir tape quelques lignes de code.

- W

Salut,

Très bon exercice.

Pour visualiser plus aisément les résultats, utilise ceci à la fin de ton code:
Code:

1 2 3 4 5 for data in DATA: print data run += 1 print '---------------------------------------'
tes grilles seront correctement alignées et change ton premier while 1:
Code:

1 2 3 run = 0 while run < 6:
Ici j'ai mis 6 pour ne pas avoir un défilé de grille.

On peut voir aux résultats que c'est toujours la première grille qui est reproduite et qui ne compte que 7 dames et non huit. (cherchez la femme ...)

Cela dit, c'est un bon début.

Deux conseils:

1- Utilise 'l' pour ligne au lieu de 'i' et 'c' pour colonne au lieu de 'j', tu verras comme cela rend la lecture plus aisée. Personnellement, j'utilise 'line' et 'column'

2- Tu utilises if DATA[l][test]=='1' and test!= j: et if DATA[test2][j]=='1' and test2!= i: c'est à dire que tu vérifies que tu ne sois pas sur la même ligne ou sur la même colonne. ces vérifications vont se faire (8 x 8) x 8 x 2 fois tu peux éviter ça en enlevant le numéro de ligne ou colonne de la liste.

exemple:
Code:

1 2 3 def get_list(n): return [i for i in range(8) if i != n]
et donc tu remplaces les lignes que j'ai commentées ci-dessous:
Code:

1 2 3 4 5 6 7 #for test in range(0,8): #Test Colonne for test in get_list(c): if DATA[l][test]=='1': DATA[l][c]='0' #for test2 in range(0,8):#Test Ligne for test2 in get_list(l):
Pour les diagonales, je pense que tu ne vérifies pas toutes. Voir les résultats.

Merci pour vos réponses.
Effectivement pour les diagos, j'ai ensuite rajouté deux autres conditions pour les Diago Haut Droite et Bas Gauche :

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
 
            while 0<l-test3<7 and 0<c+test3<7 and flag == True :#Test Diago Haut/Droite
                test3 += 1
                if DATA[l-test3][c+test3]=='1':
                    DATA[l][c]='0'
                    flag = False
            test3=0
            while 0<l+test3<7 and 0<c-test3<7 and flag == True :#Test Diago Bas/Gauche
                test3 += 1
                if DATA[l+test3][c-test3]=='1':
                    DATA[l][c]='0'
                    flag = False
            test3=0

Je n'ai pas python sur ce PC, mais de tête, je crois que c'est ce que j'avais mis.
Je vais étudier le lien de Wiztricks et faire les changements que VinsS et je revient vers vous si je bloque.

Merci et bonne soirée.