Una estrategia estocástica de búsqueda local para el cubo de rubik

A local stochastic search strategy for rubik´s cube

En este artículo se estudia a fondo la estructura del grupo de permutaciones G asociado al cubo de Rubik, con el propósito de diseñar un algoritmo estocástico de búsqueda local que, partiendo de cualquier posicion, lleve el cubo a su posicion inicial. Para ello se encuentra una ltracion apropiada de subgrupos de G (Id) C G_3 C G_2 C G_1 C G; que permiten fraccionar el proceso de búsqueda y seleccióon del algoritmo en cuatro pasos que corresponderán a cada uno de los subgrupos Gi y que converge en el último paso al elemento identidad de G, que corresponde a la posicion en la que el rompecabezas queda "resuelto".

In this article we study the structure of the permutation group G associated with Rubik's Cube, with the purpose of designing a stochastic local search algorithm that, starting from any position, takes the cube to its initial conguration, i.e., that position where the puzzle is "solved". For this, we find a filtration of G (Id) C G_3 C G_2 C G_1 C G; which partitions the search and selection process of the algorithm in four steps, each one corresponding to each of the subgroups Gi. In the last step the algorithm reaches the identity element of G, what amounts to reaching the initial conguration of the cube.