爱因斯坦谜题：谁养鱼(C#版)续-阿里云开发者社区

+ expand sourceview plaincopy to clipboardprint?
//[叶帆工作室] http://yfsoft.blog.51cto.com
#define FastCompute
using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.Data;
using System.Drawing;
using System.Text;
using System.Windows.Forms;
using System.Diagnostics;
namespace Einstein
{
public partial class frmMain : Form
{
public frmMain()
{
InitializeComponent();
}
private void btnRun_Click(object sender, EventArgs e)
{
Arithmetic arithmetic = new Arithmetic();
DateTime dt = DateTime.Now;
string result = arithmetic.DoResult();
MessageBox.Show(result + "\r\n耗时:" + (DateTime.Now - dt).TotalSeconds.ToString() + "秒");
}
}
public class Arithmetic
{
string[] people = new string[] { "英国", "瑞典", "丹麦", "挪威", "德国" };
string[] house = new string[] { "红", "绿", "白", "黄", "蓝" };
string[] drink = new string[] { "茶", "咖啡", "牛奶", "啤酒", "水" };
string[] smoke = new string[] { "Pall Mall", "Dunhill", "Blends", "Blue Master", "Prince" };
string[] pet = new string[] { "狗", "鸟", "猫", "马", "鱼" };
List<string[]> lstCombination = new List<string[]>(); //存放全部结果（预删减后的结果）
List<string[]> lstCombination0 = new List<string[]>();
List<string[]> lstCombination1 = new List<string[]>();
List<string[]> lstCombination2 = new List<string[]>();
List<string[]> lstCombination3 = new List<string[]>();
List<string[]> lstCombination4 = new List<string[]>();
public string DoResult()
{
string[,] result = new string[5, 5];
//生成全部的组合
MakeCombination();
//预剔除不符合条件的组合
EliminateCombination();
//获得有可能的组合0
EliminateCombination0();
//获得有可能的组合1
EliminateCombination1();
//获得有可能的组合2
EliminateCombination2();
//获得有可能的组合3
EliminateCombination3();
//获得有可能的组合4
EliminateCombination4();
string strInfo = "";
int intNum = 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 += "---------------- " + (++intNum).ToString()+" ----------------\r\n";
for (int ii = 0; ii < 5; ii++)
{
for (int jj = 0; jj < 5; jj++)
{
strInfo += result[ii, jj] + " ";
}
strInfo += "\r\n";
}
#if FastCompute
strInfo += "------------------------------------\r\n";
return strInfo;
#endif
}
}
}
}
}
}
strInfo += "------------------------------------\r\n";
return strInfo;
}
private void ToCombination(string[,] result,int index, List<string[]> lst,int num)
{
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());
}
}
}
}
}
}
//剔除组合的判断条件
private bool JudgeCombination(string[] combination)
{
//1、英国住红房子
if (combination[0] == "英国" && combination[1] != "红") return false;
//2、瑞典养狗
if (combination[0] == "瑞典" && combination[4] != "狗") return false;
//3、丹麦喝茶
if (combination[0] == "丹麦" && combination[2] != "茶") return false;
//5、绿房子主喝咖啡
if (combination[1] == "绿" && combination[2] != "咖啡") return false;
//6、抽Pall Mall香烟的养鸟
if (combination[3] == "Pall Mall" && combination[4] != "鸟") return false;
//7、黄房子主抽Dunhill香烟
if (combination[1] == "黄" && combination[3] != "Dunhill") return false;
//12、抽Blue Master的喝啤酒
if (combination[3] == "Blue Master" && combination[2] != "啤酒") return false;
//13、德国抽Prince香烟
if (combination[0] == "德国" && combination[3] != "Prince") return false;
return true;
}
//预剔除不符合条件的组合
private void EliminateCombination()
{
string[] combination=new string[5];
int num=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] != "红" && combination[1] != "蓝" && combination[1] != "白" && combination[1] != "绿"
#if FastCompute
if (combination[0] == "挪威" && combination[1] == "黄" && combination[2] != "牛奶" && combination[2] != "茶" && combination[3] != "Prince" && combination[4] != "狗")
#else
if (combination[0] == "挪威" && combination[1] != "红" && combination[1] != "蓝" && combination[1] != "白" && combination[2] != "牛奶" && combination[2] != "茶" && combination[3] != "Prince" && combination[4] != "狗")
#endif
{
lstCombination0.Add(combination);
}
}
}
//创建组合1
private void EliminateCombination1()
{
lstCombination1.Clear();
foreach (string[] combination in lstCombination)
{
if (combination[0] != "挪威" && combination[1] == "蓝" && combination[2] != "牛奶")
{
lstCombination1.Add(combination);
}
}
}
//创建组合2
private void EliminateCombination2()
{
lstCombination2.Clear();
foreach (string[] combination in lstCombination)
{
#if FastCompute
if (combination[0] != "挪威" && combination[0] != "丹麦" && combination[1] != "蓝" && combination[1] != "黄" && combination[1] != "白" && combination[2] == "牛奶")
#else
if (combination[0] != "挪威" && combination[0] != "丹麦" && combination[1] != "蓝" && combination[2] == "牛奶")
#endif
{
lstCombination2.Add(combination);
}
}
}
//创建组合3
private void EliminateCombination3()
{
lstCombination3.Clear();
foreach (string[] combination in lstCombination)
{
#if FastCompute
if (combination[0] != "挪威" && combination[1] != "黄" && combination[1] != "蓝" && combination[2] != "牛奶")
#else
if (combination[0] != "挪威" && combination[1] != "蓝" && combination[2] != "牛奶")
#endif
{
lstCombination3.Add(combination);
}
}
}
//创建组合4
private void EliminateCombination4()
{
lstCombination4.Clear();
foreach (string[] combination in lstCombination)
{
#if FastCompute
if (combination[0] != "挪威" && combination[1] != "黄" && combination[1] != "蓝" && combination[1] != "绿" && combination[2] != "牛奶")
#else
if (combination[0] != "挪威" && combination[1] != "蓝" && combination[1] != "绿" && 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] == "白" && combination[index - 1, 1] != "绿") return false;
#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] != "牛奶") return false;
//9、挪威住第一间房
if (combination[0, 0] != "挪威") return false;
//10、抽Blends香烟的住在养猫的隔壁
if (combination[index, 3] == "Blends")
{
if(!((index>0 && combination[index-1,4]=="猫") || (index<4 && combination[index+1,4]=="猫")))
{
return false;
}
}
//11、养马住在抽Dunhill香烟的隔壁
if (combination[index, 4] == "马")
{
if (!((index > 0 && combination[index - 1, 3] == "Dunhill") || (index < 4 && combination[index + 1, 3] == "Dunhill")))
{
return false;
}
}
//14、挪威住蓝房子隔壁
if (combination[index, 0] == "挪威")
{
if (!((index > 0 && combination[index - 1, 1] == "蓝") || (index < 4 && combination[index + 1, 1] == "蓝")))
{
return false;
}
}
//15、抽Blends香烟的人有一个喝水的邻居
if (combination[index, 3] == "Blends")
{
if (!((index > 0 && combination[index - 1, 2] == "水") || (index < 4 && 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

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

本文转自yefanqiu51CTO博客，原文链接：http://blog.51cto.com/yfsoft/324083，如需转载请自行联系原作者

爱因斯坦谜题：谁养鱼(C#版)续

热门文章

最新文章

相关课程

相关电子书

相关实验场景