Как я могу решить Груду Журнала деревянная загадка с компьютерной программой?
Кто-либо может предложить, как решить Груду Журнала деревянная загадка с помощью компьютерной программы?
Посмотрите здесь для визуализации загадки: http://www.puzzlethis.co.uk/products/madcow/the_log_pile.htm
Изображение только показывает некоторые части. Полный набор 10 частей настроен следующим образом с 1 представлением штепселя,-1 представлением дыры и 0 представлениями ни штепсель, ни дыры.
- 1,1,0,-1,0
1,0,1,0,0
1,-1,1,0,0
- 1,-1,0,0,-1
- 1,1,0,1,0
0,1,0,0,1
1,0,-1,0,-1
0,-1,0,1,0
0,0,-1,1,-1
1,0,-1,0,0
Части могут взаимно блокироваться в двух слоях 5 частей каждый с верхним слоем на уровне 90 градусов к нижнему слою как показано в вышеупомянутой ссылке.
Я уже создал решение этой проблемы сам с помощью Java, но я чувствую, что это было неуклюжее решение, и мне интересно видеть некоторые более комплексные решения. Не стесняйтесь или предлагать общий подход или предоставлять рабочую программу в языке по Вашему выбору.
Мой подход должен был использовать числовую нотацию выше для создания массива "Logs". Я затем использовал генератор комбинации/перестановки для попытки всех возможных расположений Журналов, пока решение не было найдено где все пересечения, приравненные к нулю (т.е. Штепсель к Дыре, Дыре, чтобы Привязать или Очистить для Очищения). Я использовал некоторые ускорения для обнаружения первого неудавшегося пересечения для данной перестановки и движения к следующей перестановке.
Я надеюсь, что Вы находите это столь же интересным, как я имею.
Спасибо, Craig.
3 ответа
Следуя совету Джея Элстона, я реализовал бы это, используя следующий псевдокод:
Read in the pieces
Annotate each piece with its number of pegs and holes
Generate all possible base layers (10 over 5 = 252, selecting 5 from the set),
so that sum(above, pegs) == sum(below, holes) and sum(below, pegs) == sum(above, holes)
For each base layer, (5! = 120 of them, permuting the 'below' pieces)
compute 'rotated pieces' for the base layer
if one-to-one match between top layer and rotated base-layer pieces,
report successful solution
Там, где «повернутые части» были бы для данного базового слоя идеальными частями, которые вам нужно было бы покрыть. Вычислив эти части и сопоставив их с частями верхнего слоя, вы можете использовать сортировку O (N log N) для сопоставления повернутых частей с реальным верхним слоем вместо сопоставления со всеми N! возможные варианты расположения верхнего слоя. Плюс, при первом не матче, вы можете выйти раньше срока.
Ключ к написанию эффективных алгоритмов - как можно раньше сократить поиск и использовать любые симметрии. Например, вы можете сократить время выполнения вдвое, если считаете, что головоломка симметрична, и поэтому произвольно назначаете кусок нижнему слою: тогда у вас будет только 9 из 4 базовых слоев для исследования.
Эта проблема, по-видимому, является формой проблемы булевой выполнимости . Если это так, то самый известный подход - это грубая сила.
Но есть некоторые симметрии и некоторые свойства проблемы, которые могут позволить вам сократить количество решений, которые вам нужно попробовать. Например -
- Если вы разделите бревна на два подмножества по 5 частей TOP и BOTTOM, колышки # в TOP должны совпадать с # отверстиями в BOTTOM. , а # отверстий в TOP должны совпадать с # колышками в BOTTOM, а # квартир в TOP должны соответствовать # квартирам в BOTTOM. Если # колышков и # отверстий совпадают, то # квартир также будут совпадать, поэтому вам не нужно проверять # квартир.
- Существует 10 * 9 * 8 * 7 * 6 способов разбить журналы на два подмножества по 5 частей. (После того, как вы выбрали первые 5 журналов для подмножества TOP, оставшиеся журналы будут в подмножестве BOTTOM.
- Когда вы тестируете подмножество из 5 частей, есть 5 * 8 * 6 * 4 * 2 способа расположить один слой журналов. То есть после выбора журнала 1 остается 4 журнала. Для второго журнала вы можете выбрать один из четырех и есть два способа ориентировать его с относительно первого бревна.
- Когда у вас есть базовый слой, вы можете попытаться подогнать каждое бревно из другого слоя по одному за раз , пока не найдете тот, который не подходит. На этом этапе вы отказываетесь от текущего расположения журнала базового уровня и пробуете следующий.
Пролог популярен для задач этого типа. Я создал несколько более простых задач-головоломок , которые имеют относительно хорошие решения в Прологе.
В Haskell есть очень элегантные способы решения подобных проблем с использованием функций и поиска с возвратом. Мой друг решил очень неприятную физическую головоломку - Puzzling Pets - чуть более чем в 200 строках Haskell, включая описания всех частей и всего остального. Хороший способ изучить соответствующие методы - прочитать статью Джона Хьюза Почему функциональное программирование имеет значение , установить Haskell Platform и попробовать свои силы.