Einstein's riddle solved in C++

• Download source files - 39.9 Kb

Introduction

Einstein wrote a riddle last century. He said that 98% of the world could not solve it.

Einstein's riddle

• There are 5 houses in five different colors
• 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

• 1.) the Brit lives in the red house
• 2.) the Swede keeps dogs as pets
• 3.) the Dane drinks tea
• 4.) the green house is on the left of the white house
• 5.) the green house's owner drinks coffee
• 6.) the person who smokes Pall Mall rears birds
• 7.) the owner of the yellow house smokes Dunhill
• 8.) the man living in the center house drinks milk
• 9.) the Norwegian lives in the first house
• 10.) the man who smokes blends lives next to the one who keeps cats
• 11.) the man who keeps horses lives next to the man who smokes Dunhill
• 12.) the owner who smokes BlueMaster drinks beer
• 13.) the German smokes Prince
• 14.) the Norwegian lives next to the blue house
• 15.) the man who smokes blends has a neighbor who drinks water

The solution

Of course, you can solve this riddle by your own, and many web-pages will be found giving hints and solutions. But here I will give you the tutorial to solve the problem using c++. It is written for beginners and shows how to handle a problem and adapt it into object oriented programming.

Tutorial

Define classes

Einstein spoke about houses and persons. So we need a class who defines a house (CHouse) and a class who defines a person (CPerson). All other things (like colors, nationality, beverage ... ) are attributes of one of these classes. Then we need a class for the riddle itselve (CEinsteinsRiddle) to handle the hints and solve the riddle. Let's begin with the given attributes. We take enumerations to handle them.

enum COLOR       
  { COLOR_UNKNOWN,       BLUE,   GREEN,       RED,      WHITE,     YELLOW };
enum NATIONALITY 
  { NATIONALITY_UNKNOWN, BRIT,   DANE,        GERMAN,   NORWEGIAN, SWEDE  };
enum BAVERAGE    
  { BAVERAGE_UNKNOWN,    BEER,   COFFEE,      MILK,     TEA,       WATER  };
enum CIGAR       
  { CIGAR_UNKNOWN,       BLENDS, BLUEMASTER,  DUNHILL,  PALLMALL,  PRINCE };
enum PET         
  { PET_UNKNOWN,         BIRD,   CAT,         DOG,      FISH,      HORSE  };
enum HOUSENUMBER 
  { HOUSENUMBER_UNKNOWN, NR1,    NR2,         NR3,      NR4,       NR5    };

To make these values printable whe need some text.

char sColor[MAX+2][20] =       { "    ?    ", "  blue   ", 
    "  green  ", "   red   ", "  white  ", " yellow  " };
char sNationality[MAX+2][20] = { "    ?    ", "  Brit   ", 
    "  Dane   ", " German  ", "Norwegian", "  Swede  " };
char sBaverage[MAX+2][20] =    { "    ?    ", "  Beer   ", 
    " Coffee  ", "  Milk  ",  "   Tea   ", "  Water  " };
char sCigar[MAX+2][20] =       { "    ?    ", " Blends  ", 
    "BlueMastr", " Dunhill ", "Pall Mall", " Prince  " };
char sPet[MAX+2][20] =         { "    ?    ", "  Bird   ", 
    "   Cat   ", "   Dog   ", "  Fish   ", "  Horse  " };

And also text for the Einstein's hints.

char sHint[15][80] =
{
 " 1.) the Brit lives in the red house",
 " 2.) the Swede keeps dogs as pets",
 " 3.) the Dane drinks tea",
 " 4.) the green house is on the left of the white house",
 " 5.) the green house's owner drinks coffee",
 " 6.) the person who smokes Pall Mall rears birds",
 " 7.) the owner of the yellow house smokes Dunhill",
 " 8.) the man living in the center house drinks milk",
 " 9.) the Norwegian lives in the first house",
 "10.) the man who smokes blends lives next to the one who keeps cats",
 "11.) the man who keeps horses lives next to the man who smokes Dunhill",
 "12.) the owner who smokes BlueMaster drinks beer",
 "13.) the German smokes Prince",
 "14.) the Norwegian lives next to the blue house",
 "15.) the man who smokes blends has a neighbor who drinks water"
};

Now we take the class who define a person. Each person have a nationality, an baverage, a cigar and a pet. All this things are attributes of the person, so it's very easy to define the class.

class CPerson
{
private:
 // Membervariables of the class

 NATIONALITY m_eNationality;
 BAVERAGE    m_eBaverage;
 CIGAR       m_eCigar;
 PET         m_ePet;

public:
 // Constructor u. Destructor of the class

 CPerson(void);
 ~CPerson(void);

 // Functions to read membervariables

 NATIONALITY GetNationality(void) { return m_eNationality; };
 BAVERAGE    GetBaverage(void)    { return m_eBaverage;    };
 CIGAR       GetCigar(void)       { return m_eCigar;       };
 PET         GetPet(void)         { return m_ePet;         };

 // Functions to set membervariables

 void SetNationality(NATIONALITY nationality) 
    { m_eNationality = nationality; };
 void SetBaverage(BAVERAGE baverage)          
    { m_eBaverage    = baverage;    };
 void SetCigar(CIGAR cigar)                   
    { m_eCigar       = cigar;       };
 void SetPet(PET pet)                         
    { m_ePet         = pet;         };
};

Here are the constuctor and destructor of the class.

CPerson::CPerson(void)
{
 m_eNationality = NATIONALITY_UNKNOWN;
 m_eBaverage    = BAVERAGE_UNKNOWN;
 m_eCigar       = CIGAR_UNKNOWN;
 m_ePet         = PET_UNKNOWN;
};

CPerson::~CPerson(void)
{
};

Now let's define the class for the houses. Each house have a housnumber and a color. Then we need a pointer to the person, who lives in the house. We need also a pointer to the left- and righthand neighbouring house, because we have to check hints like (4. the green house is on the left of the white house).

class CHouse
{
private:

 // Membervariables of the class

 HOUSENUMBER m_eHouseNumber;
 COLOR       m_eColor;
 CPerson*    m_pPerson;
 CHouse*     m_pNeighbouringHouseRight;
 CHouse*     m_pNeighbouringHouseLeft;

public:
 // Constructor u. Destructor of the class

 CHouse(HOUSENUMBER eHouseNumber);
 ~CHouse(void);

 // Functions to read membervariables

 HOUSENUMBER GetHouseNumber(void)            
    { return m_eHouseNumber;            };
 COLOR       GetColor(void)                  
    { return m_eColor;                  };
 CPerson*    GetPerson(void)                 
    { return m_pPerson;                 };
 CHouse*     GetNeighbouringHouseRight(void) 
    { return m_pNeighbouringHouseRight; };
 CHouse*     GetNeighbouringHouseLeft(void)  
    { return m_pNeighbouringHouseLeft;  };

 // Functions to set membervariables

 void SetColor(COLOR color)                    
    { m_eColor                  = color; };
 void SetNeighbouringHouseRight(CHouse* right) 
    { m_pNeighbouringHouseRight = right; };
 void SetNeighbouringHouseLeft(CHouse* left)   
    { m_pNeighbouringHouseLeft  = left;  };
};

Because the house number and the person never changed during the riddle, we don't need methods to set them. The constuctor should handle this for us.

Here are the constuctor and destructor of the class.

CHouse::CHouse(HOUSENUMBER eHouseNumber)
{
 m_eHouseNumber            = eHouseNumber;
 m_eColor                  = COLOR_UNKNOWN;
 m_pPerson                 = new CPerson();
 m_pNeighbouringHouseRight = NULL;
 m_pNeighbouringHouseLeft  = NULL;
};

CHouse::~CHouse(void)
{
 delete m_pPerson;
}

Ok! That was very easy I think. But now we have to think about the class for the riddle. Well, I think it should be clear that we use a collection of houses, because we need five of them. A dummy-house is needed for the left neighbouring house of the first and the right neighbouring house of the last house. Some methods are needed, getting the houses values.
To store the attributes, we need also a couple of member-variables.

Then we need the constructor and destructor and a function to initialize data "Initialize".
To print out the result we also need a function "PrintOut". This program should solve "Solve" the riddle by testing all possibilities and verifying the hints "VerifyingHints". But what are this possibilities? Well when you have a number of things (e.g. the five different numbers 1, 2, 3, 4 and 5) there would be fact(5) = 1x2x3x4x5 = 120 posibilities to set then in an order.
These sequences are shown below.

{ 1,2,3,4,5 }
{ 1,2,3,5,4 }
{ 1,2,4,3,5 }
{ 1,2,4,5,3 }
{ 1,2,5,3,4 }
{ 1,2,5,4,3 }
...
{ 5,4,3,2,1 }

All we have to do is to create a data-field who represent this sequence-values. After that you can iterate through this values. Because we have to iterate the color, the nationality, the beverage, the cigar and the pet we need a method "NextSequence" to iterate, and a method to set the sequence-data "SetSequence".

That's it! Here is the definition of the class for the riddle.

class CEinsteinsRiddle
{
private:
 // Membervariables of the class

 char*               m_pBackupFile;
 char*               m_pSolutionFile;
 CHouse*             m_pHouse[MAX+1];
 CHouse*             m_pDummyHouse;
 int                 m_nSequences[MAX_ITEMS][MAX+1];
 double              m_dSequenceIndex;

 int m_nColor,       m_nColorMarker;
 int m_nNationality, m_nNationalityMarker;
 int m_nBaverage,    m_nBaverageMarker;
 int m_nCigar,       m_nCigarMarker;
 int m_nPet,         m_nPetMarker;

 // Functions to read membervariables

 CHouse* GetHouse(HOUSENUMBER Nr);
 CHouse* GetHouse(COLOR Color);
 CHouse* GetHouse(NATIONALITY Nationality);
 CHouse* GetHouse(CIGAR Cigar);
 CHouse* GetHouse(PET Pet);
 double  GetPass(void) { return m_dSequenceIndex; };

 // Functions to set membervariables

 BOOLEAN NextSequence(void);
 int  SetSequence(void);

 // Function to print out

 unsigned int PrintOut(char *pFile = NULL);

 // Function to verifying the hints

 unsigned int VerifyingHints(BOOLEAN BreakOnError = FALSE);


public:
 // Constructor u. Destructor of the class

 CEinsteinsRiddle(char *pBackupFile, char *pSolutionFile);
 ~CEinsteinsRiddle(void);

 // Function zur initialize

 void Initialize(double dSequenceIndex=0, int nColor=-1, 
    int nNationality=-1, int nBaverage=-1, int nCigar=-1, int nPet=-1);

 // Function to solve then riddle

 int Solve(int argc, char* argv[]);
};

Here we are. Now let's talk about the main-routine. It's very simple. First we create a instanze of the riddle, and then we let solve the problem.

int main(int argc, char* argv[])
{
 CEinsteinsRiddle EinsteinsRaetsel( BACKUPFILE, SOLUTIONFILE );

 return EinsteinsRaetsel.Solve(argc, argv);
}

The function who solve the problem take sequence for sequence and verify the hints. This should be done until user-break or the riddle is solved.

Here is an extract of the source.

int CEinsteinsRiddle::Solve(int argc, char* argv[])
{
 ...
 
 do
 {
  // Get next sequence of the riddle...

  bValidData = NextSequence();


  // Check hints...

  nHintValue = VerifyingHints(WITH_BREAK_ON_ERROR);


  // Check keyboard entry

  ...

 } while (nHintValue!=0 && bValidData);


 ...
 
 return 0;
}

Now let me show you the function who verify the hints. It's the most important function in this project. This function check the hints. It returned 0 if all hints are OK. In this case the riddle was solved. Elsewhere the return-value is an error-code:

• If Bit1 (1) is set, hint 1 doesn't apply
• If Bit2 (2) is set, hint 2 doesn't apply
• If Bit3 (4) is set, hint 3 doesn't apply
• If Bit4 (8) is set, hint 4 doesn't apply
• etc.

We use the classes member-functions to check hint by hint. Let me explain the first hint:

1.) the Brit lives in the red house

pHouse = GetHouse(BRIT) give you the pointer of the house whos person is a brit. After that you use the member-function of the house to get the attribute color and to check the value. if (pHouse->GetColor() != RED) Easy isn't it?

unsigned int CEinsteinsRiddle::VerifyingHints(BOOLEAN BreakOnError)
{
 //

 // Veryfying hints...

 //

 
 CHouse * pHouse;
 unsigned int returnValue=0;
 unsigned int index=1;
 

 //  1.) the Brit lives in the red house

 if((pHouse = GetHouse(BRIT))!=NULL)
 { if (pHouse->GetColor() != RED)
  { returnValue+=index;
   if (BreakOnError)
    return returnValue;
  }
 }
 index = index*2;

 //  2.) the Swede keeps dogs as pets

 if((pHouse = GetHouse(SWEDE))!=NULL)
 { if (pHouse->GetPerson()->GetPet() != DOG)
  { returnValue+=index;
   if (BreakOnError)
    return returnValue;
  }
 }
 index = index*2;

 //  3.) the Dane drinks tea

 if((pHouse = GetHouse(DANE))!=NULL)
 { if (pHouse->GetPerson()->GetBaverage() != TEA)
  { returnValue+=index;
   if (BreakOnError)
    return returnValue;
  }
 }
 index = index*2;

 //  4.) the green house is on the left of the white house

 if((pHouse = GetHouse(WHITE))!=NULL)
 { if (pHouse->GetNeighbouringHouseLeft() != GetHouse(GREEN))
  { returnValue+=index;
   if (BreakOnError)
    return returnValue;
  }
 }
 index = index*2;

 //  5.) the green house's owner drinks coffee

 if((pHouse = GetHouse(GREEN))!=NULL)
 { if (pHouse->GetPerson()->GetBaverage() != COFFEE)
  { returnValue+=index;
   if (BreakOnError)
    return returnValue;
  }
 }
 index = index*2;

 //  6.) the person who smokes Pall Mall rears birds 

 if((pHouse = GetHouse(PALLMALL))!=NULL)
 { if (pHouse->GetPerson()->GetPet() != BIRD)
  { returnValue+=index;
   if (BreakOnError)
    return returnValue;
  }
 }
 index = index*2;

 //  7.) the owner of the yellow house smokes Dunhill 

 if((pHouse = GetHouse(YELLOW))!=NULL)
 { if (pHouse->GetPerson()->GetCigar() != DUNHILL)
  { returnValue+=index;
   if (BreakOnError)
    return returnValue;
  }
 }
 index = index*2;

 //  8.) the man living in the center house drinks milk 

 if((pHouse = GetHouse(NR3))!=NULL)
 { if (pHouse->GetPerson()->GetBaverage() != MILK)
  { returnValue+=index;
   if (BreakOnError)
    return returnValue;
  }
 }
 index = index*2;

 //  9.) the Norwegian lives in the first house 

 if((pHouse = GetHouse(NR1))!=NULL)
 { if (pHouse->GetPerson()->GetNationality() != NORWEGIAN)
  { returnValue+=index;
   if (BreakOnError)
    return returnValue;
  }
 }
 index = index*2;

 // 10.) the man who smokes blends lives next to the one who keeps cats 

 if((pHouse = GetHouse(BLENDS))!=NULL)
 { if ((pHouse->GetNeighbouringHouseLeft()->GetPerson()->GetPet() != CAT) 
    && (pHouse->GetNeighbouringHouseRight()->GetPerson()->GetPet() != CAT))
  { returnValue+=index;
   if (BreakOnError)
    return returnValue;
  }
 }
 index = index*2;

 // 11.) the man who keeps horses lives next to the man who smokes Dunhill 

 // or   the man who smokes Dunhill lives next to the man who keeps horses

 if((pHouse = GetHouse(DUNHILL))!=NULL)
 { if ((pHouse->GetNeighbouringHouseLeft()->GetPerson()->GetPet() != HORSE) 
    && (pHouse->GetNeighbouringHouseRight()->GetPerson()->GetPet() != HORSE))
  { returnValue+=index;
   if (BreakOnError)
    return returnValue;
  }
 }
 index = index*2;

 // 12.) the owner who smokes BlueMaster drinks beer 

 if((pHouse = GetHouse(BLUEMASTER))!=NULL)
 { if (pHouse->GetPerson()->GetBaverage() != BEER)
  { returnValue+=index;
   if (BreakOnError)
    return returnValue;
  }
 }
 index = index*2;

 // 13.) the German smokes Prince 

 if((pHouse = GetHouse(GERMAN))!=NULL)
 { if (pHouse->GetPerson()->GetCigar() != PRINCE)
  { returnValue+=index;
   if (BreakOnError)
    return returnValue;
  }
 }
 index = index*2;

 // 14.) the Norwegian lives next to the blue house 

 if((pHouse = GetHouse(BLUE))!=NULL)
 { if ((pHouse->GetNeighbouringHouseLeft()->GetPerson()->GetNationality() 
    != NORWEGIAN) && 
   (pHouse->GetNeighbouringHouseRight()->GetPerson()->GetNationality() 
    != NORWEGIAN))
  { returnValue+=index;
   if (BreakOnError)
    return returnValue;
  }
 }
 index = index*2;

 // 15.) the man who smokes blends has a neighbor who drinks water

 if((pHouse = GetHouse(BLENDS))!=NULL)
 { if ((pHouse->GetNeighbouringHouseLeft()->GetPerson()->GetBaverage() 
    != WATER) && 
    (pHouse->GetNeighbouringHouseRight()->GetPerson()->GetBaverage()
    != WATER))
  { returnValue+=index;
   if (BreakOnError)
    return returnValue;
  }
 }
 index = index*2;

 return returnValue;
}

I hope you've understand my tutorial. If so, I'm happy and wish you kind regards...

Manfred...

Beware of my english translation, I'm a german writer!

Revision History

• December 9, 2003, Initial version.