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

Question

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

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

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

Answer 1

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

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

Answer 2

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

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

Answer 3

Это похоже на более легкое подмножество трехмерной проблемы с упаковкой polyomino. На эту тему есть различные scholarly papers.

Answer 4

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

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

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

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

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

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