Discussion :

[bromy]

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 :

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
 
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.

[wiztricks]

Salut,

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

[VinsS]

Salut,

Très bon exercice.

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

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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.

[bromy]

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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.