The Einstein's puzzle or zebra puzzle is a well-known logic puzzle. Are there any very easy ways to solve it fast?
$\begingroup$
$\endgroup$
11
-
$\begingroup$ Do you mean to solve the symbolic version or the textual version? $\endgroup$– user20May 15, 2014 at 7:16
-
$\begingroup$ @Emracool: do the strategies for them differ? $\endgroup$– SF.May 15, 2014 at 7:24
-
$\begingroup$ Yes, slightly. The textual version requires laying out intuitive grids, while the symbolic version requires different methods of reduction. I can go into detail on both tomorrow. $\endgroup$– user20May 15, 2014 at 7:26
-
$\begingroup$ could someone give links with examples of the puzzles? (Yes, I can google them, but this kinda defeats the rationale for the group) $\endgroup$– mauMay 15, 2014 at 8:22
-
$\begingroup$ @mau I added links to Wikipedia and an example puzzle. $\endgroup$– TartoriMay 15, 2014 at 9:06
|
Show 6 more comments
4 Answers
$\begingroup$
$\endgroup$
3
The canonical Einstein's Puzzle can be solved using a grid of possibilities, and the easiest way to do so is to track each of the possible states.
Each letter in this grid stands for the associated entity:
- Nationality stands for Enlgishman, Swede, Dane, Norwegian, and German
- Colors (house color) stand for Blue, Green, Red, White, Yellow
- Animals stand for Bird, Cat, Dog, Fish, Horse
- Drinks stand for Bier, Coffee, Milk, Tea, Water
- Cigarette stands for Blend, Blue Master (M), Dunhill, Pall Mall, Prince (R)
We therefore have:
Natl. | ESDNG | ESDNG | ESDNG | ESDNG | ESDNG |
Color | BGRWY | BGRWY | BGRWY | BGRWY | BGRWY |
Animl | BCDFH | BCDFH | BCDFH | BCDFH | BCDFH |
Drink | BCMTW | BCMTW | BCMTW | BCMTW | BCMTW |
Cigar | BMDPR | BMDPR | BMDPR | BMDPR | BMDPR |
Thus, the clues help you immediately reduce the possibilities in this grid. I'll go through a couple steps to exemplify. I've pulled the rules from Stanford's page, and they look correct from memory.
(4) The green house is just to the left of the white one.
Therefore, because the green house must be to the left of a house, and the white house must be to the right of a house, we know that the green house cannot be on the right, and the white house cannot be on the left.
Natl. | ESDNG | ESDNG | ESDNG | ESDNG | ESDNG |
Color | BGR Y | BGRWY | BGRWY | BGRWY | B RWY |
Animl | BCDFH | BCDFH | BCDFH | BCDFH | BCDFH |
Drink | BCMTW | BCMTW | BCMTW | BCMTW | BCMTW |
Cigar | BMDPR | BMDPR | BMDPR | BMDPR | BMDPR |
(5) The owner of the green house drinks coffee.
We know that, since the fifth house cannot be green, its owner cannot drink coffee.
Natl. | ESDNG | ESDNG | ESDNG | ESDNG | ESDNG |
Color | BGR Y | BGRWY | BGRWY | BGRWY | B RWY |
Animl | BCDFH | BCDFH | BCDFH | BCDFH | BCDFH |
Drink | BCMTW | BCMTW | BCMTW | BCMTW | B MTW |
Cigar | BMDPR | BMDPR | BMDPR | BMDPR | BMDPR |
(8) The man in the center house drinks milk.
This one should be obvious.
Natl. | ESDNG | ESDNG | ESDNG | ESDNG | ESDNG |
Color | BGR Y | BGRWY | BGRWY | BGRWY | B RWY |
Animl | BCDFH | BCDFH | BCDFH | BCDFH | BCDFH |
Drink | BC TW | BC TW | M | BC TW | B TW |
Cigar | BMDPR | BMDPR | BMDPR | BMDPR | BMDPR |
(9) The Norwegian lives in the first house.
Once again, this is obvious.
Natl. | N | ESD G | ESD G | ESD G | ESD G |
Color | BGR Y | BGRWY | BGRWY | BGRWY | B RWY |
Animl | BCDFH | BCDFH | BCDFH | BCDFH | BCDFH |
Drink | BC TW | BC TW | M | BC TW | B TW |
Cigar | BMDPR | BMDPR | BMDPR | BMDPR | BMDPR |
(14) The Norwegian lives next to the blue house.
Since the Norwegian lives in house 1, we know that the blue house must be house 2, because that is the only house the Norwegian is next to.
Natl. | N | ESD G | ESD G | ESD G | ESD G |
Color | GR Y | B | GRWY | GRWY | RWY |
Animl | BCDFH | BCDFH | BCDFH | BCDFH | BCDFH |
Drink | BC TW | BC TW | M | BC TW | B TW |
Cigar | BMDPR | BMDPR | BMDPR | BMDPR | BMDPR |
It should be immediately obvious why this strategy works. You can both reduce clues away as well as insert solutions into this grid, which is vitally important. Without tracking where pieces can't be, you lose a significant amount of vital information.
-
$\begingroup$ This does not make it easy to capture all of the information in the statement that the owner of the green house drinks coffee, but does capture right/left information better than the grids I show. Different styles work with different types of clues. $\endgroup$ May 15, 2014 at 17:08
-
$\begingroup$ @Ross It actually does still capture that! If a house isn't green, or a house doesn't drink coffee, then that house can't drink coffee or be green respectively. It does indeed retain that information in the possibilities it holds, and the clues still operate on them like normal. $\endgroup$– user20May 15, 2014 at 17:11
-
$\begingroup$ @Ross Yes you do - you can actually eliminate these possibilities quite easily. For instance, since the green house is to the left of the white house, it must be to the left of a house, and therefore can't be all the way on the right. In this sense, you aren't reducing specifically where clues are, but primarily where they aren't, thus reducing the grid. $\endgroup$– user20May 15, 2014 at 17:14
$\begingroup$
$\endgroup$
For small puzzles of this type, a grid is very useful. If there are three types of item, with five of each type, you can use a grid like this. Put an x in all the squares you know cannot hold, and fill the boxes you know are true. So if you are told 1 is not a, you x the upper left box. If you are told B is 2 you fill the corresponding box, then x all the boxes in the same row and column. You can also copy x's from one grid to another when you fill a box. For four types, put types 1,2,3 across the top, 4,3,2 down the left and you will have six grids. It becomes unwieldy after five types
This is especially useful to see when you have eliminated all but one possibility. To capture the left/right information, one of your types of item can be the house number.
$\begingroup$
$\endgroup$
Just to finish the solving of this puzzle (which I am sure has been done elsewhere), you can see there are some non trivial spots, even when using the accepted strategy. I've put this in bold italics so they stand out. The rest is trivially going through the rules and applying them. However, without these key steps you will get to a stand still where further application of the rules leads no where.
This is the zebra version, but I believe they are equivalent.
Country: ESUNJ | ESUNJ | ESUNJ | ESUNJ | ESUNJ |
Color: RGIYB | RGIYB | RGIYB | RGIYB | RGIYB |
Pet: DSFHZ | DSFHZ | DSFHZ | DSFHZ | DSFHZ |
Drink: CTMOW | CTMOW | CTMOW | CTMOW | CTMOW |
Smokes: OKCLP | OKCLP | OKCLP | OKCLP | OKCLP |
9- Milk is drunk in the middle house.
10- The Norwegian lives in the first house.
15- The Norwegian lives next to the blue house.
Country: N | ESU J | ESU J | ESU J | ESU J |
Color: RGIY | B | RGIY | RGIY | RGIY |
Pet: DSFHZ | DSFHZ | DSFHZ | DSFHZ | DSFHZ |
Drink: CT OW | CT OW | M | CT OW | CT OW |
Smokes: OKCLP | OKCLP | OKCLP | OKCLP | OKCLP |
6- The green house is immediately to the right of the ivory house.
The 3rd and 4th are Ivory and Green or the 4th and 5th are. Thus, the first is neither and the 4th cannot be red.
2- The Englishman lives in the red house.
Country: N | SU J | ESU J | SU J | ESU J |
Color: Y | B | R I | GI | RG |
Pet: DSFHZ | DSFHZ | DSFHZ | DSFHZ | DSFHZ |
Drink: CT OW | CT OW | M | CT OW | CT OW |
Smokes: OKCLP | OKCLP | OKCLP | OKCLP | OKCLP |
8- Kools are smoked in the yellow house.
12- Kools are smoked in the house next to the house where the horse is kept.
Country: N | SU J | ESU J | SU J | ESU J |
Color: Y | B | R I | GI | RG |
Pet: DSF Z | H | DSF Z | DSF Z | DSF Z |
Drink: CT OW | CT OW | M | CT OW | CT OW |
Smokes: K | O CLP | O CLP | O CLP | O CLP |
4- Coffee is drunk in the green house.
5- The Ukrainian drinks tea.
13- The Lucky Strike smoker drinks orange juice.
Country: N | SU J | ES J | SU J | ESU J |
Color: Y | B | R I | GI | RG |
Pet: DSF Z | H | DSF Z | DSF Z | DSF Z |
Drink: W | T O | M | CT O | CT O |
Smokes: K | O CLP | O C P | O CLP | O CLP |
3- The Spaniard owns the dog.
7- The Old Gold smoker owns snails.
Country: N | U J | ES J | SU J | ESU J |
Color: Y | B | R I | GI | RG |
Pet: F Z | H | DSF Z | DSF Z | DSF Z |
Drink: W | T O | M | CT O | CT O |
Smokes: K | CLP | O C P | O CLP | O CLP |
If the 2nd house is Japanese and smokes parliaments(14), then he can't smoke Lucky Strikes, so he doesn't drink Orange Juice(13), leaving only Tea. But then he must be Ukrainian(5) - contradiction.
Country: N | U | ES J | S J | ES J |
Color: Y | B | R I | GI | RG |
Pet: F Z | H | DSF Z | DSF Z | DSF Z |
Drink: W | T | M | C O | C O |
Smokes: K | C | O P | O LP | O LP |
If the last house is the Englishman, then his house is red(2) so he doesn't drink coffee(4). This leaves orange juice, so he smokes Lucky Strikes(13). But then the 3rd and 4th houses are incompatible because if the Spaniard is in either, then he has the dog(3), and not the snails, thus does not smoke Old Gold(7), leaving only Parliaments, making him Japanese(14) - contradiction.
Country: N | U | E | S J | S J |
Color: Y | B | R I | GI | RG |
Pet: F Z | H | DSF Z | DSF Z | DSF Z |
Drink: W | T | M | C O | C O |
Smokes: K | C | O P | O LP | O LP |
2- The Englishman lives in the red house.
4- Coffee is drunk in the green house.
13- The Lucky Strike smoker drinks orange juice.
Country: N | U | E | S J | S J |
Color: Y | B | R | I | G |
Pet: F Z | H | DSF Z | DSF Z | DSF Z |
Drink: W | T | M | O | C |
Smokes: K | C | O P | L | O LP |
14- The Japanese smokes Parliaments.
7- The Old Gold smoker owns snails.
3- The Spaniard owns the dog.
Country: N | U | E | S | J |
Color: Y | B | R | I | G |
Pet: F Z | H | S | D | F Z |
Drink: W | T | M | O | C |
Smokes: K | C | O | L | P |
11- The man who smokes Chesterfields lives in the house next to the man with the fox.
Country: N | U | E | S | J |
Color: Y | B | R | I | G |
Pet: F | H | S | D | Z |
Drink: W | T | M | O | C |
Smokes: K | C | O | L | P |
$\begingroup$
$\endgroup$
This answer is more about choosing the puzzle than general strategies. Once you have the grid, a lot of reduction tactics are the same as with Sudoku.
Playing around with timed versions of the Einstein puzzle like this can soon net you shortcuts for solving the grid. Granted, you get everything laid out and can start solving immediately, but our brain is more suited to certain types of cues. Some solved squares may help, but it all depends on its position and the other cues. Particularly the "X is between A and B" hints can be very helpful, especially when they are chained or you can place them immediately. Since most hints are relative, you get several new anchor points to try out. Perhaps their higher apparent benefit is also due to the way we process information, as they usually clear the most amount of possibilities upon placement and the same amount (2) as is-before when uncertain, reducing the problem space. In general, if you can solve any of the near-central squares, that can reduce the positioning options of the triplets significantly.
During plays, I've noticed a particular pattern that I can solve fast (as opposed to 15+ minutes). All my best time (2 min) games started like this, but I don't know if the speed can be attributed to just the initial layout. It's when you start with a solved square one square from the border that can be expanded with an in-between cue. It's better than border squares, since you can then also discard some guesses via is-a-neighbour cues, but still gives only one possible orientation.
