C++博客-hainan-最新评论

re: 读书的时光

nan — Sun, 06 May 2007 15:24:00 GMT

看了，《律政俏佳人》后，感觉生活又充满了激情，好想像篇中的女主人公那样生活，生命诸多挑战、、、、、、我当时看的时候简直是愤青一个。
、、、、、、
人大概都是这样，非得有外物刺激，才开始又一次励志，即使到头来是枉然。
于是开始抱怨时运的不济，命途多舛倒好，好歹终日有事可做。

nan 2007-05-06 23:24 发表评论

re: 世界上最难的一道题！

小新新 — Sat, 05 May 2007 11:50:00 GMT

德国人养金鱼咯!

小新新 2007-05-05 19:50 发表评论

re: 读书的时光

Hainan's CppBlog — Sun, 29 Apr 2007 05:07:00 GMT

糜烂的生活依然继续，
我已是焦头烂额。
几千次的痛下决心，
终于练就了嘴上功夫。
或是干脆让糜烂肆恣，
也落得个自在。
、、、、、、
躲进被窝成一统，
管他春夏与秋冬。

Hainan's CppBlog 2007-04-29 13:07 发表评论

re: 生活的磨砺啊(1)

雪个驴 — Sun, 29 Apr 2007 04:47:00 GMT

有感于今日之人民医院的全数字化......
以前有个什么头疼脑热的就去附近的诊所，叫什么什么堂的。出门便是，方便快捷。自来广东上学之后越发觉自己是乡里娃了，
这里竟没有私人诊所（这样说未免有些夸张，据说是有，但不是给人看的），动不动就以什么院啊站啊的标榜，听起来好生气派，但
对于来自消费水平低的地方的人来说大都是不怎么敢进的。
一日鄙人抱恙，多半觉得的是肠胃炎，这已是旧疾。本想去学校的医疗室看看算了，花上几十块。不料男友见我神情痛苦，眉头
紧锁的已不见五官，执意拉我去某某人民闪医院。嚇！我脑子里顿时一阵闪算，妈呀，好几百块啊，这足足是我一个月的伙食费啊。
脸上稍露难色，但还是去了,真是死要面子活受罪。
到了医院门口，他搀着我，我手捂着肚子，挪进了赫然写着急诊的地方。哇，简直是门庭若市，看来老百姓还是“信任”规格化、
正统化的东西，似乎从那里出出进进的也比较有面子。进去有个保安站在门口，这就着实让我了没了安全感（我向来对穿制服的没什么
好感）。先是填了个有关个人资料的单子，然后我找了个位子坐下，他站在一个很长很长的队的队尾，领了一张医疗卡，卡上是个人
资料交些钱方可就医。我们很费周折的找到了医生的栖地，又得排队，当然队是要排的，命可以不要，规章制度却是要的，在中国，
如果。

我强忍着剧痛，其他患者看着我的表情面无表情，医生就更不用说了，简单的问过症状，就开了方子，在电脑上点了几下就完成了
全部过程。古时不是有望、闻、问、切，难道时至今日，有了先进的检测仪器就不需要了吗？轮到我时，问倒是做到了，我对他说可能
是肠胃炎，当然我不是有扰医生“专业”的判断，只是就我以前的病历经验看。但他置若罔闻，因为他是医生。于是让我做尿检、血检，
对此我不能说什么。以为可以直接做完了事，没想又要跑到楼下在不同的窗口，同样又在长长的队尾，交钱方可进行治疗的下一环节，
我没跟着去，我已经是步履维艰了，一个人捂着肚子蹲在角落，每一个路过我身边的人都知道我脸上是快要死的表情。好怀念家对面的诊
所啊，此时。医生会根据轻重缓急诊治。做完了化验之后竟然完全正常，真希望出点什么事，应一下的医生的话。我惊呼，惊呼那位业内
资深的主治医生说这个没问题的话，那就是肠胃炎了。天啊，他把看病当做是在用排除法做题吗？照这样人人都可以做医生，挂牌上岗。
这还能为我国解决不少就业问题呢，但可能犯罪率就要上升了。我当时想啐他两口，简直无异于江湖术士，如果说医院是一坨屎，那医
生就是那坨屎上的苍蝇。他们跟他们身上穿的白大褂一样麻木、冷酷与无能。
但凡大医院，先不管什么病，先让你做化验、CT、B超，让你把什么引进国际先进治疗仪用个遍，当然这时你的钱也花的差不多了，
走的话已经花费不菲了，不走又的受宰割，唉！
接下来就是注射了，这总该顺利点吧。可医务人员告诉我们必须去对面的那个急诊室注射。此时我已毫无耐心，想一走了知，死就死了。
可是已经花了钱了，于是乎男友又搀着我走出了医疗室，医院的中央有花园、长椅，痛使我不能抬头，我的眼皮微微抬起，瞟了一下，人
们倒挺惬意。他为了逗我就说，你看我搀着你，你又捂着肚子，别人还以为你、、、、、、怀孕了呢，我想骂他，但嘴憋不住笑，扑哧全出来了。
他呢还是得排队交钱，我的天，又要跑回刚才那个急诊区的窗口。。已经好几个小时过去了，病还没治医院就先把人弄死了。
我终于算是躺在了注射的椅子上，已经是在注射止痛药了，但好像没丝毫起色，痛就这样开始肆恣，于是又叫来另一位医生，他倒是很快诊断
我是肠痉挛，唉，本来是很轻的病情，硬是给这一整套数字化系统拖严重了。又于是又注射2针阿托品、、、、、、
我有点晕呼呼的了、、、、、、
我发誓死也不来这鬼地方了，现代社会不是什么数字化都好的。我拿着厚厚的医疗单，作为明天向我妈申报伙食费的凭证。我走出医院，回头看看，
依旧门庭若市，中国人，搞不明白。

雪个驴 2007-04-29 12:47 发表评论

re: 最近上课不用心

Hainan's CppBlog — Tue, 24 Apr 2007 04:48:00 GMT

@江水兽
你是学电子的啊？

Hainan's CppBlog 2007-04-24 12:48 发表评论

re: 最近上课不用心

江水兽 — Tue, 24 Apr 2007 04:03:00 GMT

有同感！
估计可能是由于这学期的几门专业课有点难学：电子线路电磁场理论。所以要认真和努力！共勉了！

江水兽 2007-04-24 12:03 发表评论

re: 世界上最难的一道题！

Hainan's CppBlog — Wed, 28 Mar 2007 07:02:00 GMT

@pengkuny
#include
#include
#include

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

这是看得懂的实现

Hainan's CppBlog 2007-03-28 15:02 发表评论

re: 世界上最难的一道题！

pengkuny — Tue, 20 Mar 2007 08:16:00 GMT

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.

pengkuny 2007-03-20 16:16 发表评论

re: 世界上最难的一道题！

Hainan's CppBlog — Mon, 19 Mar 2007 05:23:00 GMT

答对啦！

Hainan's CppBlog 2007-03-19 13:23 发表评论

re: 世界上最难的一道题！

小豆子 — Sun, 18 Mar 2007 14:20:00 GMT

德国人养鱼

小豆子 2007-03-18 22:20 发表评论