爱因斯坦在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香烟的人有一个喝水的邻居 

33 个解决方案

#1

请写出您的思路，代码。

#2

有兴趣看别人的算法~~ 嘻嘻~~

#3

恩，期待！。。。

#4

德国人

#5

mark!!

#6

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)
           条件满足
    }
}

将满足所有条件的组合举出来就行了。

见笑了，这个是大体的思路，效率不会很高，希望牛人给个高级的算法

#7

5x5的矩阵，按条件添入，空缺的位置穷举验证就可以了。

#8

这种问题好象可以用prolog

#9

牛

#10

我没出这样的题

#11

有意思

#12

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

#13

哎,迟了,本人在2004年就完成了一个Delphi版本的算法,只是一直没有公开算法,结果,被人抢先了.

#14

mark

#15

答案是不是有两个的?
我推算出来是两个答案

#16

mark

#17

厉害，呵呵～～

#18

多解，呵呵

#19

我是来拜高人的~

#20

MARK

#21

我不禁希望有代码，而且希望有思路，最好是自己想出来的，本来想给kerberos7(特立独行的猪)和mLee79() 分的，可是给了就结贴了。我还想继续寻找算法和思路。另外代码最好是C或者C++的，java的也行。

#22

另外，现在也不一定非得要求是A*算法，其他算法也行，但是最好是A*算法写出来的。

#23

mark

#24

mark

#25

mark

#26

不标记不行。

#27

关注！

#28

留个记号...

#29

真的好强

#30

mark:)

#31

mark

#32

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

#33

mark