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 };
enum CatID
{
COLOR,
NATIONALITY,
BAVERAGE,
CIGAR,
PET
};
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 = (0 << BITS_CatID) | PET + 1
};
PropID m_property[COUNT_CATEGORIES];
public:
CHouse()
{
for (int i = 0; i < COUNT_CATEGORIES; i++)
m_property[i] = EMPTY;
}
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; CHouse* m_pNewOwner0; CHouse* m_pNext;
static CHouse house[COUNT_HOUSES]; private:
static CHouse* propowner[COUNT_CATEGORIES*COUNT_EXTENDED_CatID];
static int count_solutions;
protected:
CHint(PropID pid0) : m_pid0(pid0) {}
public:
virtual int AssignPropToNextEligibles() = 0;
virtual void RemovePropFromPrevEligibles() = 0;
virtual void ResetSeekPosition() = 0;
static void PrintOut();
protected:
void RemoveProperty(); int AssignPropertySetNextPos(CHouse* p0, CHouse* pNext);
protected:
static CHouse* GetPropertyOwner(PropID pid)
{ return propowner[pid]; }
static void RegisterOwnership(PropID pid, CHouse* pOwner)
{
propowner[pid] = pOwner;
}
public:
static int GetSolutionCount() { return count_solutions; };
private:
static void IncSolutionCount() { count_solutions++; };
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 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 CMultiPropertiesHint : public CHint
{
protected:
const PropID m_pid1;
CHouse* m_pNewOwner1;
protected:
virtual void RemovePropFromPrevEligibles();
protected:
CMultiPropertiesHint(PropID pid0,
PropID pid1) : CHint(pid0), m_pid1(pid1) { }
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 CSingleHouseHint : public CMultiPropertiesHint
{
public:
CSingleHouseHint(PropID pid0,
PropID pid1) : CMultiPropertiesHint(pid0, pid1) { }
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 CNeighborsHint : public CMultiPropertiesHint
{
private:
int m_NextReverse;
public:
CNeighborsHint(PropID pid0,
PropID pid1) : CMultiPropertiesHint(pid0, pid1) { }
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 COrderedNeighborsHint : public CMultiPropertiesHint
{
public:
COrderedNeighborsHint(PropID pid0,
PropID pid1) : CMultiPropertiesHint(pid0, pid1) {}
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 CSolver
{
private:
static CHint* hint[COUNT_HINTS]; static int count_nodes;
public:
static void DoTheWork();
private:
static void Search(CHint** ppCHint); 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:
CHint* CSolver::hint[COUNT_HINTS] =
{
new CSingleHouseHint(BRIT, RED), new CSingleHouseHint(SWEDE, DOG), new CSingleHouseHint(DANE, TEA), new COrderedNeighborsHint(GREEN, WHITE), new CSingleHouseHint(GREEN, COFFEE), new CSingleHouseHint(PALLMALL, BIRD), new CSingleHouseHint(YELLOW, DUNHILL), new CKnownHouseHint(HOUSE2, MILK), new CKnownHouseHint(HOUSE0, NORWEGIAN), new CNeighborsHint(BLENDS, CAT), new CNeighborsHint(HORSE, DUNHILL), new CSingleHouseHint(BLUEMASTER, BEER), new CSingleHouseHint(GERMAN, PRINCE), new CNeighborsHint(NORWEGIAN, BLUE), new CNeighborsHint(BLENDS, WATER) };
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();
while (hint[index_of_hint]->AssignPropToNextEligibles())
{
if (index_of_hint != 15 - 1) Search(index_of_hint + 1); else CHint::PrintOut(); 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.