凤林松山

以前在csdn上写的文章，今天贴出来测试一下代码高亮的组件，呵呵。

同事转了一个题目，号称世界上最难的问题。爱因斯坦在20世纪初出的这个谜语，他说世界上有98％的人答不出来：

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香烟的人有一个喝水的邻居

借助本子和笔，经过一段时间思考后总算把思路整理清楚，算出了谜底。后来一时兴起，想通过java写段程序来验证一下结果，大约估计了一下，大概有200多亿种可能性。。。最后程序计算了10亿次可能性后得出的答案，程序如下（临时写的程序，比较乱，大家将就着看看^^）：

import java.util.LinkedList;
import java.util.List;

public class Einstein {

	public static void main(String[] args) {
		// 计数，看看需要多少次才能得出结果
		long count = 0;

		// 用于存放一种可能性的所有属性
		int[][] houses = new int[5][5];

		// 给数组付初始值
		int[] arr = new int[5];
		for (int xx = 0; xx < arr.length; xx++) {
			arr[xx] = xx;
		}

		// 获取5个数字的所有组合可能性的列表
		List sequenceList = getAllSequence(arr);

		// 根据可能性的列表来组合各种属性
		finded: for (int[] color : sequenceList) {
			for (int[] country : sequenceList) {
				for (int[] smoke : sequenceList) {
					for (int[] pet : sequenceList) {
						for (int[] drink : sequenceList) {
							// 用组合出的属性生成一个完整的实例
							houses[Property.Color.ordinal()] = color;
							houses[Property.Country.ordinal()] = country;
							houses[Property.Smoke.ordinal()] = smoke;
							houses[Property.Pet.ordinal()] = pet;
							houses[Property.Drink.ordinal()] = drink;
							// 比较这个实例是否符合命题要求
							if (testRules(houses)) {
								// 打印结果
								System.out
										.println(Country.values()[houses[Property.Country
												.ordinal()][findByProperty(
												houses, Property.Pet, Pet.Fish)]]);
								System.out.println(count);
								break finded;
							} else {
								count++;
							}
						}
					}
				}
			}
		}

	}

	/**
	 * 判断目前的组合是否符合所有条件
	 * 
	 * @param houses
	 * @return
	 */
	public static boolean testRules(int[][] houses) {

		if (findByProperty(houses, Property.Country, Country.England) != findByProperty(
				houses, Property.Color, Color.Red)) {
			return false;
		}

		if (findByProperty(houses, Property.Country, Country.Sweden) != findByProperty(
				houses, Property.Pet, Pet.Dog)) {
			return false;
		}

		if (findByProperty(houses, Property.Country, Country.Danmark) != findByProperty(
				houses, Property.Drink, Drink.Tea)) {
			return false;
		}

		if (findByProperty(houses, Property.Color, Color.White)
				- findByProperty(houses, Property.Color, Color.Green) != 1) {
			return false;
		}

		if (findByProperty(houses, Property.Color, Color.Green) != findByProperty(
				houses, Property.Drink, Drink.Coffee)) {
			return false;
		}

		if (findByProperty(houses, Property.Smoke, Smoke.PallMall) != findByProperty(
				houses, Property.Pet, Pet.Bird)) {
			return false;
		}

		if (findByProperty(houses, Property.Color, Color.Yellow) != findByProperty(
				houses, Property.Smoke, Smoke.Dunhill)) {
			return false;
		}

		if (findByProperty(houses, Property.Drink, Drink.Milk) != 2) {
			return false;
		}

		if (findByProperty(houses, Property.Country, Country.Norway) != 0) {
			return false;
		}

		if (Math.abs(findByProperty(houses, Property.Smoke, Smoke.Blends)
				- findByProperty(houses, Property.Pet, Pet.Cat)) != 1) {
			return false;
		}

		if (Math.abs(findByProperty(houses, Property.Smoke, Smoke.Dunhill)
				- findByProperty(houses, Property.Pet, Pet.Horse)) != 1) {
			return false;
		}

		if (findByProperty(houses, Property.Smoke, Smoke.BlueMaster) != findByProperty(
				houses, Property.Drink, Drink.Beer)) {
			return false;
		}

		if (findByProperty(houses, Property.Country, Country.Germany) != findByProperty(
				houses, Property.Smoke, Smoke.Prince)) {
			return false;
		}

		if (findByProperty(houses, Property.Country, Country.Germany) != findByProperty(
				houses, Property.Smoke, Smoke.Prince)) {
			return false;
		}

		if (Math.abs(findByProperty(houses, Property.Country, Country.Norway)
				- findByProperty(houses, Property.Color, Color.Blue)) != 1) {
			return false;
		}

		if (Math.abs(findByProperty(houses, Property.Smoke, Smoke.Blends)
				- findByProperty(houses, Property.Drink, Drink.Water)) != 1) {
			return false;
		}
		return true;
	}

	/**
	 * 根据提供的属性和值获取该属性房子的位置
	 * 
	 * @param houses
	 * @param property
	 * @param value
	 * @return
	 */
	public static int findByProperty(int[][] houses, int property, int value) {
		for (int ii = 0; ii < houses[property].length; ii++) {
			if (houses[property][ii] == value) {
				return ii;
			}
		}
		return -1;
	}

	/**
	 * 重载findByProperty，便于使用
	 * 
	 * @param houses
	 * @param property
	 * @param value
	 * @return
	 */
	public static int findByProperty(int[][] houses, Enum property, Enum value) {
		return findByProperty(houses, property.ordinal(), value.ordinal());
	}

	/**
	 * 获取数组内元素的所有可能性组合
	 * 
	 * @param arr
	 * @return
	 */
	public static List getAllSequence(int[] arr) {

		List result = new LinkedList();

		getSequence(result, arr, 0);

		return result;
	}

	/**
	 * 获取数组内元素的可能性组合（递归）
	 * 
	 * @param result
	 * @param arr
	 * @param layer
	 */
	public static void getSequence(List result, int[] arr, int layer) {

		int[] arr2 = (int[]) arr.clone();

		if (arr.length - layer < 2) {
			result.add(arr2);
			return;
		}

		for (int ii = 0; ii < arr2.length - layer; ii++) {
			if (ii != 0) {
				int t = arr2[layer + ii];
				arr2[layer + ii] = arr2[layer];
				arr2[layer] = t;
			}

			getSequence(result, arr2, layer + 1);
		}

		return;
	}

}

enum Property {
	Color, Country, Smoke, Pet, Drink;
}

enum Color {
	Yellow, Blue, Green, White, Red;
}

enum Country {
	Sweden, Danmark, England, Germany, Norway;
}

enum Smoke {
	Dunhill, BlueMaster, Prince, Blends, PallMall;
}

enum Pet {
	Bird, Fish, Dog, Horse, Cat;
}

enum Drink {
	Tea, Coffee, Water, Milk, Beer;
}