爱因斯坦谜题：谁养鱼（C#版）

一个偶然的机会再次接触到了爱因斯坦谜题，一时来了兴致，用C#做了一个程序，看看到底是谁养鱼（大学毕业后接触过这道题，不过很遗憾，那时的我没有成为2%的人，所以不知道是谁在养鱼）？

这道迷题出自1981年柏林的德国逻辑思考学院，据说世界上只有2%的人能出答案，就连大名鼎鼎的爱因斯坦也成为此题大伤脑。爱因斯坦谜题的中文表述是这样的：

1．有5栋5种颜色的房子

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

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

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

已知条件：

1．英国人住在红房子里

2．瑞典人养了一条狗

3．丹麦人喝?

4．绿房子在白房子的左边

5．绿房子主人喝咖啡

6．抽pallmall烟的人养了一只鸟

7．黄房子主人抽dunhill烟

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

9．挪威人住在第一间房子

10．抽混合烟的人住在养猫人的旁边

11．养马人住在抽dunhill烟人的旁边

12．抽bluemaster烟的人喝啤酒

13．德国人抽prince烟

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

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

问题：谁养鱼？

很遗憾的是，这个中文表述有问题，至少有以下几方面的歧义：

一、如何区分左右？二、已知条件中的第4条，绿房子在白房子的左边，是紧邻？还是可以分开？三、第一个房子，从什么方向开始算起，左，还是右？

如果仅把上面的第二点提到的绿房子在白房子的左边，不限于紧邻，则会出现7组符合条件的组合，3个答案：丹麦人养鱼（3组）、德国人养鱼（3组）、挪威人养鱼（1组）。

这显然不符合爱因斯坦谜题的本意，所以又查了查英文原题，结果真相大白，其严谨的表述有效的消除了以上的歧义。那最终的结果究竟又如何呢？

英文原题：

The Einstein Puzzle

There are 5 houses in five different colors. They are lined up in a row side by side.

In each house lives a person with a different nationality.

These 5 owners drink a certain drink, smoke a certain brand of tobacco and keep a certain pet.

No owners have the same pet, smoke the same tobacco, or drink the same drink.

As you look at the 5 houses from across the street, the green house is adjacent（woog注释：adjacent adj，毗连的，邻近的，接近的；n，近邻） to the left of the white house

The Big Question is:

Who owns the Fish?

CLUES:

1、The Brit lives in the red house

2、The Swede keeps dogs as pets

3、The Dane drinks tea

4、The green house is on the immediate left of the white house as you stare at the front of the 5 houses

5、The green house owner drinks coffee

6、The person who smokes Pall Mall raises birds

7、The owner of the yellow house smokes Dunhill

8、The man living in the house right in the center drinks milk

9、The Norwegian lives in the first house

10、The man who smokes Blends lives next to the one who keeps cats

11、The man who keeps horses lives next to the one who smokes Dunhill

12、The owner who smokes Bluemaster drinks juice

13、The German smokes Prince

14、The Norwegian lives next to the blue house

15、The man who smokes Blend has a neighbor who drinks water.

相关代码如下（考虑了两种情况，当#define FastCompute时，仅有一组答案）：

//[叶帆工作室] http://blog.csdn.net/yefanqiu #define FastCompute using System;

usingSystem.Collections.Generic; usingSystem.ComponentModel; usingSystem.Data; usingSystem.Drawing; usingSystem.Text;

usingSystem.Windows.Forms; usingSystem.Diagnostics;

namespace Einstein {

public partial class frmMain : Form {

publicfrmMain() {

InitializeComponent(); }

private void btnRun_Click(object sender, EventArgs e)

{ Arithmetic arithmetic = new Arithmetic(); DateTimedt = DateTime.Now;

string result = arithmetic.DoResult();

MessageBox.Show(result + \耗时:\秒\ } }

public class Arithmetic {

string[] people = new string[] { \英国\瑞典\丹麦\挪威\德国\ string[] house = new string[] { \红\绿\白\黄\蓝\

string[] drink = new string[] { \茶\咖啡\牛奶\啤酒\水\

string[] smoke = new string[] { \\

string[] pet = new string[] { \狗\鸟\猫\马\鱼\

ListlstCombination = new List(); //存放全部结果（预删减后的结果）

List lstCombination0 = new List(); List lstCombination1 = new List(); List lstCombination2 = new List(); List lstCombination3 = new List(); List lstCombination4 = new List();

public string DoResult() {

string[,] result = new string[5, 5];

//生成全部的组合 MakeCombination();

//预剔除不符合条件的组合 EliminateCombination();

//获得有可能的组合0

EliminateCombination0();

//获得有可能的组合1 EliminateCombination1();

//获得有可能的组合2 EliminateCombination2();

//获得有可能的组合3 EliminateCombination3();

//获得有可能的组合4 EliminateCombination4();

stringstrInfo = \intintNum = 0;

for (int i = 0; i < lstCombination0.Count; i++) {

ToCombination(result, 0, lstCombination0,i); for (int j =0; j < lstCombination1.Count; j++) {

ToCombination(result, 1, lstCombination1,j); for (int k = 0; k < lstCombination2.Count; k++) {

ToCombination(result, 2,lstCombination2, k); for (int l =0; l < lstCombination3.Count; l++) {

ToCombination(result, 3,lstCombination3, l); for (int m =0; m < lstCombination4.Count; m++) {

ToCombination(result, 4,lstCombination4, m);

bool Flag=true;

for (int e = 0; e < 5; e++)

{

if (result[0, e] == result[1, e] || result[0, e] == result[2, e] || result[0, e] == result[3, e] || result[0, e] == result[4, e] ||

result[1, e] == result[2, e] || result[1, e] == result[3, e] || result[1, e] == result[4, e] || result[2, e] == result[3, e] || result[2, e] == result[4, e] || result[3, e] == result[4, e])

{

Flag = false; break;

} }

//判断组合是否成立

if (Flag && Judge(result))

{

strInfo += \for (int ii = 0; ii < 5; ii++)

{ for (intjj = 0; jj< 5; jj++)

{ strInfo += result[ii, jj] + \

} strInfo += \

} #if FastCompute

strInfo += \returnstrInfo; #endif

} } } } } }

strInfo += \returnstrInfo; }

private void ToCombination(string[,] result,int index, Listlst,intnum) {

for (int i = 0; i < 5; i++) {

result[index, i] = lst[num][i]; } }

//生成全部的组合 private void MakeCombination() {

string[] combination = new string[5];

//5*5*5*5*5=3125

for (int i = 0; i < 5; i++) //国籍 {

combination[0] = people[i];

for (int j = 0; j < 5; j++) //房子

{

combination[1] = house[j];

for (int k = 0; k < 5; k++) //饮料 { combination[2] = drink[k];

for (int l = 0; l < 5; l++) //香烟 { combination[3] = smoke[l];

for (int m = 0; m < 5; m++) //宠物 { combination[4] = pet[m];

lstCombination.Add((string[])combination.Clone()); } } } } } }

//剔除组合的判断条件

privateboolJudgeCombination(string[] combination) {

//1、英国住红房子

if (combination[0] == \英国\红\ //2、瑞典养狗

if (combination[0] == \瑞典\狗\ //3、丹麦喝茶

if (combination[0] == \丹麦\茶\ //5、绿房子主喝咖啡

if (combination[1] == \绿\咖啡\ //6、抽Pall Mall香烟的养鸟

if (combination[3] == \鸟\ //7、黄房子主抽Dunhill香烟

if (combination[1] == \黄\ //12、抽Blue Master的喝啤酒

if (combination[3] == \啤酒\ //13、德国抽Prince香烟

if (combination[0] == \德国\return true; }

//预剔除不符合条件的组合 private void EliminateCombination() {

string[] combination=new string[5]; intnum=lstCombination.Count; int index = 0; while ((num--)>0) {

if (!JudgeCombination(lstCombination[index])) {

lstCombination.RemoveAt(index); } else

{ index++;

} } }

//创建组合0

private void EliminateCombination0() {

lstCombination0.Clear();

foreach (string[] combination in lstCombination) {

//combination[1] != \红\蓝\白\绿\#if FastCompute

if (combination[0] == \挪威\黄\

combination[2] != \牛奶\茶\combination[4] != \狗\#else

if (combination[0] == \挪威\红\

combination[1] != \蓝\白\ && combination[2] != \牛奶\combination[2] != \茶\狗\#endif

{ lstCombination0.Add(combination);

} } }

//创建组合1

private void EliminateCombination1() {

lstCombination1.Clear();

foreach (string[] combination in lstCombination)

{

if (combination[0] != \挪威\ combination[1] == \蓝\牛奶\ {

lstCombination1.Add(combination); } } }

//创建组合2

private void EliminateCombination2() {

lstCombination2.Clear();

foreach (string[] combination in lstCombination) { #if FastCompute

if (combination[0] != \挪威\丹麦\

combination[1] != \蓝\黄\白\== \牛奶\

#else

if (combination[0] != \挪威\丹麦\蓝\ && combination[2] == \牛奶\#endif

{

lstCombination2.Add(combination); } } }

//创建组合3

private void EliminateCombination3() {

lstCombination3.Clear();

foreach (string[] combination in lstCombination) { #if FastCompute

if (combination[0] != \挪威\黄\蓝\combination[2] != \牛奶\#else

if (combination[0] != \挪威\蓝\牛奶\#endif

{

lstCombination3.Add(combination); } }

}

//创建组合4

private void EliminateCombination4() {

lstCombination4.Clear();

foreach (string[] combination in lstCombination) { #if FastCompute

if (combination[0] != \挪威\黄\combination[1] != \蓝\绿\牛奶\#else

if (combination[0] != \挪威\蓝\绿\combination[2] != \牛奶\#endif

{

lstCombination4.Add(combination); } } }

//判断

private static bool Judge(string[,] combination) {

for (int index = 0;index < 5; index++) {

//4、绿房子在白房子左面 #if FastCompute

if (index > 0 && combination[index, 1] == \白\1] != \绿\#else

if (combination[index, 1] == \白\ {

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

if (combination[i, 1] == \绿\ //绿房子不可能出现在白房子的右边

return false;

} } #endif

//8、住在中间的喝牛奶 if (combination[2, 2] != \牛奶\ //9、挪威住第一间房

if (combination[0, 0] != \挪威\

//10、抽Blends香烟的住在养猫的隔壁 if (combination[index, 3] == \ {

if(!((index>0 && combination[index-1,4]==\猫\猫\ { return false;

} }

//11、养马住在抽Dunhill香烟的隔壁 if (combination[index, 4] == \马\ {

if (!((index > 0 && combination[index - 1, 3] == \3] == \

{ return false;

} }

//14、挪威住蓝房子隔壁

if (combination[index, 0] == \挪威\ {

if (!((index > 0 && combination[index - 1, 1] == \蓝\== \蓝\

{ return false;

} }

//15、抽Blends香烟的人有一个喝水的邻居 if (combination[index, 3] == \ {

if (!((index > 0 && combination[index - 1, 2] == \水\== \水\

{ return false;

} }

}

return true; }

} }

最终的计算结果如下（7组结果由于不合理，故省略，有兴趣的朋友可以自己把上面的代码运行一下）：

-----------------------------------

挪威黄水 Dunhill 猫

丹麦蓝茶 Blends 马

英国红牛奶 Pall Mall 鸟

德国绿咖啡 Prince 鱼

瑞典白啤酒 Blue Master 狗

-----------------------------------

耗时:115.15625秒

如果大家对手动计算感兴趣，下面的文章写的不错，可以参考一下： http://www.cnblogs.com/terryli/archive/2008/04/06/1138788.html

此外大家如果有更好的算法，不妨拿出来秀一秀！

本文来自CSDN博客，转载请标明出处：

http://blog.csdn.net/yefanqiu/archive/2009/09/27/4602659.aspx

本文来源：https://www.bwwdw.com/article/5k55.html