java - rapida - ¿Es el algoritmo más fácil de codificar para el cubo de Rubik?
como armar un cubo rubik para principiantes (6)
El algoritmo no trivial más simple que he encontrado es este:
http://www.chessandpoker.com/rubiks-cube-solution.html
No parece demasiado difícil de codificar. El enlace mencionado en la respuesta de Yannick M. también se ve bien, pero la solución del paso " cruzado " parece que podría ser un poco más complejo para mí.
Hay una serie de implementaciones de solucionador de código abierto que le gustaría echar un vistazo. Aquí hay una implementación de Python . Este applet de Java también incluye un solucionador, y el código fuente está disponible. También hay un solucionador de Javascript , también con código fuente descargable.
La respuesta de Anthony Gatlin hace un punto excelente sobre la idoneidad de Prolog para esta tarea. Aquí hay un artículo detallado sobre cómo escribir su propio solucionador de Prolog . Las heurísticas que utiliza son particularmente interesantes.
Lo que sería un algoritmo relativamente fácil de codificar en Java para resolver un cubo de Rubik. La eficiencia también es importante pero una consideración secundaria.
Entiendo que su pregunta está relacionada con Java, pero en una nota práctica, los lenguajes como Prolog son problemas mucho más adecuados como resolver un cubo de Rubik. Sin embargo, supongo que esto es probablemente para una clase y es posible que no tenga margen de maniobra para elegir la herramienta.
Para su referencia, ciertamente puede mirar esta implementación de Java. -> Usa algoritmo de dos fases para resolver el cubo de Rubik . Y he probado este código y también funciona.
Puede que desee revisar: http://peter.stillhq.com/jasmine/rubikscubesolution.html
Tiene una representación gráfica de un algoritmo para resolver un cubo de Rubik de 3x3x3
Puedes hacerlo haciendo BFS (búsqueda de amplitud). Creo que la implementación no es tan difícil (es uno de los algoritmos más simples en la categoría del gráfico). Al hacerlo con la estructura de datos llamada cola, lo que realmente trabajará es construir un árbol BFS y encontrar una llamada ruta más corta desde la condición dada a la condición deseada. El inconveniente de este algoritmo es que no es lo suficientemente eficiente (sin ninguna modificación, incluso para resolver 2x2x2 cúbicos, la cantidad de tiempo necesaria es de ~ 5 minutos). Pero siempre puedes encontrar algunos trucos para aumentar la velocidad.
Para ser honesto, es uno de los deberes del curso llamado " Introducción al algoritmo " del MIT. Aquí está el enlace de la tarea: http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-006-introduction-to-algorithms-fall-2011/assignments/MIT6_006F11_ps6.pdf . Tienen algunas bibliotecas para ayudarlo a visualizarlo y para ayudarlo a evitar esfuerzos innecesarios.
Realiza operaciones aleatorias hasta obtener la solución correcta. El algoritmo más sencillo y el menos eficiente.