解决爱因斯坦谜题的机器方法（修订版）
本文介绍了一种使用暴力搜索快速解决爱因斯坦谜题的方法。
引言
我在 Manfred Becker 的文章 Einstein's riddle solved in C++ 中发现了这个有趣的谜题。于是我急忙运行了他的代码，想快速得到答案。然而，屏幕上几分钟都没有出现解决方案，我不得不退出，然后回到源代码中寻找线索。我发现了一个时间表，上面写着在 700MHz Pentium III 上需要 2 天 19 小时 24 分钟！
虽然我理解 Becker 的解决方案只是为了展示面向对象的设计，但我认为对于我们这些没耐心的人来说，有一个快速的解决方案会更好。
为了方便参考和内容的完整性，这里附上谜题原文
爱因斯坦的谜题
- 一排有五栋房子，每栋房子颜色都不同。
- 每栋房子里住着一个不同国籍的人。
- 这五位主人喝一种特定的饮料，抽一种特定的香烟品牌，养一种特定的宠物。
- 所有主人都不拥有相同的宠物，不抽相同的香烟品牌，也不喝相同的饮料。
问题是：谁养了鱼？
爱因斯坦的线索
- 英国人住在红房子里。
- 瑞典人养狗作为宠物。
- 丹麦人喝茶。
- 绿房子在白房子正左边。
- 绿房子主人喝咖啡。
- 抽 Pall Mall 的人养鸟。
- 黄房子主人抽 Dunhill。
- 住在中间房子里的人喝牛奶。
- 挪威人住在第一栋房子里。
- 抽 Blends 的人住在养猫的人旁边。
- 养马的人住在抽 Dunhill 的人旁边。
- 抽 BlueMaster 的主人喝啤酒。
- 德国人抽 Prince。
- 挪威人住在蓝房子旁边。
- 抽 Blends 的人有一个喝水的邻居。
类设计考量
爱因斯坦谈论了房子和人。很自然地，我们需要一个房子类 (CHouse) 和一个人类 (CPerson)，就像 Becker 那样。然而，如果你更深入地思考这些类之间的关系，你会发现它们是一对一的关系。人们经常谈论房主。那么为什么我们不只为他们设置一个类呢？当然，我们可以将一个人视为房子的所有者，同时也将一个人视为房子里的一个属性 :)。
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; }
};
很简单，对吧？CHouse 只有一个数据成员 m_property，它是一个按类别 (CatID) 索引的数组，用于存放 5 种属性。CHouse 对象是自包含的，它不知道它的邻居。我们都知道狗是宠物，啤酒是饮料。为了满足用户的需求，CHouse 通过其成员函数 GetCatID(PropID pid) 和 PropID 的组合定义来理解这种类型关系。
让我们转向问题的另一部分，即线索，它们描述了属性和所有者之间的关联。我们需要一个类来表示这些线索。我敢打赌，你一眼就会注意到这些线索差异很大。显然，我们不会得到一个像 CHouse 这样简单的统一类。好吧，我们将通过抽象和派生来解决这些差异。
那么，所有线索的共同点是什么呢？它们都至少涉及一个属性和一个可能的该属性的所有者。因此，我们将线索命名为一个基类 CHint，并使其有两个数据成员 m_pid0 和 m_pNewOwner，分别代表属性和可能的拥有者。CHint 对象还需要访问任何 CHouse 对象，因为其中的属性 (m_pid0) 可以被任何符合线索的房主拥有。我们在 CHint 中以静态数据成员的形式放置了一个包含 5 个 CHouse 对象的数组。在我们继续讨论 CHint 的成员函数之前，请看它的蓝图。
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();
};
它有三个纯虚函数，使得 CHint 成为一个抽象类。正如 CHouse 对象不知道它的邻居一样，CHint 对象也不应该知道其他 CHint 对象，以保持事情的简单性。但是 CHint 对象应该有一个方法来查找所有符合该线索要求的房子。它不必一次性返回所有可能的房主列表。相反，我们希望它一次找到一个房主 (m_pNewOwner) 来匹配其属性 (m_pid0)，并按顺序进行。这可以提供更好的整体效率，因为内存流量更少。这三个虚函数正好满足了这一需求。
AssignPropToNextEligibles()查找下一个匹配的房主，并将属性分配给他。数据成员m_pNext用于让AssignPropToNextEligibles()知道在哪里恢复其工作。RemovePropFromPrevEligibles()用于撤销AssignPropToNextEligibles()所做的属性分配，以便我们可以再次调用AssignPropToNextEligibles()来查找另一个房主。- 最后一个虚函数
ResetSeekPosition()是一个用于将搜索位置重置到起点的接口。
这些纯虚函数可以被视为占位符和规范。任何派生自 CHint 的类仍然必须实现这三个函数。
CHint 中包含了静态数据成员 propowner 及其函数 GetPropertyOwner 和 RegisterOwnership，以便于访问任何属性的拥有者。该数据成员和这两个函数是属性分类账的实现，因此我们可以避免每次需要知道谁拥有特定属性时都进行线性搜索。
静态函数 VerifyCurrentSolution 和 PrintOut 分别用于验证和打印解决方案，从概念上讲，它们与 CHint 类关系不大。我将它们包含在这里只是因为它们也需要访问这五栋房子。如果我在 OOP 设计方面是个原教旨主义者，我可能会把它们踢出去，而是提供只读服务。
现在我们可以从 CHint 派生类了。线索 8 和 9 只涉及基类已提供的单个属性。但它们每个都有一个已知的房子编号。所以我们这样定义类：
// 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(); }
};
其余的线索涉及两个属性，它们可以由不同的拥有者拥有。我们通过派生 CMultiPropertiesHint 类来反映这种差异。
// 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 仍然是进一步派生的抽象基类，尽管它提供了一些有用的服务。
有些线索只涉及单个房主，例如线索 1。CSingleHouseHint 从 CMultiPropertiesHint 派生，用于处理这些线索。
// 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(); }
};
有些线索涉及两个房主，例如线索 15。CNeighborsHint 从 CMultiPropertiesHint 派生，用于处理这些线索。
// 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;
}
};
线索 4 也提到了两栋房子。但这两栋房子必须是顺序排列的。我们只有这一个实例，但我们必须为它派生一个类来完成 CHint 类家族。
// 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(); }
};
我在这里省略了这些类的实现。你可以在源代码文件中找到它们。
既然谜题现在可以用一组 CHint 对象和一组 CHouse 对象来很好地表示，让我们通过定义一个 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 在一个指向 CHint 对象的指针静态数组中封装了这 15 条线索。在实现文件中，我们只需一步创建这些对象并初始化数组。
// 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
};
现在 CSolver 可以使用指向 CHint 对象的指针进行工作，并忽略这些对象之间的差异。CSolver 有一个单一的公共接口函数 DoTheWork()，它将被 main() 函数调用。DoTheWork() 将实际工作委托给 Search 函数。
暴力搜索
下面是穷举 Search 函数的一个简化版本。
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();
}
}
正如你所看到的，Search 是一个递归函数。它尝试为当前线索找到匹配项。如果找到了匹配项，它会调用自身来处理下一条线索，前提是当前线索不是最后一条，此时它会打印出解决方案，并继续搜索。如果它完成了查找所有可能的匹配项，或者未能找到任何匹配项，它就会将控制权返回给上一条线索。
DoTheWork() 将以 index_of_hint = 0 开始第一次调用。
性能
在以前的版本中，当使用标准的 clock() 进行计时时，它在 1.6GHz P4 上需要 0.016 秒，在 166MHz Pentium MMX 上需要 0.056 秒。
当前版本使用高分辨率性能计数器来获得更精确的结果。然而，不同的运行时会话仍然显示出相当大的时间差异。一点点的性能分析表明，程序超过 80% 的时间花在打印解决方案上！我不得不对绘图代码进行一些优化，以减少差异。经过这些调整后，在 2.60GHz P4 上只需 0.0014 秒。
无论如何，这比我预期的要快得多。现在我认为一台旧的 8086 也可以轻松破解这个谜题。可惜我找不到一台。
更新
如果我们能通过玩这个程序来更深入地了解这个谜题，那将很有趣。这里有一些。
线索 15 被证明是冗余的，因为在将其从线索列表中注释掉后，会产生完全相同的解决方案。我们也可以去掉线索 5，让那些喜欢纸笔计算的人更有挑战性。
版本 1.04 (2003/12/23) 中的一些调整使得在列表中添加或删除线索更加容易。
版本 1.05 (2013/10/25) 增加了 UNICODE 支持；同时发布了 C# 移植源代码，并附带更新的 C++ 代码。