Introduction

I found this interesting puzzle in Manfred Becker's article Einstein's riddle solved in C++. So I rushed to run his code for an easy answer. However several minutes had passed without a solution on the screen before I had to quit it, and went back to the source code for a clue. And I found a time table that states it takes 2 days 19 hours 24 minutes on a 700MHz Pentium III!

Although I understand that Becker's solution is just to demonstrate object oriented design, I think it would be better to have a fast solution for our impatient guys.

Here is a copy of the problem for easy reference and for the sake of completeness:

Einstein's riddle

There are 5 houses in five different colors in a row.
In each house lives a person with a different nationality.
These five owners drink a certain type of beverage, smoke a certain brand of cigar and keep a certain pet.
No owners have the same pet, smoke the same brand of cigar or drink the same beverage.

The question is: Who owns the fish?

Einstein's hints

The Brit lives in the red house.
The Swede keeps dogs as pets.
The Dane drinks tea.
The green house is on the immediate left of the white house.
The green house's owner drinks coffee.
The person who smokes Pall Mall rears birds.
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 one who keeps cats.
The man who keeps horses lives next to the man who smokes Dunhill.
The owner 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.

Class Design Considerations

Einstein spoke of houses and persons. It seems natural that we need a class of houses (CHouse) and a class of persons (CPerson) as Becker did it this way. However, if you think a little more about the relationship between these classes, you will notice that they have a one to one relationship. People often talk about homeowners. So why don't we just have one class for them? Sure, we can do it by viewing a person as a owner of a house and treating a person as a property in a house as well :)

enum Problem_Constants
{ 
    COUNT_HOUSES = 5, 
    COUNT_CATEGORIES = 5, 
    COUNT_HINTS = 15,
    BITS_CatID = 3,
    COUNT_EXTENDED_CatID = 1 << BITS_CatID  //  COUNT_EXTENDED_CatID = 8
};

// Property Category ID
enum CatID 
{
    COLOR,
    NATIONALITY,
    BAVERAGE,
    CIGAR,
    PET
};

// Property Identifications
enum PropID
{
    BLUE       = (0 << BITS_CatID) | COLOR,    
    GREEN      = (1 << BITS_CatID) | COLOR,         
    RED        = (2 << BITS_CatID) | COLOR,      
    WHITE      = (3 << BITS_CatID) | COLOR,     
    YELLOW     = (4 << BITS_CatID) | COLOR, 

    BRIT       = (0 << BITS_CatID) | NATIONALITY,   
    DANE       = (1 << BITS_CatID) | NATIONALITY,        
    GERMAN     = (2 << BITS_CatID) | NATIONALITY,   
    NORWEGIAN  = (3 << BITS_CatID) | NATIONALITY, 
    SWEDE      = (4 << BITS_CatID) | NATIONALITY,  

    BEER       = (0 << BITS_CatID) | BAVERAGE,
    COFFEE     = (1 << BITS_CatID) | BAVERAGE, 
    MILK       = (2 << BITS_CatID) | BAVERAGE,
    TEA        = (3 << BITS_CatID) | BAVERAGE,
    WATER      = (4 << BITS_CatID) | BAVERAGE,

    BLENDS     = (0 << BITS_CatID) | CIGAR,
    BLUEMASTER = (1 << BITS_CatID) | CIGAR,
    DUNHILL    = (2 << BITS_CatID) | CIGAR,
    PALLMALL   = (3 << BITS_CatID) | CIGAR,
    PRINCE     = (4 << BITS_CatID) | CIGAR,

    BIRD       = (0 << BITS_CatID) | PET,
    CAT        = (1 << BITS_CatID) | PET,
    DOG        = (2 << BITS_CatID) | PET,
    FISH       = (3 << BITS_CatID) | PET,
    HORSE      = (4 << BITS_CatID) | PET
};

enum HouseID
{
    HOUSE0, HOUSE1, HOUSE2, HOUSE3, HOUSE4
};

class CHouse
{
private:
    enum 
    {    
        // EMPTY is a flag to indicate a null property of any category.
        // Its value must not be equal to any
        // real property (any element of PropID).
        EMPTY  = (0 << BITS_CatID) | PET + 1
    };

    PropID m_property[COUNT_CATEGORIES];

// constructor
public:
    CHouse() 
    {
        for (int i = 0; i < COUNT_CATEGORIES; i++)
            m_property[i] = EMPTY;
    }

// operations
public:
    int IsEmpty(CatID cid)          { return m_property[cid] == EMPTY; }
    int IsEmpty(PropID pid)         { return IsEmpty(GetCatID(pid)); }
    int GetPropIndex(CatID cid)     { return GetIndex(m_property[cid]); }
    void SetProperty(PropID pid)    { m_property[GetCatID(pid)] = pid; }
    void ClearProperty(PropID pid)  { m_property[GetCatID(pid)] = EMPTY;}

private:
    CatID GetCatID(PropID pid)  
      { return (CatID) (pid & (COUNT_EXTENDED_CatID - 1)); }
    int GetIndex(PropID pid)    { return pid >> BITS_CatID; }
};

Simple as it is, isn't? CHouse has only one data member m_property that is an array indexed by category (CatID) and used to hold the 5 properties. A CHouse object is self-contained, which knows nothing about its neighbors. We all know that a dog is a pet and beer is beverage. To please its users, CHouse understands this type-of relation by means of its member function GetCatID(PropID pid) and the composite definition of PropID.

Let's move to the other part of the problem, the hints, which describe the associations of properties and owners. We need a class to represent the hints. I bet, you will notice that the hints vary considerably at a glance. It is obvious that we will not end up with a simple uniform class like CHouse. Well, we will attack these variations by abstraction and derivation.

So what are in common, in all the hints? They all have to do with at least one property and one possible owner of the property. Therefore we name a base class CHint for the hints, and make it have two data members m_pid0 and m_pNewOwner, to represent the property and the possible owner. A CHint object also needs access to any CHouse object because the property (m_pid0) in it can be owned by any house owner that meets the hint. We put an array of 5 CHouse objects in CHint as a static data member. Before we continue with CHint method members, take a look at its blue print:

class CHint
{
protected:
    const PropID m_pid0;  // a property in the hint
    CHouse* m_pNewOwner0; // ptr to a would-be owner
                          // of the property to meet the hint
    CHouse* m_pNext;      // the next house to be checked and filled

    static CHouse house[COUNT_HOUSES]; // array of the houses
private:
    // array of pointers to house owners indexed by PropID
    static CHouse* propowner[COUNT_CATEGORIES*COUNT_EXTENDED_CatID];
    static int count_solutions; // count of solutions found

// constructor
protected:
    CHint(PropID pid0) : m_pid0(pid0) {}

public:
    // starting from house specified by m_pNext, seek and assign the 
    // first eligible houseowner(s) with properties. 
    //
    // return value:
    //       0 : failed    
    // nonzero : successful
    //
    virtual int AssignPropToNextEligibles() = 0;    

    // undo AssignPropToNextEligibles
    virtual void RemovePropFromPrevEligibles() = 0;
    // reset the seek to start position
    virtual void ResetSeekPosition() = 0;
    // print out a solution
    static  void PrintOut();

// helpers
protected:
    void RemoveProperty();   // remove property from new owner
    int AssignPropertySetNextPos(CHouse* p0, CHouse* pNext);

// property register operations
protected:
    static CHouse* GetPropertyOwner(PropID pid) 
                     { return propowner[pid]; }
    static void RegisterOwnership(PropID pid, CHouse* pOwner) 
    {    
        propowner[pid] = pOwner;
    }

// counter
public:
    static int GetSolutionCount()  { return count_solutions; };
private:
    static void IncSolutionCount() { count_solutions++; };

// helper
    // verify a solution and check for errors
    static CHouse* VerifyCurrentSolution();
};

There are three pure virtual functions in it, that make CHint an abstract class. Just as a CHouse object knows nothing about its neighbors, a CHint object should know nothing about other CHint objects, in order to keep things simple. But a CHint object should have a method of finding all possible houses that meet the requirements of the hint. It is not necessary that the method returns a list of all possible house owners at a time. Instead, we want it find one house owner (m_pNewOwner) for its property (m_pid0) at a time, in an order. This can deliver better overall efficiency due to less memory traffic. These three virtual functions come in to fill the bill.

AssignPropToNextEligibles() finds the next matching house owner and assigns the property to him. Data member m_pNext is used to keep AssignPropToNextEligibles() knowing where to resume its work.
RemovePropFromPrevEligibles() is used to undo the property assignments made by AssignPropToNextEligibles() so that we can call AssignPropToNextEligibles() again to find yet another owner.
The last virtual function ResetSeekPosition() is an interface to reset the seek to its start position.

Those pure virtual functions can be viewed as place holders and specifications. Any class derived from CHint still has to implement these three functions.

The static data member propowner and its functions GetPropertyOwner and RegisterOwnership are included in CHint for easy access to the owner of any property. The data member and these 2 functions are an implementation of a property ledger so that we can avoid doing a linear search every time we need to know who owns a specific property.

The static functions VerifyCurrentSolution and PrintOut that verifies and prints out a solution respectively, are quite foreign to the CHint class from a concept point of view. I include them here simply because they also need access to the 5 houses. If I were a fundamentalist in OOP design, I would probably kick them out and give them a read only service instead.

Now we can derive classes from CHint. Hint 8 and 9 deal with only one property that the base class already provides. But each of them has a known house number. So we define the class this way:

// class for any hint of Known house number
//
class CKnownHouseHint : public CHint
{
private:
    CHouse* const m_pKnownHouse;

public:
    CKnownHouseHint(HouseID i, PropID pid) : 
        CHint(pid), m_pKnownHouse(&house[i]) {}

private:
    virtual int AssignPropToNextEligibles();    
    virtual void ResetSeekPosition()           { m_pNext = m_pKnownHouse; }
    virtual void RemovePropFromPrevEligibles() { RemoveProperty(); }
};

The rest of the hints involve two properties that can be owned by different owners. We reflect this difference by deriving a CMultiPropertiesHint class:

// class for any hint that involves Multiple properties
//
class CMultiPropertiesHint : public CHint
{
protected:
    // a property in the hint
    const PropID m_pid1;
    // ptr to a would-be owner of the property to meet the hint
    CHouse* m_pNewOwner1;

// implementations
protected:
    virtual void RemovePropFromPrevEligibles();

// constructor
protected:
    CMultiPropertiesHint(PropID pid0, 
      PropID pid1) : CHint(pid0), m_pid1(pid1) { }

// helpers
protected:
    void ResetSeekPositionToFirstHouse() { m_pNext = &house[HOUSE0]; }
    int AssignPropertiesSetNextPos(CHouse* p0, CHouse* p1, CHouse* pNext);
};

CMultiPropertiesHint is still an abstract base class for further derivations, though it provides some useful services.

Some hints only deal with a single house owner, hint 1 for example. CSingleHouseHint is derived from CMultiPropertiesHint for those hints:

// class for the any hint that only involves a Single houseowner
//
class CSingleHouseHint : public CMultiPropertiesHint
{
// constructor
public:
    CSingleHouseHint(PropID pid0, 
      PropID pid1) : CMultiPropertiesHint(pid0, pid1) { }

// implementations
private:
    virtual int AssignPropToNextEligibles();    
    virtual void ResetSeekPosition() { ResetSeekPositionToFirstHouse(); }
};

Some hints deal with two house owners, hint 15 for instance. CNeighborsHint is derived from CMultiPropertiesHint for those hints:

// class for any hint that involves
// 2 Neighbors without a directional restriction
//
class CNeighborsHint : public CMultiPropertiesHint
{
private:
    int m_NextReverse; // are the properties to be filled in reverse order?

// constructor
public:
    CNeighborsHint(PropID pid0, 
      PropID pid1) : CMultiPropertiesHint(pid0, pid1) { }

// implementations
private:
    virtual int AssignPropToNextEligibles();    
    virtual void ResetSeekPosition()        
    { 
        ResetSeekPositionToFirstHouse(); 
        m_NextReverse = 0;
    }
};

Hint 4 also talks about two houses. But the houses should be in a sequential order. We have only one instance of this kind, yet we have to derive a class for it to complete CHint class family:

// class for any hint that involves
// 2 Neighbors Ordered by direction
//
class COrderedNeighborsHint : public CMultiPropertiesHint
{
// constructor
public:
    COrderedNeighborsHint(PropID pid0, 
      PropID pid1) : CMultiPropertiesHint(pid0, pid1) {}

// implementations
private:
    virtual int AssignPropToNextEligibles();    
    virtual void ResetSeekPosition() { ResetSeekPositionToFirstHouse(); }
};

I skip the implementations of these classes here. You can find them in the source file.

Since the riddle now can be well represented by a set of CHint objects and a set of CHouse objects, let's start to crack the puzzle by defining a class CSolver:

// class for finding the solutions
//
class CSolver
{
private:
    static CHint* hint[COUNT_HINTS]; // array of pointers to CHint objects
    static int count_nodes; // count of nodes searched

// operations
public:
    static void DoTheWork(); // search driver

// helpers
private:
    static void Search(CHint** ppCHint); // search engine
    static void PrintEinsteinRiddleDescription();
    static void IncNodeCount() { count_nodes++; };
    static int GetNodeCount() { return count_nodes; };
};

CSolver encapsulates those 15 hints in a static array of pointers to CHint objects. In the implementation file, we simply create these objects and initialize the array in a single step:

// Array of pointers to CHint objects, i.e. a list of hints.
//
CHint* CSolver::hint[COUNT_HINTS] = 
{
    new CSingleHouseHint(BRIT, RED),                // Hint 1
    new CSingleHouseHint(SWEDE, DOG),               // Hint 2
    new CSingleHouseHint(DANE, TEA),                // Hint 3
    new COrderedNeighborsHint(GREEN, WHITE),        // Hint 4
    new CSingleHouseHint(GREEN, COFFEE),            // Hint 5
    new CSingleHouseHint(PALLMALL, BIRD),           // Hint 6
    new CSingleHouseHint(YELLOW, DUNHILL),          // Hint 7
    new CKnownHouseHint(HOUSE2, MILK),              // Hint 8
    new CKnownHouseHint(HOUSE0, NORWEGIAN),         // Hint 9
    new CNeighborsHint(BLENDS, CAT),                // Hint 10
    new CNeighborsHint(HORSE, DUNHILL),             // Hint 11
    new CSingleHouseHint(BLUEMASTER, BEER),         // Hint 12
    new CSingleHouseHint(GERMAN, PRINCE),           // Hint 13
    new CNeighborsHint(NORWEGIAN, BLUE),            // Hint 14
    new CNeighborsHint(BLENDS, WATER)               // Hint 15
};

Now CSolver can work with pointers to CHint objects and forget about the differences among those objects. CSolver has a single public interface function DoTheWork(), which will be called by the main() function. DoTheWork() will delegate the real work to the Search function.

Brutal Search

Here is a simplified version of the exhaustive Search function:

void CSolver::Search(int index_of_hint)
{
    
    hint[index_of_hint]->ResetSeekPosition(); // reset to start position.

    // seek each set of eligibles & assign
    // properties to them if needed.
    while (hint[index_of_hint]->AssignPropToNextEligibles()) 
    {

        if (index_of_hint != 15 - 1) // if the hint is not the last one.
            Search(index_of_hint + 1); // search with next hint.
        else  // all hints have been met.
            CHint::PrintOut(); // a solution has been found.
        // undo the assign operations.
        hint[index_of_hint]->RemovePropFromPrevEligibles();
    }
}

As you see, Search is a recursive function. It tries to find a match for the current hint. If it has found one, it then calls itself with the next hint, provided that the current hint is not the last one where it prints a solution, and continues the search. If it has finished finding all possible matches or it has failed finding any match for the current hint, it returns the control to the previous hint.

DoTheWork() will make the first call with index_of_hint = 0.

Performance

It takes 0.016 seconds on a 1.6GHz P4 and 0.056 seconds on a 166Mhz Pentium MMX, when the standard clock() were used to do the timing in a previous version.

The current version uses high resolution performance counters to get more accurate results. However, different runtime sessions still showed quiet big variations of time. A little profiling work indicated, the program spends more than 80% of its time in printing out a solution! I had to optimize the drawing code a little bit in order to reduce the variations. After these tweaks, it takes only 0.0014 seconds on a 2.60GHz P4.

It is much faster than I had expected anyways. Now I think an old 8086 can easily crack the riddle too. Unfortunately, I could not find one.

Update

It would be interesting if we could gain some insight into the puzzle by playing with the program. Here are some:

Hint 15 is proved to be redundant because exactly the same solution is produced after it is commented out in the hint list. We can also leave out Hint 5 to make it more challenging for those who prefer pencils and papers.

Some tweaks in Version 1.04 (12/23/2003) makes it easier to add or delete hints in the list.

Version 1.05 (10/25/2013) adds UNICODE support; C# port source is also released along with updated C++ code.

Machine Solution to Einstein's Riddle Revisited