爱因斯坦的谜题用 C++ 解决

ManiB

4.60/5 (29投票s)

2003年12月9日

CPOL

5分钟阅读

108634

1267

使用 C++ 解决爱因斯坦谜题的教程

下载源文件 - 39.9 Kb

引言

爱因斯坦在上个世纪写了一个谜题。他说世界上98%的人都无法解开它。

爱因斯坦的谜题

有五个不同颜色的房子
每栋房子里住着一个不同国籍的人。
这五位主人喝一种特定的饮料，抽一种特定的香烟品牌，养一种特定的宠物。
所有主人都不拥有相同的宠物，不抽相同的香烟品牌，也不喝相同的饮料。

问题是：谁养了鱼？

爱因斯坦的提示

1.) 英国人住红房子
2.) 瑞典人养狗作为宠物
3.) 丹麦人喝茶
4.) 绿房子在白房子左边
5.) 绿房子主人喝咖啡
6.) 抽 Pall Mall 的人养鸟
7.) 黄房子主人抽 Dunhill
8.) 住在中间房子的人喝牛奶
9.) 挪威人住第一间房子
10.) 抽 Blends 的人住在养猫的人旁边
11.) 养马的人住在抽 Dunhill 的人旁边
12.) 抽 BlueMaster 的主人喝啤酒
13.) 德国人抽 Prince
14.) 挪威人住在蓝房子旁边
15.) 抽 Blends 的人有一个喝水的朋友

解决方案

当然，你可以自己解决这个谜题，网上也会有很多提供提示和解决方案的网页。但在这里，我将教你如何使用 C++ 来解决这个问题。这是为初学者准备的，将展示如何处理一个问题并将其改编为面向对象编程。

教程

定义类

爱因斯坦谈到了房子和人。所以我们需要一个定义房子的类 (CHouse) 和一个定义人的类 (CPerson)。所有其他东西（如颜色、国籍、饮料……）都是这些类的一个属性。然后我们需要一个类来处理谜题本身 (CEinsteinsRiddle)，来处理提示并解决谜题。让我们从给定的属性开始。我们使用枚举来处理它们。

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    };

为了使这些值可打印，我们需要一些文本。

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  " };

还有爱因斯坦提示的文本。

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"
};

现在我们来看定义人的类。每个人都有国籍、饮料、香烟和宠物。所有这些都是人的属性，所以定义这个类非常容易。

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;         };
};

这是类的构造函数和析构函数。

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

CPerson::~CPerson(void)
{
};

现在我们来定义房子的类。每栋房子都有房号和颜色。然后我们需要一个指向住在房子里的人的指针。我们还需要一个指向左邻居和右邻居的指针，因为我们需要检查提示，例如（4. 绿房子在白房子左边）。

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;  };
};

由于房号和人在这整个谜题过程中都不会改变，所以我们不需要设置它们的函数。构造函数应该为我们处理这个问题。

这是类的构造函数和析构函数。

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;
}

好的！我觉得这很简单。但是现在我们必须考虑谜题的类。嗯，我认为很明显，我们将使用一个房子集合，因为我们需要五个房子。第一个房子左边的邻居和最后一个房子右边的邻居需要一个虚拟房子。需要一些函数来获取房子的值。
为了存储属性，我们还需要一些成员变量。

然后我们需要构造函数、析构函数以及一个初始化数据的函数“Initialize”。
为了打印出结果，我们还需要一个“PrintOut”函数。这个程序应该通过测试所有可能性来“Solve”谜题，并通过“VerifyingHints”来验证提示。但这些可能性是什么呢？嗯，当你有 N 个事物（例如，数字 1、2、3、4 和 5）时，将它们排列成一个顺序就有 fact(5) = 1x2x3x4x5 = 120 种可能性。
这些序列如下所示。

{ 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 }

我们所要做的就是创建一个数据字段来表示这些序列值。之后，您可以遍历这些值。因为我们需要遍历颜色、国籍、饮料、香烟和宠物，所以我们需要一个“NextSequence”函数来迭代，以及一个函数来设置序列数据“SetSequence”。

就这样！这是谜题类的定义。

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[]);
};

我们完成了。现在我们来谈谈主程序。它非常简单。首先，我们创建一个谜题的实例，然后让它解决问题。

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

 return EinsteinsRaetsel.Solve(argc, argv);
}

解决问题的函数会逐个序列地验证提示。这应该一直进行，直到用户中断或谜题被解决。

这是源代码的摘录。

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;
}

现在让我向您展示验证提示的函数。这是本项目中最重要的函数。此函数检查提示。如果所有提示都正确，则返回 0。在这种情况下，谜题已解决。否则，返回值是一个错误代码。

如果设置了 Bit1 (1)，则提示 1 不适用
如果设置了 Bit2 (2)，则提示 2 不适用
如果设置了 Bit3 (4)，则提示 3 不适用
如果设置了 Bit4 (8)，则提示 4 不适用
等等。

我们使用类的成员函数来逐个提示地检查。让我解释第一个提示。

1.) 英国人住红房子

pHouse = GetHouse(BRIT) 返回居住者是英国人的房子的指针。之后，您可以使用房子的成员函数来获取颜色属性并检查值。if (pHouse->GetColor() != RED) 很简单，不是吗？

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;
}

我希望您已经理解了我的教程。如果理解了，我很高兴，并致以诚挚的问候……

Manfred…

请注意我的英文翻译，我是一个德国作者！

修订历史

2003 年 12 月 9 日，初始版本。