probleme des 8 reines

a marqué ce sujet comme résolu.

Bonjour,

je dois créer un algorithme permettant, sur un échequier de 8x8, de placer 8 reines qui ne se menacent pas. Pour ce faire j’ai suivant le methode de resolution ici: http://zanotti.univ-tln.fr/ALGO/I51/Reines.html?fbclid=IwAR0N3QXDU94ZEk3YhGZ8onYzlUqJaJ7HEMS2-liI4f0vXL-2SCkp_j7D8Qk

import matplotlib.pyplot as plt
import random

#fonctions

def pointban(x,y):                          #supprime les cases menacees de la liste "dispo"
    for i in point:
        for j in dispo:
            if (x,i)==j:
                dispo.remove((x,i))
        for j in dispo:
            if (i,y)==j:
                dispo.remove((i,y))

    a,b=x-1,y-1
    while 1<=a<=8 and 1<=b<=8:
        for j in dispo:
            if (a,b)==j:
                dispo.remove((a,b))
        a=a-1
        b=b-1

    a,b=x-1,y+1
    while 1<=a<=8 and 1<=b<=8:
        for j in dispo:
            if (a,b)==j:
                dispo.remove((a,b))
        a=a-1
        b=b+1

    a,b=x+1,y-1
    while 1<=a<=8 and 1<=b<=8:
        for j in dispo:
            if (a,b)==j:
                dispo.remove((a,b))
        a=a+1
        b=b-1

    a,b=x+1,y+1
    while 1<=a<=8 and 1<=b<=8:
        for j in dispo:
            if (a,b)==j:
                dispo.remove((a,b))
        a=a+1
        b=b+1

def pointdeban():                       #refait la liste des points dispo après avoir supprime une reine dans la liste "Rei"
    dispo=[]
    for i in point:
        for j in point:
            dispo.append((i,j))
    for (a,b) in Rei:
        pointban(a,b)

def verif(x,y):                         #verifie si une point appartient a la liste "dispo"
    for (a,b) in dispo:
        if (x,y)==(a,b):
            return True
    return False
        

def reine(l):                           #place les reines de maniere a ce qu'elle ne se menacent pas
    while len(Rei)<n:                   #tant que je n'ai pas n reines dans la liste "Rei"
        taille=len(Rei)                 #je mets la taille initiale de liste "Rei" en memoire
        print('taille ini :',taille)
        rang=rligne[l-1]                #rang prends la liste des cases a tester sur la ligne "l"
        print('Rei :',Rei)
        while len(rang)>0:              #tant qu'il y a des cases a tester
            p=rang[random.randint(0,(len(rang)-1))]     #je prends un nombre aleatoire dans la liste des cases a tester
            print(l,p)
            print('dispo :',dispo)
            print('rang :',rang)


            if verif(l,p)==True:                    #je regarde si (l,p) appartient a la liste des cases disponible "dispo"
                print('Yes')
                Rei.append((l,p))                   #si c'est le cas, je l'ajoute a la liste des reines "Rei"
                rang=rligne[l-1]                    #je reprends la liste initiale des cases a tester sur la ligne "l" puis je supprime la colonne "p" pour ne pas la retester plus tard
                rang.remove(p)
                rang=rligne[l]
                pointban(l,p)                       #je supprime toutes les cases menacees par cette nouvelle reine de la liste des cases disponible "dispo"
                l=l+1                               #je passe a la ligne suivante
                rang=rligne[(l-1)]                  #je prends les cases a tester de la nouvelle ligne "l"
                print('Rei verif :',Rei)

            else:
                rang.remove(p)                      #si (l,p) n'appartient pas a la liste des cases disponible "dispo", je retire "p" de la liste des cases a tester

        print('taille fin :',taille)
        if len(Rei)==taille:                        #je regarde si la taille finale de ma liste "Rei" est la meme que la taille initiale ce qui signifie que j'ai tester toutes les cases de la ligne "l" sans succes
            rligne[l-1]=point                       #si c'est le cas, je refixe la liste des cases a tester sur la ligne "l" a : toutes les cases de la ligne
            del Rei[-1]                             #je supprime la derniere reine de la liste "Rei" donc celle de la ligne "l-1"
            pointdeban()                            #je mets a jour les cases disponible dans la liste "dispo" suite a la suppression de cette reines
            l=l-1                                   #je me place a la ligne "l-1"
            reine(l)                                #je recommence l'opération a cette ligne sachant que la case de rang "p" de la reine qui a ete supprimee n'est plus dans la liste des cases a tester




#initialisation

Rei=[]
dispo=[]
point=[]
rligne=[]
n=8
l=1

for i in range(1,n+1):                          #je cree une liste de chiffres de 1 a n
    point.append(i)

for i in range(0,n):                            #je cree une liste de n liste de chiffres allant de 1 a n, chaque liste de chiffres correspondant a une ligne contenant n cases a tester
    rligne.append(point)

for i in point:                                 #je cree simplement la liste initiale des points disponible c'est a dire tous
    for j in point:
        dispo.append((i,j))


quad=[0.5,0.5,1.5,2.5,3.5,4.5,5.5,6.5,7.5,8.5]

for x in quad:                          #cree un quadrillage pour echequier
    plt.plot([x,x],[0.5,8.5],"k")

for y in quad:
    plt.plot([0.5,8.5],[y,y],"k")

for x in point:                         #dessine un point dans chaque case
    for y in point:
        plt.plot(x,y,"ok")

#code


reine(l)        #execution de la fonction "reine"









plt.show()

Mon probleme est que quand je regarde le contenant de ma liste "rang" a la ligne 72, je me rend compte qu’en avancant dans les lignes de mon echequier, ma liste initiale de cases a tester ne correspond pas a [1,2,3,4,5,6,7,8] comme attendu. Chaque fois que je passe ligne cette liste est plus petite que la précédente

Voila, j’ai fait au mieux pour expliquer mon problème. J’espere que vous saurez m’aider car je galere un peu…

+0 -0

Salut,

Est-ce qu’il serait possible d’éditer ton messager pour formater le code correctement ? (balise ```python pour débuter et ``` pour terminer).

Vu le soucis que tu exposes, j’imagine que c’est un problème de références. Tu crois faire une copie d’une liste alors que tu ne crées qu’une nouvelle référence vers cette liste : donc quand tu la modifies, ça affecte l’originale.

+0 -0

```python et ``` doivent être seuls sur leurs lignes pour que ça fonctionne correctement (avec la coloration).

Tu n’as pas nécessairement besoin de tuples, il y a plusieurs manières de procéder. L’une pourrait être de faire des copies de listes quand tu en as besoin.

+0 -0

Rebonjour, j’ai modifié pour ne faire que des copies de ma liste "rligne" contenant les listes des cases a tester selon la ligne ou j’en suis mais quand je modifie une liste dans ma liste "rligne" toutes les autres sont impactées, que faire svp ?

import matplotlib.pyplot as plt
import random

#fonctions

def pointban(x,y):                          #supprime les cases menacees de la liste "dispo"
    for i in point:
        for j in dispo:
            if (x,i)==j:
                dispo.remove((x,i))
        for j in dispo:
            if (i,y)==j:
                dispo.remove((i,y))

    a,b=x-1,y-1
    while 1<=a<=8 and 1<=b<=8:
        for j in dispo:
            if (a,b)==j:
                dispo.remove((a,b))
        a=a-1
        b=b-1

    a,b=x-1,y+1
    while 1<=a<=8 and 1<=b<=8:
        for j in dispo:
            if (a,b)==j:
                dispo.remove((a,b))
        a=a-1
        b=b+1

    a,b=x+1,y-1
    while 1<=a<=8 and 1<=b<=8:
        for j in dispo:
            if (a,b)==j:
                dispo.remove((a,b))
        a=a+1
        b=b-1

    a,b=x+1,y+1
    while 1<=a<=8 and 1<=b<=8:
        for j in dispo:
            if (a,b)==j:
                dispo.remove((a,b))
        a=a+1
        b=b+1

def pointdeban():                       #refait la liste des points dispo apres avoir supprime une reine dans la liste "Rei"
    dispo=[]
    for i in point:
        for j in point:
            dispo.append((i,j))
    for (a,b) in Rei:
        pointban(a,b)

def verif(x,y):                         #verifie si une point appartient a la liste "dispo"
    for (a,b) in dispo:
        if (x,y)==(a,b):
            return True
    return False


def reine(l):                           #place les reines de maniere a ce qu'elle ne se menacent pas
    while len(Rei)<n:                   #tant que je n'ai pas n reines dans la liste "Rei"
        taille=len(Rei)                 #je mets la taille initiale de liste "Rei" en memoire
        print('taille ini :',taille)
        rang=list(rligne[l-1])                #rang prends la liste des cases a tester sur la ligne "l"
        print('Rei :',Rei)
        while len(rang)>0:              #tant qu'il y a des cases a tester
            p=rang[random.randint(0,(len(rang)-1))]     #je prends un nombre aleatoire dans la liste des cases a tester
            print(l,p)
            print('dispo :',dispo)
            print('rang :',rang)


            if verif(l,p)==True:                    #je regarde si (l,p) appartient a la liste des cases disponible "dispo"
                print('Yes')
                Rei.append((l,p))                   #si c'est le cas, je l'ajoute a la liste des reines "Rei"
                rligne[l].remove(p)
                print('rligne l :',rligne[l])
                print('rligne l+1 :',rligne[(l+1)])
                pointban(l,p)                       #je supprime toutes les cases menacees par cette nouvelle reine de la liste des cases disponible "dispo"
                l=l+1                               #je passe a la ligne suivante
                rang=list(rligne[(l-1)])                  #je prends les cases a tester de la nouvelle ligne "l"
                print('Rei verif :',Rei)

            else:
                rang.remove(p)                      #si (l,p) n'appartient pas a la liste des cases disponible "dispo", je retire "p" de la liste des cases a tester

        print('taille fin :',taille)
        if len(Rei)==taille:                        #je regarde si la taille finale de ma liste "Rei" est la meme que la taille initiale ce qui signifie que j'ai tester toutes les cases de la ligne "l" sans succes
            rligne[l-1]=list(point)                       #si c'est le cas, je refixe la liste des cases a tester sur la ligne "l" a : toutes les cases de la ligne
            del Rei[-1]                             #je supprime la derniere reine de la liste "Rei" donc celle de la ligne "l-1"
            pointdeban()                            #je mets a jour les cases disponible dans la liste "dispo" suite a la suppression de cette reines
            l=l-1                                   #je me place a la ligne "l-1"




#initialisation

Rei=[]
dispo=[]
point=[]
rligne=[]
n=8
l=1

for i in range(1,n+1):                          #je cree une liste de chiffres de 1 a n
    point.append(i)

for i in range(0,n):                            #je cree une liste de n liste de chiffres allant de 1 a n, chaque liste de chiffres correspondant a une ligne contenant n cases a tester
    rligne.append(point)

for i in point:                                 #je cree simplement la liste initiale des points disponible c'est a dire tous
    for j in point:
        dispo.append((i,j))


quad=[0.5,0.5,1.5,2.5,3.5,4.5,5.5,6.5,7.5,8.5]

for x in quad:                          #cree un quadrillage pour echequier
    plt.plot([x,x],[0.5,8.5],"k")

for y in quad:
    plt.plot([0.5,8.5],[y,y],"k")

for x in point:                         #dessine un point dans chaque case
    for y in point:
        plt.plot(x,y,"ok")

#code


reine(l)        #execution de la fonction "reine"


plt.show()
+0 -0

En effet, le problème reste le même, et la simple copie d’une liste ne fait que créer une nouvelle liste contenant les mêmes éléments.

Ici, les éléments sont des références vers des listes, donc copier une référence revient à avoir une nouvelle référence vers la même liste.

Pour résoudre ce problème, il te faudrait une copie en profondeur (dans toutes les dimensions), et la fonction deepcopy du module copy te sera utile pour cela.

+0 -0

J’ai un autre soucis, quand je reviens sur une ligne précédente pour modifié la place d’une reine, je supprime celle-ci de la liste "Rei" et ensuite j’utilise la fonction "pointdeban" point remettre a jour la liste des points dispo "dispo". Dans cette fonction "pointdeban" je remets toutes les cases de l’échiquier dans la liste "dispo" puis je parcours la liste "Rei" afin de rebannir avec "pointban" toutes les cases menacées par les reines restantes.

Mon problème est que d’abord quand j’utilise la fonction "pointban" dans "pointdeban" je récupère quand même une liste dispo contenant toutes les cases de l’échequier. Et ensuite quand je sors de la fonction "pointdeban" ma liste "dispo" est la même qu’avant de passer pas la fonction.

import matplotlib.pyplot as plt
import random

#fonctions

def pointban(x,y):
    print('Ok :',(x,y))                        #supprime les cases menacees de la liste "dispo"
    for i in point:
        for j in dispo:
            if (x,i)==j:
                dispo.remove((x,i))
        for j in dispo:
            if (i,y)==j:
                dispo.remove((i,y))

    a,b=x-1,y-1
    while 1<=a<=8 and 1<=b<=8:
        for j in dispo:
            if (a,b)==j:
                dispo.remove((a,b))
        a=a-1
        b=b-1

    a,b=x-1,y+1
    while 1<=a<=8 and 1<=b<=8:
        for j in dispo:
            if (a,b)==j:
                dispo.remove((a,b))
        a=a-1
        b=b+1

    a,b=x+1,y-1
    while 1<=a<=8 and 1<=b<=8:
        for j in dispo:
            if (a,b)==j:
                dispo.remove((a,b))
        a=a+1
        b=b-1

    a,b=x+1,y+1
    while 1<=a<=8 and 1<=b<=8:
        for j in dispo:
            if (a,b)==j:
                dispo.remove((a,b))
        a=a+1
        b=b+1

def pointdeban():                       #refait la liste des points dispo apres avoir supprime une reine dans la liste "Rei"
    dispo=[]
    for i in point:
        for j in point:
            dispo.append((i,j))
    print('dispo deban :',dispo)
    print('Rei deban :',Rei)
    for (i,j) in Rei:
        pointban(i,j)
    print('dispo ban :',dispo)

def verif(x,y):                         #verifie si une point appartient a la liste "dispo"
    for (a,b) in dispo:
        if (x,y)==(a,b):
            return True
    return False


def reine(l):                           #place les reines de maniere a ce qu'elle ne se menacent pas
    while len(Rei)<n:                   #tant que je n'ai pas n reines dans la liste "Rei"
        taille=len(Rei)                 #je mets la taille initiale de liste "Rei" en memoire
        tail=l
        print('taille ini :',taille)
        rang=list(rligne[l-1])                #rang prends la liste des cases a tester sur la ligne "l"
        print('Rei :',Rei)
        while len(rang)>0 and len(dispo)>0 and l==tail:              #tant qu'il y a des cases a tester
            p=rang[random.randint(0,(len(rang)-1))]     #je prends un nombre aleatoire dans la liste des cases a tester
            print(l,p)
            print('dispo :',dispo)
            print('rang :',rang)


            if verif(l,p)==True:                    #je regarde si (l,p) appartient a la liste des cases disponible "dispo"
                print('Yes')
                Rei.append((l,p))                   #si c'est le cas, je l'ajoute a la liste des reines "Rei"
                rligne[l-1].remove(p)
                pointban(l,p)                       #je supprime toutes les cases menacees par cette nouvelle reine de la liste des cases disponible "dispo"
                l=l+1                               #je passe a la ligne suivante
                print('Rei verif :',Rei)

            else:
                rang.remove(p)                      #si (l,p) n'appartient pas a la liste des cases disponible "dispo", je retire "p" de la liste des cases a tester

        print('taille fin :',len(Rei))
        if len(Rei)==taille:                        #je regarde si la taille finale de ma liste "Rei" est la meme que la taille initiale ce qui signifie que j'ai tester toutes les cases de la ligne "l" sans succes
            rligne[l-1]=list(point)                       #si c'est le cas, je refixe la liste des cases a tester sur la ligne "l" a : toutes les cases de la ligne
            del Rei[-1]                             #je supprime la derniere reine de la liste "Rei" donc celle de la ligne "l-1"
            pointdeban()                            #je mets a jour les cases disponible dans la liste "dispo" suite a la suppression de cette reines
            l=l-1                                   #je me place a la ligne "l-1"




#initialisation

Rei=[]
dispo=[]
point=[]
rligne=[]
n=8
l=1

for i in range(1,n+1):                          #je cree une liste de chiffres de 1 a n
    point.append(i)

for i in range(0,n):                            #je cree une liste de n liste de chiffres allant de 1 a n, chaque liste de chiffres correspondant a une ligne contenant n cases a tester
    rligne.append(list(point))

for i in point:                                 #je cree simplement la liste initiale des points disponible c'est a dire tous
    for j in point:
        dispo.append((i,j))


quad=[0.5,0.5,1.5,2.5,3.5,4.5,5.5,6.5,7.5,8.5]

for x in quad:                          #cree un quadrillage pour echequier
    plt.plot([x,x],[0.5,8.5],"k")

for y in quad:
    plt.plot([0.5,8.5],[y,y],"k")

for x in point:                         #dessine un point dans chaque case
    for y in point:
        plt.plot(x,y,"ok")

#code


reine(l)        #execution de la fonction "reine"


plt.show()
+0 -0

Ton code est tout de même assez difficile à relire, et je vois pas mal de choses inutilement compliquées, ou propices à des erreurs

  • Tu crées une liste de listes pour représenter ton échiquier et les emplacements des reines. Mais chaque reine étant nécessairement sur une ligne différente, pourquoi ne pas simplement utiliser une liste de nombres, ces nombres étant les colonnes où se situe la reine de chaque ligne.
  • Ta fonction verif pourrait se simplifier en un test in entre l’élément que tu recherches et la liste.
  • Dans pointban, tu modifies tes listes en même temps que tu itères dessus, et tu répètes le même soucis qu’avec verif.
  • Ta fonction pointdeban redéfinit une variable locale dispo référençant la liste []. Elle n’affecte en rien la variable globale. Il aurait plutôt fallu appeler dispo.clear() ou dispo[:] = [].
+0 -0

Par curiosité, j’ai écrit une solution en OCaml:

let okay (i1, j1) (i2, j2) =
  i1 <> i2
  && j1 <> j2
  && abs (j1 - j2) <> abs (i1 - i2)

let safe new_queen queens =
  List.for_all (okay new_queen) queens

let rec nqueens limit =
  let exception Solution of (int * int) list in
  let rec loop i queens =
    if i = limit then raise (Solution queens);
    for j = 0 to limit - 1 do
      if safe (i, j) queens
      then loop (i+1) ((i,j) :: queens)
    done
  in try
    loop 0 [];
    assert false (* unreachable: there is always a solution *)
  with (Solution sol) -> List.rev sol

Appeler nqueens 8 renvoie une solution: [(0, 0); (1, 4); (2, 7); (3, 5); (4, 2); (5, 6); (6, 1); (7, 3)].

(On peut écrire ce code sans stocker les positions des lignes pour chaque reine, seulement des colonnes, puisque les positions des lignes sont toujours consécutives et peuvent donc se deviner à partir de la place dans la liste. C’est plus court mais c’est moins clair.)

+1 -0
Connectez-vous pour pouvoir poster un message.
Connexion

Pas encore membre ?

Créez un compte en une minute pour profiter pleinement de toutes les fonctionnalités de Zeste de Savoir. Ici, tout est gratuit et sans publicité.
Créer un compte