hainan

# re: 世界上最难的一道题！ 2007-03-18 22:20 小豆子

德国人养鱼  回复  更多评论   

# re: 世界上最难的一道题！ 2007-03-19 13:23 Hainan's CppBlog

答对啦！  回复  更多评论   

# re: 世界上最难的一道题！ 2007-03-20 16:16 pengkuny

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 :)

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

Collapse
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();
};
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 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(); }
};
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 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 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 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(); }
};
Some hints deal with two house owners, hint 15 for instance. CNeighborsHint is derived from CMultiPropertiesHint for those hints:

// 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;
}
};
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 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(); }
};
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 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 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:

Collapse
// 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
};
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(); // 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();
}
}
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.

  回复  更多评论   

# re: 世界上最难的一道题！ 2007-03-28 15:02 Hainan's CppBlog

@pengkuny
#include <iostream>
#include <string>
#include <fstream>

using namespace std;

int main(void)
{
string Title[5] = {"国籍","颜色","宠物","饮料","香烟"};
struct problem{
string nation;
string color;
string pet;
string drink;
string cigarette;
} House[5];//房子从左到右编号

House[0].nation = "挪威";//挪威人住在第一个房子里面
House[1].color = "蓝色";//挪威人和住在蓝房子的人相邻,即蓝房子是第2个房子
House[2].drink = "牛奶";// 住在中间那个房子里的人喝牛奶

for (int e=1; e<5; e++) //表示英国人的房子序号
for (int r=1; r<5; r++)//表示瑞典人的房子序号
for (int d=1; d<5; d++)//表示丹麦人的房子序号
for (int g=0; g<5; g++)//表示绿房子的序号
for (int p=0; p<5; p++)//表示抽Pall Mall牌香烟的人的房子序号
for (int y=0; y<5; y++)//表示黄色房子的序号
for (int b=0; b<5; b++)//表示喝啤酒人的房子序号
for (int h=0; h<5; h++)//表示养马的人的房子序号
for (int cat=0; cat<5; cat++)//表示养猫的人的房子序号
{
int Germany = 10 - 0 - e - r - d; //表示德国人的房子序号,德国人抽Prince牌香烟；
int Blends = 10 - p - y - b - Germany;//表示抽Blends牌香烟的人的房子序号
int white = 10 - 1 - e - g - y; //表示白房子的序号
int water = 10 - 2 - d - g - b; //表示喝矿泉水的人的房子序号
int fish = 10 - r - p - h - cat;//表示养鱼的人的房子序号

bool A1 = (e!=1); //英国人住在红色的房子里；根据房子和国家判断
bool A2 = (r!=e); //瑞典人养狗作为宠物；根据国家和宠物判断
bool A3 = (d!=e && d!=r && d!=2);//丹麦人喝茶；根据国家和饮料判断
bool A4 = (g!=1 && g!=2 && g!=e && g!=d);//绿房子的主人喝咖啡；根据颜色和饮料判断
bool A5 = (p!=r); //抽Pall Mall牌香烟的人养鸟；根据香烟和宠物判断
bool A6 = (y!=e && y!=1 && y!=g && y!=p);//黄色房子里的人抽Dunhill牌香烟；根据颜色和香烟判断
bool A7 = (b!=2 && b!=d && b!=g && b!=p && b!=y);//抽BlueMaster牌香烟的人喝啤酒；根据香烟和饮料判断
bool A8 = (h!=r && h!=p && (h==y+1 || h==y-1));//养马的人和抽Dunhill牌香烟的人相邻,根据香烟和宠物判断
bool A9 = (white == g + 1); //绿房子紧挨着白房子，在白房子的左边；
bool A0 = (cat==Blends-1 || cat==Blends+1);//Blends牌香烟的人和养猫的人相邻；
bool A11 = (water==Blends-1 || water==Blends+1);//抽Blends牌香烟的人和喝矿泉水的人相邻

if (A1 && A2 && A3 && A4 && A5 && A6 && A7 && A8 && A9 && A0 && A11)
{//把满足条件的序号填入结构数组
House[e].nation = "英国";
House[e].color = "红色";
House[r].nation = "瑞典";
House[r].pet = "狗";
House[d].nation = "丹麦";
House[d].drink = "茶";
House[g].color = "绿色";
House[g].drink = "咖啡";
House[p].cigarette = "Pall Mall";
House[p].pet = "鸟";
House[y].color = "黄色";
House[y].cigarette = "Dunhill";
House[b].cigarette = "BlueMaster";
House[b].drink = "啤酒";
House[h].pet = "马";
House[Germany].nation = "德国";
House[Germany].cigarette = "Prince";
House[Blends].cigarette = "Blends";
House[white].color = "白色";
House[water].drink = "矿泉水";
House[cat].pet = "猫";
House[fish].pet = "鱼";

goto end;
}
}
end:
for (int i=0; i<5; i++)
cout << Title[i] << "\t";
cout << endl << endl;

for (i=0; i<5; i++)
{
cout << House[i].nation << "\t";
cout << House[i].color << "\t";
cout << House[i].pet << "\t";
cout << House[i].drink << "\t";
cout << House[i].cigarette << "\t";
cout << endl;
}
//输出到文件
ofstream out("爱因斯坦的思考题.txt");
for (i=0; i<5; i++)
out << Title[i] << "\t";
out << endl << endl;

for (i=0; i<5; i++)
{
out << House[i].nation << "\t";
out << House[i].color << "\t";
out << House[i].pet << "\t";
out << House[i].drink << "\t";
out << House[i].cigarette << "\t";
out << endl;
}
out.close();

system("pause");
return 0;
}


这是看得懂的实现  回复  更多评论   

# re: 世界上最难的一道题！ 2007-05-05 19:50 小新新

德国人养金鱼咯!  回复  更多评论