C#轻松解决世纪迷题 hadelu（原作）
关键字:c# 爱因斯坦 算法
作者：李志勇 发表于赛迪网。e-mail: netsafe@sina.com;转载请注明出处。
下面的问题相信很多人都听过：
- 有五栋五种颜色的房子
- 每一位房子的主人国籍都不同
- 这五个人每人只喝一种饮料，只抽一种牌子的香烟，只养一种宠物
- 没有人有相同的宠物，抽相同牌子的香烟，喝相同的饮料
提示：
- 英国人住在红房子里
- 瑞典人养了一条狗
- 丹麦人喝茶
- 绿房子在白房子左边
- 绿房子主人喝咖啡
- 抽PALL MALL烟的人养了一只鸟
- 黄房子主人抽DUNHILL烟
- 住在中间那间房子的人喝牛奶
- 挪威人住第一间房子
- 抽混合烟的人住在养鱼人的旁边
- 养马人住在DUNHILL烟的人旁边
- 抽BLUE MASTER烟的人喝啤酒
- 德国人抽PRINCE烟
- 挪威人住在蓝房子旁边
- 抽混合烟的人的邻居喝矿泉水
问题是： 谁养鱼？
这道迷题出自1981年柏林的德国逻辑思考学院。据说世界上只有2%的人能出答案。就连大名鼎鼎的爱因斯坦也成为此题大伤脑筋，所以这道题也经常被国内外知名公司用做面试题目，相信许多朋友都只做出过一个答案，如果碰巧你属于那98%该怎么办呢。没关系，如果这个问题用电脑来解决就非常easy了。
程序代码如下：
using System;
namespace netsafe.math
{
public class ayst
{
/// <summary>
/// 问题中的所有元素
/// </summary>
string[,] data = {{"黄房子", "蓝房子", "白房子", "红房子", "绿房子"},
{"挪威人", "英国人", "德国人", "丹麦人", "瑞典人"},
{"DUNHILL", "PRINCE", "混合烟", "PALL MALL", "BLUE MASTER"},
{"咖 啡", "矿泉水", "茶", "牛奶", " 啤酒 "},
{"鱼", " 恐龙", "马", "鸟", "狗"}};
/// <summary>
/// answer用来存放答案
/// </summary>
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();
}
}
}
}
}
}
/// <summary>
/// 非常典型的用递归实现排列组合算法。5!
/// </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--;
}
/// <summary>
/// 写入all数组
/// </summary>
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;
}
/// <summary>
/// 将答案打印出来
/// </summary>
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,
咖 啡,矿泉水,牛奶,茶, 啤酒 ,
鸟, 恐龙,马,鱼,狗,
对该文的评论 人气：341
lubaixu (2004-3-11 8:32:54)
呵呵天才.
BinzyWu (2004-3-9 16:37:28)
不错不错 鼓掌鼓掌