Легче всего кодировать алгоритм для кубика Рубика?

Question

Какой бы относительно простой алгоритм для кодирования на Java для решения кубика Рубика. Эффективность также важна, но вторична.

Answer 1

Выполняйте случайные операции, пока не получите правильное решение. Самый простой алгоритм и наименее эффективный.

Answer 2

Самый простой нетривиальный алгоритм, который я нашел, это:

http://www.chessandpoker.com/rubiks-cube-solution.html

Код выглядит не слишком сложно. Ссылка, упомянутая в ответе Янника М. , тоже выглядит хорошо, но решение шага ' крест ' выглядит для меня немного сложнее.

Существует несколько реализаций решателя с открытым исходным кодом, на которые вы могли бы взглянуть. Вот реализация Python . Этот Java-апплет также включает решатель, и исходный код доступен. Также имеется Javascript solver , также с загружаемым исходным кодом.

Ответ Энтони Гатлина дает отличное замечание о пригодности Пролога для этой задачи. Вот подробная статья о том, как написать собственный Prolog solver . Используемая им эвристика особенно интересна.

Answer 3

Могу захотеть проверить: http://peter.stillhq.com/jasmine/rubikscubesolution.html

Имеет графическое представление алгоритма для решения кубика Рубика 3x3x3

Answer 4

Я понимаю, что ваш вопрос связан с Java, но с практической точки зрения такие языки, как Prolog, гораздо лучше подходят для таких задач, как решение кубика Рубика. Я предполагаю, что это, вероятно, для класса, и у вас может не быть свободы выбора инструмента.

Answer 5

Одним из решений является угадать одновременно все возможные маршруты. Это звучит глупо, но вот логика - более 99% возможных схваток будут решены менее чем за 20 ходов. Это означает, что, хотя вы перебираете огромное количество возможностей, вы все равно будете делать это в конце концов. По сути, это будет работать, если вы сделаете свой первый шаг в качестве зашифрованного куба. Тогда у вас будут новые кубы, хранящиеся в переменных для каждого возможного хода в этом первом кубе. Для каждого из этих новых кубов вы делаете то же самое. После каждого возможного перемещения проверьте, завершено ли оно, и если да, то это решение. Здесь, чтобы убедиться, что у вас есть решение, вам понадобится дополнительный бит данных в каждом кубе Рубика, сообщающий о шагах, проделанных для достижения этой стадии.

Answer 6

Для справки, вы, безусловно, можете посмотреть на эту реализацию Java. -> Использует двухфазный алгоритм для решения кубика Рубика . И попробовал этот код, и он также работает.

Answer 7

Вы можете сделать это, выполнив BFS (поиск в ширину). Я думаю, что реализация не так сложна (это один из самых простых алгоритмов в категории графа). Делая это со структурой данных, называемой очередью, вы действительно будете работать над созданием дерева BFS и находить так называемый кратчайший путь от заданного условия до состояния желания. Недостаток этого алгоритма состоит в том, что он недостаточно эффективен (без какой-либо модификации, даже для решения куба 2x2x2 необходимое количество времени составляет ~ 5 минут). Но вы всегда можете найти некоторые приемы, чтобы повысить скорость.

Если честно, это одно из домашних заданий курса под названием " Введение алгоритма " из MIT. Вот ссылка на домашнее задание: http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-006-introduction-to-algorithms-fall-2011/assignments/MIT6_006F11_ps6.pdf. У них есть несколько библиотек, которые помогут вам визуализировать это и избежать ненужных усилий.