Układanie puzzle Zebra (aka puzzle Einsteina) przy pomocy biblioteki clpfd Prolog

Question

Otrzymałem zadanie, aby rozwiązać zagadkę zebry za pomocą wybranego przeze mnie narzędzia ograniczającego, a spróbowałem go używając Prolog clpfd library.

Mam świadomość, że istnieją inne, bardziej idiomatyczne sposoby rozwiązania tego problemu w Prologu, ale to pytanie dotyczy pakietu clpfd!

Tak specyficzna odmiana puzzli (biorąc pod uwagę, że istnieje wiele z nich) próbuję rozwiązać jest to jedno:

Istnieje pięć domów

1. życiu Englishman w czerwonym domu
2. szwedzka właścicielem psa
3. Duński lubi pić herbatę
4. zielona h ouse pozostało do białego domu
5. Właściciel zielonego napojów kawiarni
6. Osoba, która pali Pall Mall posiada ptaka
7. mleko jest pijany w środku domu
8. Właściciel żółtego domu pali Dunhill
9. Norweg mieszka w pierwszym domu
10. palacz Marlboro mieszka obok właściciela kota
11. Właściciel konia mieszka obok osoby, która pali Dunhill
12. The Winfield palacz lubi pić piwo
13. Norweg mieszka obok niebieskiego domu
14. niemieckiego pali rothmanns
15. Marlboro palacz ma sąsiada, który pije wodę

próbowałem go rozwiązać z następujące podejście:

Each attribute a house can have is modeled as a variable, e.g. "British", "Dog", "Green", etc. The attributes can take values from 1 to 5, depending on the house in which they occur, e.g. if the variable "Dog" takes the value 3, the dog lives in the third house.

Takie podejście ułatwia modelowanie ograniczeń sąsiada tak:

def neighbor(X, Y) :- 
    (X #= Y-1) #\/ (X #= Y+1). 

Ale jakoś, pakiet clpfd nie przynosi rozwiązanie, choć (IMO) problem wzorowany jest poprawnie (użyłem dokładnie tego samego modelu z Choco constraint solver a wynik był prawidłowy).

Oto kompletny kod:

:- 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 

Czy ja rozumieją pojęcie zasięgu clpfd, albo ja po prostu brakuje czegoś oczywiste tutaj? Jeśli to pomoże, here można znaleźć takie samo podejście realizowane za pomocą Choco i Scala.

---

Edit: Powodem dlaczego uważam, że Solver nie jest w stanie rozwiązać problemu ist że nigdy nie wyjdzie z określonych wartości dla zmiennych, ale tylko z zakresami, np "Ryba 1..3 \/5".

Answer 1

prowadzenie kodu w SWI-Prolog, mam

?- solve(X),label(X). 
X = [3, 5, 2, 1, 4]. 

Bez label:

?- solve(X). 
X = [3, _G3351, _G3354, 1, _G3360], 
_G3351 in 4..5, 
all_different([_G3351, _G3386, _G3389, 2, _G3395]), 
all_different([3, _G3351, _G3354, 1, _G3360]), 
_G3386 in 3..5, 
all_different([_G3386, _G3444, 1, _G3450, _G3360]), 
_G3389 in 1\/3..5, 
_G3389+1#=_G3478, 
_G3492+1#=_G3389, 
_G3395 in 1\/3..5, 
_G3478 in 2..6, 
_G3444#=_G3478#<==>_G3529, 
_G3444 in 2..5, 
_G3444#=_G3556#<==>_G3553, 
_G3444#=_G3568#<==>_G3565, 
_G3444#=_G3492#<==>_G3577, 
_G3450 in 2\/5, 
all_different([_G3354, 4, 3, _G3450, _G3614]), 
_G3360 in 2\/4..5, 
_G3354 in 2\/5, 
_G3614 in 1..2\/5, 
_G3614+1#=_G3556, 
_G3568+1#=_G3614, 
_G3556 in 2..3\/6, 
_G3553 in 0..1, 
_G3565#\/_G3553#<==>1, 
_G3565 in 0..1, 
_G3568 in 0..1\/4, 
_G3492 in 0..4, 
_G3577 in 0..1, 
_G3577#\/_G3529#<==>1, 
_G3529 in 0..1. 

Jeśli zmienię all_different do all_distinct uzyskać rozwiązanie bez etykiety:

.... 
all_distinct(Nationalities), 
all_distinct(Colors), 
all_distinct(Beverages), 
all_distinct(Cigarettes), 
all_distinct(Pets), 
.... 

?- solve(X). 
X = [3, 5, 2, 1, 4]. 

Jak widać, dokumenty mówią o silniejszej propagacji dla all_distinct vs all_different. Uruchamianie proponowanej próby pomocy, aby zrozumieć różnicę między tymi:

?- maplist(in, Vs, [1\/3..4, 1..2\/4, 1..2\/4, 1..3, 1..3, 1..6]), all_distinct(Vs). 
false. 

?- maplist(in, Vs, [1\/3..4, 1..2\/4, 1..2\/4, 1..3, 1..3, 1..6]), all_different(Vs). 
Vs = [_G419, _G422, _G425, _G428, _G431, _G434], 
_G419 in 1\/3..4, 
all_different([_G419, _G422, _G425, _G428, _G431, _G434]), 
_G422 in 1..2\/4, 
_G425 in 1..2\/4, 
_G428 in 1..3, 
_G431 in 1..3, 
_G434 in 1..6. 

Answer 2

Istnieje kilka nieporozumień tutaj: Pan, „pakiet clpfd nie przynosi rozwiązania”, ale w rzeczywistości to nie uzyskując jeden:

?- solve(Ls, Fish), label(Ls). 
Ls = [3, 5, 2, 1, 4], 
Fish in 1\/4, 
all_different([5, 3, _G3699, 2, Fish]), 
_G3699 in 1\/4, 
_G3699+1#=_G3727, 
_G3741+1#=_G3699, 
_G3727 in 2\/4..5, 
2#=_G3727#<==>_G3766, 
_G3766 in 0..1, 
_G3792#\/_G3766#<==>1, 
_G3792 in 0..1, 
2#=_G3741#<==>_G3792, 
_G3741 in 0\/2..3. 

Więc wiemy, że jeśli istnieje rozwiązanie, a następnie Ryba jest albo 1 albo 4. Spróbujmy 1:

?- solve(Ls, Fish), label(Ls), Fish = 1. 
false. 

nr Więc spróbujmy 4:

?- solve(Ls, Fish), label(Ls), Fish = 4. 
Ls = [3, 5, 2, 1, 4], 
Fish = 4. 

To działa i jest podstawowym rozwiązaniem problemu. Można ją uzyskać w inny sposób, na przykład poprzez włączenie ryb w zmiennych, które mają być oznakowane:

?- solve(Ls, Fish), label([Fish|Ls]). 
Ls = [3, 5, 2, 1, 4], 
Fish = 4 ; 
false. 

Celem znakowania jest dokładnie wypróbować wartości konkretne dla ograniczonych zmiennych, niezależnie od tego, czy rzeczywiście jest rozwiązanie. Zbiegiem okoliczności, all_distinct/1 jest wystarczająco silny, aby w tym przypadku samemu uzyskać rozwiązanie naziemne, ale ogólnie rzecz biorąc, nie jest to prawdą i musisz ostatecznie użyć etykietowania, aby uzyskać bezwarunkową (tj. Nie więcej oczekujących ograniczeń) odpowiedź. Oczywiście musisz również ogólnie oznaczać zmienne, które Cię interesują, a nie tylko ich podzbiór, jak na początku. Aby oznaczyć pojedynczą zmienną, możesz użyć indomain/1, więc również dodanie indomain (Fish) do pierwszego powyższego zapytania również będzie działać. Nie mogłem odtworzyć błędu wystąpienia, o którym wspomniałeś w kolejnym komentarzu, w rzeczywistości, jak widać powyżej najbardziej ogólne zapytanie (X, Y) działa z opublikowanym przez ciebie kodem. Na koniec sprawdź:

neighbor(X, Y) :- abs(X-Y) #= 1.