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

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

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

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

Ответы

Ответ 1

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

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

Ответ 2

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

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

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

Ответ 3

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

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

Ответ 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