Utilisation de Python et d'une recherche en largeur bilatérale pour résoudre un Rubiks Cube 2x2.
Inspiré du projet du MIT 6.006. Créé à partir de zéro de manière unique.
https://youtu.be/ZHxLO6fubaU
Création de l'API, de l'algorithme et de l'interface graphique du cube à partir de zéro. Chacun des 6 côtés comporte 4 carrés différents, ce qui donne 24 carrés. De plus, le cube est composé de 8 pièces de coin au total, chacune ayant 3 orientations et accompagnant donc les 24 carrés.
J'ai défini chacune des 24 sous-sections de chaque côté comme une chaîne avec « xyz » comme format où x est la couleur immédiatement en face et y et z vont dans le sens des aiguilles d'une montre autour du cube pour ce coin.
J'ai fait le tour du cube et j'ai attribué à chaque côté un nombre fixe représentant l'état résolu. Par exemple, 0, 1, 2, 3 sont les 4 parties du côté blanc face avant où 0 est en haut à gauche et les autres vont dans le sens des aiguilles d'une montre.
Il y a 12 mouvements qui peuvent être effectués sur le cube. Droite, gauche, haut, bas, avant, arrière. Chacun d'eux a également ses mouvements dans le sens inverse des aiguilles d'une montre, donc 6x2 = 12 mouvements. Chacun de ces 12 manipule la moitié du cube donc 12 carrés. Pour effectuer ces mouvements, j'ai créé des dictionnaires pour chacun des 6 dans le sens des aiguilles d'une montre pour lesquels le sous-carré tourne de l'original à la position suivante. Pour faire les nombres premiers, j'ai juste changé les clés et les valeurs.
La résolution de ce problème est particulièrement délicate en raison du grand nombre de permutations possibles du cube. Il y a 24 sous-carrés et cela donne 24P24 = 24 !. C'est de l'ordre de 10 ^ 23. Il y en a moins en raison de certaines situations, mais le nombre reste énorme.
Pour créer l'arbre, je devrais exécuter chacun des mouvements et exécuter tous les mouvements à partir des mouvements, ce qui devient très gros. 12^hauteur de l'arbre. J'ai pu limiter cette taille en créant un dictionnaire des positions visitées afin de ne pas refaire l'action pour les permutations précédemment visitées.
J'ai commencé par créer un BFS unilatéral, mais cela atteindrait la limite de récursion car l'arbre de branchement deviendrait trop grand. Pour résoudre ce problème, j'ai utilisé un BFS recto verso en alternant la création de branches depuis le début et la solution de fin. Cela créerait les arbres et vérifierait si le côté opposé avait déjà trouvé le point. Si c'était le cas, cela renverrait le point de connexion.
Pendant tout cela, chaque nœud enregistre son parent (pour le branchement avant) ou son enfant (pour le branchement arrière). Pour trouver l'itinéraire emprunté, j'ai trouvé récursivement le parent du nœud de connexion, puis tous les enfants de ce point. Cela a abouti à une série de positions adoptées, de la situation brouillée à la résolution.
Ce projet a appliqué mon utilisation de la théorie des graphes et de Breadth First Search . J'ai amélioré mes compétences en Python et en récursivité. J'ai également trouvé expérimentalement que le nombre maximum de mouvements pour résoudre un cube 2x2 était de 11 mouvements, car je n'ai jamais pu trouver une solution qui prenait plus de temps.
J'ai appris à utiliser la bibliothèque tkinter pour créer une interface graphique pour le projet
