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

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

爱因斯坦的超级问题
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中的运行结果：