爱因斯坦在20世纪初出的这个谜语,能用A*算法写出来！
以下的谜语能用A*算法算出来，请教算法代码。
爱因斯坦在20世纪初出的这个谜语。他说世界上有98％的人答不出来。
1、在一条街上，有5座房子，喷了5种颜色。
2、每个房里住着不同国籍的人
3、每个人喝不同的饮料，抽不同品牌的香烟，养不同的宠物
问题是：谁养鱼？
提示：
1、英国人住红色房子
2、瑞典人养狗
3、丹麦人喝茶
4、绿色房子在白色房子左面
5、绿色房子主人喝咖啡
6、抽Pall Mall 香烟的人养鸟
7、黄色房子主人抽Dunhill 香烟
8、住在中间房子的人喝牛奶
9、 挪威人住第一间房
10、抽Blends香烟的人住在养猫的人隔壁
11、养马的人住抽Dunhill 香烟的人隔壁
12、抽Blue Master的人喝啤酒
13、德国人抽Prince香烟
14、挪威人住蓝色房子隔壁
15、抽Blends香烟的人有一个喝水的邻居
问题点数：100、回复次数：33Top
1 楼top_lihai（冬虫夏草）回复于 2006-07-18 17:09:04 得分 0
请写出您的思路，代码。Top
2 楼Eddie005（♂) №.零零伍 (♂）回复于 2006-07-18 17:46:53 得分 0
有兴趣看别人的算法~~ 嘻嘻~~Top
3 楼chenhu_doc（^0^纯一狼^0^ 看书看到大笑，直到不能自已）回复于 2006-07-18 19:47:38 得分 0
恩，期待！。。。Top
4 楼yzwgh（大梦）回复于 2006-07-19 20:03:36 得分 0
德国人Top
5 楼zhh007（gogogo...upupup,aZaZaZa...........）回复于 2006-07-19 21:18:23 得分 0
mark!!Top
6 楼kerberos7（特立独行的猪）回复于 2006-07-19 22:13:22 得分 40
1 2 3 4 5
色
国
饮
烟
宠
----------------------------------
根据8,9,14得
1 2 3 4 5
色 蓝色
国 挪威
饮 牛奶
烟
宠
----------------------------------
根据4,5得四种情况
1 2 3 4 5
色 蓝色 绿色 白色
国 挪威
饮 牛奶 咖啡
烟
宠
1 2 3 4 5
色 绿色 蓝色 白色
国 挪威
饮 咖啡 牛奶
烟
宠
1 2 3 4 5
色 绿色 蓝色 白色
国 挪威
饮 咖啡 牛奶
烟
宠
1 2 3 4 5
色 绿色 蓝色 白色
国 挪威
饮 咖啡 牛奶
烟
宠
----------------------------------
第一种情况：根据1,7得,这样颜色的顺序确定下来了
1 2 3 4 5
色 黄色 蓝色 红色 绿色 白色
国 挪威 英国
饮 牛奶 咖啡
烟 Dun
宠
－－－－－－－－－－－－－－
第一种情况：根据11得
1 2 3 4 5
色 黄色 蓝色 红色 绿色 白色
国 挪威 英国
饮 牛奶 咖啡
烟 Dun
宠 马
－－－－－－－－－－－－－－
第一种情况：其它条件综合推理得
1 2 3 4 5
色 黄色 蓝色 红色 绿色 白色
国 挪威 丹麦 英国 德国 瑞典
饮 水 茶 牛奶 咖啡 酒
烟 Dun Blen Pall prin Blue
宠 猫 马 鸟 狗
得到德国人养鱼。
－－－－－－－－－－－－－－－－
其它情况可以得到其它结果。
如果用代码实现的话，我的想法是用二维数组存储int nArray[1-5][1-5]，每种属性都用数值１－５表示，枚举出所有可能，（假设英国人的值为1,红色的值也为１）条件“英国人住红色房子 ”可表示为：
for (i = 1; i <= 5; i++ )
{
if (nArray[2][i] == 1)
{
if (nArray[1][i] == 1)
条件满足
}
}
将满足所有条件的组合举出来就行了。
见笑了，这个是大体的思路，效率不会很高，希望牛人给个高级的算法Top
7 楼DelphiGuy（）回复于 2006-07-19 22:13:24 得分 0
5x5的矩阵，按条件添入，空缺的位置穷举验证就可以了。
Top
8 楼Sephiroth52（色色）回复于 2006-07-20 00:57:41 得分 0
这种问题好象可以用prologTop
9 楼liujiayu10（活着就好）回复于 2006-07-20 08:05:45 得分 0
牛Top
10 楼AlbortEinstein（爱因斯坦）回复于 2006-07-20 08:16:08 得分 0
我没出这样的题Top
11 楼LifeForCode（用生命编程.再入轮回(2007)）回复于 2006-07-20 08:21:16 得分 0
有意思Top
12 楼mLee79（）回复于 2006-07-20 08:37:03 得分 50
/*
* www.justJF.com / pure UP
*/
/*
[03/12-11:57:35]
当年爱因斯坦称全世界有98%的人做不出来！不过他肯定低估了人类进化的速度
1、在一条街上，有5座房子，喷了5种颜色。
2、每个房里住着不同国籍的人
3、每个人喝不同的饮料，抽不同品牌的香烟，养不同的宠物
问题是：谁养鱼？（所有的对应关系）
提示：
1、英国人住红色房子
2、瑞典人养狗
3、丹麦人喝茶
4、绿色房子在白色房子左面
5、绿色房子主人喝咖啡
6、抽Pall Mall 香烟的人养鸟
7、黄色房子主人抽Dunhill 香烟
8、住在中间房子的人喝牛奶
9、挪威人住第一间房
10、抽Blends香烟的人住在养猫的人隔壁
11、养马的人住抽Dunhill 香烟的人隔壁
12、抽Blue Master的人喝啤酒
13、德国人抽Prince香烟
14、挪威人住蓝色房子隔壁
15、抽Blends香烟的人有一个喝水的邻居
*/
#include <iostream>
#include <cassert>
using namespace std;
enum Color { Red, White, Green, Yellow, Blue };
enum People { Britain, Sweden, Danmark, Norway, Germany };
enum Drink { Tea, Coffee, Milk, Beer, Water };
enum Pet { Fish, Dog, Bird, Cat, Horse };
enum Smoke { PallMall, Dunhill, Blends, BlueMaster, Prince };
struct peopleInfo
{
People ppl;
Color clr;
Drink drk;
Pet pet;
Smoke smk;
};
static peopleInfo info[5];
/* */
inline int findPeo(People p)
{
for(int i=0; i < 5; ++i)
{
if(info[i].ppl == p) return i;
}
assert(false);
return -1;
}
/* */
inline int findClr(Color c)
{
for(int i=0; i < 5; ++i)
{
if(info[i].clr == c) return i;
}
assert(false);
return -1;
}
/* */
inline int findDrk(Drink d)
{
for(int i=0; i < 5; ++i)
{
if(info[i].drk == d) return i;
}
assert(false);
return -1;
}
/* */
inline int findPet(Pet p)
{
for(int i=0; i < 5; ++i)
{
if(info[i].pet == p) return i;
}
assert(false);
return -1;
}
/* */
inline int findSmk(Smoke s)
{
for(int i=0; i < 5; ++i)
{
if(info[i].smk == s) return i;
}
assert(false);
return -1;
}
/* */
inline bool cond1(void)
{ //!
return info[findPeo(Britain)].clr == Red;
}
/* */
inline bool cond2(void)
{ //!
return info[findPeo(Sweden)].pet == Dog;
}
/* */
inline bool cond3(void)
{ //!
return info[findPeo(Danmark)].drk == Tea;
}
/* */
inline bool cond4(void)
{ //!
return findClr(Green) + 1 == findClr(White);
}
/* */
inline bool cond5(void)
{ //!
return info[findClr(Green)].drk == Coffee;
}
/* */
inline bool cond6(void)
{
return info[findSmk(PallMall)].pet == Bird;
}
/* */
inline bool cond7(void)
{
return info[findClr(Yellow)].smk == Dunhill;
}
/* */
inline bool cond8(void)
{ //!
return info[2].drk == Milk;
}
/* */
inline bool cond9(void)
{ //!
return info[0].ppl == Norway;
}
/* */
inline bool cond10(void)
{
int n1=findSmk(Blends), n2=findPet(Cat);
return n1 - n2 == 1 || n1 - n2 == -1;
}
/* */
inline bool cond11(void)
{
int n1=findPet(Horse), n2=findSmk(Dunhill);
return n1 - n2 == 1 || n1 - n2 == -1;
}
/* */
inline bool cond12(void)
{
return info[findSmk(BlueMaster)].drk == Beer;
}
/* */
inline bool cond13(void)
{
return info[findPeo(Germany)].smk == Prince;
}
/* */
inline bool cond14(void)
{ //!
return info[1].clr == Blue;
}
/* */
inline bool cond15(void)
{
int n1=findSmk(Blends), n2=findDrk(Water);
return n1 - n2 == 1 || n1 - n2 == -1;
}
/* */
bool condOther(void)
{ //!( 9 ) ( 1 4 14 ) ( 3 5 8 ) ( 2 )
return cond6() && cond7() && cond10() && cond11() && cond12() && cond13() && cond15();
}
static int indexTab[120][5]; //!5! == 120.
/* */
void makeIndex(void)
{
int nIndex=0;
for(int a=0; a < 5; ++a)
{
for(int b=0; b < 5; ++b)
{
for(int c=0; c < 5; ++c)
{
for(int d=0; d < 5; ++d)
{
for(int e=0; e < 5; ++e)
{
if( a != b && a != c && a != d && a != e &&
b != c && b != d && b != e &&
c != d && c != e &&
d != e)
{
assert(nIndex < 120);
indexTab[nIndex][0]=a;
indexTab[nIndex][1]=b;
indexTab[nIndex][2]=c;
indexTab[nIndex][3]=d;
indexTab[nIndex][4]=e;
++nIndex;
}
}
}
}
}
}
assert(nIndex == 120);
}
const char *szPeo[]={ "Bri", "Swe", "Dan", "Nor", "Ger" };
const char *szClr[]={ "Red", "Wht", "Grn", "Yel", "Blu" };
const char *szDrk[]={ "Tea", "Cof", "Mil", "Bee", "Wat" };
const char *szPet[]={ "Fis", "Dog", "Bir", "Cat", "Hor" };
const char *szSmk[]={ "Pal", "Dun", "Ble", "Blu", "Pri" };
/* */
void showAnser(int a, int b, int c, int d, int e)
{
int i;
cout << "Peo : ";
for(i=0; i < 5; ++i) cout << szPeo[indexTab[a][i]] << ' ';
cout << endl << "Clr : ";
for(i=0; i < 5; ++i) cout << szClr[indexTab[b][i]] << ' ';
cout << endl << "Drk : ";
for(i=0; i < 5; ++i) cout << szDrk[indexTab[c][i]] << ' ';
cout << endl << "Pet : ";
for(i=0; i < 5; ++i) cout << szPet[indexTab[d][i]] << ' ';
cout << endl << "Smk : ";
for(i=0; i < 5; ++i) cout << szSmk[indexTab[e][i]] << ' ';
cout << endl;
}
/* */
int main(void)
{
makeIndex();
int a, b, c, d, e, i;
for(a=0; a < 120; ++a)
{
//cout << "Process a == " << a << endl;
for(i=0; i < 5; ++i) info[i].ppl=(People) indexTab[a][i];
if(!cond9()) continue;
for(b=0; b < 120; ++b)
{
for(i=0; i < 5; ++i) info[i].clr=(Color) indexTab[b][i];
if(!cond14() || !cond1() || !cond4()) continue;
for(c=0; c < 120; ++c)
{
for(i=0; i < 5; ++i) info[i].drk=(Drink) indexTab[c][i];
if(!cond8() || !cond3() || !cond5()) continue;
for(d=0; d < 120; ++d)
{
for(i=0; i < 5; ++i) info[i].pet=(Pet) indexTab[d][i];
if(!cond2()) continue;
for(e=0; e < 120; ++e)
{
for(i=0; i < 5; ++i) info[i].smk=(Smoke) indexTab[e][i];
if(condOther())
{
showAnser(a, b, c, d, e);
}
}
}
}
}
}
return 0;
}
Top
13 楼CXXSoft（西部阿呆）回复于 2006-07-20 08:48:54 得分 0
哎,迟了,本人在2004年就完成了一个Delphi版本的算法,只是一直没有公开算法,结果,被人抢先了.
Top
14 楼cbo5（）回复于 2006-07-20 08:57:39 得分 0
markTop
15 楼bbdx2523（模二战士）回复于 2006-07-20 08:58:06 得分 0
答案是不是有两个的?
我推算出来是两个答案Top
16 楼LuoZhiWei2008（追梦）回复于 2006-07-20 09:04:05 得分 0
mark
Top
17 楼netdust（静时常思己过，闲谈勿论人非）回复于 2006-07-20 09:06:38 得分 0
厉害，呵呵～～Top
18 楼xiaoxiao1984（笨猫儿）回复于 2006-07-20 09:33:59 得分 0
多解，呵呵Top
19 楼Nowish（看我能忍耐多久）回复于 2006-07-20 09:50:07 得分 0
我是来拜高人的~Top
20 楼staffhc（看喽才晓得）回复于 2006-07-20 10:24:36 得分 0
MARKTop
21 楼top_lihai（冬虫夏草）回复于 2006-07-20 11:17:37 得分 0
我不禁希望有代码，而且希望有思路，最好是自己想出来的，本来想给kerberos7(特立独行的猪)和mLee79() 分的，可是给了就结贴了。我还想继续寻找算法和思路。另外代码最好是C或者C++的，java的也行。Top
22 楼top_lihai（冬虫夏草）回复于 2006-07-20 11:19:14 得分 0
另外，现在也不一定非得要求是A*算法，其他算法也行，但是最好是A*算法写出来的。Top
23 楼hax123（Anson）回复于 2006-07-20 11:35:14 得分 0
markTop
24 楼huitouren519（细节决定成败）回复于 2006-07-20 12:02:36 得分 0
markTop
25 楼universes（及时揭帖是一种美德 | CSDN也这么黑）回复于 2006-07-20 12:14:41 得分 0
markTop
26 楼YFY（天易）回复于 2006-07-20 12:33:07 得分 0
不标记不行。Top
27 楼IBetter（软件文盲）回复于 2006-07-20 12:53:41 得分 0
关注！Top
28 楼BlueDestiny（Design Life - never-online.net）回复于 2006-07-20 13:24:13 得分 0
留个记号...Top
29 楼rachellui（IVG）回复于 2006-07-20 14:36:51 得分 0
真的好强Top
30 楼janwang2000（不是终点）回复于 2006-07-20 15:05:49 得分 0
mark:)Top
31 楼livehome（）回复于 2006-07-20 15:39:58 得分 0
markTop
32 楼hax123（Anson）回复于 2006-07-20 15:44:45 得分 10
#include <iostream>
#include <cassert>
using namespace std;
enum Color { Red, White, Green, Yellow, Blue };
enum People { Britain, Sweden, Danmark, Norway, Germany };
enum Drink { Tea, Coffee, Milk, Beer, Water };
enum Pet { Fish, Dog, Bird, Cat, Horse };
enum Smoke { PallMall, Dunhill, Blends, BlueMaster, Prince };
struct peopleInfo
{
People ppl;
Color clr;
Drink drk;
Pet pet;
Smoke smk;
};
static peopleInfo info[5];
/* */
inline int findPeo(People p)
{
for(int i=0; i < 5; ++i)
{
if(info[i].ppl == p) return i;
}
assert(false);
return -1;
}
/* */
inline int findClr(Color c)
{
for(int i=0; i < 5; ++i)
{
if(info[i].clr == c) return i;
}
assert(false);
return -1;
}
/* */
inline int findDrk(Drink d)
{
for(int i=0; i < 5; ++i)
{
if(info[i].drk == d) return i;
}
assert(false);
return -1;
}
/* */
inline int findPet(Pet p)
{
for(int i=0; i < 5; ++i)
{
if(info[i].pet == p) return i;
}
assert(false);
return -1;
}
/* */
inline int findSmk(Smoke s)
{
for(int i=0; i < 5; ++i)
{
if(info[i].smk == s) return i;
}
assert(false);
return -1;
}
/* */
inline bool cond1(void)
{ //!
return info[findPeo(Britain)].clr == Red;
}
/* */
inline bool cond2(void)
{ //!
return info[findPeo(Sweden)].pet == Dog;
}
/* */
inline bool cond3(void)
{ //!
return info[findPeo(Danmark)].drk == Tea;
}
/* */
inline bool cond4(void)
{ //!
return findClr(Green) + 1 == findClr(White);
}
/* */
inline bool cond5(void)
{ //!
return info[findClr(Green)].drk == Coffee;
}
/* */
inline bool cond6(void)
{
return info[findSmk(PallMall)].pet == Bird;
}
/* */
inline bool cond7(void)
{
return info[findClr(Yellow)].smk == Dunhill;
}
/* */
inline bool cond8(void)
{ //!
return info[2].drk == Milk;
}
/* */
inline bool cond9(void)
{ //!
return info[0].ppl == Norway;
}
/* */
inline bool cond10(void)
{
int n1=findSmk(Blends), n2=findPet(Cat);
return n1 - n2 == 1 || n1 - n2 == -1;
}
/* */
inline bool cond11(void)
{
int n1=findPet(Horse), n2=findSmk(Dunhill);
return n1 - n2 == 1 || n1 - n2 == -1;
}
/* */
inline bool cond12(void)
{
return info[findSmk(BlueMaster)].drk == Beer;
}
/* */
inline bool cond13(void)
{
return info[findPeo(Germany)].smk == Prince;
}
/* */
inline bool cond14(void)
{ //!
return info[1].clr == Blue;
}
/* */
inline bool cond15(void)
{
int n1=findSmk(Blends), n2=findDrk(Water);
return n1 - n2 == 1 || n1 - n2 == -1;
}
/* */
bool condOther(void)
{ //!( 9 ) ( 1 4 14 ) ( 3 5 8 ) ( 2 )
return cond6() && cond7() && cond10() && cond11() && cond12() && cond13() && cond15();
}
static int indexTab[120][5]; //!5! == 120.
/* */
void makeIndex(void)
{
int nIndex=0;
for(int a=0; a < 5; ++a)
{
for(int b=0; b < 5; ++b)
{
for(int c=0; c < 5; ++c)
{
for(int d=0; d < 5; ++d)
{
for(int e=0; e < 5; ++e)
{
if( a != b && a != c && a != d && a != e &&
b != c && b != d && b != e &&
c != d && c != e &&
d != e)
{
assert(nIndex < 120);
indexTab[nIndex][0]=a;
indexTab[nIndex][1]=b;
indexTab[nIndex][2]=c;
indexTab[nIndex][3]=d;
indexTab[nIndex][4]=e;
++nIndex;
}
}
}
}
}
}
assert(nIndex == 120);
}
const char *szPeo[]={ "英国", "瑞典", "丹麦", "挪威", "德国" };
const char *szClr[]={ "红色", "白色", "绿色", "黄色", "蓝色" };
const char *szDrk[]={ "茶", "咖啡", "牛奶", "Bee", "水" };
const char *szPet[]={ "鱼", "狗", "鸟", "猫", "马" };
const char *szSmk[]={ "Pal", "Dun", "Ble", "Blu", "Pri" };
/* */
void showAnser(int a, int b, int c, int d, int e)
{
int i;
cout << "Peo : ";
for(i=0; i < 5; ++i) cout << szPeo[indexTab[a][i]] << ' ';
cout << endl << "Clr : ";
for(i=0; i < 5; ++i) cout << szClr[indexTab[b][i]] << ' ';
cout << endl << "Drk : ";
for(i=0; i < 5; ++i) cout << szDrk[indexTab[c][i]] << ' ';
cout << endl << "Pet : ";
for(i=0; i < 5; ++i) cout << szPet[indexTab[d][i]] << ' ';
cout << endl << "Smk : ";
for(i=0; i < 5; ++i) cout << szSmk[indexTab[e][i]] << ' ';
cout << endl;
}
/* */
int main(void)
{
makeIndex();
int a, b, c, d, e, i;
for(a=0; a < 120; ++a)
{
//cout << "Process a == " << a << endl;
for(i=0; i < 5; ++i) info[i].ppl=(People) indexTab[a][i];
if(!cond9()) continue;
for(b=0; b < 120; ++b)
{
for(i=0; i < 5; ++i) info[i].clr=(Color) indexTab[b][i];
if(!cond14() || !cond1() || !cond4()) continue;
for(c=0; c < 120; ++c)
{
for(i=0; i < 5; ++i) info[i].drk=(Drink) indexTab[c][i];
if(!cond8() || !cond3() || !cond5()) continue;
for(d=0; d < 120; ++d)
{
for(i=0; i < 5; ++i) info[i].pet=(Pet) indexTab[d][i];
if(!cond2()) continue;
for(e=0; e < 120; ++e)
{
for(i=0; i < 5; ++i) info[i].smk=(Smoke) indexTab[e][i];
if(condOther())
{
showAnser(a, b, c, d, e);
}
}
}
}
}
}
return 0;
}
Top
33 楼sharkly（申夏）回复于 2006-07-21 14:50:06 得分 0
markTop
