Проще всего кодировать алгоритм для куба Rubik?

Ответ 1

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

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

Не слишком сложно кодировать код. Ссылка, упомянутая в Yannick M. answer, тоже выглядит хорошо, но решение cross 'выглядит так, как будто это может быть немного сложнее для меня.

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

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

Ответ 2

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

Ответ 3

Возможно, вы захотите проверить: http://peter.stillhq.com/jasmine/rubikscubesolution.html

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

Ответ 4

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

Ответ 5

Вы можете сделать это, выполнив BFS (Breadth-First-Search). Я считаю, что реализация не так сложна (это один из простейших алгоритмов под категорией графика). Делая это с помощью структуры данных, называемой queue, то, на что вы действительно будете работать, - это построить дерево 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. У них есть несколько библиотек, которые помогут вам визуализировать их и помочь вам избежать ненужных усилий.