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