Génération d'un graphe d'objets

Bonour,

Je me suis lancé le défi de résoudre le rubiks cube par une methode mois conventionnelle que celles couramment utilisées, a commencer par le résoudre via un algorithme ! :D Je detaille ma methode ci dessus mais je ne suis pas sur que cela soit essentiel a la comprehension de mon probleme...

Ma méthode est la suivante: on utilise un graphe.
- Chaque noeud représente une configuration du cube (une position)
- Deux noeuds sont reliés si et seulement si on peut passer de l'un a l'autre en un mouvement (rotation d'une face d'un quart de tour). Une fois le graph généré, un algorithme de recherche de plus court (ou pour commencer, pas forcement le plus court) chemin part du noeud initial (configuration du cube melangé) et remonte jusqu'a l'état fini.
J'ai décidé de modeliser le cube sous forme de dictionnaire. Il comporte autant de clés que de pieces (physiques, les petits cube composant le gros) et chaque clé se voit attribuer une liste correspondant qux couleurs actuellement presentes dessus (les pieces jouent le role de receptacle aux couleurs). Pour faire tourner une face on echange les listes des differentes clés concernées, et si bseoin on effectue une permutation dans l'ordre d'enumartion des couleurs (dictées selon un repere orthonormé direct).

Voial mon probleme a proprement parler. J'utilise un cube 2x2x2 Deja le code:

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

# Cube(): classe de l'objet representant le cube (cube.piece() renvoie le dictionnaire representant le cube) # cube.allRot() renvoie l'ensemble des cubes relies a cube par un mouvement # cube1.check(cube2) renvoie true si les deux cubes sont dans la meme configuration, false sinon   import rotations_2.py   def makeGraph(): # La queue represente l'ensmble des cubes a lier avec le reste du graph root = Cube() queue = [root] graph = {root: []} # Tant qu'il reste des cubes non relies au reste du graphe while queue != []: # On etete la queue cube = queue.pop() # On recupere l'ensmble des cubes relies au dernier cube_liste = cube.allRot()   for cube1 in cube_liste: # On regarde si le cube n'est pas dans le graphe for cube2 in graph.keys(): if not(cube1.check(cube2)): # Si il n'est pas dans le graphe # On le rajoute dans la queue et dans le graph queue.append(cube1) graph[cube1] = []   # On relie le cube au reste du graph for cube1 in cube_liste: if cube.check(cube1): graph[cube].append(cube1) graph[cube1].append(cube)   return graph

---

Mon probleme est que lorsque je fais:

Code:

---

graph[cube1].append(cube)

---

je ne retombe pas sur la meme case memoire que a:

Code:

---

graph[cube1] = []

---

Alors que les objets viennent de la meme liste dans les deux cas (liste_cube)...

Voila, si vous avez des remarques/conseils je suis preneur, sachant que je debute en python !
Merci,
UPCBRA

Je ne suis pas certain d'avoir compris ta question mais je fais une tentative.

Pour pouvoir utiliser tes cubes comme clés dans un dictionnaire, tu as du définir les méthodes __eq__ et __hash__. En fait je ne comprends pas en quoi ta méthode check différerait de __eq__. Pour que cela fonctionne correctement, il faut que __hash__ retourne la même valeur quand __eq__ renvoie true. De plus, il faut que les objets soient immutables (en tout cas les attributs sur lesquels se basent __eq__ et __hash__). Si ces critères ne sont pas respectés, tu peux arriver à des aberrations quand tu les utilises comme clés dans un dictionnaire.

Si elles sont définies correctement, tu peux écrire cube1 == cube2 au lieu de cube1.check(cube2) et cube1 not in graph au lieu de faire une boucle sur les clés du dictionnaire.

Aussi, ce n'est pas la peine d'essayer de définir les adjacences dans les deux sens dans ta boucle principale; les arêtes dans l'autre sens seront ajoutées lorsque l'état voisin sera extrait de la queue (en réalité, comme tu l'utilises, ce n'est pas une queue (FIFO) mais une pile (LIFO)).