Teenits 2008-4-8 23:56
暴力算法解益智题(c#2.0版本)
现有题号称爱因斯坦出的智力题全世界只有2%能够做出。
------------------------------------------------
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香烟的人有一个喝水的邻居
---------------------------------------
这里我想讲的是通过暴力算法穷举所有可能让计算机进行求解。
第一次试验使用“纯暴力”解法。问题规模达到(5!=120)5次幂，大于10G。本人花了将近30分钟运行，计算机依然没有算出结果。估计就是算一天也未必能结束。
于是在第二次试验中该进算法，通过使用类似逻辑中“短路”（如：a&&b&&c当a为假时b，c可以不需要计算结果也为假）的生成算法瞬间即可得到结果。
结论：
在这次经历中，我既感到通过写程序解决实际问题带来的快乐也进一步感受了算法的重要性。好的算法带来的效率是十分可观的。
说明：
1根据试验第四句话的左临意思包括相邻，否则解不惟一。
ProTable.cs
using System;
using System.Collections.Generic;
using System.Text;
namespace SolvePuzzle
{
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)T.饮料] == (int)饮料.啤酒
))
return false;
return true;
}
//13、德国人抽Prince香烟
private bool assert13()
{
if (!(
array[get国籍(国籍.德国), (int)T.香烟] == (int)香烟.prince
))
return false;
return true;
}
//14、挪威人住蓝色房子隔壁
private bool assert14()
{
int t1 = get国籍(国籍.挪威);
int t2 = get颜色(颜色.蓝);
if (!(
t1 == (t2 + 1) || t1 == (t2 - 1)
))
return false;
return true;
}
//15、抽Blends香烟的人有一个喝水的邻居
private bool assert15()
{
int t1 = get香烟(香烟.blends);
int t2 = get饮料(饮料.水);
if (!(
t1 == (t2 + 1) || t1 == (t2 - 1)
))
return false;
return true;
}
private bool assert()
{
return assert1() && assert2() && assert3() && assert4() && assert5() && assert6() && assert7() && assert8() && assert9() &&
assert10() && assert11() && assert12() && assert13() && assert14() && assert15();
}
/*纯暴力算法以作比较
public void Solve_()
{
for (int i0 = 0; i0 < aid.GetUpperBound(0); i0++)
{
replace(0, i0);
for (int i1 = 0; i1 < aid.GetUpperBound(0); i1++)
{
replace(1, i1);
for (int i2 = 0; i2 < aid.GetUpperBound(0); i2++)
{
replace(2, i2);
for (int i3 = 0; i3 < aid.GetUpperBound(0); i3++)
{
replace(3, i3);
for (int i4 = 0; i4 < aid.GetUpperBound(0); i4++)
{
replace(4, i4);
if (assert())
{
Console.WriteLine(this);
}
}
}
}
}
}
}
*/
public void Solve()
{
//解号
int sn = 1;
//逐步生成判别表的算法
for (int i0 = 0; i0 < aid.GetUpperBound(0); i0++)
{
replace((int)T.国籍, i0);
if (!assert9())
continue;
for (int i1 = 0; i1 < aid.GetUpperBound(0); i1++)
{
replace((int)T.饮料, i1);
if (!assert8())
continue;
if (!(assert3()))
continue;
for (int i2 = 0; i2 < aid.GetUpperBound(0); i2++)
{
replace((int)T.颜色, i2);
if (!assert4())
continue;
if (!(assert1() && assert14()&&assert5()))
continue;
for (int i3 = 0; i3 < aid.GetUpperBound(0); i3++)
{
replace((int)T.宠物, i3);
if (!(assert2()))
continue;
for (int i4 = 0; i4 < aid.GetUpperBound(0); i4++)
{
replace((int)T.香烟, i4);
if (!(assert6() && assert7() && assert10() && assert11() && assert12() && assert15() && assert13()))
continue;
if (assert())
{
Console.WriteLine("解："+sn++);
Console.WriteLine(this);
}
}
}
}
}
}
}
//国籍=0,颜色,宠物,饮料,香烟
public override string ToString()
{
StringBuilder sb = new StringBuilder();
for (int i = 0; i < 5; i++)
{
sb.Append((i+1).ToString()+": ");
sb.Append(Enum.GetName(typeof(国籍),array[i,(int)T.国籍])+", ");
sb.Append(Enum.GetName(typeof(颜色), array[i, (int)T.颜色]) + ", ");
sb.Append(Enum.GetName(typeof(宠物), array[i, (int)T.宠物]) + ", ");
sb.Append(Enum.GetName(typeof(饮料), array[i, (int)T.饮料]) + ", ");
sb.Append(Enum.GetName(typeof(香烟), array[i, (int)T.香烟]) + "\n");
}
return sb.ToString();
}
}
}
-------------------------
Program.cs
using System;
using System.Collections.Generic;
using System.Text;
namespace SolvePuzzle
{
class Program
{
static void Main(string[] args)
{
ProTable t = new ProTable();
t.Solve();
}
}
}
zyld52883344 2008-6-21 16:28
为什么我用不了？？？