Решение кубика Рубика программно

Question

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

Пожалуйста, дайте мне предложения о том, как решить эту проблему более эффективно - например, о других методах или о том, как откатить саму себя. В Google я нашел много ярлыков для решения этой проблемы, но я не хочу решать это с помощью ярлыков.

Answer 1

Почему бы не использовать ориентированное на человека решение и запрограммировать его.

Вам нужно какое-то сопоставление с образцом, но это будет не так сложно. (Кроме того, есть программы, решающие 1000x1000x1000).

Основная идея - работать поэтапно:

• Первый слой
• Второй слой
• Третий слой

Для каждого слоя вы реализуете пару алгоритмов, которые превращают шаблон X в шаблон X '. Каждый шаг в фазе должен приблизить куб к решению. Вы можете сделать это, добавив значение к каждому шаблону (где более высокие значения задаются для более неразрешенных кубов). Вы также можете добавить сложность (например, количество ходов), чтобы выбрать алгоритм, основанный на получении максимального значения за сложность (или достичь наилучшего результата с наименьшим количеством ходов).

Самое интересное в этом подходе - вы можете добавлять новые алгоритмы, если хотите, и проверять, как часто они используются. Таким образом, вы можете проверить полезность каждого алгоритма.

Если вы действительно хотите заработать эти geekpoints, создайте отдельный язык для описания алгоритмов и паттерна, который они решают.

Answer 2

Есть много алгоритмов для решения проблемы Рубика, но вы можете обратиться к этому оптимальному http://en.wikipedia.org/wiki/Optimal_solutions_for_Rubik's_Cube

Answer 3

Я не уверен, что понимаю вашу проблему и что вы подразумеваете под ярлыками.Если вы используете какой-либо метод динамического программирования для решения кубика рубика, вам нужно убедиться, что вы смотрите на достаточно далеко идущие шаги, чтобы найти решение.Я считаю, что если вы поддерживаете только 2 типа движений (вращение вправо, вращение вверх), вам нужно посмотреть на 12 шагов (не уверен), прежде чем принимать решение по каждому шагу, чтобы обеспечить решение.

Если выДелая что-то вроде этого, вы обнаружили, что у вас недостаточно места в памяти, и имейте в виду, что вам нужно только сохранить путь, который вы проходите, чтобы принять решение о правильном решении (а не обо всем дереве).

Я успешно использовал этот подход для решения кубика Рубика в Java, поэтому у С не должно быть никаких проблем (в отношении объема памяти).

Answer 4

Если вас не волнует количество задействованных ходов, вот способ разделить пространство состояний, чтобы ваш метод брутфорс работал.

Поиск решения для кубика Рубикса для чайников

• Сначала перебор всех граней рубика, НО углы на места
• затем найдите ходы, которые позволяют инварианту получить эту фасетку (например, (f.g.f-1.g-1) ^ 3). Два хода на самом деле достаточно. Чтобы найти их, рассмотрим перестановку для угловых и не угловых субкубов, а затем итерируем ppcm длины угловых циклов, чтобы получить и инвариантную по углам)
• Используйте алгоритм обратного отслеживания, чтобы расположить углы (но для выравнивания цветов они все еще требуют поворота)
• Найдите магические ходы, которые заставляют куб на одном отрезке вращаться вместе. Нет движения, которое

Answer 5

Кубик Рубика имеет размер пространства состояний порядка 2 ⁶⁵ . Алгоритм обратного отслеживания, который просматривает пространство состояний вслепую, может потребоваться исследовать большую часть пространства состояний, прежде чем он найдет решение, поэтому очевидно, что простой алгоритм обратного отслеживания не будет работать очень хорошо. Но тогда эта проблема уже решена много раз. Смотрите, например http://www.cs.princeton.edu/courses/archive/fall06/cos402/papers/korfrubik.pdf