Решение CuFrog с использованием CLPFD

Итак, у меня есть головоломка под названием CuFrog, которая состоит в заполнении куба 3x3x3 числом в каждой позиции, но с перепрыгиванием через позицию при переходе от одной к другой. Например, для сплющенного куба правильное положение справа от (1,1) на стороне 1 будет (3,1) на стороне 1.

Поэтому я использую для этого ограничения в Прологе и задаю домен каждой переменной (от 1 до 54), я сказал, что все они должны быть разными, и что для каждой позиции одна из позиций в наборе право-лево-вниз-вверх должно быть текущим значением такой позиции + 1.

Кроме того, я дал точку входа в головоломку, что означает, что я поставил цифру 1 уже на первую позицию.

Дело в том, что SICStus не находит мне ответа, когда я маркирую переменные. :( Кажется, я где-то пропускаю какое-то ограничение или, может быть, я что-то делаю не так. Кто-нибудь может помочь?

Спасибо.


puzzle prolog clpfd
person Sidner    schedule 09.12.2012    source источник
comment
Используйте 1_. А потом вводите запрос без маркировки! Вы определенно не пропустили ограничение, скорее наоборот: вы слишком сильно ограничиваете!   -  person false    schedule 09.12.2012
comment
Извините, но как мне использовать это в моем коде? Так? length(Vars,54), domain(Vars,1,54), restriction_predicate(), asserta(clpfd:full_answer). %labelling([min],Vars) -- This is what I was doing.   -  person Sidner    schedule 09.12.2012
comment
Ах хорошо. Затем рядом со строкой use_module.   -  person Sidner    schedule 09.12.2012
comment
Вам нужно ввести его один раз в подсказке | ?-.   -  person false    schedule 09.12.2012
comment
Но разве не маркировка создает экземпляры переменных в Vars в соответствии с ограничениями? Потому что, делая это так, я не получаю определенного ответа, только домены...   -  person Sidner    schedule 09.12.2012
comment
Вы правы, но прежде всего вы должны убедиться, что получаете ответ без ярлыков. Этот ответ является условным ответом. Часто проблемы могут быть выявлены непосредственно на этом уровне.   -  person false    schedule 09.12.2012
comment
давайте продолжим это обсуждение в чате   -  person Sidner    schedule 09.12.2012

Ответы (1)


arrow_upward
2
arrow_downward

Итак, вы говорите, что CLP(FD) не находит решения. Вы имеете в виду, что он заканчивается "нет" или вы имеете в виду, что он не заканчивается?

Проблема выглядит как проблема с путем Гамильтона. Возможно, поиск требует экспоненциального времени и просто не заканчивается практически.

В этом конкретном случае введение ограничений, таких как эвристика нарушения симметрии, может фактически сократить время поиска! Например, из вашей начальной точки вы можете зафиксировать поиск в 2 направлениях, остальные направления можно вывести позже.

Так что если ответ «Нет», это означает слишком много ограничений. Если ответ заключается в том, что он не завершается, это означает, что ограничений недостаточно или их практически невозможно решить.

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

до свидания

person Mostowski Collapse    schedule 01.09.2015