Zagadka Einsteina

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacji, wyszukiwania

Zagadka Einsteinazagadka znana w kilku różnych wersjach, której autorstwo tradycja przypisuje Albertowi Einsteinowi. Miał on powiedzieć, że jest w stanie ją rozwiązać w pamięci jedynie 2% populacji świata[1][2][3][4]. Czasami uważa się za jej twórcę Lewisa Carolla[5].

Jedno z możliwych sformułowań[edytuj | edytuj kod]

5 ludzi różnych narodowości zamieszkuje 5 domów w 5 różnych kolorach. Wszyscy palą papierosy 5 różnych marek i piją 5 różnych napojów. Hodują zwierzęta 5 różnych gatunków. Który z nich hoduje rybki?

  1. Norweg zamieszkuje pierwszy dom
  2. Anglik mieszka w czerwonym domu.
  3. Zielony dom znajduje się bezpośrednio po lewej stronie domu białego.
  4. Duńczyk pija herbatkę.
  5. Palacz papierosów light mieszka obok hodowcy kotów.
  6. Mieszkaniec żółtego domu pali cygara.
  7. Niemiec pali fajkę.
  8. Mieszkaniec środkowego domu pija mleko.
  9. Palacz papierosów light ma sąsiada, który pija wodę.
  10. Palacz papierosów bez filtra hoduje ptaki.
  11. Szwed hoduje psy.
  12. Norweg mieszka obok niebieskiego domu.
  13. Hodowca koni mieszka obok żółtego domu.
  14. Palacz mentolowych pija piwo.
  15. W zielonym domu pija się kawę.

Zakłada się, że domy ustawione są w jednej linii (1-2-3-4-5), a określenie "po lewej stronie" w punkcie 3. dotyczy lewej strony z perspektywy naprzeciw tych domów (tj. dom o numerze n jest bezpośrednio po lewej stronie domu n+1).

Rozwiązanie zagadki[edytuj | edytuj kod]

Wszystkie pewne fakty: W pierwszym domu mieszka Norweg (1), drugi dom jest niebieski (12), w trzecim domu pija się mleko (8).

Zielony dom znajduje się po lewej stronie domu białego (3), a więc na pewno nie są to domy 1. i 2., ponieważ drugi jest niebieski. Mogą to być domy 3. i 4., lub 4. i 5. W zielonym domu pija się kawę (15), a więc jest to dom 4. lub 5. (w domu 3. pija się mleko). Jednak gdyby był to dom 5., to nie miałby żadnego domu po prawej stronie, a musi mieć biały dom (3). Więc dom 4. jest zielony, a 5. biały.

Anglik mieszka w czerwonym domu (2), więc pozostaje mu tylko dom środkowy.

4 domy mają już przyporządkowane kolory, pozostał tylko pierwszy, więc wiemy że jest on żółty, a jego mieszkaniec pali cygara (6). Skoro Norweg mieszka w żółtym, to jego sąsiad z niebieskiego domu, hoduje konie (13).

Co pije Norweg? Na pewno nie mleko, ani nie kawę, ponieważ te są już pite w innych domach. Na pewno nie herbatę, ponieważ ją pije Duńczyk (4). Na pewno nie piwo, ponieważ je pije palacz mentolowych (14), a Norweg pali cygara. Podsumowując, Norweg pije wodę, a co za tym idzie, jego sąsiad, pali papierosy light (9).

Kto może palić mentolowe i pić piwo? Norweg nie może, bo pije wodę i pali cygara. Jego sąsiad nie może, bo pali papierosy light. Anglik nie może, bo pija mleko. W czwartym domu pija się kawę, a więc piwo i mentolowe przypadają do ostatniego domu.

Według punktu (7), Niemiec pali fajkę, a my nie wiemy jakie papierosy pali się w domu 3. i 4. W domu 3. nie może mieszkać palacz fajki, ponieważ mieszka tam Anglik, więc w domu 4. mieszka Niemiec i pali fajkę. Anglik natomiast pali papierosy bez filtra (tylko to zostało), a co za tym idzie hoduje też ptaki (10).

Skoro palacz papierosów light (drugi dom), mieszka obok hodowcy kotów, to tym hodowcą jest Norweg (drugi sąsiad to Anglik, ale on hoduje ptaki).

Pozostaje jeden napój do rozdzielenia – herbata, więc pije ją mieszkaniec domu 2., a co za tym idzie jest on Duńczykiem (4).

Pozostała tylko jedna informacja (11). Zatem w ostatnim domu musi mieszkać Szwed, hodujący psy (tylko ten dom nie ma określonego mieszkańca).

Wiadomo już co hodują wszyscy, oprócz Niemca – zatem to on hoduje rybki. Jedyne możliwe rozwiązanie:

pierwszy dom drugi dom trzeci dom czwarty dom piąty dom
Norweg Duńczyk Anglik Niemiec Szwed
żółty niebieski czerwony zielony biały
woda herbata mleko kawa piwo
cygara papierosy light papierosy bez filtra fajka papierosy mentolowe
koty konie ptaki rybki psy

Algorytmizacja rozwiązywania[edytuj | edytuj kod]

Zagadka Einsteina jest dobrze określonym zagadnieniem programistycznym: jej rozwiązanie można znaleźć używając komputera i odpowiedniego algorytmu, zaimplementowanego w wybranym języku programowania. Rozwiązanie zagadki za pomocą komputera wiąże się z dwoma rodzajami trudności.

Po pierwsze, reprezentacja występujących w zagadce obiektów (takich jak Norweg, papierosy light, psy) i relacji pomiędzy nimi (takich jak mieszka na lewo od) wymaga stworzenia adekwatnej do rozwiązywanego problemu struktury danych.

Po drugie, samo stworzenie efektywnego algorytmu rozwiązującego zagadkę nie jest zadaniem łatwym. Najprostszy w implementacji jest tu algorytm klasy brute force, polegający na generowaniu wszystkich możliwych permutacji danych (innymi słowy, wszystkich możliwych wersji tabelki takiej, jak wyżej przedstawiona) i sprawdzaniu piętnastu warunków podanych w zagadce. Liczba kombinacji, które należy sprawdzić, jest jednak dość duża i przy użyciu typowego komputera osobistego z początków XXI wieku może wymagać wielotygodniowych obliczeń. Tabelkę zawierającą 5 rzędów (narodowość mieszkańca, kolor domu, preferowany napój, rodzaj papierosów, hodowane zwierzęta) i 5 kolumn (związanych z pięcioma domami) możemy bowiem wypełnić na 5!\,^5\,=\,(1\cdot 2\cdot 3\cdot 4\cdot 5)\,^5 \,=\, 120\,^5 \,=\, 24\,883\,200\,000 sposobów.

Znaczącą redukcję ilości porównań można uzyskać poprzez generowanie i testowanie jedynie takich permutacji, które spełniają kilka oczywistych kryteriów wstępnych, np. niebranie pod uwagę permutacji w których Norweg mieszka w domu innym niż pierwszy, itp. Umiejętna konstrukcja algorytmu pozwala na osiągnięcie czasu rozwiązywania zagadki na komputerze klasy pentium III rzędu kilku setnych sekundy; programy rozwiązujące zagadkę napisano m.in. w językach Lisp[6], C++[7][8], Python[9].

Implementacja programu rozwiązującego zagadkę jest szczególnie łatwa w językach programowania logicznego, takich jak Prolog.

Przypisy