Решение головоломки с ограничением в прологе

Для первой попытки я бы сделал что-то в этом роде:

Для каждого поля используйте 5 переменных. Первая переменная обозначает часть головоломки, которая выходит на поле. Каждая часть имеет свой идентификатор. В случае головоломки, которую вы упомянули в своем комментарии выше, есть 12 частей, поэтому каждая переменная будет иметь домен {1..12}:

P #:: 1..12,

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

[EL,EU,ER,ED] #:: 0..1,

Кусочек головоломки можно закодировать следующим образом:

piece(1,  [](0,1,1,0)).

Это, например, часть А в описании вашей головоломки на веб-сайте, которое вы дали в комментарии.

Теперь вы можете определить отношение соседства между двумя соседними полями. Поскольку у вас есть логические переменные, а вкладка должна соответствовать вмятине, вы устанавливаете ограничение (не «ограничение»), требующее, чтобы сумма была равна единице:

R1 + L2 #= 1,

То есть правый край фигуры на поле один должен совпадать с левым краем фигуры на поле 2.

Вы также устанавливаете аналогичные ограничения для краев вдоль границ.

Вы устанавливаете ограничение, требующее, чтобы все поля содержали разные части:

alldifferent(Fields),

(где Fields — список, содержащий переменные P)

Вам нужна переменная, которая обозначает ориентацию частей головоломки:

O #:: 0..1,

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

Наконец, вам нужны ограничения, которые объединяют переменные части, ориентации и края для каждого поля, так что, когда вы выбираете часть для поля (и ориентация известна), вы можете соответствующим образом установить переменные края:

 once(piece(N, [](L,U,V,D))),
 ( ((P#=N) #/\ (O#=0)) #=> ((EL#=L) #/\ (EU#=  U) #/\ (ER#=R) #/\ (ED#=  D)) ),
 ( ((P#=N) #/\ (O#=1)) #=> ((EL#=R) #/\ (EU#=1-D) #/\ (ER#=L) #/\ (ED#=1-U)) ),

(синтаксис не для Sicstus, а для ECLiPSe. Однако библиотеки ограничений FD должны быть достаточно похожими)

Обратите внимание, что мне пришлось инвертировать кодировку нижнего края при переворачивании куска вверх ногами. Это позволило мне сохранить ограничения «сумма равна единице» для ребер вверх/вниз, но это неоптимально, так как это мешало мне легко распространять информацию из переменных ребра в переменные части (кусок может получить ту же кодировку, что и другой в перевернутом виде). Но мне было лень менять кодировку для первой попытки.

(Редактировать: это должно быть легко исправить, инвертируя кодировку для нижнего края, например: piece(1, [](0,1,1,1))., и используя ограничения, которые требуют, чтобы верхние и нижние края соседних частей имели одинаковое значение, а не имели сумму один.)

Собрав все вместе и просто пометив переменные P (после первого создания экземпляра переменной ориентации), мы получим два решения:

?- rapids(S,O).
S = []([](5, 2, 8, 6), [](11, 10, 1, 4), [](3, 9, 12, 7))
O = 0
Yes (0.01s cpu, solution 1, maybe more)
S = []([](5, 3, 11, 12), [](8, 9, 7, 4), [](2, 10, 6, 1))
O = 1
Yes (0.04s cpu, solution 2, maybe more)
No (0.05s cpu)

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