《爱因斯坦的问题》解答

看到这样一个问题，题目就叫《爱因斯坦的问题》，光看题目就很有意思，打开后看了问题内容，第一反应是“晕”，而后在纸上画了画，大体理清了思路，不过实在是懒得算，就准备写个程序来帮忙。

首先把问题的内容贴出来：

爱因斯坦的超级问题
1、在一条街上，有5座房子，喷了5种颜色。
2、每个房里住着不同国籍的人
3、每个人喝不同的饮料，抽不同品牌的香烟，养不同的宠物
问题是：谁养鱼？
提示：
1、英国人住红色房子
2、瑞典人养狗
3、丹麦人喝茶
4、绿色房子在白色房子左面
5、绿色房子主人喝咖啡
6、抽PallMall香烟的人养鸟
7、黄色房子主人抽Dunhill香烟
8、住在中间房子的人喝牛奶
9、挪威人住第一间房
10、抽Blends香烟的人住在养猫的人隔壁
11、养马的人住抽Dunhill香烟的人隔壁
12、抽BlueMaster的人喝啤酒
13、德国人抽Prince香烟
14、挪威人住蓝色房子隔壁
15、抽Blends香烟的人有一个喝水的邻居

 通过程序解这种题，第一个反应是穷举法。现在先算算穷举法有多少种组合。一条街，包含5间有序的房屋，每间房屋有五个互不相同的属性：国籍、颜色、宠物、饮料和香烟。因为5间房屋相同类型的属性都不一样，所以每个属性都有5!=120种组合，5种属性加起来，共有120^5=24883200000种！接近250亿了。

直接穷举这么多种情况，显得很不合适，所以在使用穷举法的时候，不要等把一种组合确定下来之后再去判断是否符合条件，而是在组合中的一部分属性确定下来后马上做判断，这样会快很多。

本来想把房屋和街道抽象成java类，但是感觉有点兴师动众，所以就只写了一个类，以解决问题为主。下面直接上代码。

import java.util.ArrayList;

public class Einstein {
	private static final String[] MEN = { "挪威", "瑞典", "英国", "丹麦", "德国" };
	private static final int NORWAY = 0;
	private static final int SWEDEN = 1;
	private static final int ENGLAND = 2;
	private static final int DENMARK = 3;
	private static final int GERMANY = 4;
	// ================================================================
	private static final String[] PET = { "狗", "鸟", "马", "猫", "鱼" };
	private static final int DOG = 0;
	private static final int BIRD = 1;
	private static final int HORSE = 2;
	private static final int CAT = 3;
	private static final int FISH = 4;
	// ================================================================
	private static final String[] COL = { "蓝色", "红色", "黄色", "白色", "绿色" };
	private static final int BLUE = 0;
	private static final int RED = 1;
	private static final int YELLOW = 2;
	private static final int WHITE = 3;
	private static final int GREEN = 4;
	// ================================================================
	private static final String[] WIN = { "牛奶", "咖啡", "啤酒", "水", "茶" };
	private static final int MILK = 0;
	private static final int COFFE = 1;
	private static final int BEER = 2;
	private static final int WHAT = 3;
	private static final int TEE = 4;

	// ================================================================
	private static final String[] SMO = { "PallMall", "Dunhill", "BlueMaster",
			"Prince", "Blends" };
	private static final int PM = 0;
	private static final int DH = 1;
	private static final int BM = 2;
	private static final int P = 3;
	private static final int B = 4;

	// ================================================================
	private static final ArrayList<int[]> list = new ArrayList<int[]>(120);

	public static void main(String[] args) {
		// 先生成0-4的全排列。算法很笨，但是很有效。
		for (int i1 = 0; i1 < 5; i1++) {
			for (int i2 = 0; i2 < 5; i2++) {
				if (i2 == i1) {
					continue;
				}
				for (int i3 = 0; i3 < 5; i3++) {
					if (i3 == i1 || i2 == i1 || i2 == i3) {
						continue;
					}
					for (int i4 = 0; i4 < 5; i4++) {
						if (i3 == i1 || i2 == i1 || i4 == i1 || i3 == i4
								|| i3 == i2 || i2 == i4) {
							continue;
						}
						int[] arr = new int[] { i1, i2, i3, i4,
								(10 - i1 - i2 - i3 - i4) };
						list.add(arr);
					}
				}
			}
		}
		getM();
	}

	/**
	 * 国籍的全排列
	 */
	private static final void getM() {
		long begin = System.nanoTime();
		// 开始
		for (int[] men : list) {
			if (men[0] != NORWAY) {
				// 9、挪威人住第一间房
				continue;
			}
			getC(men);
		}
		System.out.println("耗时：" + (System.nanoTime() - begin) + "纳秒。");
	}

	/**
	 * 颜色的全排列
	 */
	private static void getC(int[] men) {
		out: for (int[] color : list) {
			if (color[1] != BLUE || color[4] == GREEN) {
				// 14、挪威人住蓝色房子隔壁
				// 所以，左起第二间房屋一定是蓝色色的
				// 4、绿色房子在白色房子左面
				// 所以，最右边的房屋一定不是绿色的
				continue;
			}
			for (int i = 0; i < 4; i++) {
				if (color[i] == GREEN && color[i + 1] != WHITE) {
					// 4、绿色房子在白色房子左面
					continue out;
				}
			}
			for (int i = 0; i < 5; i++) {
				if (men[i] == ENGLAND && color[i] != RED) {
					// 1、英国人住红色房子
					continue out;
				}
			}
			getP(men, color);
		}
	}

	/**
	 * 宠物的全排列
	 */
	private static void getP(int[] men, int[] color) {
		out: for (int[] pet : list) {
			for (int i = 0; i < 5; i++) {
				if (men[i] == SWEDEN && pet[i] != DOG) {
					// 2、瑞典人养狗
					continue out;
				}
			}
			getW(men, color, pet);
		}
	}

	/**
	 * 饮料的全排列
	 */
	private static void getW(int[] men, int[] color, int[] pet) {
		out: for (int[] win : list) {
			if (win[2] != MILK) {
				// 8、住在中间房子的人喝牛奶
				continue;
			}
			for (int i = 0; i < 5; i++) {
				if (men[i] == DENMARK && win[i] != TEE) {
					// /3、丹麦人喝茶
					continue out;
				}
			}
			for (int i = 0; i < 5; i++) {
				if (color[i] == GREEN && win[i] != COFFE) {
					// 5、绿色房子主人喝咖啡
					continue out;
				}
			}
			getS(men, color, pet, win);
		}
	}

	/**
	 * 香烟的全排列
	 */
	private static void getS(int[] men, int[] color, int[] pet, int[] win) {
		out: for (int[] smo : list) {
			for (int i = 0; i < 5; i++) {
				if (pet[i] == BIRD && smo[i] != PM) {
					// 6、抽PallMall香烟的人养鸟
					continue out;
				}
			}
			for (int i = 0; i < 5; i++) {
				if (color[i] == YELLOW && smo[i] != DH) {
					// 7、黄色房子主人抽Dunhill香烟
					continue out;
				}
			}
			for (int i = 0; i < 5; i++) {
				if (win[i] == BEER && smo[i] != BM) {
					// /12、抽BlueMaster的人喝啤酒
					continue out;
				}
			}
			for (int i = 0; i < 5; i++) {
				int man = men[i];
				if (man == GERMANY && smo[i] != P) {
					// 13、德国人抽Prince香烟
					continue out;
				}
			}

			boolean b = true;
			for (int i = 0; i < 4; i++) {
				if ((smo[i] == B && pet[i + 1] == CAT)
						|| (smo[i + 1] == B && pet[i] == CAT)) {
					// 10、抽Blends香烟的人住在养猫的人隔壁
					b = false;
					break;
				}
			}
			if (b) {
				continue;
			}

			b = true;
			for (int i = 0; i < 4; i++) {
				if ((smo[i] == B && win[i + 1] == WHAT)
						|| (smo[i + 1] == B && win[i] == WHAT)) {
					// 15、抽Blends香烟的人有一个喝水的邻居
					b = false;
					break;
				}
			}
			if (b) {
				continue;
			}

			b = true;
			for (int i = 0; i < 4; i++) {
				if ((smo[i] == DH && pet[i + 1] == HORSE)
						|| (smo[i + 1] == DH && pet[i] == HORSE)) {
					// 11、养马的人住抽Dunhill香烟的人隔壁
					b = false;
					break;
				}
			}
			if (b) {
				continue;
			}
			int[][] old = new int[][] { men, color, pet, win, smo };
			print(old);
		}
	}

	/**
	 * 打印结果
	 */
	private static final void print(int[][] old) {
		int[][] arr = new int[5][5];
		// 转置
		for (int i = 0; i < 5; i++) {
			for (int j = 0; j < 5; j++) {
				arr[j][i] = old[i][j];
			}
		}
		StringBuilder sb = new StringBuilder("房屋位置\t国籍\t房子颜色\t宠物\t饮料\t香烟");
		for (int i = 0; i < arr.length; i++) {
			sb.append("\n左起").append(i + 1);
			sb.append("\t").append(MEN[arr[i][0]]);
			sb.append("\t").append(COL[arr[i][1]]);
			sb.append("\t").append(PET[arr[i][2]]);
			sb.append("\t").append(WIN[arr[i][3]]);
			sb.append("\t").append(SMO[arr[i][4]]);
		}
		sb.append("\n============================");
		System.out.println(sb);
	}
}

 在MyEclipse中的运行结果：

 

评论

1 楼 xlaohe1 2012-03-02  

   
佩服啊