File APIs for Java Developers
Manipulate DOC, XLS, PPT, PDF and many others from your application.
http://aspose.com/file-tools
The moose likes Programming Diversions and the fly likes Einstein's riddle Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login


Win a copy of Murach's Java Servlets and JSP this week in the Servlets forum!
JavaRanch » Java Forums » Other » Programming Diversions
Bookmark "Einstein Watch "Einstein New topic
Author

Einstein's riddle

Mark Herschberg
Sheriff

Joined: Dec 04, 2000
Posts: 6037
This was sent to a mailing list I'm on. I have no idea if Einstein invented it, or even if there is a solution (i.e. I haven't confirmed that it is a solveable problem).
--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.
Greg Harris
Ranch Hand

Joined: Apr 12, 2001
Posts: 1012
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


  • what?
    Anupam Sinha
    Ranch Hand

    Joined: Apr 13, 2003
    Posts: 1088
    I think the fish is with the German.
    Anupam Sinha
    Ranch Hand

    Joined: Apr 13, 2003
    Posts: 1088
    Was pretty much engrossed in solving the puzzle that I didn't realize that Greg had already posted the result.
    Michael Morris
    Ranch Hand

    Joined: Jan 30, 2002
    Posts: 3451
    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
    Greg Harris
    Ranch Hand

    Joined: Apr 12, 2001
    Posts: 1012
    Originally posted by Michael Morris:

    ... I'm not so sure this is a 98 percentile logic problem though...

    gosh... and i was starting to think that i was really smart.
    Michael Morris
    Ranch Hand

    Joined: Jan 30, 2002
    Posts: 3451
    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.
    Mark Herschberg
    Sheriff

    Joined: Dec 04, 2000
    Posts: 6037
    It strikes me that this type of problem is ideal for a rule based language like Lisp or Prolog.
    --Mark
    Greg Harris
    Ranch Hand

    Joined: Apr 12, 2001
    Posts: 1012
    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.
    Michael Morris
    Ranch Hand

    Joined: Jan 30, 2002
    Posts: 3451
    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.
    Arjun Shastry
    Ranch Hand

    Joined: Mar 13, 2003
    Posts: 1874
    I also got the answer!This is similar to Analytical section of older GRE problem but somewhat tougher.


    MH
    Bhushan Jawle
    Ranch Hand

    Joined: Nov 22, 2001
    Posts: 249
    That was really thought provoking one
    Timothy Chen Allen
    Ranch Hand

    Joined: Mar 16, 2003
    Posts: 161
    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?


    Timothy Chen Allen
    Learn Spanish in Washington, DC
    Michael Morris
    Ranch Hand

    Joined: Jan 30, 2002
    Posts: 3451
    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.
    John Smith
    Ranch Hand

    Joined: Oct 08, 2001
    Posts: 2937
    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.
    Michael Morris
    Ranch Hand

    Joined: Jan 30, 2002
    Posts: 3451
    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.
    Mark Herschberg
    Sheriff

    Joined: Dec 04, 2000
    Posts: 6037
    I would imagine something like the following. You define state: people's location, pet, etc. You then try possible solutions to the zero order, first order, second order, etc...
    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
    John Smith
    Ranch Hand

    Joined: Oct 08, 2001
    Posts: 2937
    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.
    Michael Morris
    Ranch Hand

    Joined: Jan 30, 2002
    Posts: 3451
    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.
    John Smith
    Ranch Hand

    Joined: Oct 08, 2001
    Posts: 2937
    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.
    Michael Morris
    Ranch Hand

    Joined: Jan 30, 2002
    Posts: 3451
    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.
    Mark Herschberg
    Sheriff

    Joined: Dec 04, 2000
    Posts: 6037
    Originally posted by Michael Morris:

    Just like Elvis, I'll go out singin' "I did it my way".

    AAARRRRGGGG! That's Frankie's song! Not Elvis'!
    --Mark
    Michael Morris
    Ranch Hand

    Joined: Jan 30, 2002
    Posts: 3451
    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.
    leo donahue
    Ranch Hand

    Joined: Apr 17, 2003
    Posts: 327
    Here is what I got:
    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
    Michael Morris
    Ranch Hand

    Joined: Jan 30, 2002
    Posts: 3451
    The Dell Book of Logic Problems #2 should give you some pretty good practice. There are myraiads of magazines at your local book store that have these things too.
    Timothy Chen Allen
    Ranch Hand

    Joined: Mar 16, 2003
    Posts: 161
    Originally posted by Mark Herschberg:

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

    Wait, I thought "Frankie say Relax"...
    Bob Shiels
    Greenhorn

    Joined: May 31, 2004
    Posts: 3
    Considering that this is a logic riddle, it amazes me that there is one detail that everyone has overlooked...

    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.
    Aaron Roberts
    Ranch Hand

    Joined: Sep 10, 2002
    Posts: 174
    You are probably the 2%

    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>
    Bob Shiels
    Greenhorn

    Joined: May 31, 2004
    Posts: 3
    If you actually want to solve this programmatically (and assume that a fish is the fifth pet), there are two approaches I can think of.

    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 ]
    Sonny Pondrom
    Ranch Hand

    Joined: Jun 05, 2001
    Posts: 128
    You know what would be neat.
    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 ]
    Carlos Devoto
    Greenhorn

    Joined: Sep 07, 2011
    Posts: 1
    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) .
    Daniel Doboseru
    Ranch Hand

    Joined: Sep 26, 2011
    Posts: 57
    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.
     
    I agree. Here's the link: http://aspose.com/file-tools
     
    subject: Einstein's riddle
     
    Similar Threads
    Riddle
    Who have the fish?
    Big Smokes Domain Model
    22 Nov Riddle
    Hat Riddle: Require Java Algorithm