Мне дали упражнение по решению загадки зебры с использованием решателя ограничений по моему выбору, и я попробовал его, используя Библиотека Prolog clpfd.
Я знаю, что есть и другие, более идиоматические способы решения этой проблемы в Prolog, но этот вопрос касается конкретно пакета clpfd!
Вот конкретный вариант головоломки (учитывая, что их много), который я пытаюсь решить:
Всего пять домов
- Англичанин живет в красном доме
- У шведов есть собака
- Датчанин любит пить чай
- Зеленый дом оставлен белому дому
- Хозяин зеленого дома пьет кофе
- Человек, который курит Pall Mall, владеет птицей.
- В среднем доме пьют молоко
- Хозяин желтого дома курит Dunhill
- Норвежец живет в первом доме
- Курильщик мальборо живет рядом с хозяином кошки
- Владелец лошади живет рядом с человеком, который курит данхилл.
- Курильщик winfield любит пить пиво
- Норвежец живет рядом с синим домом
- Немец курит ротманны
- У курильщика мальборо есть сосед, который пьет воду
Я попытался решить эту проблему следующим образом:
Каждый атрибут, который может иметь дом, моделируется как переменная, например «Британский», «Собака», «Зеленый» и т. Д. Атрибуты могут принимать значения от 1 до 5, в зависимости от дома, в котором они встречаются, например если переменная «Собака» принимает значение 3, собака живет в третьем доме.
Такой подход упрощает моделирование ограничений соседей следующим образом:
def neighbor(X, Y) :-
(X #= Y-1) #\/ (X #= Y+1).
Но почему-то пакет clpfd не дает решения, хотя (ИМО) проблема смоделирована правильно (я использовал ту же модель с Решатель ограничений Choco, и результат был правильным).
Вот полный код:
:- use_module(library(clpfd)).
neighbor(X, Y) :-
(X #= (Y - 1)) #\/ (X #= (Y + 1)).
solve([British, Swedish, Danish, Norwegian, German], Fish) :-
Nationalities = [British, Swedish, Danish, Norwegian, German],
Colors = [Red, Green, Blue, White, Yellow],
Beverages = [Tea, Coffee, Milk, Beer, Water],
Cigarettes = [PallMall, Marlboro, Dunhill, Winfield, Rothmanns],
Pets = [Dog, Bird, Cat, Horse, Fish],
all_different(Nationalities),
all_different(Colors),
all_different(Beverages),
all_different(Cigarettes),
all_different(Pets),
Nationalities ins 1..5,
Colors ins 1..5,
Beverages ins 1..5,
Cigarettes ins 1..5,
Pets ins 1..5,
British #= Red, % Hint 1
Swedish #= Dog, % Hint 2
Danish #= Tea, % Hint 3
Green #= White - 1 , % Hint 4
Green #= Coffee, % Hint 5,
PallMall #= Bird, % Hint 6
Milk #= 3, % Hint 7
Yellow #= Dunhill, % Hint 8,
Norwegian #= 1, % Hint 9
neighbor(Marlboro, Cat), % Hint 10
neighbor(Horse, Dunhill), % Hint 11
Winfield #= Beer, % Hint 12
neighbor(Norwegian, Blue), % Hint 13
German #= Rothmanns, % Hint 14,
neighbor(Marlboro, Water). % Hint 15
Я неправильно понял концепцию в clpfd, или я просто упускаю здесь что-то очевидное? Если это поможет, здесь вы можете найти то же самое подход реализован с использованием Choco и Scala.
Изменить: Причина, по которой я считаю, что решатель не может решить проблему, заключается в том, что он никогда не дает определенных значений для переменных, а только с диапазонами, например «Рыба 1..3 \ / 5».
V in -1\/1, но если разрешить выражения для первого аргумента, это сделает его дефолтным. - person false schedule 23.06.2012