爱因斯坦谜题解答(三种算法比较).docx

爱因斯坦谜题：
    在一条街上有颜色互不相同的五栋房子，不同国籍的人分别住在这五栋房子力，每人抽不同品牌的香烟，喝不同的饮料，养不同的宠物。已知如下情况：
1.  英国人住红色房子里。
2.  瑞典人养狗。
3.  丹麦人喝茶。
4.  绿色房子坐落在白色房子的左面。
5.  绿色房子的主人喝咖啡。
6.  抽Pall Mall香烟的人养鸟。
7.  黄色房子的主人抽Dunhill香烟。
8.  挪威人住第一间房子。
9.  五座房子中间的那座的主人喝牛奶。
10. 抽Blends香烟的住在养猫人的隔壁。
11. 养马的人住在抽Dunhill香烟者的隔壁。
12. 抽Blue Master香烟的喝啤酒。
13. 德国人抽Prince香烟。
14. 挪威人住的房子在蓝色房子的隔壁。
15. 抽Blends香烟的人有一个喝水的邻居。
问：谁养鱼？

谜题的英文原文：
Let us assume that there are five houses of different colors next to each other on the same road.
In each house lives a man of a different nationality. Every man has his favorite drink, his
favorite brand of cigarettes, and keeps pets of a particular kind.

1.The Englishman lives in the red house.
2.The Swede keeps dogs.
3.The Dane drinks tea.
4.The green house is just to the left of the white one.
5.The owner of the green house drinks coffee.
6.The Pall Mall smoker keeps birds.
7.The owner of the yellow house smokes Dunhills.
8.The man in the center house drinks milk.
9.The Norwegian lives in the first house.
10.The Blend smoker has a neighbor who keeps cats.
11.The man who smokes Blue Masters drinks bier.
12.The man who keeps horses lives next to the Dunhill smoker.
13.The German smokes Prince.
14.The Norwegian lives next to the blue house.
15.The Blend smoker has a neighbor who drinks water.

The question to be answered is: Who keeps fish?

 这道迷题出自1981年柏林的德国逻辑思考学院。据说世界上只有2%的人能出答案。就连大名鼎鼎的爱因斯坦也成为此题大伤脑筋，所以这道题也经常被国内外知名公司用做面试题目，相信许多朋友都只做出过一个答案，今天就用计算机来看看答案：
 C#代码（代码来源：
using System;
namespace netsafe.math
{
    public class ayst
    {
        ///                           {"DUNHILL","PRINCE","混合烟", "PALL MALL","BLUE MASTER"},
                           {"咖 啡","矿泉水","茶","牛奶"," 啤酒 "},
                           {"鱼"," 恐龙","马",    "鸟","狗"}
                         };
        /// [,] answer = new int[6, 6];
        int[,] ALL = new int[6, 122];
        int count = 1;
        int nLevel = 0;
        int[] List = new int[6];
        public static void Main(string[] args)
        {
            ayst c = new ayst();
            c.p();    ///生成全排列到all
            c.run();
            Console.Read(); /// 按任意键继续
        }
        void run()
        {
            int i1, i2, i3, i4, i5;///通过逻辑条件顺序的有效选择来优化程序
            for (i1 = 1; i1 <= 120; i1++)///房子
            {
                ///9 、挪威人住第一间房子
                ///14 、挪威人住在蓝房子旁边
                ///不满足条件就短路
                ///    
                if (ALL[2, i1] != 2) continue;
                for (int j = 0; j < 5; j++, answer[j, 1] = ALL[j, i1]) ;
                for (i2 = 1; i2 <= 120; i2++)///人种
                {
                    for (int j = 0; j < 5; j++, answer[j, 2] = ALL[j, i2]) ;
                    ///9 、挪威人住第一间房子
                    if (ALL[1, i2] != 1) continue;
                    ///1、 英国人住在红房子里 
                    ///
                    if (find(1, 4) != find(2, 2)) continue;
                    ///4 、绿房子在白房子左边 
                    ///    
                    if (find(1, 5) > find(1, 3)) continue;
                    for (i3 = 1; i3 <= 120; i3++)///烟
                    {
                        for (int j = 0; j < 5; j++, answer[j, 3] = ALL[j, i3]) ;
                        ///13、 德国人抽PRINCE烟
                        ///        
                        if (find(2, 3) != find(3, 2)) continue;
                        ///7 、黄房子主人抽DUNHILL烟
                        ///        
                        if (find(1, 1) != find(3, 1)) continue;
                        for (i4 = 1; i4 <= 120; i4++)///饮料
                        {
                            for (int j = 0; j < 5; j++, answer[j, 4] = ALL[j, i4]) ;
                            ///8 、住在中间那间房子的人喝牛奶    
                            ///        
                            if (ALL[3, i4] != 4) continue;
                            ///5 、绿房子主人喝咖啡 
                            ///    

                            if (find(1, 5) != find(4, 1)) continue;
                            ///3 、丹麦人喝茶 
                            ///        
                            if (find(2, 4) != find(4, 3)) continue;
                            ///15 、抽混合烟的人的邻居喝矿泉水    
                            if (Math.Abs(find(3, 3) - find(4, 2)) != 1) continue;
                            ///12 、抽BLUE    MASTER烟的人喝啤酒
                            ///        
                            if (find(3, 5) != find(4, 5)) continue;
                            for (i5 = 1; i5 <= 120; i5++)///宠物
                            {
                                for (int j = 0; j < 5; j++, answer[j, 5] = ALL[j, i5]) ;
                                ///10 、抽混合烟的人住在养鱼人的旁边
                                ///    
                                if (Math.Abs(find(3, 3) - find(5, 1)) != 1) continue;
                                ///2 、瑞典人养了一条狗 
                                ///        
                                if (find(2, 5) != find(5, 5)) continue;
                                ///6 、抽PALL MALL烟的人养了一只鸟    
                                ///        
                                if (find(3, 4) != find(5, 4)) continue;
                                ///11 、养马人住在DUNHILL烟的人旁边 
                                ///    
                                if (Math.Abs(find(5, 3) - find(3, 1)) != 1) continue;
                                ///
                                ///能活到这里的data,当然是答案喽
                                ///
                                write_answer();
                            }
                        }
                    }
                }
            }
        }
        /// summary>
        public void p()
        {
            int nCount, nJudge, key;
            nLevel++;
            if (nLevel > 5)
            {
                writeall();///有一种排列就写到All数组里
                nLevel--;
                return;
            }
            for (nCount = 1; nCount <= 5; nCount++)
            {
                key = 0;
                for (nJudge = 0; nJudge <= nLevel - 1; nJudge++)
                    if (nCount == List[nJudge])
                    {
                        key = 1;
                        break;
                    }
                if (key == 0)
                {
                    List[nLevel] = nCount;
                    p();
                }
            }
            nLevel--;
        }
        ///          for (i = 1; i <= 5; i++)
            {
                ALL[i, count] = List[i];
            }
            count++;
        }
        int find(int i, int j)
        {
            int k;
            for (k = 0; k <= 5; k++)
            {
                if (answer[k, i] == j)
                {
                    return k;
                }
            }
            return -1;
        }
        /// int j = 1; j <= 5; j++)
                {
                    Console.Write(data[i - 1, answer[j, i] - 1] + ",");
                }
                Console.WriteLine();
            }
            Console.WriteLine();
        }
    }
}

运行以后结果是：　

可以看出答案并不唯一，有许多组合理的答案。
还有一种暴力破解的算法
C#代码如下（代码来源：
using System;
using System.Collections.Generic;
using System.Text;

namespace 爱因斯坦迷题1
{
    enum 国籍 { 英国, 瑞典, 丹麦, 挪威, 德国 };
    enum 颜色 { 红, 绿, 蓝, 黄, 白 };
    enum 宠物 { 鸟, 猫, 马, 鱼, 狗 };
    enum 饮料 { 水, 牛奶, 咖啡, 茶, 啤酒 };
    enum 香烟 { blends, blue, prince, dunhill, pall };

    public class ProTable
    {
        private const string rule = @"
            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香烟的人有一个喝水的邻居 ";

        public string Rule { get { return rule; } }

        private enum T { 国籍 = 0, 颜色, 宠物, 饮料, 香烟 };
        private const int N = 5;
        //求排列
        private static int[,] aid = new int[120, N];
        static ProTable()
        {
            int k = 0;
            for (int i0 = 0; i0 < N; i0++)
            {
                for (int i1 = 0; i1 < N; i1++)
                {
                    if (i1 == i0) continue;
                    for (int i2 = 0; i2 < N; i2++)
                    {
                        if (i2 == i1 || i2 == i0) continue;
                        for (int i3 = 0; i3 < N; i3++)
                        {
                            if (i3 == i2 || i3 == i1 || i3 == i0) continue;
                            for (int i4 = 0; i4 < N; i4++)
                            {
                                if (i4 == i3 || i4 == i2 || i4 == i1 || i4 == i0) continue;
                                aid[k, 0] = i0;
                                aid[k, 1] = i1;
                                aid[k, 2] = i2;
                                aid[k, 3] = i3;
                                aid[k, 4] = i4;
                                k++;
                            }
                        }
                    }
                }
            }
        }

        //判断矩阵
        //  国籍,颜色,宠物,饮料,香烟
        //1
        //2
        //3
        //4
        //5
        private int[,] array = new int[N, N];

        //根据排列数组生成
        private void replace(int i, int j)
        {
            for (int k = 0; k < N; k++)
            {
                array[k, i] = aid[j, k];
            }
        }

        //通过getXX得到相应的行号
        private int get香烟香烟 n)
        {
            for (int i = 0; i < array.Length; i++)
                if (array[i, (int)T.香烟] == (int)n)
                    return i;
            return -1;
        }
        private int get饮料(饮料 n)
        {
            for (int i = 0; i < array.Length; i++)
                if (array[i, (int)T.饮料] == (int)n)
                    return i;
            return -1;
        }
        private int get宠物(宠物 n)
        {
            for (int i = 0; i < array.Length; i++)
                if (array[i, (int)T.宠物] == (int)n)
                    return i;
            return -1;
        }
        private int get国籍(国籍 n)
        {
            for (int i = 0; i < array.Length; i++)
                if (array[i, (int)T.国籍] == (int)n)
                    return i;
            return -1;
        }
        private int get颜色(颜色 n)
        {
            for (int i = 0; i < array.Length; i++)
                if (array[i, (int)T.颜色] == (int)n)
                    return i;
            return -1;
        }

        //规则：
        //1、英国人住红色房子
        //2、瑞典人养狗
        //3、丹麦人喝茶
        //4、绿色房子在白色房子左面
        //5、绿色房子主人喝咖啡
        //6、抽Pall Mall 香烟的人养鸟
        //7、黄色房子主人抽Dunhill 香烟
        //8、住在中间房子的人喝牛奶
        //9、 挪威人住第一间房
        //10、抽Blends香烟的人住在养猫的人隔壁
        //11、养马的人住抽Dunhill 香烟的人隔壁
        //12、抽Blue Master的人喝啤酒
        //13、德国人抽Prince香烟
        //14、挪威人住蓝色房子隔壁
        //15、抽Blends香烟的人有一个喝水的邻居

        //1、英国人住红色房子
        private bool assert1()
        {
            if (!(
                array[get国籍(国籍.英国), (int)T.颜色] == (int)颜色.红
            ))
                return false;
            return true;
        }
        //2、瑞典人养狗
        private bool assert2()
        {
            if (!(
                array[get国籍(国籍.瑞典), (int)T.宠物] == (int)宠物.狗
            ))
                return false;

            return true;
        }
        //3、丹麦人喝茶
        private bool assert3()
        {
            if (!(
               array[get国籍(国籍.丹麦), (int)T.饮料] == (int)饮料.茶
            ))
                return false;

            return true;
        }
        //4、绿色房子在白色房子左面
        private bool assert4()
        {
            if (!(
                   get颜色(颜色.绿) == (get颜色(颜色.白) - 1) //另一种理解get颜色(颜色.绿) < get颜色(颜色.白)
                ))
                return false;

            return true;
        }
        //5、绿色房子主人喝咖啡
        private bool assert5()
        {
            if (!(
                array[get颜色(颜色.绿), (int)T.饮料] == (int)饮料.咖啡
             ))
                return false;

            return true;
        }
        //6、抽Pall Mall 香烟的人养鸟
        private bool assert6()
        {
            if (!(
                array[get香烟(香烟.pall), (int)T.宠物] == (int)宠物.鸟
            ))
                return false;

            return true;
        }
        //7、黄色房子主人抽Dunhill 香烟
        private bool assert7()
        {
            if (!(
               array[get颜色(颜色.黄), (int)T.香烟] == (int)香烟.dunhill
            ))
                return false;

            return true;
        }
        //8、住在中间房子的人喝牛奶
        private bool assert8()
        {
            if (!(
              array[2, (int)T.饮料] == (int)饮料.牛奶
            ))
                return false;

            return true;
        }
        //9、 挪威人住第一间房
        private bool assert9()
        {
            int i = get国籍(国籍.挪威);
            if (!(
               i == 0 || i == 4
            ))
                return false;

            return true;
        }
        //10、抽Blends香烟的人住在养猫的人隔壁
        private bool assert10()
        {
            int t1 = get香烟(香烟.blends), t2 = get宠物(宠物.猫);
            if (!(
              t1 == (t2 + 1) || t1 == (t2 - 1)
            ))
                return false;

            return true;
        }
        //11、养马的人住抽Dunhill 香烟的人隔壁
        private bool assert11()
        {
            int t1 = get宠物(宠物.马);
            int t2 = get香烟(香烟.dunhill);
            if (!(
                t1 == (t2 + 1) || t1 == (t2 - 1)
            ))
                return false;
            return true;
        }
        //12、抽Blue Master的人喝啤酒
        private bool assert12()
        {
            if (!(
                array[get香烟(香烟.blue), (int