Einstein's Riddle

Here’s a sucky program I wrote to solve Einstein’s Riddle, which has nothing to do with Einstein. It is many, many times slower than other much better solutions.

Perhaps 'sucky' is a bit harsh. In its favor I believe it to be correct: it cycles through all 24,883,200,000 (= 5^5 x 4^5 x 3^5 x 2^5 x 1^5) possible solutions and finds the one and only combination that satisfies all the requirements. It is also a straight-forward representation of the stated riddle, and was therefore quick to write. On the downside, it does take 10 minutes to find the solution, which does not compare well with the solutions referred to above.

// Anthony C. Hay - Find the solution to Einstein's riddle. (slow & prosaic) // See http://en.wikipedia.org/wiki/Zebra_Puzzle // and http://weitz.de/einstein.html #include <iostream> #include <algorithm> namespace { // the possible values of the five variables enum nation { british, swedish, norwegian, german, danish }; enum colour { red, green, yellow, blue, white }; enum animal { dog, horse, cat, bird, fish }; enum cigarette { marlboro, winfield, rothmans, pallmall, dunhill }; enum drink { tea, coffee, milk, beer, water }; // these are for printing the results; obviously the order must correspond to the enums above const char * nation_names[] = { "british", "swedish", "norwegian", "german", "danish" }; const char * colour_names[] = { "red", "green", "yellow", "blue", "white" }; const char * animal_names[] = { "dog", "horse", "cat", "bird", "fish" }; const char * cigarette_names[] = { "marlboro", "winfield", "rothmans", "pallmall", "dunhill" }; const char * drink_names[] = { "tea", "coffee", "milk", "beer", "water" }; // arbitrarily assign the leftmost house an index of 0, and the rightmost 4; // e.g. the nationality of the owner of the left-most house would be given by // nations[0], and the pet he keeps would be given by animals[0], and the pet // his neighbour (on his right) keeps would be given by animals[1], and so on const int num_houses = 5; nation nations[num_houses]; colour colours[num_houses]; animal animals[num_houses]; cigarette cigarettes[num_houses]; drink drinks[num_houses]; // set 'array' to first permutation, which is numerically { 0, 1, 2, 3, 4 } template <class T, size_t size> void init(T (& array)[size]) { for (int i = 0; i < size; ++i) array[i] = static_cast<T>(i); } // set 'array' to next permutation if possible, otherwise return false template <class T, size_t size> bool next_permutation(T (& array)[size]) { return std::next_permutation(array, array + size); } // set the combination of all house variables to the next permutation bool permute() { if (next_permutation(nations)) return true; init(nations); if (next_permutation(colours)) return true; init(colours); if (next_permutation(animals)) return true; init(animals); if (next_permutation(cigarettes)) return true; init(cigarettes); if (next_permutation(drinks)) return true; init(drinks); // we have cycled through all permutations of all variables return false; } // return the number of the house of the given colour inline int find_colour(colour c) { int i = 0; while (colours[i] != c) ++i; return i; } // return the number of the house whose owner is of the given nationality inline int find_nation(nation n) { int i = 0; while (nations[i] != n) ++i; return i; } // return the number of the house whose owner smokes the given brand of cigarette inline int find_cigarette(cigarette c) { int i = 0; while (cigarettes[i] != c) ++i; return i; } // the Norwegian lives next to the blue house inline bool norwegian_lives_next_to_blue_house() { const int i = find_nation(norwegian); return (i > 0 && colours[i-1] == blue) || (i < (num_houses - 1) && colours[i+1] == blue); } // the green house is on the left of the white house inline bool green_left_of_white() { const int i = find_colour(green); return i < (num_houses - 1) && colours[i+1] == white; } // the person who smokes Marlboro lives next to the one who keeps cats inline bool smokes_marlboro_next_cats() { const int i = find_cigarette(marlboro); return (i > 0 && animals[i-1] == cat) || (i < (num_houses - 1) && animals[i+1] == cat); } // the person who keeps horses lives next to the person who smokes Dunhill inline bool smokes_dunhill_next_horses() { const int i = find_cigarette(dunhill); return (i > 0 && animals[i-1] == horse) || (i < (num_houses - 1) && animals[i+1] == horse); } // the person who smokes Marlboro has a neigbor who drinks water inline bool smokes_marlboro_next_water() { const int i = find_cigarette(marlboro); return (i > 0 && drinks[i-1] == water) || (i < (num_houses - 1) && drinks[i+1] == water); } // return true iff all the stated conditions are met bool is_solution() { return // the Norwegian lives in the first house nations[0] == norwegian // the man living in the centre house drinks milk && drinks[num_houses/2] == milk // the Brit lives in the red house && colours[find_nation(british)] == red // the Swede keeps dogs as pets && animals[find_nation(swedish)] == dog // the Dane drinks tea && drinks[find_nation(danish)] == tea // the German smokes Rothmans && cigarettes[find_nation(german)] == rothmans // the green house's owner drinks coffee && drinks[find_colour(green)] == coffee // the owner of the yellow house smokes Dunhill && cigarettes[find_colour(yellow)] == dunhill // the person who smokes Pall Mall rears birds && animals[find_cigarette(pallmall)] == bird // the person who smokes Winfield drinks beer && drinks[find_cigarette(winfield)] == beer && norwegian_lives_next_to_blue_house() && green_left_of_white() && smokes_marlboro_next_cats() && smokes_dunhill_next_horses() && smokes_marlboro_next_water(); } // print the details for all houses void print() { std::cout << '\n'; for (int i = 0; i < num_houses; ++i) std::cout << "house " << i + 1 << ' ' << colour_names[colours[i]] << ' ' << nation_names[nations[i]] << ' ' << animal_names[animals[i]] << ' ' << cigarette_names[cigarettes[i]] << ' ' << drink_names[drinks[i]] << "\n"; } }//anonymous namespace int main () { init(nations); init(colours); init(animals); init(cigarettes); init(drinks); if (is_solution()) print(); while (permute()) { if (is_solution()) print(); } }

Update November 2013:

I wanted to create a solution that was nearer to the performance of Edi Weitz’s Lisp code, referred to above. Here is what I came up with:

// Anthony C. Hay - Find the solution to Einstein's riddle. (better) // See http://howtowriteaprogram.blogspot.co.uk/2009/07/einsteins-riddle.html // // Compile with // g++ -O3 -o einstine einstine.cpp // or, with MSVC // cl /nologo /EHs /O2 einstine.cpp #include <iostream> #include <algorithm> namespace { const int num_houses = 5; const int num_unique_values = 5; // the possible values of the five attributes enum nation { british, swedish, norwegian, german, danish }; enum colour { red, green, yellow, blue, white }; enum animal { dog, horse, cat, bird, fish }; enum cigarette { marlboro, winfield, rothmans, pallmall, dunhill }; enum drink { tea, coffee, milk, beer, water }; // these are for printing the results; obviously the order must correspond to the enums above const char * nation_names[num_unique_values] = { "british", "swedish", "norwegian", "german", "danish" }; const char * colour_names[num_unique_values] = { "red", "green", "yellow", "blue", "white" }; const char * animal_names[num_unique_values] = { "dog", "horse", "cat", "bird", "fish" }; const char * cigarette_names[num_unique_values] = { "marlboro", "winfield", "rothmans", "pallmall", "dunhill" }; const char * drink_names[num_unique_values] = { "tea", "coffee", "milk", "beer", "water" }; // print the details for all houses void print(const int * nations, const int * drinks, const int * colours, const int * cigarettes, const int * animals) { std::cout << '\n'; for (int i = 0; i < num_houses; ++i) std::cout << "house " << i + 1 << ' ' << colour_names[colours[i]] << ' ' << nation_names[nations[i]] << ' ' << animal_names[animals[i]] << ' ' << cigarette_names[cigarettes[i]] << ' ' << drink_names[drinks[i]] << "\n"; } // create a lookup 'table' for given 'perm' such that // table[n] -> number of house with attribute n // // e.g. if p is {2, 3, 4, 1, 0} then mk_lookup_table(p, t) will // initialise t to {4, 3, 0, 1, 2} so we can ask "where is 1?" // like this, t[1], and get the answer 3 inline void mk_lookup_table(const int * perm, int * table) { for (int i = 0; i < num_unique_values; ++i) table[perm[i]] = i; } // return true iff the house either side of 'house_number' is/has 'desired_value' inline bool neighbour(int house_number, const int * attributes, int desired_value) { return house_number > 0 && attributes[house_number - 1] == desired_value || house_number < num_unique_values-1 && attributes[house_number + 1] == desired_value; } // each of these possible() functions returns false if the given information is // sufficient to eliminate the branch from the search space, otherwise it returns // true, which means we don't yet have enough information to eliminate the branch // test the given permutation of the nations attribute and reject it (return false) // if it is definitely not on the branch leading to a solution inline bool possible(const int * nations) { // with our very limited information we can test only that... // the Norwegian lives in the first house return nations[0] == norwegian; } inline bool possible(const int * nations, const int * drinks) { int nationalities[num_unique_values]; mk_lookup_table(nations, nationalities); return // the man living in the centre house drinks milk drinks[num_houses/2] == milk // the Dane drinks tea && drinks[nationalities[danish]] == tea; } inline bool possible(const int * nations, const int * drinks, const int * colours) { int nationalities[num_unique_values]; mk_lookup_table(nations, nationalities); int house_colours[num_unique_values]; mk_lookup_table(colours, house_colours); return // the Brit lives in the red house colours[nationalities[british]] == red // the green house's owner drinks coffee && drinks[house_colours[green]] == coffee // the green house is on the left of the white house && (house_colours[green] < num_unique_values-1 && colours[house_colours[green]+1] == white) // the Norwegian lives next to the blue house && neighbour(nationalities[norwegian], colours, blue); } inline bool possible(const int * nations, const int * drinks, const int * colours, const int * cigarettes) { int nationalities[num_unique_values]; mk_lookup_table(nations, nationalities); int house_colours[num_unique_values]; mk_lookup_table(colours, house_colours); int smokes[num_unique_values]; mk_lookup_table(cigarettes, smokes); return // the German smokes Rothmans cigarettes[nationalities[german]] == rothmans // the owner of the yellow house smokes Dunhill && cigarettes[house_colours[yellow]] == dunhill // the person who smokes Winfield drinks beer && drinks[smokes[winfield]] == beer; } inline bool possible(const int * nations, const int * drinks, const int * /*colours*/, const int * cigarettes, const int * animals) { int nationalities[num_unique_values]; mk_lookup_table(nations, nationalities); int smokes[num_unique_values]; mk_lookup_table(cigarettes, smokes); int pets[num_unique_values]; mk_lookup_table(animals, pets); return // the Swede keeps dogs as pets animals[nationalities[swedish]] == dog // the person who smokes Pall Mall rears birds && animals[smokes[pallmall]] == bird // the person who smokes Marlboro lives next to the one who keeps cats && neighbour(smokes[marlboro], animals, cat) // the person who keeps horses lives next to the person who smokes Dunhill && neighbour(pets[horse], cigarettes, dunhill) // the person who smokes Marlboro has a neigbor who drinks water && neighbour(smokes[marlboro], drinks, water); } // search for all possible solutions and print each one found (there is only one) void solve() { // Each attribute has 5 unique values. E.g. there are five colours. // Here we create one table of all permutations of 5 unique values. // Then the current permutation of all five attributes may be // maintained with five simple indexes into this one table. const int num_permutations = 120; // = num_unique_values! = 5! int ptab[num_permutations][num_unique_values]; int values[num_unique_values] = {0, 1, 2, 3, 4}; for (int i = 0; i < num_permutations; ++i) { std::copy(values, values + num_unique_values, ptab[i]); std::next_permutation(values, values + num_unique_values); } // each for loop cycles through every permutation of one of the attributes; // each if tests whether it's worth looking further down that branch of the search space for (int nation = 0; nation < num_permutations; ++nation) if (possible(ptab[nation])) for (int drink = 0; drink < num_permutations; ++drink) if (possible(ptab[nation], ptab[drink])) for (int colour = 0; colour < num_permutations; ++colour) if (possible(ptab[nation], ptab[drink], ptab[colour])) for (int cigarette = 0; cigarette < num_permutations; ++cigarette) if (possible(ptab[nation], ptab[drink], ptab[colour], ptab[cigarette])) for (int animal = 0; animal < num_permutations; ++animal) if (possible(ptab[nation], ptab[drink], ptab[colour], ptab[cigarette], ptab[animal])) print(ptab[nation], ptab[drink], ptab[colour], ptab[cigarette], ptab[animal]); } }//anonymous namespace int main() { solve(); /* expected output: house 1 yellow norwegian cat dunhill water house 2 blue danish horse marlboro tea house 3 red british bird pallmall milk house 4 green german fish rothmans coffee house 5 white swedish dog winfield beer */ }

Notes:

- Let's call my original code Einstine09 and my new code Einstine13.

- Einstine13 run time is 0.012s (real 0.012s, user 0.001s, sys 0.002s) on a 2.8GHz Intel E8235 processor. (But an "int main() {}" runs in 0.010s (real), so should we subtract that from 0.012s and call it 2ms? I'm not sure. It doesn't really matter; what matters is that Einstine13 is in the same ballpark as the fastest solutions given by others, and not in the next county as Einstine09 was.) Einstine09 runs in 350.808s (real) on the same machine, compiled with the same compiler and -O3 option. Choosing a better algorithm gave us a 30,000× speed improvement (350.808 / 0.012 = 29,234).

- There are 5 different attributes (such as colour, nationality) and each attribute has 5 unique values. There are 5! permutations of 5 unique values so the total number of possible solution states is (5!)⁵ = 24,883,200,000. Einstine09 calls is_solution() for each and every one of these states and is sloooow. Einstine13 calls the possible() functions a total of just 18,360 times and is much faster.

- I knew the problem was one of combinatorial search, like the eight queens problem. But I couldn’t see how to prune the search tree by applying all the rules at each branch because a rule might refer to something that hadn’t yet been decided: you can’t chop off a branch where the Winfield smoker doesn’t drink beer if you don’t yet know who the Winfield smoker is. And so on. My personal aha! moment came while reading Edi Weitz’s explanation of his Lisp solution: “Note that every condition has to return T if [...] not all of its parameters are defined yet.” Yes, it’s obvious to me too, now.

- Reading Edi Weitz’s commentary gave me one of the clearest glimpses I’ve had of the secret ingredient in Lisp and I recommend it to anyone struggling to understand why so many Lisp cognoscenti rave about the language. But I have to say that without his explanation I think I would have struggled to understand his code. My C++ solution is fast, but it's specific to solving the Einstein problem. Dr. Weitz's Lisp solution is also fast, but in more-or-less the same amount of code he has created a domain-specific language for solving any Einstine-like problem. Thank you Dr. Weitz for sharing it.

index of blog posts