Edycja: ta łamigłówka jest również znana jako „Zagadka Einsteina”
Kto jest właścicielem Zebra (można spróbować wersji online tutaj ) jest przykładem klasycznego zestawu zagadek i założę się, że większość ludzi na przepełnienie stosu można go rozwiązać za pomocą pióra i papieru. Ale jak wyglądałoby rozwiązanie programowe?
W oparciu o wskazówki wymienione poniżej ...
- Jest pięć domów.
- Każdy dom ma swój niepowtarzalny kolor.
- Wszyscy właściciele domów są różnych narodowości.
- Wszyscy mają różne zwierzęta.
- Wszyscy piją różne napoje.
- Wszyscy palą różne papierosy.
- W czerwonym domu mieszka Anglik.
- Szwed ma psa.
- Duńczyk pije herbatę.
- Zielony dom znajduje się po lewej stronie białego domu.
- Piją kawę w zielonym domu.
- Mężczyzna, który pali Pall Mall, ma ptaki.
- W żółtym domu palą Dunhill.
- W środkowym domu piją mleko.
- Norweg mieszka w pierwszym domu.
- Mężczyzna, który pali Blend, mieszka w domu obok domu z kotami.
- W domu obok domu, w którym mają konia, palą Dunhill.
- Mężczyzna, który pali Blue Master, pije piwo.
- Niemiec pali Prince.
- Norweg mieszka obok niebieskiego domu.
- Piją wodę w domu obok domu, w którym palą Blend.
... kto jest właścicielem Zebry?
language-agnostic
logic
constraint-programming
zebra-puzzle
activout.se
źródło
źródło
Odpowiedzi:
Oto rozwiązanie w Pythonie oparte na programowaniu z ograniczeniami:
Wynik:
Znalezienie rozwiązania zajmuje 0,6 sekundy (procesor 1,5 GHz).
Odpowiedź brzmi: „Niemiec jest właścicielem zebry”.
Aby zainstalować
constraint
moduł przezpip
: pip install python-constraintAby zainstalować ręcznie:
Ściągnij:
$ wget https://pypi.python.org/packages/source/p/python-constraint/python-constraint-1.2.tar.bz2#md5=d58de49c85992493db53fcb59b9a0a45
wypakuj (Linux / Mac / BSD):
$ bzip2 -cd python-constraint-1.2.tar.bz2 | tar xvf -
wypakuj (Windows, z 7zip ):
> 7z e python-constraint-1.2.tar.bz2
> 7z e python-constraint-1.2.tar
zainstalować:
$ cd python-constraint-1.2
$ python setup.py install
źródło
pip install python-constraint
? Zrobiłem to przed chwilą i wydaje się, że przyniosło to oczekiwane rezultaty.W Prologu możemy utworzyć instancję domeny, po prostu wybierając z niej elementy :) (dokonując wzajemnie wykluczających się wyborów , dla wydajności). Używając SWI-Prolog,
Działa dość natychmiastowo:
źródło
Jeden z plakatów wspomniał już, że Prolog jest potencjalnym rozwiązaniem. To prawda i właśnie tego bym użył. Mówiąc bardziej ogólnie, jest to doskonały problem dla zautomatyzowanego systemu wnioskowania. Prolog to logiczny język programowania (i powiązany z nim interpreter), który tworzy taki system. W zasadzie pozwala wnioskować o faktach na podstawie stwierdzeń złożonych za pomocą logiki pierwszego rzędu . FOL jest w zasadzie bardziej zaawansowaną formą logiki zdań. Jeśli zdecydujesz, że nie chcesz używać Prologu, możesz użyć podobnego systemu własnego stworzenia, używając techniki takiej jak modus ponens, aby wyciągnąć wnioski.
Będziesz oczywiście musiał dodać kilka zasad dotyczących zebr, ponieważ nigdzie o tym nie wspomniano ... Myślę, że chodzi o to, abyś mógł rozgryźć pozostałe 4 zwierzaki i wydedukować, że ostatnim z nich jest zebra? Będziesz chciał dodać zasady, zgodnie z którymi zebra jest jednym ze zwierząt domowych, a każdy dom może mieć tylko jednego zwierzaka. Wprowadzenie tego rodzaju wiedzy „zdroworozsądkowej” do systemu wnioskowania jest główną przeszkodą w używaniu tej techniki jako prawdziwej sztucznej inteligencji. Istnieją projekty badawcze, takie jak Cyc, które próbują przekazać taką powszechną wiedzę brutalną siłą. Odnieśli interesujący sukces.
źródło
Zgodność ze SWI-Prolog:
U tłumacza:
źródło
Oto, jak bym to zrobił. Najpierw wygenerowałem wszystkie zamówione n-krotki
5 ^ 6 z nich, 15625, łatwe w zarządzaniu. Potem odfiltrowałbym proste warunki logiczne. jest ich dziesięć, a każdy z nich, którego można się spodziewać, aby odfiltrować 8/25 warunków (1/25 warunków zawiera Szweda z psem, 16/25 zawiera nie-Szweda z innym psem) . Oczywiście nie są niezależne, ale po ich odfiltrowaniu nie powinno ich zbyt wiele pozostać.
Potem masz ładny problem z wykresem. Utwórz wykres, w którym każdy węzeł będzie reprezentował jedną z pozostałych n-krotek. Dodaj krawędzie do wykresu, jeśli dwa końce zawierają duplikaty w jakiejś pozycji n-krotek lub naruszają jakiekolwiek ograniczenia „pozycyjne” (jest ich pięć). Stamtąd jesteś już prawie w domu, przeszukaj wykres pod kątem niezależnego zestawu pięciu węzłów (bez żadnego z węzłów połączonych krawędziami). Jeśli nie ma ich zbyt wiele, możesz po prostu wyczerpująco wygenerować wszystkie 5-krotek n-krotek i ponownie je przefiltrować.
To może być dobry kandydat do kodu golfa. Ktoś prawdopodobnie może rozwiązać to w jednej linii za pomocą czegoś takiego jak haskell :)
refleksja: początkowe przejście filtru może również wyeliminować informacje z ograniczeń pozycyjnych. Niewiele (1/25), ale nadal znaczące.
źródło
Kolejne rozwiązanie w języku Python, tym razem wykorzystujące PyKE (silnik wiedzy Python). To prawda, jest bardziej rozwlekłe niż użycie modułu „constraint” Pythona w rozwiązaniu @JFSebastian, ale zapewnia interesujące porównanie dla każdego, kto szuka surowego silnika wiedzy dla tego typu problemów.
clues.kfb
relations.krb
driver.py (właściwie większy, ale to jest istota)
Przykładowe dane wyjściowe:
Źródło: https://github.com/DreadPirateShawn/pyke-who-owns-zebra
źródło
Oto fragment pełnego rozwiązania wykorzystującego NSolver , opublikowany w Einstein's Riddle w C # :
źródło
Oto proste rozwiązanie w CLP (FD) (patrz także clpfd):
Uruchomienie go powoduje:
źródło
neighbor(X,Y) :- abs(X-Y) #= 1.
W PAIP (Rozdział 11) Norvig rozwiązuje zagadkę zebry za pomocą Prologu osadzonego w Lispie .
źródło
Rozwiązanie ES6 (Javascript)
Z dużą ilością generatorów ES6 i odrobiną lodashu . Będziesz potrzebował Babel, aby to uruchomić.
Wynik:
Czas działania to dla mnie około 2,5 sekundy, ale można to znacznie poprawić, zmieniając kolejność reguł. Postanowiłem zachować oryginalny porządek dla jasności.
Dzięki, to było fajne wyzwanie!
źródło
To naprawdę problem rozwiązujący ograniczenia. Możesz to zrobić z uogólnionym rodzajem propagacji ograniczeń w językach programowania logicznego. Mamy demo specjalnie dla problemu Zebry w systemie ALE (silnik logiki atrybutów):
http://www.cs.toronto.edu/~gpenn/ale.html
Oto link do kodowania uproszczonej układanki Zebra:
http://www.cs.toronto.edu/~gpenn/ale/files/grammars/baby.pl
Aby zrobić to skutecznie, to inna sprawa.
źródło
Najłatwiejszym sposobem programowego rozwiązania takich problemów jest użycie zagnieżdżonych pętli dla wszystkich permutacji i sprawdzenie, czy wynik spełnia predykaty w pytaniu. Wiele predykatów można przenieść z pętli wewnętrznej do pętli zewnętrznych, aby radykalnie zmniejszyć złożoność obliczeniową, aż odpowiedź będzie mogła zostać obliczona w rozsądnym czasie.
Oto proste rozwiązanie F # pochodzące z artykułu w F # Journal :
Wynik uzyskany w 9 ms to:
źródło
Przykład Microsoft Solver Foundation z: https://msdn.microsoft.com/en-us/library/ff525831%28v=vs.93%29.aspx?f=255&MSPPError=-2147217396
źródło
Oto rozwiązanie MiniZinc do układanki zebry, zgodnie z definicją w Wikipedii:
Rozwiązanie:
źródło