C#轻松解决世纪迷题

下面的问题相信很多人都听过：

　　1 有五栋五种颜色的房子

　　2 每一位房子的主人国籍都不同

　　3 这五个人每人只喝一种饮料，只抽一种牌子的香烟，只养一种宠物

　　4 没有人有相同的宠物，抽相同牌子的香烟，喝相同的饮料

　　提示：

　　1、 英国人住在红房子里

　　2 、瑞典人养了一条狗

　　3 、丹麦人喝茶

　　4 、绿房子在白房子左边

　　5 、绿房子主人喝咖啡

　　6 、抽PALL MALL烟的人养了一只鸟

　　7 、黄房子主人抽DUNHILL烟

　　8 、住在中间那间房子的人喝牛奶

　　9 、挪威人住第一间房子

　　10 、抽混合烟的人住在养鱼人的旁边

　　11 、养马人住在DUNHILL烟的人旁边

　　12 、抽BLUE MASTER烟的人喝啤酒

　　13、 德国人抽PRINCE烟

　　14 、挪威人住在蓝房子旁边

　　15 、抽混合烟的人的邻居喝矿泉水

　　问题是：谁养鱼？

　　这道迷题出自1981年柏林的德国逻辑思考学院。据说世界上只有2%的人能出答案。就连大名鼎鼎的爱因斯坦也成为此题大伤脑筋，所以这道题也经常被国内外知名公司用做面试题目，相信许多朋友都只做出过一个答案，如果碰巧你属于那98%该怎么办呢。没关系，如果这个问题用电脑来解决就非常easy了。程序代码如下：

　　using System;

　　namespace netsafe.math

　　{

　　public class ayst

　　{

　　///

　　/// 问题中的所有元素

　　///

　　string[,] data= ,

　　,

　　{"DUNHILL","PRINCE","混合烟", "PALL MALL","BLUE MASTER"},

　　{"咖 啡","矿泉水","茶","牛奶"," 啤酒 "},

　　{"鱼"," 恐龙","马", "鸟","狗"}};

　　///

/// answer用来存放答案

　　///

　　int[,] 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();

　　}

　　}

　　}

　　}

　　}

　　}

　　///

　　/// 非常典型的用递归实现排列组合算法。

　　///

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

　　}

　　///

　　/// 写入all数组

　　///

　　void writeall()

　　{

　　int i;

　　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;

　　}

　　///

　　/// 将答案打印出来

　　///

　　void write_answer()

　　{

　　for (int i = 1;i<=5;i++)

　　{

　　for(int j=1 ;j<=5;j++)

　　{

　　Console.Write(data[i-1,answer[j,i]-1]+",");

　　}

　　Console.WriteLine();

　　}

　　Console.WriteLine();

　　}

　　}

　　}

　　说明：程序使用目前最热门的C#语言，在Microsoft Visual Studio.net下编译执行通过。如果你没有Microsoft Visual C# 需要安装Microsoft(r) .NET Framework SDK ,把上述代码保存到ayst.cs,然后在命令行模式下执行csc ayst.cs ,然后执行ayst.exe也可以。这个程序是很久之前写的。当时只是为了得到答案，所以程序写的比较乱。让同行见笑了。以下是程序的运行结果（答案一总7种，没想到吧）：

　　黄房子,蓝房子,红房子,绿房子,白房子,

　　挪威人,丹麦人,英国人,德国人,瑞典人,

　　DUNHILL,混合烟,PALL MALL,PRINCE,BLUE MASTER,

　　矿泉水,茶,牛奶,咖 啡, 啤酒 ,

　　鱼,马,鸟, 恐龙,狗,

　　绿房子,蓝房子,黄房子,红房子,白房子,

　　挪威人,德国人,瑞典人,英国人,丹麦人,

　　混合烟,PRINCE,DUNHILL,BLUE MASTER,PALL MALL,

　　咖 啡,矿泉水,牛奶, 啤酒 ,茶,

　　恐龙,鱼,狗,马,鸟,

　　绿房子,蓝房子,白房子,黄房子,红房子,

　　挪威人,德国人,瑞典人,丹麦人,英国人,

　　PALL MALL,PRINCE,混合烟,DUNHILL,BLUE MASTER,

　　咖 啡,矿泉水,牛奶,茶, 啤酒 ,

　　鸟,鱼,狗, 恐龙,马,

　　绿房子,蓝房子,白房子,黄房子,红房子,

　　挪威人,德国人,瑞典人,丹麦人,英国人,

　　PALL MALL,PRINCE,混合烟,DUNHILL,BLUE MASTER,

　　咖 啡,矿泉水,牛奶,茶, 啤酒 ,

　　鸟, 恐龙,狗,鱼,马,

　　绿房子,蓝房子,白房子,红房子,黄房子,

　　挪威人,德国人,瑞典人,英国人,丹麦人,

　　PALL MALL,PRINCE,混合烟,BLUE MASTER,DUNHILL,

　　咖 啡,矿泉水,牛奶, 啤酒 ,茶,

　　鸟,鱼,狗,马, 恐龙,

　　绿房子,蓝房子,红房子,黄房子,白房子,

　　挪威人,德国人,英国人,丹麦人,瑞典人,

　　PALL MALL,PRINCE,混合烟,DUNHILL,BLUE MASTER,

　　咖 啡,矿泉水,牛奶,茶, 啤酒 ,

　　鸟,鱼,马, 恐龙,狗,

　　绿房子,蓝房子,红房子,黄房子,白房子,

　　挪威人,德国人,英国人,丹麦人,瑞典人,

　　PALL MALL,PRINCE,混合烟,DUNHILL,BLUE MASTER,

　　咖 啡,矿泉水,牛奶,茶, 啤酒 ,

　　鸟, 恐龙,马,鱼,狗,