Riddle challenge

[Joanna from IRC]

Here is a riddle to solve for fun.

There are five houses.
The Englishman lives in the red house.
The Spaniard owns the dog.
Coffee is drunk in the green house.
The Ukrainian drinks tea.
The green house is immediately to the right of the ivory house.
The Old Gold smoker owns snails.
Kools are smoked in the yellow house.
Milk is drunk in the middle house.
The Norwegian lives in the first house.
The man who smokes Chesterfields lives in the house next to the man with the fox.
Kools are smoked in the house next to the house where the horse is kept.
The Lucky Strike smoker drinks orange juice.
The Japanese smokes Parliaments.
The Norwegian lives next to the blue house.

who drinks water? Who owns the zebra?

If you succeed in solving on your own, please explain how you solved it. 

[dbannon]

You sure there is a solution ?

Attached my attempt, Monte Carlo simulation, 10 Million runs and no successful candidate.  I may well have made a mistake, midnight here, I'll look in the morning.

Its seriously rough work, only started when the TV got boring. But you can see the idea. Generate a random model, test it, repeat....

Davo

[MarkMLl]

I've solved things like this in the past using Prolog, but right now can't afford the time to get "back into the mood".

However I don't believe that that is soluble as it stands, since there are at least two facts missing, which I suggest tentatively are "every houseowner drinks something" and "every houseowner owns an animal": without those the questions relating to "water" and "a zebra" are meaningless.

https://en.wikipedia.org/wiki/Zebra_Puzzle is relevant, and quotes the version of the puzzle given by Joanna as having the important rider

In the interest of clarity, it must be added that each of the five houses is painted a different color, and their inhabitants are of different national extractions, own different pets, drink different beverages and smoke different brands of American cigarets [sic]. One other thing: in statement 6, right means your right.

Updated: https://www.literateprograms.org/zebra_puzzle__prolog_.html

MarkMLl

[Joanna from IRC]

I tried to work out the solution on paper first starting with the easiest ones which are first 3 houses. Listing known characteristics about each one from the list.

I then got to the part  where there is an ivory color house to the left of the green house but I wasn’t sure if these were for house 3&4 or house 4&5 so I made two separate ones for both possibilities and continued adding by clues but then I got to another part where the clues could fit several different houses.

It’s like the number of possibilities branch as you get into the puzzle and you need to try all possible answers to find out which one is correct.

I solved the house colors , nationalities , beverages, cigarettes and didn’t quite solve the pets part. In general I think solving the clues with the most information first helps.

[440bx]

I've got half of it solved.  I know who drinks water.  That took about 10 minutes.  That was fairly easy.

The second half looks pretty tough... (who owns the zebra), spent about another 10 minutes on that and didn't figure it out yet (and don't have much time to dedicate to it in the next few days.)

@MarkMLI,

I thought of Prolog too.  It's the perfect kind of problem for Prolog's goal seeking engine.

[MarkMLl]

I thought of Prolog too.  It's the perfect kind of problem for Prolog's goal seeking engine.

Yes, but I've seen this type of puzzle equated to finding a path through a non-directed graph.

The important point is that techniques have been developed over the last 60 years or so (i.e. since that specific puzzle was posed) to solve logical and- in the more general case- constraints-based problems efficiently: something that humans aren't all that good at since the vast majority of us lack the focus to tackle the problem methodically without getting sidetracked.

MarkMLl

[Joanna from IRC]

440bx what methodology did you use to solve it?
It kind of reminds me of solving a sudoku puzzle...

[440bx]

440bx what methodology did you use to solve it?
It kind of reminds me of solving a sudoku puzzle...

It does feel somewhat similar to sudoku.

I made a 5x5 matrix and filled in the cells as I figured out what their value was based on the given constraints.  Currently I have slightly under 1/3 of the matrix filled (7 cells) which is enough to know who drinks water but, definitely not enough to figure out who owns the zebra.  I'm currently 18 cells short and I have a distinct feeling that many of the cells left require solving sets of constraints that involve relations among 4 or more constraints which is not very easy to visualize.

Figuring out who drinks water was rather easy compared to figuring out who owns the zebra.

[LV]

https://en.wikipedia.org/wiki/Zebra_Puzzle

Code: Pascal  [Select][+][-]

1. program project1;
2.  
3. uses
4.   crt;
5.  
6. type
7.   THouse = record
8.     Color: string;
9.     Nationality: string;
10.     Drink: string;
11.     Smoke: string;
12.     Pet: string;
13.   end;
14.  
15. const
16.   HouseCount = 5;
17.  
18. var
19.   Houses: array[1..HouseCount] of THouse;
20.   i: integer;
21.   WaterDrinker, ZebraOwner: string;
22.  
23. begin
24.   clrscr;
25.  
26.   { Manually assigning values based on logical deductions }
27.   Houses[1].Color := 'Yellow';
28.   Houses[1].Nationality := 'Norwegian';
29.   Houses[1].Drink := 'Water';
30.   Houses[1].Smoke := 'Kools';
31.   Houses[1].Pet := 'Fox';
32.   Houses[2].Color := 'Blue';
33.   Houses[2].Nationality := 'Ukrainian';
34.   Houses[2].Drink := 'Tea';
35.   Houses[2].Smoke := 'Parliaments';
36.   Houses[2].Pet := 'Horse';
37.   Houses[3].Color := 'Red';
38.   Houses[3].Nationality := 'Englishman';
39.   Houses[3].Drink := 'Milk';
40.   Houses[3].Smoke := 'Old Gold';
41.   Houses[3].Pet := 'Snails';
42.   Houses[4].Color := 'Ivory';
43.   Houses[4].Nationality := 'Spaniard';
44.   Houses[4].Drink := 'Orange Juice';
45.   Houses[4].Smoke := 'Chesterfields';
46.   Houses[4].Pet := '';
47.   Houses[5].Color := 'Green';
48.   Houses[5].Nationality := 'Japanese';
49.   Houses[5].Drink := 'Coffee';
50.   Houses[5].Smoke := 'Lucky Strike';
51.   Houses[5].Pet := 'Zebra';
52.  
53.   { Finding Water Drinker and Zebra Owner }
54.   for i := 1 to HouseCount do
55.   begin
56.     if Houses[i].Drink = 'Water' then
57.       WaterDrinker := Houses[i].Nationality;
58.     if Houses[i].Pet = 'Zebra' then
59.       ZebraOwner := Houses[i].Nationality;
60.   end;
61.  
62.   writeln('The person who drinks water is: ', WaterDrinker);
63.   writeln('The person who owns the zebra is: ', ZebraOwner);
64.  
65.   readln;
66. end.
67.  

[440bx]

But, the real solution is to figure out all the necessary inferences that lead to the solution matrix they present.

They give the half that's really easy (who drinks water.) They leave out all the inferences needed to fill the remaining 18 cells.

[LV]

If you use translate.google, you can read the solution at the link

https://ru.wikipedia.org/wiki/Загадка_Эйнштейна

[440bx]

If you use translate.google, you can read the solution at the link

https://ru.wikipedia.org/wiki/Загадка_Эйнштейна

Thank you for that but, first I want to try to figure out myself

[MathMan]

Thanks for that Joanna,

I went with human intelligence, Excell and manual backtracking. There were two decisions I had to make

- positioning the red house <= two choices
- positioning the Ukrainian <= two choices again

Took me around 30min to solve -  if I hadn't missed a slot in the second decision I made I would have been there after ~15min.

Anyway - one could also solve this via SAT solver - but setting up the equivalent boolean equations would probably have taken more time than the direct approach.

Cheers,
MathMan

[MathMan]

https://en.wikipedia.org/wiki/Zebra_Puzzle

...

There is an error in the initial assignments in the program - look at the Japanese sharply.

However - the deducted water drinker & zebra owner are correct.

[speter]

I worked out a solution; the Norwegian drinks water and the Japanese has the zebra.

I put the 'facts' into a grid (5x5 as MarkMLI did) and added all the other facts that were ambiguous. I then tried 6 permutations until I resolved the options into a single set of 'answers'.

Have a look at the attached spreadsheet, if you want to check out my process.
I haven't checked the webpage with the solution, so my "answer" could be wrong.

cheers
S.