Как решить деревянную головоломку Log Pile с помощью компьютерной программы?

Question

Кто-нибудь может подсказать, как с помощью компьютерной программы решить деревянную головоломку Log Pile?

Смотрите здесь, чтобы визуализировать головоломку: 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, но я чувствую, что это было неуклюжее решение, и мне интересно увидеть более сложные решения. Не стесняйтесь либо предложить общий подход, либо предоставить рабочую программу на выбранном вами языке.

Мой подход состоял в том, чтобы использовать числовую запись выше для создания массива «Журналов». Затем я использовал генератор комбинации / перестановки, чтобы опробовать все возможные варианты расположения Журналов, пока не было найдено решение, в котором все пересечения равнялись нулю (т. Е. Peg to Hole, Hole to Peg или Blank to Blank). Я использовал некоторые ускорения, чтобы обнаружить первое неудачное пересечение для данной перестановки и перейти к следующей перестановке.

Надеюсь, вы найдете это столь же интересным, как и я.

Спасибо, Крейг.

Answer 1

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

Но есть некоторые симметрии и некоторые свойства проблемы, которые могут позволить вам уменьшить количество решений, которые вам нужно попробовать. Например -

• Если вы разделите журналы на две части Подмножества из 5 частей TOP и BOTTOM, # колышки в ТОПе должны соответствовать # отверстия в нижней части, и # отверстия в TOP должен соответствовать # колышкам в ДНО, и # квартиры в ТОПе нуждаются чтобы соответствовать # квартир в нижней части. Если # колышки и # отверстия совпадают, затем # квартиры будут совпадать, так что вы должны не нужно проверять # квартиры.
• Есть 10 * 9 * 8 * 7 * 6 способов можно разделить журналы на два Подмножества из 5 частей. (Как только вы выбрал первые 5 журналов для подмножества TOP, остальные журналы находятся в подмножестве ИТОГ.
• Когда вы тестируете подмножество из 5 частей, есть 5 * 8 * 6 * 4 * 2 способов, которыми вы можете расположить один слой журналов. То есть после того, как вы выбрали журнал 1, осталось 4 журнала. Для второго журнала Вы можете выбрать из четырех, и есть двумя способами это может быть ориентировано с уважение к первому бревну.
• Если у вас есть базовый слой, вы можете попытаться подогнать каждый журнал из другого слоя по одному, пока не найдете тот, который не подходит. В этот момент вы отказываетесь от текущей схемы ведения журнала базового уровня и пробуете следующую.

Answer 2

Следуя совету Джея Элстона, я бы реализовал его, используя следующий псевдокод:

 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 базовых слоев для исследования.

Answer 3

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

В Haskell есть очень элегантные способы решения подобных проблем с использованием функций и возврата. Мой друг решил очень неприятную физическую головоломку - Puzzling Pets - всего за 200 строк Haskell, включая описания всех кусочков и всего остального. Хороший способ освоить соответствующие приемы - прочитать статью Джона Хьюза Почему функциональное программирование имеет значение , установить платформу Haskell и попробовать свои силы.

Answer 4

У меня есть (грязное!) Решение в javascript, но я не смог опубликовать его. Основной используемый алгоритм: Найдите все итерации 5 журналов из 10 журналов, и с каждым набором из 5 журналов создайте каждую возможную итерацию с обращением журналов в обратном порядке. Для каждого из этих состояний мы будем знать, какой шаблон журналов нужно разместить сверху. Итак, мы затем определяем, могут ли остальные 5 журналов быть размещены сверху.

Что приводит к этому представлению решения:

(Bottom, right-> left)  
[0,0,1,-1,1],[-1,-1,0,0,-1],[0,0,1,0,1],[-1,1,0,-1,0],[1,0,-1,0,0]  
(Top, up->down)  
[0,1,0,1,-1],[0,1,0,-1,0],[-1,0,-1,0,1],[1,0,0,1,0],[-1,1,-1,0,0]  


0 - flat   
1 - dowel  
-1 - hole