Discussion :

[UPCBRA]

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 ! 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 :

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
 
# 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 :

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

graph[cube1].append(cube)

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

Code :

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

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

[dividee]

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