--mARK

Einstein's Riddle

=================

Albert Einstein wrote this riddle. He was quoted as saying that he believed that 98% of the world could not solve it. Are you in the top 2% of intelligent people in the world? There is no trick - just pure logic.

1. There are 5 houses in a raw, each has a different color.

2. In each house lives a different person with a different nationality.

3. These 5 people drink a certain type of beverage, smoke a certain brand of cigar, and keep a certain pet.

4. No person has the same pet, smokes the same brand of cigar, or drinks the same beverage.

The question is, who owns the Fish? Good luck!

The Brit lives in the Red house.

The Swede has a Dog.

The Dane drinks Tea.

The Green house is on the Left of the White house.

The Green house's owner drinks Coffee.

The person who smokes PallMall has a Bird.

The owner of the Yellow house smokes Dunhill.

The man living in the Center house drinks Milk.

The Norwegian lives in the First house.

The man who smokes Blends lives next to the Cat owner.

The man who owns a Horse lives next to the one who smokes Dunhill.

The man who smokes BlueMaster drinks Beer.

The German smokes Prince.

The Norwegian lives next to the Blue house.

The man who smokes Blends has a neighbor who drinks Water.

Originally posted by Greg Harris:

the german has the fish... houses from left to right.

Norwegian - Yellow - Water - Dunhill - Cat Dane - Blue - Tea - Blends - Horse Brit - Red - Milk - PallMall - Bird German - Green - Coffee - Prince - Fish Swede - White - Beer - BlueMaster - Dog

I got the same thing. I'm not so sure this is a 98 percentile logic problem though. Now anyone want to try writing a program to solve it? After all this is

*Programming*Diversions.

*Any intelligent fool can make things bigger, more complex, and more violent. It takes a touch of genius - and a lot of courage - to move in the opposite direction.* - Ernst F. Schumacher

Originally posted by Greg Harris:

gosh... and i was starting to think that i was really smart.

We would probably both like to believe that. The only thing that makes this problem tougher than the garden variety logic problems in magazines is there are more items to keep up with and the twist on the proximity of the houses. For someone who hadn't solved 100s of these things over the years, it could be a sticky problem.

So Gregg, can you figure a generic way to solve this sort of problem programatically? I've been thinking of some sort of contrived data structure to do it but can't quite get a handle on it. At first you think booleans would handle it but you actually have tristate conditions: yes, no, maybe. You could probably create an object for each possible item with references to all the other items but that would seem inefficient.

*Any intelligent fool can make things bigger, more complex, and more violent. It takes a touch of genius - and a lot of courage - to move in the opposite direction.* - Ernst F. Schumacher

i was thinking of booleans like you said - maybe an adjacency matrix, but there are the pesky "maybe" situations you mentioned.

now i am thinking of using graph theory - but there are too many factors for a regular graph coloring.

the way i solved it manually was to figure out the houses first, and then fill in what i knew for certain. then, i put the men in five columns and filled in what i knew for certain about them. after that, the rest fell into place.

what?

Originally posted by Greg Harris:

hmmm... i am supposed to be working today... thanks, michael.

i was thinking of booleans like you said - maybe an adjacency matrix, but there are the pesky "maybe" situations you mentioned.

now i am thinking of using graph theory - but there are too many factors for a regular graph coloring.

the way i solved it manually was to figure out the houses first, and then fill in what i knew for certain. then, i put the men in five columns and filled in what i knew for certain about them. after that, the rest fell into place.

I created truth tables for all possibilities starting with Nationality at the columns, then houses at the columns and so on down. It follows a nice permutation : 4 row sets, 3 row sets, etc.

The house location I solved after filling in all the knowns. It just seems we could come up with something like a TruthTable class with TruthTableItems.

I doubt I could write a Lisp program now. More than a couple of parenthesis and my old brain starts self-destructing. I've never written in Prolog, so can't make a judgement there.

*Any intelligent fool can make things bigger, more complex, and more violent. It takes a touch of genius - and a lot of courage - to move in the opposite direction.* - Ernst F. Schumacher

Originally posted by Tim Allen:

I *really* would like to see this worked out as a Java program. I think the algorithm for how to do this would really teach all of us a new way of thinking about problem solving-- anyone?

I'm pretty sure it can be done. The trick is going to be the data structure. In essence what you have is C(n)(2) or n!/(2*(n-2)!) n X n arrays where n is the number of types, in the above case it could be 5 for: nationality, house color, pet, drink and smoke; or 6 if you add house proximity. Creating the arrays is no big deal, you would need some tristate value, you could use constants like 1, 0 and -1 to indicate yes, no, or maybe. The tough part is relating individual cells across the arrays. For example if we determine that the Brit lives in the Red house we would then set that cell to yes and every other cell in the same row and column to no, then we would need to check other arrays like the Nationality-Smokes array and if Brit is known to smoke Pall Mall then we would have to set Pall Mall to yes in the House-Smokes array.

Originally posted by Eugene Kononov:

This may be one of those problems that cannot be solved in polynomially bounded time. If you employ a brute search algorithm, it may take up to 1.45519E+25 iterations, if my calculations are right. Even if each iteration takes only 1 microsecond, it will take about 460 billion years to find a solution.

Are you sure? If the set of data is conclusive it would seem that it is possible. I wasn't considering a brute force attack on it. Maybe I'm not seeing something? It may have to be heuristic instead of deterministic. If you have to make too many inductions I can see where it could get out of hand. I think I've got a data structure worked out, I'll play around with it as time allows and see where I get.

Start with zero order rule application. Try each person drinking milk. As you apply all rules, you see that only the person in the center house can drink milk. The people in other locations are not. You've just set some state.

After you apply all zero order rules, you do first order rules. Copy the state and then "Suppose the German is in the center house...." (i.e. set nationality and location state to go with that asusmption) and apply the rules again. See if you get a conflict. If you do, you've just ruled out one more possibility.

I'm not sure if it makes sense to continue applying first order rules repeatedly (e.g. try them all a second time and third time, etc) until it no longer yields results. Then you move to second order rules. This makes 2 suppositions. If it yields a contradiction, you don't yet know which is false, you just know that both can't be true together.

I'm not quite sure what to do at this point. Maybe given two propositions which aren't true together, you vary one of those two and try the other 4 possibilities. If you can't show that proposition A3 can't work with B1, B2, B3, B4, or B5, then A1 can't be true.

I also think you'd need keep reapplying the base rules between the first order / second order rules, etc. You also need to to find a way to cross link state. That is, you need to recognize that if the Brit is in the red house, and the red house has the bird, then the Brit has a bird.

--Mark

**Are you sure? If the set of data is conclusive it would seem that it is possible.**

I don't have a formal proof, but I laid down the problem on paper and it is awefully simplar to those graphs problems, such as Hamiltonian Cycle and Traveling Salesmen, which are NP-complete. I'll do some search, maybe there is reference to this particular problem as an NP-complete, too.

Originally posted by Eugene Kononov:

Are you sure? If the set of data is conclusive it would seem that it is possible.

I don't have a formal proof, but I laid down the problem on paper and it is awefully simplar to those graphs problems, such as Hamiltonian Cycle and Traveling Salesmen, which are NP-complete. I'll do some search, maybe there is reference to this particular problem as an NP-complete, too.

I've got the data structure down. My next step is to add the knowns into it and then write a solve method. When I get to that point, it should become obvious if we have a Traveling Salesmen dillema.

**I've got the data structure down. My next step is to add the knowns into it and then write a solve method. When I get to that point, it should become obvious if we have a Traveling Salesmen dillema.**

Go on, man. I did some search and found that people have written programs in Lisp, Prolog, and C++ to solve this problem in a very short computational time (order of seconds). So my guess about NP-completeness was wrong. I intentionally do not list the references to the solutions here, but you can easily find them on the web. Of course, creating your own solution is much more fun.

Originally posted by Eugene Kononov:

I've got the data structure down. My next step is to add the knowns into it and then write a solve method. When I get to that point, it should become obvious if we have a Traveling Salesmen dillema.

Go on, man. I did some search and found that people have written programs in Lisp, Prolog, and C++ to solve this problem in a very short computational time (order of seconds). So my guess about NP-completeness was wrong. I intentionally do not list the references to the solutions here, but you can easily find them on the web. Of course, creating your own solution is much more fun.

Just like Elvis, I'll go out singin'

*"I did it my way"*. I won't peek yet. It'll be neat to compare solutions after the fact.

Originally posted by Mark Herschberg:

AAARRRRGGGG! That's Frankie's song! Not Elvis'!

--Mark

Gee Mark, I thought you were too young to know such things. OK, like Ol' Blue Eyes

*I did it my way*.

house12345

__________________________________________________________________________________________

coloryellow(20)blue(2)red(17)green(4)white(6)

personnorwegian(1)dane(13)brit(16)german(15)swede(23)

drinkwater(8)tea(12)milk(3)coffee(5)beer(10)

smokedunhill(21)blends(7)pall mall(18)prince(14)bluemaster(11)

petcat(9)horse(22)bird(19)fish(25)dog(24)

1. The norwegian lives in first house

2. The norwegian lives next to blue house

(so house 2 is blue)

3. The man living in the center house drinks milk

4. The green house is on the left of the white house

(it has to be house # 4 b/c house #3 has milk and house #2 is blue)

5. The green house owner drinks coffee

6. (The white house is # 5)

7. The man who smokes blends has a neighbor who drinks water

(it isn't house #5 or #3, so it's house #1)

8. House #1 drinks water

(If we assume the neighbor who drinks water is same neighbor as the cat owner, then)

9. The man who smokes blends lives next to the cat owner

10 The man who smokes bluemaster drinks beer

(we know it isn't house #2, b/c they smoke blends. so beer is house #5, everyone else

has a drink)

11 House #5 smokes bluemaster

12 Only one drink left now is: tea

13 The dane drinks tea

14 The german smokes prince, he might be in house #4

(the german isn't in house #2 or #5 b/c they already have their smokes, the brit lives in the red

house and the yellow house smokes dunhill, so the brit doesn't smoke dunhill which means he smokes pall mall and has a bird. the red and yellow houses are either house #1 or #3.)

15 House #4 is the german

16 The brit lives in the red house

(which is house #3. why? b/c we know he smokes pall mall -- he's not in house #5 -- and has a bird and lives in a red house and because the man who owns a horse lives next to the one who smokes

dunhill, and the owner of the yellow house smokes dunhill.)

17 House #3 is the red house

18 The person who smokes pall mall has a bird(19)

20 House #1 is the yellow house

21 The owner of the yellow house smokes dunhill

22 The man who owns a horse a horse lives next to the one who smokes dunhill

23 There is only one man left, the swede

24 The swede has a dog

25 The german owns the fish!

It's not formatted the same as in notepad, but...

Where can I get a book with more puzzles like this one?

[ July 11, 2003: Message edited by: leo donahue ]

Thanks, leo

The only conclusion regarding pets that can logically be drawn is that the German does not own a bird, cat, dog, or horse.

There is no rule specifying that a fish is owned by anyone.

I remember doing these as a kid and we used to have what lookedlike graph paper to solve them. The shape was somewhat like a triangle and you would have names written on both the side and the bottom. Where similiar names lined up would be grayed out. I think I'm remembering correctly. Maybe a data structure would resemble what I'm describing. You could elminate rows and columns that were adjacent, depending upon which information you knew for sure.

Not sure how good my explanation is, but c'est la vie!

If you really want to enjoy more puzzles, go here -

www.puzzledonkey.com

Be warned, the puzzles range from mindbending to in your face obvious. Enjoy!

Aaron R>

1. Enumerate all possible solutions. In each of the 5 house positions, there are 5 colors, 5 pets, 5 nationalities, 5 smokes, and 5 drinks. Each of these attributes can be arranged in 120 possible combinations (5!). Therefore the total number of combinations of attributes is 120^5 (because there are 5 attributes). I think this is just under 25 billion combinations. Then for each of these possbile solutions, test each of the rules until one (or more) are found satisfying all of the rules.

2. A less compute intensive solution is one of the ways we solve it manually. Create a 5x5 grid where the rows correspond to attributes, and the columns to house positions. In each cell write the 5 possible attribute values. Then repetitively apply the rules, striking out invalid attribute values until only one attribute value appears in each cell. For this puzzle, the first rule applied would be rule 8. You can strike Milk from columns 1, 2, 4, and 5, and all drinks but Milk from column 3. Rule 9 can be applied in the same fashion. Rule 14 can be applied as a result of applying rule 9. When we repeat the list of rules, Rule 1 can be used to eliminate Red from column 1 (given that Rule 9 removed Brit from column 1). After a bit of repetition, the correct answer emerges.

It seems possible that solution #2 could fail if there were multiple soutions, but in this case it works just fine.

A program to implement solution #2 would need to utilize several different algorithms for the different kind of rules:

1. Direct associations where the house # of some particular attribute value can be directly determined

2. Indirect associations where invalid attribute values can be stricken based on remaining possible attribute values.

3. Logic to deal with the "next to" or "left of" rules.

4. Finally a generic "process of elimination" algorithm can be applied after each rule is processed. If only a single attribute value remains in a cell, it can be safely removed as a possiblity from all other cells.

[ June 11, 2004: Message edited by: Bob Shiels ]

[ June 11, 2004: Message edited by: Bob Shiels ]

If Bob would act as a leader, and divide his solution into the required classes. Then ask for volunteers to plan, write and test each puzzle part. We could build the solution as an open source project. Anyone game?

-------------------------------------------------

On second thought (after reading this article on hacking) , I see that no one person should lead an open source project. I should not be a "back seat coder" I should have said Bob's ideas were worth following and asked, "What can I do to help start a project like this?"

[ June 20, 2004: Message edited by: Sonny Pondrom ]

Mark Herschberg wrote:It strikes me that this type of problem is ideal for a rule based language like Lisp or Prolog.

--Mark

You are spot on. This type of logic problem lends itself perfectly to a rule engine like Jess (see http://www.developer.com/java/other/article.php/3089641/Jess-Meets-Einsteinrsquos-Riddle.htm) .

Michael Morris wrote:

So Gregg, can you figure a generic way to solve this sort of problem programatically? I've been thinking of some sort of contrived data structure to do it but can't quite get a handle on it. At first you think booleans would handle it but you actually have tristate conditions: yes, no, maybe. You could probably create an object for each possible item with references to all the other items but that would seem inefficient.

We studied this in high-school as a classic back-tracking problem ...so I guess, generically you could use back-tracking to solve this kind of problems. As form of organisation for this one, I used a 2x2 table, with nations / characteristics and nulled the missing info or completed the solved cells. Don't know how to implement this generic, but in this case, gives you a very good overview about your standing.

It is sorta covered in the JavaRanch Style Guide. |