кто же разводит рыбок?

[avva]

Увидел в очередной раз так называемую "загадку Эйнштейна" в записи quantum_angel и решил на этот раз её решить. Долго думал, но никак не получалось увидеть форсированный путь к решению. Удивился. Написал программку, чтобы умно перебрала и нашла все решения, и что же оказалось? Что есть четыре разных решения, в трёх из которых рыбок разводит англичанин, а в одной - датчанин. Вот они:
1.
В первом, зелёном, доме живёт норвежец, пьёт кофе, курит Pall Mall, разводит птиц.
Во втором, жёлтом, доме живёт датчанин, пьёт чай, курит Dunhill, разводит кошек.
В третьем, красном, доме живёт англичанин, пьёт молоко, курит Rothmans, разводит рыбок.
В четвёртом, синем, доме живёт немец, пьёт воду, курит Marlboro, разводит лошадей.
В пятом, белом, доме живёт швед, пьёт пиво, курит Phillip Morris, разводит собак.

2.
В первом, синем, доме живёт норвежец, пьёт пиво, курит Phillip Morris, разводит лошадей.
Во втором, жёлтом, доме живёт датчанин, пьёт чай, курит Dunhill, разводит рыбок.
В третьем, красном, доме живёт англичанин, пьёт молоко, курит Pall Mall, разводит птиц.
В четвёртом, зелёном, доме живёт швед, пьёт кофе, курит Rothmans, разводит собак.
В пятом, белом, доме живёт немец, пьёт воду, курит Marlboro, разводит кошек.


3.
В первом, синем, доме живёт норвежец, пьёт пиво, курит Phillip Morris, разводит лошадей.
Во втором, жёлтом, доме живёт швед, пьёт воду, курит Dunhill, разводит собак.
В третьем, красном, доме живёт англичанин, пьёт молоко, курит Rothmans, разводит рыбок.
В четвёртом, зелёном, доме живёт немец, пьёт кофе, курит Marlboro, разводит кошек.
В пятом, белом, доме живёт датчанин, пьёт чай, курит Pall Mall, разводит птиц.


4.
В первом, зелёном, доме живёт норвежец, пьёт кофе, курит Pall Mall, разводит птиц.
Во втором, жёлтом, доме живёт датчанин, пьёт чай, курит Dunhill, разводит кошек.
В третьем, белом, доме живёт швед, пьёт молоко, курит Rothmans, разводит собак.
В четвёртом, синем, доме живёт немец, пьёт воду, курит Marlboro, разводит лошадей.
В пятом, красном, доме живёт англичанин, пьёт пиво, курит Phillip Morris, разводит рыбок.


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

Ну хорошо. Решил взять какое-нибудь условие по-английски и посмотреть, что будет там. Взял условие с этой страницы. Правила номер 12 и 13 там другие, а остальные идентичные (кроме названий двух марок сигарет, что ничего не меняет в данном случае). Запустил. Получилось уже семь решений, рыбок в которых попеременно разводят датчанин, норвежец и немец. На той странице ответ только один - немец, но он является только одним из семи возможных.

Наконец, нашёл ещё одну страницу с подробным объяснением решения. Условие (по-английски) на ней такое же, как на предыдущей, только опять изменены немного марки сигарет (какая-то странная обсессия на марках сигарет, ей-богу). Но чтение решения наконец всё прояснило: в условии номер 3 (в русской нумерации как у quantum_angel; на английской странице это условие номер 4) имеется в виду, что зелёный дом стоит слева от белого дома, рядом с ним; я же понял русское условие "Зеленый дом находится левее белого" как то, что он находится по левую руку, но необязательно рядом. Если бы я сразу читал английский вариант с его "on the left", то понял бы правильно. Опять проблема перевода!

Запустив заново программу с правильным условием, я действительно получил единственный ответ. Но русский набор правил, как у quantum_angel, не даёт единственного ответа даже если исправить условие номер 3: всё равно выходят два решения с англичанином и датчанином. Необходимо исправить условия 12 и 13 по образцу соответствующих английских, и тогда всё становится на свои места. Вот исправленное условие по-русски, и единственное подходящее к нему решение:

1. Норвежец живет в первом доме.
2. Англичанин живет в красном доме.
3. Зеленый дом находится по левую руку от белого, рядом с ним.
4. Датчанин пьёт чай.
5. Тот, кто курит Rothmans, живет рядом с тем, кто выращивает кошек.
6. Тот, кто живет в желтом доме, курит Dunhill.
7. Немец курит Marlboro.
8. Тот кто живет в центре, пьёт молоко.
9. Сосед того, кто курит Rothmans, пьёт воду.
10. Тот, кто курит Pall Mall, выращивает птиц.
11. Швед выращивает собак.
12. Норвежец живет рядом с синим домом.
13. Тот, кто выращивает лошадей, живет рядом с тем, кто курит Dunhill.
14. Тот, кто курит Philip Morris, пьёт пиво.
15. В зеленом доме пьют кофе.

Решение:

В первом, жёлтом, доме живёт норвежец, пьёт воду, курит Dunhill, разводит кошек.
Во втором, синем, доме живёт датчанин, пьёт чай, курит Rothmans, разводит лошадей.
В третьем, красном, доме живёт англичанин, пьёт молоко, курит Pall Mall, разводит птиц.
В четвёртом, зелёном, доме живёт немец, пьёт кофе, курит Marlboro, разводит рыбок.
В пятом, белом, доме живёт швед, пьёт пиво, курит Phillip Morris, разводит собак.

Откуда взялась неправильная русская версия? Не знаю. Сетевым поиском находятся две страницы (1, 2) с неправильным текстом и несколько с правильным, например здесь, где также обсуждают вопрос о двусмысленности условия.

По сути дела эта задачка является одной из таких задач, которые забавно прочесть, но редко кто собственно решает. Поэтому искажённое условие в принципе может путешествовать по сети, переходить из языка в язык и т.п. - то, что оно неверное, оказывается не таким уж важным фактом. Забавно.

Comments

[ex-ilyavinar899.livejournal.com]

С помощью DPLL такое можно решить.

не так уж много свободного времени, но

[rydel23.livejournal.com]

Я её несколько месяцев назад впервые увидел. Убил около 20 минут. Сначала решил неправильно (ушло минут 10), потом сел внимательно все расписал и получился немец. :)

[ex-ilyavinar899.livejournal.com]

Алексей, посмотрите на алгоритмы решения задачи SATISFIABILITY: DPLL и GSAT.

http://www.cs.duke.edu/~mlittman/topics/sat.html

[ex-ilyavinar899.livejournal.com]

http://www.cs.cornell.edu/home/selman/

Re:

[avva.livejournal.com]

Мне немного стыдно -- наверняка можно было написать в десять раз быстрее и удобнее. Так что учтите, что это quick'n'dirty, просто чтобы за пару минут избавиться от этой проблемы.

Числа 0..24 кодируют все 25 возможных свойств. Функция recurse последовательно строит последовательность выбора, которая является списком домов для первых N свойств. Члены последовательности - числа от 1 до 5, номера домов слева направо. Функция choice возвращает 1, если выбранные до сих пор свойства не нарушают поставленных условий. Т.к. она вызывается на каждом шаге рекурсии, подавляющее большинство неверных вариантов отрубаются близко к началу и поэтому дерево перебора получается небольшим. Первое длинное условие в функции choice проверяет, что каждые 5 свойств действительно попадают в 5 разных домов. Комментами #1, #2 и т.д. пронумерованы условия задачи, причём 3, 12 и 13 исправлены на верные.

sub different {
    my ($v1, $v2, $v3, $v4, $v5) = @_;
    return 1 unless $v1 && $v2 && $v3 && $v4 && $v5;
    return 0 if $v1==$v2 || $v1==$v3 || $v1==$v4 || $v1==$v5 || $v2==$v3 ||
        $v2==$v4 || $v2==$v5 || $v3==$v4 || $v3==$v5 || $v4==$v5;
    return 1;
}

sub eq2 {
    my ($v1, $v2) = @_;
    return 1 unless $v1 && $v2 && $v1!=$v2;
    return 0;
}

sub near {
    my ($v1, $v2) = @_;
    return 1 unless $v1 && $v2;
    return 1 if ($v1-$v2==1) || ($v2-$v1==1);
    return 0;
}

sub correct {
    my $choice=shift;
    my @list = @$choice;

    return 0 unless different(@list[0..4]) && different(@list[5..9]) &&
            different(@list[10..14]) && different(@list[15..19]) && 
            different(@list[20..24]);

#1
    return 0 unless eq2($list[0], 1);
#2
    return 0 unless eq2($list[1], $list[5]);
#3
#    return 0 if $list[6] && $list[7] && $list[6]>$list[7];
    return 0 if $list[6] && $list[7] && $list[7]-$list[6]!=1;
#4
    return 0 unless eq2($list[2], $list[10]);
#5
    return 0 unless near($list[15], $list[20]);
#6
    return 0 unless eq2($list[8], $list[16]);    
#7
    return 0 unless eq2($list[3], $list[17]);
#8 
    return 0 unless eq2($list[11], 3);
#9
    return 0 unless near($list[15], $list[12]);
#10
    return 0 unless eq2($list[18], $list[21]);
#11
    return 0 unless eq2($list[22], $list[4]);
#12
#    return 0 unless near($list[0], $list[8]);
    return 0 unless near($list[0], $list[9]);
#13
#    return 0 unless eq2($list[23], $list[9]);
    return 0 unless near($list[23], $list[16]);
#14
    return 0 unless eq2($list[19], $list[13]);
#15
    return 0 unless eq2($list[6], $list[14]);

    return 1;
}

my $tries = 0;

sub recurse {
    my $choice = shift;

    $tries++;
    if ($tries % 100 == 0) { print "$tries " };
    if (scalar(@$choice)==25) { 
        print "reached 25:\n"; 
        foreach my $num (1..5) {
            print("$num : ");
            foreach(0..scalar(@$choice)-1) { print "$_ " if $$choice[$_]==$num; }
            print "  ";
        }; 
        print "\n";
        return;
    }
    foreach(1..5) {
        push @$choice, $_;
        if(correct($choice)) {
            recurse($choice);
        }
        pop @$choice;
    }
    return;
}

recurse(\());

[pingva.livejournal.com]

пару недель назад выписал условия и сидя у океана, пока жена каталась на роликах, решал. Рвал подписанные бумажки, и раскладывал их на скамейке, прижимая камушками. Ветер бумажки из под камешков вырывал, но не смог меня остановить :) У меня получалось однозначно что немец.

[jama-dharma.livejournal.com]

Для решения задачи с правильными условиями потребовалось 15 минут, ручка и бумага. По-моему, компьютер для решения подобной задачи совершенно не требуется, так как задача решается не перебором, а анализом и сопоставлением данных. Мне в ходе решения пришлось прибегнуть к вероятностному методу только один раз, причем вероятность првильного выбора была 1/2. Думаю, что задачу можно решить и совсем строго. Можно посмотреть программку, которая "умно перебирает решения"?

Re:

[avva.livejournal.com]

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

[vvagr.livejournal.com]

А вот и генератор этих загадок. Любимая игра моей жены.

http://www.kaser.com/sherwin.html

[boma.livejournal.com]

Вы не поверите, папаша, но Розочка тоже умерла:-)
Мне попались правильные (русские) условия, но тоже с идиотстким "слева" без "рядом". К счастью, была приписка, что ответ единственный и система условий полная, поэтому 10 минут ушло на решение вопроса "думать самой или писать программку", еще 5 -- на определение, где находится "слева", ну и 20 -- на собственно решение.
btw, к созреванию Вашего мнения о фильме Рене, я тоже успею посмотреть еще раз:-)

[yolka.livejournal.com]

Я решила безо всякой программки, минут за двадцать, что называется, графически- просто нарисовала всё. При этом не знала ничего про Энштейна, а загадку прочитала здесь:
http://www.livejournal.com/talkread.bml?journal=vries&itemid=1806

[ella-p.livejournal.com]

А не расскажете ли, чем знаменита эта задачка, и при чем тут Энштейн?

Re:

[avva.livejournal.com]

Эйнштейн ни при чём, это как минимум известно. Просто задача приписывается ему, но это не так.

Эйнштейн ведь - символ "учёности" 20-го века.

А задача знаменита - ну не знаю чем, просто самая известная из логических задач такого рода.

[talash.livejournal.com]

Back in the 11th grade we were given this problem by our Artificial Intelligence teacher so she could show us how Prolog is capable of handling logical problems that are not easily solved by humans. She read if off a book (מבוא לבינה מלאכותית/ברוריה הברמן, מהדורה ניסוית, הוצאת מכון ויצמן-- Introduction to Artificial Intelligence/Bruria Haberman, Experimental edition, Weizmann Institute Press) and the animals, nationalities and house colours slightly varied, but it was essentially the same problem. So, everybody wrote it down from her dictation and then went home and attempted to solve it and I did too. So, I started trying to solve it and it was even worse than what you describe here, because in the end I reached a paradox. So I went over it about 5 times (manually, since we were specifically asked not to write programs on this stage) and found that yeah, there indeed was a paradox, wherefore I opened up the book (page 14, if I remember correctly-- unfortunately I no longer have it), found out the statement she misread and solved it all in about 10 minutes.

So, on the next lesson I came with the solution and found that:

1. I was the only one to come up with the correct solution, since I was the only one who bothered to look in the book.
2. 30% didn't solve the problem at all.
3. 70% came up with one of the two solutions, each of which, given the original statements the teacher had supplied, led to a paradox and neither of which was the correct one.

4. half of the students were bugging the teacher on every opportunity on the days between the lessons because they found the paradox and suspected she made an error reading one or more of the statements.
5. the teacher did not allow herself be bugged and repeatedly stated that all statements were correct and that she doesn't have the time for the students.
6. When the students found out that she had indeed misread one of the statements, they started screaming on the teacher and the teacher started screaming back at them, then asked me how I reached the correct solution, to which I honestly replied that I looked at the problem in the book and she used it as an argument against all the others-- that they should have looked it up in the book and that's the end of the story.
7. Half of the students continued to scream at her even after that, while the other half ran a game of Doom on the network.
8. The teacher noticed some of the students were playing Doom on the network, banged on the table and turned all computers off with the central switch. Thereafter, she turned it on and proceeded to explain how to write the program which solves the problem in Prolog.

yeah... school was a crazy thing and i'm glad i'm not there... anyway, i ran into many versions of this problem since then, and there are no difficulties if there are no typos or things like that-- it's just a matter of how well you draw the diagram. not something more than half an hour should be dedicated to.

[gianthare.livejournal.com]

Я вот тоже подумал, что на Прологе - раз плюнуть. Поплевал минут десять и плюнул совсем. Что-то я никак не могу взглянуть под нужным углом: где данные, а где конечная цель.

[yurkennis.livejournal.com]

здесь проплывала ещё пара ссылок и ещё одна история решения:
http://www.livejournal.com/talkread.bml?journal=yurkennis&itemid=59272

Re:

[avva.livejournal.com]

Спасибо!

[nezhit.livejournal.com]

у меня тоже случились непонятки с условиями :)))
http://www.livejournal.com/talkpost.bml?journal=nezhit&itemid=185426
но в итоге - тоже немец :)

Re:

[avva.livejournal.com]

Короче, неправильные условия - это ужас просто ;)

[nezhit.livejournal.com]

:) не то слово.
кстати leggie тоже решала с неправильными условиями, тоже получила несколько вариантов...
но программный подход конечно рулит, авва вы молодец :)