Какой лучший способ решить эту игру?

Question

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

Цель состоит в том, чтобы объединить набор твердых тел (например, кусочки тетриса в трех измерениях), чтобы сформировать форму выполнимым образом, который учитывает тот факт, что кусочки можно прикрепить или вставить в конструкцию, только если они соответствуют тип движения (игнорирование поворотов, повороты только на 90 °).

Проверьте эту картинку, чтобы понять, что я имею в виду.

Answer 1

В моем последнем CS-классе мы создали универсальный решатель головоломок, который работал, представляя состояния в C ++ как объекты.У каждого объекта был метод для сравнения состояния, которое он представлял, с другим состоянием.Это использовалось для запоминания, чтобы определить, были ли состояния уже замечены.Каждое состояние также имело метод для генерации состояний, непосредственно достижимых из этого состояния (то есть вращение блока, размещение блока, смещение блока).Решатель работал, поддерживая очередь состояний, выталкивая состояние из передней части очереди, проверяя, было ли это желаемое состояние (то есть загадка решена).Если нет, памятка (мы использовали хешированный набор) была проверена, чтобы увидеть, было ли состояние уже замечено.Если нет, то состояния, достижимые из текущего состояния, были сгенерированы и добавлены в конец очереди.Пустая очередь сигнализировала о неразрешимой головоломке.

Концептуализация чего-то подобного для 3D была бы сложной, но это основной подход к компьютерному решению головоломки.

Answer 2

Похоже на более простое подмножество трехмерной polyomino задачи упаковки. На эту тему существуют различные научные статьи .

Answer 3

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

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

Объявите произвольный куб каждого фрагмента как его источник. Обратите внимание, что для каждой части головоломки имеется 24 возможных поворота, по одной ориентации для каждой возможной грани исходного куба, обращенного вверх, и умножения на 4 возможных поворота вокруг вертикальной оси в этом положении.

Попытка отбросить пространство поиска путем поиска возможных ориентаций, которые производят ту же самую конечную часть, если данное вращение, сопровождаемое переводом исходного куба в любой из других кубов части, приводит к точно такому же занятому объему как ранее рассмотренное вращение, отбросьте это вращение из будущего рассмотрения.

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

Если последний абзац возвращается без решения, тогда головоломка была неразрешимой.

Answer 4

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

Проблема заключается в написании программы, способной выполнять все проверки состояния и преобразования из одного состояния в другое. Потому что вы должны увидеть, физически ли возможна конфигурация.