Click here to Skip to main content
15,868,164 members
Articles / Desktop Programming / MFC
Article

Einstein's riddle solved in C++

Rate me:
Please Sign up or sign in to vote.
4.60/5 (33 votes)
8 Dec 2003CPOL5 min read 106.6K   1.3K   39   16
Tutorial to solve Einstein's riddle using C++

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.

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)


Written By
Web Developer
Germany Germany
This member has not yet provided a Biography. Assume it's interesting and varied, and probably something to do with programming.

Comments and Discussions

 
GeneralMy vote of 5 Pin
Manikandan1024-Jun-14 22:26
professionalManikandan1024-Jun-14 22:26 
GeneralVery useful Pin
darkking12321-Apr-11 20:36
darkking12321-Apr-11 20:36 
GeneralRe: Very useful Pin
ManiB22-Apr-11 1:43
ManiB22-Apr-11 1:43 
GeneralRe: Very useful Pin
darkking12322-Apr-11 2:15
darkking12322-Apr-11 2:15 
GeneralMy vote of 5 Pin
darkking12315-Apr-11 22:21
darkking12315-Apr-11 22:21 
GeneralMaybe an New Idea Pin
haritail3-Feb-04 20:33
haritail3-Feb-04 20:33 
GeneralRe: Maybe an New Idea Pin
ManiB4-Feb-04 9:45
ManiB4-Feb-04 9:45 
Hello,

it's a very interestring idea, solving the riddle. If you think your solution works than post it and share your experience.

The main intension of my toturial is 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.

For a realy quick solution please have a look to
the article of Dezhi Zhao:
Machine Solution to Einstein's Riddle Revisited
http://www.codeproject.com/cpp/Einstein.asp

Thanks for your hint, and have funSmile | :)

Manfred Becker

GeneralRe: Maybe an New Idea Pin
ManiB9-Feb-04 4:11
ManiB9-Feb-04 4:11 
GeneralCool! Pin
soichih15-Dec-03 4:10
soichih15-Dec-03 4:10 
Generalnot very flexible Pin
Michel Wassink11-Dec-03 22:10
Michel Wassink11-Dec-03 22:10 
GeneralRe: not very flexible Pin
ManiB11-Dec-03 22:35
ManiB11-Dec-03 22:35 
GeneralAhh yes... Pin
Nitron10-Dec-03 16:09
Nitron10-Dec-03 16:09 
Generaltoo wide Pin
funny thing9-Dec-03 12:02
funny thing9-Dec-03 12:02 
QuestionThis Century? Pin
Tim Craig9-Dec-03 9:25
Tim Craig9-Dec-03 9:25 
AnswerHeh... Pin
dog_spawn9-Dec-03 11:18
dog_spawn9-Dec-03 11:18 
AnswerRe: This Century? Pin
ManiB9-Dec-03 21:14
ManiB9-Dec-03 21:14 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Praise Praise    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.