`

一道应聘智力题的编程求解

编程算法J#D语言搜索引擎 
阅读更多

请编程解决如下难题:
前提：
1、有五栋五种颜色的房子
2、每一位房子的主人国籍都不同
3、这五个人每人只喝一种饮料，只抽一种牌子的香烟，只养一种宠物
4、没有人有相同的宠物，抽相同牌子的香烟，喝相同的饮料
提示：
1、英国人住在红房子里
2、瑞典人养了一条狗
3、丹麦人喝茶
4、绿房子在白房子左边
5、绿房子主人喝咖啡
6、抽ＰＡＬＬ ＭＡＬＬ烟的人养了一只鸟
7、黄房子主人抽ＤＵＮＨＩＬＬ烟
8、住在中间那间房子的人喝牛奶
9、挪威人住第一间房子
10、抽混合烟的人住在养猫人的旁边
11、养马人住在抽ＤＵＮＨＩＬＬ烟的人旁边
12、抽ＢＬＵＥ　ＭＡＳＴＥＲ烟的人喝啤酒
13、德国人抽ＰＲＩＮＣＥ烟
14、挪威人住在蓝房子旁边
15、抽混合烟的人的邻居喝矿泉水
问题是：谁养鱼？

 

遇到这样的题目，一般思路是遍历所有可能，再根据给出的条件约束一一排除，最后得到正确结果。但是如果仔细算一下就会发现直接遍历的方法不可取，因为根据排列组合的公式算一下如果不排除任何约束条件大约有40亿（40^6=40亿，高中学的公式，不一定记的准确）种可能，显然直接遍历的话肯定会溢出（没测试过），所以正确的方法是首先排除掉一些可能，使遍历的长度尽可能的小。

 

仔细观察题目给出的条件，我个人认为可以分为两类：

 

第一类：

1、英国人住在红房子里
2、瑞典人养了一条狗
3、丹麦人喝茶
5、绿房子主人喝咖啡

6、抽ＰＡＬＬ ＭＡＬＬ烟的人养了一只鸟

7、黄房子主人抽ＤＵＮＨＩＬＬ烟

8、住在中间那间房子的人喝牛奶

9、挪威人住第一间房子
12、抽ＢＬＵＥ　ＭＡＳＴＥＲ烟的人喝啤酒

13、德国人抽ＰＲＩＮＣＥ烟

 

第二类：

4、绿房子在白房子左边

10、抽混合烟的人住在养猫人的旁边
11、养马人住在抽ＤＵＮＨＩＬＬ烟的人旁边

14、挪威人住在蓝房子旁边
15、抽混合烟的人的邻居喝矿泉水

 

 

如果我们画一张二维图表的话，第一类的约束条件可以直接反映出来，而第二类无法直接反映，需要间接推理。

 

 

国籍 英国人 瑞典人 丹麦人 挪威人 德国人
颜色 红色 绿、黄、白、蓝 黄、白、蓝 绿、黄 绿、黄、白、蓝
宠物 鸟、猫、鱼、马 狗 鸟、猫、鱼、马 鸟、猫、鱼、马 猫、鱼、马
饮料 牛奶、啤酒、水 咖啡、牛奶、啤酒、水 茶 咖啡、啤酒、水 咖啡、牛奶、水
香烟 PM，DH，BM，混合型 DH，BM，混合型 PM，DH，BM，混合型 PM，DH，BM，混合型 Prince
位置 2，3，4，5 2，3，4，5 2，4，5 1 2，3，4，5

 

 

这里具体的推理就不列出来了，相信大部分的朋友应该都能看的明白。这样一来，图表里的每一列的可能性分别降低到了25、21、33、14、33种，但是如果不去除重复的项，经过排列组合后所有的可能性仍旧高达超过800万种，所以在具体编程计算中，还要去掉重复的项。去掉重复的项后可能性聚降到只有1000多种，这个时候我们就可以用程序来遍历了。

 

import java.util.ArrayList;
import java.util.HashMap;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
import java.util.Map.Entry;


public class Caculate {
//英国0 瑞典1 丹麦2 挪威3 德国4
//红色0 绿色1 白色2 蓝色3 黄色4
//鸟0 狗1 猫2 鱼3 马4
//咖啡0 牛奶1 啤酒2 茶3 水4
//Price0 Pall Mall1 Blue2 Dunhill3 混合型4
	public static List makeList(){
		List list = new ArrayList();
		for (int i=0; i<5; i++ ){
			for (int j=0; j<5; j++){
				for (int k=0; k<5; k++){
					for (int p=0; p<5; p++){
						for (int q=0; q<5; q++){
							for (int r=0; r<5; r++){
								int[] lt = new int[6];
								lt[0]=i; //国籍
								lt[1]=j; //颜色
								lt[2]=k; //宠物
								lt[3]=p; //饮料
								lt[4]=q; //香烟
								lt[5]=r; //位置
								list.add(lt);		
							}
						}
					}
				}
			}
		}
		return list;
	}
	
	public static List caculateUK(){
		//英国
		List UK = makeList();
		Iterator iterator = UK.iterator();
		while (iterator.hasNext()){
			 int[] item = (int[])iterator.next();
			 //英国人
			 if (item[0]!=0){
				 iterator.remove();
				 continue;				 
			 }
			 
			 //住红房子
			 if (item[1]!=0){
				 iterator.remove();
				 continue;				 
			 }			 
			 
			 //不养狗
			 if (item[2] == 1){
				 iterator.remove();
				 continue;
			 }
			 
			 //不和咖啡和茶
			 if (item[3] == 0 || item[3] == 3){
				 iterator.remove();
				 continue;
			 }
			 
			 //不抽Price烟
			 if (item[4] == 0){
				 iterator.remove();
				 continue;
			 }
			 
			 //不住第一间
			 if (item[5] == 0){
				 iterator.remove();
				 continue;	 
			 }
			 
			 //抽ＰＡＬＬ ＭＡＬＬ烟的人养了一只鸟
			 if (item[2] == 0 && item[4]!=1){
				 iterator.remove();
				 continue;		 
			 }
			 if (item[4] == 1 && item[2]!=0){
				 iterator.remove();
				 continue;		 
			 }
			 
			 //抽ＢＬＵＥ　ＭＡＳＴＥＲ烟的人喝啤酒
			 if (item[4] == 2 && item[3]!= 2){
				 iterator.remove();
				 continue;	
			 }
			 if (item[3] == 2 && item[4]!= 2){
				 iterator.remove();
				 continue;	
			 }
			 
			 //绿房子主人喝咖啡
			 if (item[3] == 0 && item[1]!= 1){
				 iterator.remove();
				 continue;	
			 }
			 if (item[1] == 1 && item[3]!= 0){
				 iterator.remove();
				 continue;	
			 }
			 
			 //黄房子主人抽ＤＵＮＨＩＬＬ烟
			 if (item[4] == 3 && item[1]!= 4){
				 iterator.remove();
				 continue;	
			 }
			 if (item[1] == 4 && item[4]!= 3){
				 iterator.remove();
				 continue;	
			 }
			 
			 //住在中间那间房子的人喝牛奶
			 if (item[3] == 1 && item[5]!=2){
				 iterator.remove();
				 continue;					 
			 }
			 if (item[5] == 2 && item[3]!=1){
				 iterator.remove();
				 continue;					 
			 }
		 
		}
		System.out.println(UK.size());
		return UK;
	}
	
	public static List caculateSD(){
		//瑞典
		List SD = makeList();
		Iterator iterator = SD.iterator();
		iterator = SD.iterator();
		while (iterator.hasNext()){
			 int[] item = (int[])iterator.next();
			 
			 //瑞典人
			 if (item[0]!=1){
				 iterator.remove();
				 continue;				 
			 }			 
			 
			 //养狗
			 if (item[2]!= 1){
				 iterator.remove();
				 continue;
			 }
			 
			 //不喝茶
			 if (item[3] == 3){
				 iterator.remove();
				 continue;
			 }
			 
			 //不住红房子
			 if (item[1] == 0){
				 iterator.remove();
				 continue;
			 }
			 
			 //不抽Price烟和Pall Mall烟
			 if (item[4] == 0 || item[4] == 1){
				 iterator.remove();
				 continue;
			 }
			 
			 //不住第一间
			 if (item[5] == 0){
				 iterator.remove();
				 continue;	 
			 }
			 
			 //抽ＰＡＬＬ ＭＡＬＬ烟的人养了一只鸟
			 if (item[2] == 0 && item[4]!=1){
				 iterator.remove();
				 continue;		 
			 }
			 if (item[4] == 1 && item[2]!=0){
				 iterator.remove();
				 continue;		 
			 }
			 
			 //抽ＢＬＵＥ　ＭＡＳＴＥＲ烟的人喝啤酒
			 if (item[4] == 2 && item[3]!= 2){
				 iterator.remove();
				 continue;	
			 }
			 if (item[3] == 2 && item[4]!= 2){
				 iterator.remove();
				 continue;	
			 }
			 
			 //绿房子主人喝咖啡
			 if (item[3] == 0 && item[1]!= 1){
				 iterator.remove();
				 continue;	
			 }
			 if (item[1] == 1 && item[3]!= 0){
				 iterator.remove();
				 continue;	
			 }
			 
			 //黄房子主人抽ＤＵＮＨＩＬＬ烟
			 if (item[4] == 3 && item[1]!= 4){
				 iterator.remove();
				 continue;	
			 }
			 if (item[1] == 4 && item[4]!= 3){
				 iterator.remove();
				 continue;	
			 }
			 
			 //住在中间那间房子的人喝牛奶
			 if (item[3] == 1 && item[5]!=2){
				 iterator.remove();
				 continue;					 
			 }
			 if (item[5] == 2 && item[3]!=1){
				 iterator.remove();
				 continue;					 
			 }
	 
		}
		System.out.println(SD.size());
		return SD;
	}

	public static List caculateDM(){
		//丹麦
		List DM = makeList();
		Iterator iterator = DM.iterator();
		iterator = DM.iterator();
		while (iterator.hasNext()){
			 int[] item = (int[])iterator.next();
			 
			 //丹麦人
			 if (item[0]!=2){
				 iterator.remove();
				 continue;				 
			 }			 
			 
			 //喝茶
			 if (item[3]!= 3){
				 iterator.remove();
				 continue;
			 }
			 
			 //不养狗
			 if (item[2] == 1){
				 iterator.remove();
				 continue;
			 }
			 
			 //不住红房子和绿房子
			 if (item[1] == 0 || item[1] == 1){
				 iterator.remove();
				 continue;
			 }
			 
			 //不抽Price烟
			 if (item[4] == 0){
				 iterator.remove();
				 continue;
			 }
			 
			 //不住第一间和中间
			 if (item[5] == 0 || item[5] == 2){
				 iterator.remove();
				 continue;	 
			 }
			 
			 //抽ＰＡＬＬ ＭＡＬＬ烟的人养了一只鸟
			 if (item[2] == 0 && item[4]!=1){
				 iterator.remove();
				 continue;		 
			 }
			 if (item[4] == 1 && item[2]!=0){
				 iterator.remove();
				 continue;		 
			 }
			 
			 //抽ＢＬＵＥ　ＭＡＳＴＥＲ烟的人喝啤酒
			 if (item[4] == 2 && item[3]!= 2){
				 iterator.remove();
				 continue;	
			 }
			 if (item[3] == 2 && item[4]!= 2){
				 iterator.remove();
				 continue;	
			 }
			 
			 //绿房子主人喝咖啡
			 if (item[3] == 0 && item[1]!= 1){
				 iterator.remove();
				 continue;	
			 }
			 if (item[1] == 1 && item[3]!= 0){
				 iterator.remove();
				 continue;	
			 }
			 
			 //黄房子主人抽ＤＵＮＨＩＬＬ烟
			 if (item[4] == 3 && item[1]!= 4){
				 iterator.remove();
				 continue;	
			 }
			 if (item[1] == 4 && item[4]!= 3){
				 iterator.remove();
				 continue;	
			 }
			 
			 //住在中间那间房子的人喝牛奶
			 if (item[3] == 1 && item[5]!=2){
				 iterator.remove();
				 continue;					 
			 }
			 if (item[5] == 2 && item[3]!=1){
				 iterator.remove();
				 continue;					 
			 }
	 
		}
		System.out.println(DM.size());
		return DM;
	}
	
	public static List caculateNW(){
		//挪威
		List NW = makeList();
		Iterator iterator = NW.iterator();
		iterator = NW.iterator();
		while (iterator.hasNext()){
			 int[] item = (int[])iterator.next();
			 
			 //挪威人
			 if (item[0]!=3){
				 iterator.remove();
				 continue;				 
			 }			 
			 
			 //不喝茶和牛奶
			 if (item[3] == 3 ||item[3] == 1){
				 iterator.remove();
				 continue;
			 }
			 
			 //不养狗
			 if (item[2] == 1){
				 iterator.remove();
				 continue;
			 }
			 
			 //不住红房子和白房子
			 if (item[1] == 0 || item[1] == 2){
				 iterator.remove();
				 continue;
			 }
			 
			 //不抽Price烟
			 if (item[4] == 0){
				 iterator.remove();
				 continue;
			 }
			 
			 //住在第一间
			 if (item[5] != 0 ){
				 iterator.remove();
				 continue;	 
			 }
			 
			 //抽ＰＡＬＬ ＭＡＬＬ烟的人养了一只鸟
			 if (item[2] == 0 && item[4]!=1){
				 iterator.remove();
				 continue;		 
			 }
			 if (item[4] == 1 && item[2]!=0){
				 iterator.remove();
				 continue;		 
			 }
			 
			 //抽ＢＬＵＥ　ＭＡＳＴＥＲ烟的人喝啤酒
			 if (item[4] == 2 && item[3]!= 2){
				 iterator.remove();
				 continue;	
			 }
			 if (item[3] == 2 && item[4]!= 2){
				 iterator.remove();
				 continue;	
			 }
			 
			 //绿房子主人喝咖啡
			 if (item[3] == 0 && item[1]!= 1){
				 iterator.remove();
				 continue;	
			 }
			 if (item[1] == 1 && item[3]!= 0){
				 iterator.remove();
				 continue;	
			 }
			 
			 //黄房子主人抽ＤＵＮＨＩＬＬ烟
			 if (item[4] == 3 && item[1]!= 4){
				 iterator.remove();
				 continue;	
			 }
			 if (item[1] == 4 && item[4]!= 3){
				 iterator.remove();
				 continue;	
			 }
			 
			 //住在中间那间房子的人喝牛奶
			 if (item[3] == 1 && item[5]!=2){
				 iterator.remove();
				 continue;					 
			 }
			 if (item[5] == 2 && item[3]!=1){
				 iterator.remove();
				 continue;					 
			 }
 
		}
		System.out.println(NW.size());
		return NW;
	}
	public static List caculateGM(){
		//德国
		List GM = makeList();
		Iterator iterator = GM.iterator();
		iterator = GM.iterator();
		while (iterator.hasNext()){
			 int[] item = (int[])iterator.next();
			 
			 //德国人
			 if (item[0]!=4){
				 iterator.remove();
				 continue;				 
			 }			 
			 
			 //不喝茶不喝酒
			 if (item[3] == 3 || item[3] == 2){
				 iterator.remove();
				 continue;
			 }
			 
			 //不养狗不养鸟
			 if (item[2] == 1 || item[2] == 0){
				 iterator.remove();
				 continue;
			 }
			 
			 //不住红房子
			 if (item[1] == 0 ){
				 iterator.remove();
				 continue;
			 }
			 
			 //抽Price烟
			 if (item[4] != 0){
				 iterator.remove();
				 continue;
			 }
			 
			 //不住第一间
			 if (item[5] == 0 ){
				 iterator.remove();
				 continue;	 
			 }
			 
			 //抽ＰＡＬＬ ＭＡＬＬ烟的人养了一只鸟
			 if (item[2] == 0 && item[4]!=1){
				 iterator.remove();
				 continue;		 
			 }
			 if (item[4] == 1 && item[2]!=0){
				 iterator.remove();
				 continue;		 
			 }
			 
			 //抽ＢＬＵＥ　ＭＡＳＴＥＲ烟的人喝啤酒
			 if (item[4] == 2 && item[3]!= 2){
				 iterator.remove();
				 continue;	
			 }
			 if (item[3] == 2 && item[4]!= 2){
				 iterator.remove();
				 continue;	
			 }
			 
			 //绿房子主人喝咖啡
			 if (item[3] == 0 && item[1]!= 1){
				 iterator.remove();
				 continue;	
			 }
			 if (item[1] == 1 && item[3]!= 0){
				 iterator.remove();
				 continue;	
			 }
			 
			 //黄房子主人抽ＤＵＮＨＩＬＬ烟
			 if (item[4] == 3 && item[1]!= 4){
				 iterator.remove();
				 continue;	
			 }
			 if (item[1] == 4 && item[4]!= 3){
				 iterator.remove();
				 continue;	
			 }
			 
			 //住在中间那间房子的人喝牛奶
			 if (item[3] == 1 && item[5]!=2){
				 iterator.remove();
				 continue;					 
			 }
			 if (item[5] == 2 && item[3]!=1){
				 iterator.remove();
				 continue;					 
			 }
			 
		}
		System.out.println(GM.size());
		return GM;
	}		
	public static void main(String[] arg){
		List UK = caculateUK();
		List SD = caculateSD();
		List DM = caculateDM();
		List NW = caculateNW();
		List GM = caculateGM();
		
		List resultList = new ArrayList();
		
		Iterator uki = UK.iterator();
		UK:
		while (uki.hasNext()){
			int[] uk = (int[]) uki.next();
			Iterator sdi = SD.iterator();
			
			SD:
			while (sdi.hasNext()){
				int[] sd = (int[]) sdi.next();
				//去除重复
				for (int i = 1; i<6; i++){
					if (uk[i] == sd[i]){
						continue SD;
					}
				}
				Iterator dmi = DM.iterator();
				
				DM:
				while (dmi.hasNext()){
					int[] dm = (int[]) dmi.next();
					//去除重复
					for (int i = 1; i<6; i++){
						if (sd[i] == dm[i]){
							continue DM;
						}
					}
					for (int i = 1; i<6; i++){
						if (uk[i] == dm[i]){
							continue DM;
						}
					}
					Iterator nwi = NW.iterator();
					
					NW:
					while (nwi.hasNext()){
						int[] nw = (int[]) nwi.next();
						//去除重复
						for (int i = 1; i<6; i++){
							if (dm[i] == nw[i]){
								continue NW;
							}
						}
						for (int i = 1; i<6; i++){
							if (sd[i] == nw[i]){
								continue NW;
							}
						}
						for (int i = 1; i<6; i++){
							if (uk[i] == nw[i]){
								continue NW;
							}
						}
						Iterator gmi = GM.iterator();
						
						GM:
						while (gmi.hasNext()){
							int[] gm = (int[]) gmi.next();
							//去除重复
							for (int i = 1; i<6; i++){
								if (nw[i] == gm[i]){
									continue GM;
								}
							}
							for (int i = 1; i<6; i++){
								if (sd[i] == gm[i]){
									continue GM;
								}
							}
							for (int i = 1; i<6; i++){
								if (dm[i] == gm[i]){
									continue GM;
								}
							}
							for (int i = 1; i<6; i++){
								if (uk[i] == gm[i]){
									continue GM;
								}
							}
						
							//绿房子在白房子左边
							int[] green = new int[6];
							if (sd[1] == 1){
								green = sd;
							}else if (dm[1] == 1){
								green = dm;
							}else if (nw[1] == 1){
								green = nw;
							}else if (gm[1] == 1){
								green = gm;
							}
							
							int[] white = new int[6];
							if (sd[1] == 2){
								white = sd;
							}else if (dm[1] == 2){
								white = dm;
							}else if (nw[1] == 2){
								white = nw;
							}else if (gm[1] == 2){
								white = gm;
							}							
							
							if ((green[5] - white[5]!=-1 )){
								continue GM;
							}
							
							//抽混合烟的人住在养猫人的旁边
							int[] mix = new int[6];
							if (uk[4] == 4){
								mix = uk;
							}else if (sd[4] == 4){
								mix = sd;
							}else if (dm[4] == 4){
								mix = dm;
							}else if (nw[4] == 4){
								mix = nw;
							}else if (gm[4] == 4){
								mix = gm;
							}
							
							int[] cat = new int[6];
							if (uk[2] == 2){
								cat = uk;
							}else if (sd[2] == 2){
								cat = sd;
							}else if (dm[2] == 2){
								cat = dm;
							}else if (nw[2] == 2){
								cat = nw;
							}else if (gm[2] == 2){
								cat = gm;
							}
							
							if ((mix[5] - cat[5])!=1 && (cat[5] - mix[5])!=1){
								continue GM;
							}
							
							//养马人住在抽ＤＵＮＨＩＬＬ烟的人旁边
							int[] horse = new int[6];
							if (uk[2] == 4){
								horse = uk;
							}else if (sd[2] == 4){
								horse = sd;
							}else if (dm[2] == 4){
								horse = dm;
							}else if (nw[2] == 4){
								horse = nw;
							}else if (gm[2] == 4){
								horse = gm;
							}
							
							int[] dun = new int[6];
							if (uk[4] == 3){
								dun = uk;
							}else if (sd[4] == 3){
								dun = sd;
							}else if (dm[4] == 3){
								dun = dm;
							}else if (nw[4] == 3){
								dun = nw;
							}else if (gm[4] == 3){
								dun = gm;
							}
							if ((horse[5] - dun[5])!=1 && (dun[5] - horse[5])!=1){
								continue GM;
							}		
							
							//抽混合烟的人的邻居喝矿泉水
							int[] water = new int[6];
							if (uk[3] == 4){
								water = uk;
							}else if (sd[3] == 4){
								water = sd;
							}else if (dm[3] == 4){
								water = dm;
							}else if (nw[3] == 4){
								water = nw;
							}else if (gm[3] == 4){
								water = gm;
							}
							if ((mix[5] - water[5])!=1 && (water[5] - mix[5])!=1){
								continue GM;
							}
							
							//挪威人住在蓝房子旁边
							int[] p2 = new int[6];
							if (uk[5] == 1){
								p2 = uk;
							}else if (sd[5] == 1){
								p2 = sd;
							}else if (dm[5] == 1){
								p2 = dm;
							}else if (nw[5] == 1){
								p2 = nw;
							}else if (gm[5] == 1){
								p2 = gm;
							}							
							
							if (p2[1] != 3){
								continue GM;
							}
							
							
							
							Map result = new HashMap();
							result.put("uk", uk);
							result.put("sd", sd);
							result.put("dm", dm);
							result.put("nw", nw);
							result.put("gm", gm);
							
							resultList.add(result);
						}
					}
				}
			}
		}

		for (Object o : resultList){
			Map map = (Map)o;
			Iterator it = map.entrySet().iterator();
			while (it.hasNext()){
				Entry en = (Entry)it.next();
				int[] i = (int[])en.getValue();
				if (i[0]==0) System.out.print("英国人 ");
				if (i[0]==1) System.out.print("瑞典人");
				if (i[0]==2) System.out.print("丹麦人 ");
				if (i[0]==3) System.out.print("挪威人 ");
				if (i[0]==4) System.out.print("德国人 ");

				if (i[1]==0) System.out.print("红房子 ");
				if (i[1]==1) System.out.print("绿房子");
				if (i[1]==2) System.out.print("白房子 ");
				if (i[1]==3) System.out.print("蓝房子 ");
				if (i[1]==4) System.out.print("黄房子 ");
				
				if (i[2]==0) System.out.print("鸟 ");
				if (i[2]==1) System.out.print("狗 ");
				if (i[2]==2) System.out.print("猫 ");
				if (i[2]==3) System.out.print("鱼 ");
				if (i[2]==4) System.out.print("马 ");
				
				if (i[3]==0) System.out.print("咖啡 ");
				if (i[3]==1) System.out.print("牛奶 ");
				if (i[3]==2) System.out.print("啤酒 ");
				if (i[3]==3) System.out.print("茶 ");
				if (i[3]==4) System.out.print("矿泉水 ");
				
				if (i[4]==0) System.out.print("Prince ");
				if (i[4]==1) System.out.print("Pall Mall");
				if (i[4]==2) System.out.print("Blue Master");
				if (i[4]==3) System.out.print("Dunhill ");
				if (i[4]==4) System.out.print("混合型 ");

				if (i[5]==0) System.out.print("第一间 ");
				if (i[5]==1) System.out.print("第二间");
				if (i[5]==2) System.out.print("第三间 ");
				if (i[5]==3) System.out.print("第四间 ");
				if (i[5]==4) System.out.print("第五间 ");
				System.out.println();
				
			}
			System.out.println();
		}
	}
}

 

输出结果是：

 

25
21
33
14
33
德国人 绿房子鱼 咖啡 Prince 第四间 
英国人 红房子 鸟 牛奶 Pall Mall第三间 
丹麦人 蓝房子 马 茶 混合型 第二间
瑞典人白房子 狗 啤酒 Blue Master第五间 
挪威人 黄房子 猫 矿泉水 Dunhill 第一间

 

 程序随手写来，并没有刻意去追求算法效率跟书写版式，相信一定会有更优的求解。

分享到：
| 基于Java的2D mmorpg开源引擎Threerings系 ...
评论
31 楼 Mybeautiful 2010-04-19  
该类问题最好的求解方式是用 Prolog,Jess等专门用于推理的语言处理。并且解起来相当简单。
30 楼 20084896 2010-03-24  
Magicloud 写道
为啥是40^6呢？

应该是 5! ^ 5
29 楼 20084896 2010-03-24  
搜索空间有问题吧，应该不是40^6
28 楼 shermenn 2010-03-11  
楼主 逻辑 和 耐心 真强
27 楼 Magicloud 2010-03-11  
为啥是40^6呢？
26 楼 pennyxi 2010-03-11  
用Choco这个库写了个解法，jar包放在附件里了，

import choco.integer.IntDomainVar;
import choco.Problem;

public class Puzzle {

/**
* @param args
*/
public static void main(String[] args) {

          System.out.println("Problem of puzzle logic :");
   
    //create a problem
    Problem pb = new Problem();
   
    //create variable
    IntDomainVar[]  nation = new IntDomainVar[5];
    IntDomainVar[]  color = new IntDomainVar[5];
    IntDomainVar[]  drink = new IntDomainVar[5];
    IntDomainVar[]  pet = new IntDomainVar[5];
    IntDomainVar[]  tabaco = new IntDomainVar[5];
   
             //定义每个变量的范围是0到4，表示第一到第五个房子
    nation[0] = pb.makeEnumIntVar("Norwegian",0,4);
    nation[1] = pb.makeEnumIntVar("Danish",0,4);
    nation[2] = pb.makeEnumIntVar("Swede",0,4);
    nation[3] = pb.makeEnumIntVar("British",0,4);
    nation[4] = pb.makeEnumIntVar("Germen",0,4);
    color[0] = pb.makeEnumIntVar("red",0,4);
    color[1] = pb.makeEnumIntVar("yellow",0,4);
    color[2] = pb.makeEnumIntVar("green",0,4);
    color[3] = pb.makeEnumIntVar("white",0,4);
    color[4] = pb.makeEnumIntVar("blue",0,4);
    drink[0] = pb.makeEnumIntVar("water",0,4);
    drink[1] = pb.makeEnumIntVar("tea",0,4);
    drink[2] = pb.makeEnumIntVar("coffee",0,4);
    drink[3] = pb.makeEnumIntVar("beer",0,4);
    drink[4] = pb.makeEnumIntVar("milk",0,4);
    pet[0] = pb.makeEnumIntVar("dog",0,4);
    pet[1] = pb.makeEnumIntVar("cat",0,4);
    pet[2] = pb.makeEnumIntVar("horse",0,4);
    pet[3] = pb.makeEnumIntVar("fish",0,4);
    pet[4] = pb.makeEnumIntVar("bird",0,4);
    tabaco[0] = pb.makeEnumIntVar("dunhill",0,4);
    tabaco[1] = pb.makeEnumIntVar("mix",0,4);
    tabaco[2] = pb.makeEnumIntVar("pallmall",0,4);
    tabaco[3] = pb.makeEnumIntVar("prince",0,4);
    tabaco[4] = pb.makeEnumIntVar("bluemaster",0,4);
   
    //Globe Constraints，每一类的变量值不重复
    pb.post(pb.allDifferent(nation));
    pb.post(pb.allDifferent(color));
    pb.post(pb.allDifferent(drink));
    pb.post(pb.allDifferent(pet));
    pb.post(pb.allDifferent(tabaco));
   
    //Constraints 一般的约束条件
    pb.post(pb.eq(nation[3],color[0]));
    pb.post(pb.eq(nation[2],pet[0]));
    pb.post(pb.eq(nation[1],drink[1]));
    pb.post(pb.eq(pb.plus(color[2],1),color[3]));
    pb.post(pb.eq(color[2],drink[2]));
    pb.post(pb.eq(tabaco[2],pet[4]));
    pb.post(pb.eq(tabaco[0],color[1]));
    pb.post(pb.eq(2,drink[4]));
    pb.post(pb.eq(nation[3],0));
    pb.post(pb.or(pb.eq(tabaco[1], pb.plus(pet[1],1)),pb.eq(tabaco[1], pb.minus(pet[1],1))));
    pb.post(pb.or(pb.eq(pet[2], pb.plus(tabaco[0],1)),pb.eq(pet[2], pb.minus(tabaco[0],1))));
    pb.post(pb.eq(tabaco[4],drink[3]));
    pb.post(pb.eq(nation[4],tabaco[3]));
    pb.post(pb.or(pb.eq(nation[0], pb.plus(color[4],1)),pb.eq(nation[0], pb.minus(color[4],1))));
    pb.post(pb.or(pb.eq(tabaco[1], pb.plus(drink[0],1)),pb.eq(tabaco[1], pb.minus(drink[0],1))));
   
    //Search the solution
    pb.solve();
   
    //Display the solution
    for (int i =0; i < 5; i++) {
    if(pet[3].getVal() == nation[i].getVal()) {
    System.out.println("It's "+ nation[i]);
    }
    }
   
}

}
25 楼 jellyfish 2010-03-09  
I like these tables, these are the states of logical steps.

My solution is here:
http://jellyfish.iteye.com/admin/blogs/610841
24 楼 casheen 2010-03-08  
iaimstar 写道
ls你很擅长写文档啊

呵呵，谢谢;)
文章的排版是Google Document的功劳；文章的组织是在公司写案例锻炼出来的;)
23 楼 iaimstar 2010-03-07  
ls你很擅长写文档啊
22 楼 casheen 2010-03-06  
<h3>演示一下我的逻辑推理步骤：<br>
</h3>
<h3>1. 梳理出题中出现的各种值（按出现的先后次序）</h3>
<table id="c3:g" border="1" cellspacing="0" cellpadding="3" width="100%"><tbody>
<tr>
<td style="background-color: #999999;" width="16.666666666666668%">房子颜色<br>
</td>
<td width="16.666666666666668%">红色<br>
</td>
<td width="16.666666666666668%">绿色<br>
</td>
<td width="16.666666666666668%">白色<br>
</td>
<td width="16.666666666666668%">黄色<br>
</td>
<td width="16.666666666666668%">蓝色<br>
</td>
</tr>
<tr>
<td style="background-color: #999999;" width="16.666666666666668%">国籍<br>
</td>
<td width="16.666666666666668%">英国<br>
</td>
<td width="16.666666666666668%">瑞典<br>
</td>
<td width="16.666666666666668%">丹麦<br>
</td>
<td width="16.666666666666668%">挪威<br>
</td>
<td width="16.666666666666668%">德国<br>
</td>
</tr>
<tr>
<td style="background-color: #999999;" width="16.666666666666668%">养的宠物<br>
</td>
<td width="16.666666666666668%">狗<br>
</td>
<td width="16.666666666666668%">鸟<br>
</td>
<td width="16.666666666666668%">猫<br>
</td>
<td width="16.666666666666668%">马<br>
</td>
<td width="16.666666666666668%">鱼<br>
</td>
</tr>
<tr>
<td style="background-color: #999999;" width="16.666666666666668%">喝的饮料<br>
</td>
<td width="16.666666666666668%">茶<br>
</td>
<td width="16.666666666666668%">咖啡<br>
</td>
<td width="16.666666666666668%">牛奶<br>
</td>
<td width="16.666666666666668%">啤酒<br>
</td>
<td width="16.666666666666668%">矿泉水<br>
</td>
</tr>
<tr>
<td style="background-color: #999999;" width="16.666666666666668%">香烟品牌<br>
</td>
<td width="16.666666666666668%">Pall Mall<br>
</td>
<td width="16.666666666666668%">Dunhill<br>
</td>
<td width="16.666666666666668%">Blue Master<br>
</td>
<td width="16.666666666666668%">Prince<br>
</td>
<td width="16.666666666666668%">混合烟<br>
</td>
</tr>
</tbody></table>
<h3>2. 整理条件，将一一对应的条件（非常明确的条件）与其他条件区分开来</h3>
<p><span style="color: #0000ff;">1、英国人 --&gt; 红房子</span><br style="color: #0000ff;"><span style="color: #0000ff;">2、瑞典人 --&gt; 狗</span><br style="color: #0000ff;"><span style="color: #0000ff;">3、丹麦人 --&gt; 茶</span><br style="color: #0000ff;"><span style="color: #0000ff;">5、绿房子 --&gt; 咖啡</span><br style="color: #0000ff;"><span style="color: #0000ff;">6、Pall Mall --&gt; 鸟</span><br style="color: #0000ff;"><span style="color: #0000ff;">7、黄房子 --&gt; Dunhill</span><br style="color: #0000ff;"><span style="color: #0000ff;">12、Blue Master --&gt; 啤酒</span><br style="color: #0000ff;"><span style="color: #0000ff;">13、德国人 --&gt; Prince</span><br style="color: #0000ff;"><span style="color: #0000ff;">4、绿房子在白房子左边</span><br style="color: #0000ff;"><span style="color: #0000ff;">8、住在中间那间房子的人喝牛奶</span><br style="color: #0000ff;"><span style="color: #0000ff;">9、挪威人住第一间房子</span><br style="color: #0000ff;"><span style="color: #0000ff;">10、抽混合烟的人住在养猫人的旁边</span><br style="color: #0000ff;"><span style="color: #0000ff;">11、养马人住在抽Dunhill烟的人旁边</span><br style="color: #0000ff;"><span style="color: #0000ff;">14、挪威人住在蓝房子旁边</span><br style="color: #0000ff;"><span style="color: #0000ff;">15、抽混合烟的人的邻居喝矿泉水</span></p>
<h3>3. 定位房子的排序</h3>
<p>根据9、14、8、4、5，得出：2号房为蓝色，4号房为绿色，5号房为白色<br><span style="color: #0000ff;">9、挪威人住第一间房子<br>14、挪威人住在蓝房子旁边<br>8、住在中间那间房子的人喝牛奶<br>4、绿房子在白房子左边<br>5、绿房子 --&gt; 咖啡</span><br><span style="color: #0000ff;">1、英国人 --&gt; 红房子</span></p>
<table id="o-ji" border="1" cellspacing="0" cellpadding="3" width="100%"><tbody>
<tr>
<td style="background-color: #999999;" width="16.666666666666668%">房子颜色<br>
</td>
<td width="16.666666666666668%">黄色<br>
</td>
<td width="16.666666666666668%">蓝色<br>
</td>
<td width="16.666666666666668%">红色<br>
</td>
<td width="16.666666666666668%">绿色<br>
</td>
<td width="16.666666666666668%">白色<br>
</td>
</tr>
<tr>
<td style="background-color: #999999;" width="16.666666666666668%">国籍<br>
</td>
<td width="16.666666666666668%">挪威<br>
</td>
<td width="16.666666666666668%"><br></td>
<td width="16.666666666666668%">英国<br>
</td>
<td width="16.666666666666668%"><br></td>
<td width="16.666666666666668%"><br></td>
</tr>
<tr>
<td style="background-color: #999999;" width="16.666666666666668%">养的宠物<br>
</td>
<td width="16.666666666666668%"><br></td>
<td width="16.666666666666668%"><br></td>
<td width="16.666666666666668%"><br></td>
<td width="16.666666666666668%"><br></td>
<td width="16.666666666666668%"><br></td>
</tr>
<tr>
<td style="background-color: #999999;" width="16.666666666666668%">喝的饮料<br>
</td>
<td width="16.666666666666668%"><br></td>
<td width="16.666666666666668%"><br></td>
<td width="16.666666666666668%">牛奶<br>
</td>
<td width="16.666666666666668%">咖啡<br>
</td>
<td width="16.666666666666668%"><br></td>
</tr>
<tr>
<td style="background-color: #999999;" width="16.666666666666668%">香烟品牌<br>
</td>
<td width="16.666666666666668%"><br></td>
<td width="16.666666666666668%"><br></td>
<td width="16.666666666666668%"><br></td>
<td width="16.666666666666668%"><br></td>
<td width="16.666666666666668%"><br></td>
</tr>
</tbody></table>
<p>好了，有了上面的表，我们再也用不着上面5个条件了，我们把他们删掉，以免混淆视听。下面是整理后的条件列表：<br><span style="color: #0000ff;">2、瑞典人 --&gt; 狗</span><br style="color: #0000ff;"><span style="color: #0000ff;">3、丹麦人 --&gt; 茶</span><br style="color: #0000ff;"><span style="color: #0000ff;">6、Pall Mall --&gt; 鸟</span><br style="color: #0000ff;"><span style="color: #0000ff;">7、黄房子 --&gt; Dunhill</span><br style="color: #0000ff;"><span style="color: #0000ff;">12、Blue Master --&gt; 啤酒</span><br style="color: #0000ff;"><span style="color: #0000ff;">13、德国人 --&gt; Prince</span><br style="color: #0000ff;"><span style="color: #0000ff;">10、抽混合烟的人住在养猫人的旁边</span><br style="color: #0000ff;"><span style="color: #0000ff;">11、养马人住在抽Dunhill烟的人旁边</span><br style="color: #0000ff;"><span style="color: #0000ff;">15、抽混合烟的人的邻居喝矿泉水</span></p>
<h3>4. 接下来，我们将很显而易见的两个条件（7、11）也整理到表中</h3>
<p><span style="color: #0000ff;">7、黄房子 --&gt; Dunhill</span><br><span style="color: #0000ff;">11、养马人住在抽Dunhill烟的人旁边</span></p>
<table id="d0er" border="1" cellspacing="0" cellpadding="3" width="100%"><tbody>
<tr>
<td style="background-color: #999999;" width="16.666666666666668%">房子颜色<br>
</td>
<td width="16.666666666666668%">黄色<br>
</td>
<td width="16.666666666666668%">蓝色<br>
</td>
<td width="16.666666666666668%">红色<br>
</td>
<td width="16.666666666666668%">绿色<br>
</td>
<td width="16.666666666666668%">白色<br>
</td>
</tr>
<tr>
<td style="background-color: #999999;" width="16.666666666666668%">国籍<br>
</td>
<td width="16.666666666666668%">挪威<br>
</td>
<td width="16.666666666666668%"><br></td>
<td width="16.666666666666668%">英国<br>
</td>
<td width="16.666666666666668%"><br></td>
<td width="16.666666666666668%"><br></td>
</tr>
<tr>
<td style="background-color: #999999;" width="16.666666666666668%">养的宠物<br>
</td>
<td width="16.666666666666668%"><br></td>
<td width="16.666666666666668%">马<br>
</td>
<td width="16.666666666666668%"><br></td>
<td width="16.666666666666668%"><br></td>
<td width="16.666666666666668%"><br></td>
</tr>
<tr>
<td style="background-color: #999999;" width="16.666666666666668%">喝的饮料<br>
</td>
<td width="16.666666666666668%"><br></td>
<td width="16.666666666666668%"><br></td>
<td width="16.666666666666668%">牛奶<br>
</td>
<td width="16.666666666666668%">咖啡<br>
</td>
<td width="16.666666666666668%"><br></td>
</tr>
<tr>
<td style="background-color: #999999;" width="16.666666666666668%">香烟品牌<br>
</td>
<td width="16.666666666666668%">Dunhill<br>
</td>
<td width="16.666666666666668%"><br></td>
<td width="16.666666666666668%"><br></td>
<td width="16.666666666666668%"><br></td>
<td width="16.666666666666668%"><br></td>
</tr>
</tbody></table>
<p><span style="color: #0000ff;"><span style="color: #000000;">那么，剩下的条件就是这些了：</span><br>2、瑞典人 --&gt; 狗</span><br style="color: #0000ff;"><span style="color: #0000ff;">3、丹麦人 --&gt; 茶</span><br style="color: #0000ff;"><span style="color: #0000ff;">6、Pall Mall --&gt; 鸟</span><br style="color: #0000ff;"><span style="color: #0000ff;">12、Blue Master --&gt; 啤酒</span><br style="color: #0000ff;"><span style="color: #0000ff;">13、德国人 --&gt; Prince</span><br style="color: #0000ff;"><span style="color: #0000ff;">10、抽混合烟的人住在养猫人的旁边</span><br style="color: #0000ff;"><span style="color: #0000ff;">15、抽混合烟的人的邻居喝矿泉水</span></p>
<h3>5. 忘了宠物吧，我们从国籍、饮料、香烟这些条件中继续推理</h3>
<p><span style="color: #0000ff;">3、丹麦人 --&gt; 茶</span><br style="color: #0000ff;"><span style="color: #0000ff;">12、Blue Master --&gt; 啤酒</span><br style="color: #0000ff;"><span style="color: #0000ff;">13、德国人 --&gt; Prince</span><br style="color: #0000ff;"><span style="color: #0000ff;">15、抽混合烟的人的邻居喝矿泉水</span><br>根据条件3，丹麦人可能在蓝房子或白房子里；<br>根据条件12，喝啤酒的人可能在蓝房子或白房子里；<br>很显然，丹麦人和喝啤酒的人是两个人，那么这两个人会占据蓝房子和白房子；<br>同时喝啤酒的人不是德国人，因为他们抽不同的香烟。<br>所以，德国人住进了绿房子。</p>
<table id="s435" border="1" cellspacing="0" cellpadding="3" width="100%"><tbody>
<tr>
<td style="background-color: #999999;" width="16.666666666666668%">房子颜色<br>
</td>
<td width="16.666666666666668%">黄色<br>
</td>
<td width="16.666666666666668%">蓝色<br>
</td>
<td width="16.666666666666668%">红色<br>
</td>
<td width="16.666666666666668%">绿色<br>
</td>
<td width="16.666666666666668%">白色<br>
</td>
</tr>
<tr>
<td style="background-color: #999999;" width="16.666666666666668%">国籍<br>
</td>
<td width="16.666666666666668%">挪威<br>
</td>
<td width="16.666666666666668%"><br></td>
<td width="16.666666666666668%">英国<br>
</td>
<td width="16.666666666666668%">德国<br>
</td>
<td width="16.666666666666668%"><br></td>
</tr>
<tr>
<td style="background-color: #999999;" width="16.666666666666668%">养的宠物<br>
</td>
<td width="16.666666666666668%"><br></td>
<td width="16.666666666666668%">马<br>
</td>
<td width="16.666666666666668%"><br></td>
<td width="16.666666666666668%"><br></td>
<td width="16.666666666666668%"><br></td>
</tr>
<tr>
<td style="background-color: #999999;" width="16.666666666666668%">喝的饮料<br>
</td>
<td width="16.666666666666668%"><br></td>
<td width="16.666666666666668%"><br></td>
<td width="16.666666666666668%">牛奶<br>
</td>
<td width="16.666666666666668%">咖啡<br>
</td>
<td width="16.666666666666668%"><br></td>
</tr>
<tr>
<td style="background-color: #999999;" width="16.666666666666668%">香烟品牌<br>
</td>
<td width="16.666666666666668%">Dunhill<br>
</td>
<td width="16.666666666666668%"><br></td>
<td width="16.666666666666668%"><br></td>
<td width="16.666666666666668%">Prince<br>
</td>
<td width="16.666666666666668%"><br></td>
</tr>
</tbody></table>
<p>这时，我们还剩下3个条件：<br><span style="color: #0000ff;">3、丹麦人 --&gt; 茶</span><br style="color: #0000ff;"><span style="color: #0000ff;">12、Blue Master --&gt; 啤酒</span><br style="color: #0000ff;"><span style="color: #0000ff;">15、抽混合烟的人的邻居喝矿泉水</span><br>根据15推断，抽混合烟的人不可能住白色房子；<br>假设抽混合烟的人住红色房子，那么根据15住蓝色房子的人就喝矿泉水，根据3丹麦人不住蓝色房子而住白色房子，那么条件12就永远都不成立。<br>所以，抽混合烟的人住蓝色房子：</p>
<table id="ed2." border="1" cellspacing="0" cellpadding="3" width="100%"><tbody>
<tr>
<td style="background-color: #999999;" width="16.666666666666668%">房子颜色<br>
</td>
<td width="16.666666666666668%">黄色<br>
</td>
<td width="16.666666666666668%">蓝色<br>
</td>
<td width="16.666666666666668%">红色<br>
</td>
<td width="16.666666666666668%">绿色<br>
</td>
<td width="16.666666666666668%">白色<br>
</td>
</tr>
<tr>
<td style="background-color: #999999;" width="16.666666666666668%">国籍<br>
</td>
<td width="16.666666666666668%">挪威<br>
</td>
<td width="16.666666666666668%"><br></td>
<td width="16.666666666666668%">英国<br>
</td>
<td width="16.666666666666668%">德国<br>
</td>
<td width="16.666666666666668%"><br></td>
</tr>
<tr>
<td style="background-color: #999999;" width="16.666666666666668%">养的宠物<br>
</td>
<td width="16.666666666666668%"><br></td>
<td width="16.666666666666668%">马<br>
</td>
<td width="16.666666666666668%"><br></td>
<td width="16.666666666666668%"><br></td>
<td width="16.666666666666668%"><br></td>
</tr>
<tr>
<td style="background-color: #999999;" width="16.666666666666668%">喝的饮料<br>
</td>
<td width="16.666666666666668%">矿泉水<br>
</td>
<td width="16.666666666666668%"><br></td>
<td width="16.666666666666668%">牛奶<br>
</td>
<td width="16.666666666666668%">咖啡<br>
</td>
<td width="16.666666666666668%"><br></td>
</tr>
<tr>
<td style="background-color: #999999;" width="16.666666666666668%">香烟品牌<br>
</td>
<td width="16.666666666666668%">Dunhill<br>
</td>
<td width="16.666666666666668%">混合烟<br>
</td>
<td width="16.666666666666668%"><br></td>
<td width="16.666666666666668%">Prince<br>
</td>
<td width="16.666666666666668%"><br></td>
</tr>
</tbody></table>
<p>剩下的两个条件我们就很容易填充到表中了，条件12中描述的人肯定住白色房子，而丹麦人就只有住蓝色房子了。<br><span style="color: #0000ff;">3、丹麦人 --&gt; 茶</span><br style="color: #0000ff;"><span style="color: #0000ff;">12、Blue Master --&gt; 啤酒</span></p>
<table id="l9td" border="1" cellspacing="0" cellpadding="3" width="100%"><tbody>
<tr>
<td style="background-color: #999999;" width="16.666666666666668%">房子颜色<br>
</td>
<td width="16.666666666666668%">黄色<br>
</td>
<td width="16.666666666666668%">蓝色<br>
</td>
<td width="16.666666666666668%">红色<br>
</td>
<td width="16.666666666666668%">绿色<br>
</td>
<td width="16.666666666666668%">白色<br>
</td>
</tr>
<tr>
<td style="background-color: #999999;" width="16.666666666666668%">国籍<br>
</td>
<td width="16.666666666666668%">挪威<br>
</td>
<td width="16.666666666666668%">丹麦人<br>
</td>
<td width="16.666666666666668%">英国<br>
</td>
<td width="16.666666666666668%">德国<br>
</td>
<td width="16.666666666666668%"><br></td>
</tr>
<tr>
<td style="background-color: #999999;" width="16.666666666666668%">养的宠物<br>
</td>
<td width="16.666666666666668%"><br></td>
<td width="16.666666666666668%">马<br>
</td>
<td width="16.666666666666668%"><br></td>
<td width="16.666666666666668%"><br></td>
<td width="16.666666666666668%"><br></td>
</tr>
<tr>
<td style="background-color: #999999;" width="16.666666666666668%">喝的饮料<br>
</td>
<td width="16.666666666666668%">矿泉水<br>
</td>
<td width="16.666666666666668%">茶<br>
</td>
<td width="16.666666666666668%">牛奶<br>
</td>
<td width="16.666666666666668%">咖啡<br>
</td>
<td width="16.666666666666668%">啤酒<br>
</td>
</tr>
<tr>
<td style="background-color: #999999;" width="16.666666666666668%">香烟品牌<br>
</td>
<td width="16.666666666666668%">Dunhill<br>
</td>
<td width="16.666666666666668%">混合烟<br>
</td>
<td width="16.666666666666668%"><br></td>
<td width="16.666666666666668%">Prince<br>
</td>
<td width="16.666666666666668%">Blue Master<br>
</td>
</tr>
</tbody></table>
<p>接下来，我们把剩下的国籍和香烟品牌填充完毕：</p>
<table id="lbxz" border="1" cellspacing="0" cellpadding="3" width="100%"><tbody>
<tr>
<td style="background-color: #999999;" width="16.666666666666668%">房子颜色<br>
</td>
<td width="16.666666666666668%">黄色<br>
</td>
<td width="16.666666666666668%">蓝色<br>
</td>
<td width="16.666666666666668%">红色<br>
</td>
<td width="16.666666666666668%">绿色<br>
</td>
<td width="16.666666666666668%">白色<br>
</td>
</tr>
<tr>
<td style="background-color: #999999;" width="16.666666666666668%">国籍<br>
</td>
<td width="16.666666666666668%">挪威<br>
</td>
<td width="16.666666666666668%">丹麦人<br>
</td>
<td width="16.666666666666668%">英国<br>
</td>
<td width="16.666666666666668%">德国<br>
</td>
<td width="16.666666666666668%">瑞典<br>
</td>
</tr>
<tr>
<td style="background-color: #999999;" width="16.666666666666668%">养的宠物<br>
</td>
<td width="16.666666666666668%"><br></td>
<td width="16.666666666666668%">马<br>
</td>
<td width="16.666666666666668%"><br></td>
<td width="16.666666666666668%"><br></td>
<td width="16.666666666666668%"><br></td>
</tr>
<tr>
<td style="background-color: #999999;" width="16.666666666666668%">喝的饮料<br>
</td>
<td width="16.666666666666668%">矿泉水<br>
</td>
<td width="16.666666666666668%">茶<br>
</td>
<td width="16.666666666666668%">牛奶<br>
</td>
<td width="16.666666666666668%">咖啡<br>
</td>
<td width="16.666666666666668%">啤酒<br>
</td>
</tr>
<tr>
<td style="background-color: #999999;" width="16.666666666666668%">香烟品牌<br>
</td>
<td width="16.666666666666668%">Dunhill<br>
</td>
<td width="16.666666666666668%">混合烟<br>
</td>
<td width="16.666666666666668%">Pall Mall<br>
</td>
<td width="16.666666666666668%">Prince<br>
</td>
<td width="16.666666666666668%">Blue Master<br>
</td>
</tr>
</tbody></table>
<h3>6. 由剩下的有关宠物的条件填充表格完毕</h3>
<p><span style="color: #0000ff;">2、瑞典人 --&gt; 狗</span><br style="color: #0000ff;"><span style="color: #0000ff;">6、Pall Mall --&gt; 鸟</span><br style="color: #0000ff;"><span style="color: #0000ff;">10、抽混合烟的人住在养猫人的旁边</span></p>
<table id="l:ti" border="1" cellspacing="0" cellpadding="3" width="100%"><tbody>
<tr>
<td style="background-color: #999999;" width="16.666666666666668%">房子颜色<br>
</td>
<td width="16.666666666666668%">黄色<br>
</td>
<td width="16.666666666666668%">蓝色<br>
</td>
<td width="16.666666666666668%">红色<br>
</td>
<td width="16.666666666666668%">绿色<br>
</td>
<td width="16.666666666666668%">白色<br>
</td>
</tr>
<tr>
<td style="background-color: #999999;" width="16.666666666666668%">国籍<br>
</td>
<td width="16.666666666666668%">挪威<br>
</td>
<td width="16.666666666666668%">丹麦人<br>
</td>
<td width="16.666666666666668%">英国<br>
</td>
<td width="16.666666666666668%">德国<br>
</td>
<td width="16.666666666666668%">瑞典<br>
</td>
</tr>
<tr>
<td style="background-color: #999999;" width="16.666666666666668%">养的宠物<br>
</td>
<td width="16.666666666666668%">猫<br>
</td>
<td width="16.666666666666668%">马<br>
</td>
<td width="16.666666666666668%">鸟<br>
</td>
<td width="16.666666666666668%">
<span style="color: #ff0000;">鱼</span><br>
</td>
<td width="16.666666666666668%">狗<br>
</td>
</tr>
<tr>
<td style="background-color: #999999;" width="16.666666666666668%">喝的饮料<br>
</td>
<td width="16.666666666666668%">矿泉水<br>
</td>
<td width="16.666666666666668%">茶<br>
</td>
<td width="16.666666666666668%">牛奶<br>
</td>
<td width="16.666666666666668%">咖啡<br>
</td>
<td width="16.666666666666668%">啤酒<br>
</td>
</tr>
<tr>
<td style="background-color: #999999;" width="16.666666666666668%">香烟品牌<br>
</td>
<td width="16.666666666666668%">Dunhill<br>
</td>
<td width="16.666666666666668%">混合烟<br>
</td>
<td width="16.666666666666668%">Pall Mall<br>
</td>
<td width="16.666666666666668%">Prince<br>
</td>
<td width="16.666666666666668%">Blue Master<br>
</td>
</tr>
</tbody></table>
<h3>7. 所以，最后的结论是：德国人养鱼</h3>
21 楼 linghongli 2010-03-06  
gaoqs1984 写道
离散数学里讲过这样的，是太多判断了，以前是这个解的好像
A->B
C->!D
B->!C

==>B->D

A推理出B，C推理出，不是D
B推出不是C

那么B推出C


条件都说了B->!C,却说结果是B推出C
20 楼 kevindude 2010-03-05  
楼上朋友的解法相当于给出了解决该类问题的一个标准思路，相当不错，赞一个，如果能有Java版的就更好了。楼上另外几位朋友也提供了一些工具和思路，如果有时间的话也非常值得深入研究下去，在这里我就相当于起到了一个抛砖引玉的作用，哈哈。
19 楼 一粒蛋 2010-03-05  
我也写了一个解法（约 100 行），不过不适合发 Java 版，放在综合版了：

http://www.iteye.com/topic/609049

基本思路便是回溯。不需要预先人为的去画表限定范围。效率应该比 lz 的解法高一些。
18 楼 pennyxi 2010-03-05  
这个属于有约束条件的编程constraint programming

可以有一个叫choco的java库来解http://choco.sourceforge.net/first.html

基本思路就是设定一组变量，确实变量的范围，然后写约束条件，最后让程序求解

要是不用程序解的话，可以用回溯的算法手写去解
17 楼 myreligion 2010-03-05  
好像是离散数学的题目。。。
16 楼 superheizai 2010-03-05  
记得看drools的时候，看到过类似的问题。应该用规则引擎可以更好的解决这个问题吧
15 楼 lunarwayscu 2010-03-05  
robertliudeqiang 写道
lenjey 写道
robertliudeqiang 写道
学过一门课，专门讲如何推理的。

试图回忆， 不过课的名字和内容已经完全不记得了...


<<逻辑学>>？


真不记得了，数理逻辑？

只记得： 对这种题目，每个条件表示成一个式子，再通过简单的过程就可以得到结果。有基于推理的语言支持。


离散数学吧
14 楼 济南找啊 2010-03-05  
以前就不太喜欢这种类型题目
13 楼 黑暗浪子 2010-03-05  
<div class="quote_title">kevindude 写道</div>
<div class="quote_div">
<p>请编程解决如下难题:<br>前提：<br>1、有五栋五种颜色的房子<br>2、每一位房子的主人国籍都不同<br>3、这五个人每人只喝一种饮料，只抽一种牌子的香烟，只养一种宠物<br>4、没有人有相同的宠物，抽相同牌子的香烟，喝相同的饮料<br>提示：<br>1、英国人住在红房子里<br>2、瑞典人养了一条狗<br>3、丹麦人喝茶<br>4、绿房子在白房子左边<br>5、绿房子主人喝咖啡<br>6、抽ＰＡＬＬ ＭＡＬＬ烟的人养了一只鸟<br>7、黄房子主人抽ＤＵＮＨＩＬＬ烟<br>8、住在中间那间房子的人喝牛奶<br>9、挪威人住第一间房子<br>10、抽混合烟的人住在养猫人的旁边<br>11、养马人住在抽ＤＵＮＨＩＬＬ烟的人旁边<br>12、抽ＢＬＵＥ　ＭＡＳＴＥＲ烟的人喝啤酒<br>13、德国人抽ＰＲＩＮＣＥ烟<br>14、挪威人住在蓝房子旁边<br>15、抽混合烟的人的邻居喝矿泉水<br>问题是：谁养鱼？</p>
<p> </p>
<p>遇到这样的题目，一般思路是遍历所有可能，再根据给出的条件约束一一排除，最后得到正确结果。但是如果仔细算一下就会发现直接遍历的方法不可取，因为根据排列组合的公式算一下如果不排除任何约束条件大约有40亿（40^6=40亿，高中学的公式，不一定记的准确）种可能，显然直接遍历的话肯定会溢出（没测试过），所以正确的方法是首先排除掉一些可能，使遍历的长度尽可能的小。</p>
<p> </p>
<p>仔细观察题目给出的条件，我个人认为可以分为两类：</p>
<p> </p>
<p>第一类：</p>
<p>1、英国人住在红房子里<br>2、瑞典人养了一条狗<br>3、丹麦人喝茶<br>5、绿房子主人喝咖啡</p>
<p>6、抽ＰＡＬＬ ＭＡＬＬ烟的人养了一只鸟</p>
<p>7、黄房子主人抽ＤＵＮＨＩＬＬ烟</p>
<p>8、住在中间那间房子的人喝牛奶</p>
<p>9、挪威人住第一间房子<br>12、抽ＢＬＵＥ　ＭＡＳＴＥＲ烟的人喝啤酒</p>
<p>13、德国人抽ＰＲＩＮＣＥ烟</p>
<p> </p>
<p>第二类：</p>
<p>4、绿房子在白房子左边</p>
<p>10、抽混合烟的人住在养猫人的旁边<br>11、养马人住在抽ＤＵＮＨＩＬＬ烟的人旁边</p>
<p>14、挪威人住在蓝房子旁边<br>15、抽混合烟的人的邻居喝矿泉水</p>
<p> </p>
<p> </p>
<p>如果我们画一张二维图表的话，第一类的约束条件可以直接反映出来，而第二类无法直接反映，需要间接推理。</p>
<p> </p>
<p> </p>
<table style="border-right: #88777e 1px solid; border-top: #88777e 1px solid; border-left: #88777e 1px solid; border-bottom: #88777e 1px solid;" border="1"><tbody>
<tr>
<td>国籍</td>
<td>英国人</td>
<td>瑞典人</td>
<td>丹麦人</td>
<td>挪威人</td>
<td>德国人</td>
</tr>
<tr>
<td>颜色</td>
<td>红色</td>
<td>绿、黄、白、蓝</td>
<td>黄、白、蓝</td>
<td>绿、黄</td>
<td>绿、黄、白、蓝</td>
</tr>
<tr>
<td>宠物</td>
<td>鸟、猫、鱼、马</td>
<td>狗</td>
<td>鸟、猫、鱼、马</td>
<td>鸟、猫、鱼、马</td>
<td>猫、鱼、马</td>
</tr>
<tr>
<td>饮料</td>
<td>牛奶、啤酒、水</td>
<td>咖啡、牛奶、啤酒、水</td>
<td>茶</td>
<td>咖啡、啤酒、水</td>
<td>咖啡、牛奶、水</td>
</tr>
<tr>
<td>香烟</td>
<td>PM，DH，BM，混合型</td>
<td>DH，BM，混合型</td>
<td>PM，DH，BM，混合型</td>
<td>PM，DH，BM，混合型</td>
<td>Prince</td>
</tr>
<tr>
<td>位置</td>
<td>2，3，4，5</td>
<td>2，3，4，5</td>
<td>2，4，5</td>
<td>1</td>
<td>2，3，4，5</td>
</tr>
</tbody></table>
<p> </p>
<p> </p>
<p>这里具体的推理就不列出来了，相信大部分的朋友应该都能看的明白。这样一来，图表里的每一列的可能性分别降低到了25、21、33、14、33种，但是如果不去除重复的项，经过排列组合后所有的可能性仍旧高达超过800万种，所以在具体编程计算中，还要去掉重复的项。去掉重复的项后可能性聚降到只有1000多种，这个时候我们就可以用程序来遍历了。</p>
<p> </p>
<pre name="code" class="java">import java.util.ArrayList;
import java.util.HashMap;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
import java.util.Map.Entry;


public class Caculate {
//英国0 瑞典1 丹麦2 挪威3 德国4
//红色0 绿色1 白色2 蓝色3 黄色4
//鸟0 狗1 猫2 鱼3 马4
//咖啡0 牛奶1 啤酒2 茶3 水4
//Price0 Pall Mall1 Blue2 Dunhill3 混合型4
public static List makeList(){
List list = new ArrayList();
for (int i=0; i&lt;5; i++ ){
for (int j=0; j&lt;5; j++){
for (int k=0; k&lt;5; k++){
for (int p=0; p&lt;5; p++){
for (int q=0; q&lt;5; q++){
for (int r=0; r&lt;5; r++){
int[] lt = new int[6];
lt[0]=i; //国籍
lt[1]=j; //颜色
lt[2]=k; //宠物
lt[3]=p; //饮料
lt[4]=q; //香烟
lt[5]=r; //位置
list.add(lt);
}
}
}
}
}
}
return list;
}

public static List caculateUK(){
//英国
List UK = makeList();
Iterator iterator = UK.iterator();
while (iterator.hasNext()){
int[] item = (int[])iterator.next();
//英国人
if (item[0]!=0){
iterator.remove();
continue;
}

//住红房子
if (item[1]!=0){
iterator.remove();
continue;
}

//不养狗
if (item[2] == 1){
iterator.remove();
continue;
}

//不和咖啡和茶
if (item[3] == 0 || item[3] == 3){
iterator.remove();
continue;
}

//不抽Price烟
if (item[4] == 0){
iterator.remove();
continue;
}

//不住第一间
if (item[5] == 0){
iterator.remove();
continue;
}

//抽ＰＡＬＬ ＭＡＬＬ烟的人养了一只鸟
if (item[2] == 0 &amp;&amp; item[4]!=1){
iterator.remove();
continue;
}
if (item[4] == 1 &amp;&amp; item[2]!=0){
iterator.remove();
continue;
}

//抽ＢＬＵＥ　ＭＡＳＴＥＲ烟的人喝啤酒
if (item[4] == 2 &amp;&amp; item[3]!= 2){
iterator.remove();
continue;
}
if (item[3] == 2 &amp;&amp; item[4]!= 2){
iterator.remove();
continue;
}

//绿房子主人喝咖啡
if (item[3] == 0 &amp;&amp; item[1]!= 1){
iterator.remove();
continue;
}
if (item[1] == 1 &amp;&amp; item[3]!= 0){
iterator.remove();
continue;
}

//黄房子主人抽ＤＵＮＨＩＬＬ烟
if (item[4] == 3 &amp;&amp; item[1]!= 4){
iterator.remove();
continue;
}
if (item[1] == 4 &amp;&amp; item[4]!= 3){
iterator.remove();
continue;
}

//住在中间那间房子的人喝牛奶
if (item[3] == 1 &amp;&amp; item[5]!=2){
iterator.remove();
continue;
}
if (item[5] == 2 &amp;&amp; item[3]!=1){
iterator.remove();
continue;
}

}
System.out.println(UK.size());
return UK;
}

public static List caculateSD(){
//瑞典
List SD = makeList();
Iterator iterator = SD.iterator();
iterator = SD.iterator();
while (iterator.hasNext()){
int[] item = (int[])iterator.next();

//瑞典人
if (item[0]!=1){
iterator.remove();
continue;
}

//养狗
if (item[2]!= 1){
iterator.remove();
continue;
}

//不喝茶
if (item[3] == 3){
iterator.remove();
continue;
}

//不住红房子
if (item[1] == 0){
iterator.remove();
continue;
}

//不抽Price烟和Pall Mall烟
if (item[4] == 0 || item[4] == 1){
iterator.remove();
continue;
}

//不住第一间
if (item[5] == 0){
iterator.remove();
continue;
}

//抽ＰＡＬＬ ＭＡＬＬ烟的人养了一只鸟
if (item[2] == 0 &amp;&amp; item[4]!=1){
iterator.remove();
continue;
}
if (item[4] == 1 &amp;&amp; item[2]!=0){
iterator.remove();
continue;
}

//抽ＢＬＵＥ　ＭＡＳＴＥＲ烟的人喝啤酒
if (item[4] == 2 &amp;&amp; item[3]!= 2){
iterator.remove();
continue;
}
if (item[3] == 2 &amp;&amp; item[4]!= 2){
iterator.remove();
continue;
}

//绿房子主人喝咖啡
if (item[3] == 0 &amp;&amp; item[1]!= 1){
iterator.remove();
continue;
}
if (item[1] == 1 &amp;&amp; item[3]!= 0){
iterator.remove();
continue;
}

//黄房子主人抽ＤＵＮＨＩＬＬ烟
if (item[4] == 3 &amp;&amp; item[1]!= 4){
iterator.remove();
continue;
}
if (item[1] == 4 &amp;&amp; item[4]!= 3){
iterator.remove();
continue;
}

//住在中间那间房子的人喝牛奶
if (item[3] == 1 &amp;&amp; item[5]!=2){
iterator.remove();
continue;
}
if (item[5] == 2 &amp;&amp; item[3]!=1){
iterator.remove();
continue;
}

}
System.out.println(SD.size());
return SD;
}

public static List caculateDM(){
//丹麦
List DM = makeList();
Iterator iterator = DM.iterator();
iterator = DM.iterator();
while (iterator.hasNext()){
int[] item = (int[])iterator.next();

//丹麦人
if (item[0]!=2){
iterator.remove();
continue;
}

//喝茶
if (item[3]!= 3){
iterator.remove();
continue;
}

//不养狗
if (item[2] == 1){
iterator.remove();
continue;
}

//不住红房子和绿房子
if (item[1] == 0 || item[1] == 1){
iterator.remove();
continue;
}

//不抽Price烟
if (item[4] == 0){
iterator.remove();
continue;
}

//不住第一间和中间
if (item[5] == 0 || item[5] == 2){
iterator.remove();
continue;
}

//抽ＰＡＬＬ ＭＡＬＬ烟的人养了一只鸟
if (item[2] == 0 &amp;&amp; item[4]!=1){
iterator.remove();
continue;
}
if (item[4] == 1 &amp;&amp; item[2]!=0){
iterator.remove();
continue;
}

//抽ＢＬＵＥ　ＭＡＳＴＥＲ烟的人喝啤酒
if (item[4] == 2 &amp;&amp; item[3]!= 2){
iterator.remove();
continue;
}
if (item[3] == 2 &amp;&amp; item[4]!= 2){
iterator.remove();
continue;
}

//绿房子主人喝咖啡
if (item[3] == 0 &amp;&amp; item[1]!= 1){
iterator.remove();
continue;
}
if (item[1] == 1 &amp;&amp; item[3]!= 0){
iterator.remove();
continue;
}

//黄房子主人抽ＤＵＮＨＩＬＬ烟
if (item[4] == 3 &amp;&amp; item[1]!= 4){
iterator.remove();
continue;
}
if (item[1] == 4 &amp;&amp; item[4]!= 3){
iterator.remove();
continue;
}

//住在中间那间房子的人喝牛奶
if (item[3] == 1 &amp;&amp; item[5]!=2){
iterator.remove();
continue;
}
if (item[5] == 2 &amp;&amp; item[3]!=1){
iterator.remove();
continue;
}

}
System.out.println(DM.size());
return DM;
}

public static List caculateNW(){
//挪威
List NW = makeList();
Iterator iterator = NW.iterator();
iterator = NW.iterator();
while (iterator.hasNext()){
int[] item = (int[])iterator.next();

//挪威人
if (item[0]!=3){
iterator.remove();
continue;
}

//不喝茶和牛奶
if (item[3] == 3 ||item[3] == 1){
iterator.remove();
continue;
}

//不养狗
if (item[2] == 1){
iterator.remove();
continue;
}

//不住红房子和白房子
if (item[1] == 0 || item[1] == 2){
iterator.remove();
continue;
}

//不抽Price烟
if (item[4] == 0){
iterator.remove();
continue;
}

//住在第一间
if (item[5] != 0 ){
iterator.remove();
continue;
}

//抽ＰＡＬＬ ＭＡＬＬ烟的人养了一只鸟
if (item[2] == 0 &amp;&amp; item[4]!=1){
iterator.remove();
continue;
}
if (item[4] == 1 &amp;&amp; item[2]!=0){
iterator.remove();
continue;
}

//抽ＢＬＵＥ　ＭＡＳＴＥＲ烟的人喝啤酒
if (item[4] == 2 &amp;&amp; item[3]!= 2){
iterator.remove();
continue;
}
if (item[3] == 2 &amp;&amp; item[4]!= 2){
iterator.remove();
continue;
}

//绿房子主人喝咖啡
if (item[3] == 0 &amp;&amp; item[1]!= 1){
iterator.remove();
continue;
}
if (item[1] == 1 &amp;&amp; item[3]!= 0){
iterator.remove();
continue;
}

//黄房子主人抽ＤＵＮＨＩＬＬ烟
if (item[4] == 3 &amp;&amp; item[1]!= 4){
iterator.remove();
continue;
}
if (item[1] == 4 &amp;&amp; item[4]!= 3){
iterator.remove();
continue;
}

//住在中间那间房子的人喝牛奶
if (item[3] == 1 &amp;&amp; item[5]!=2){
iterator.remove();
continue;
}
if (item[5] == 2 &amp;&amp; item[3]!=1){
iterator.remove();
continue;
}

}
System.out.println(NW.size());
return NW;
}
public static List caculateGM(){
//德国
List GM = makeList();
Iterator iterator = GM.iterator();
iterator = GM.iterator();
while (iterator.hasNext()){
int[] item = (int[])iterator.next();

//德国人
if (item[0]!=4){
iterator.remove();
continue;
}

//不喝茶不喝酒
if (item[3] == 3 || item[3] == 2){
iterator.remove();
continue;
}

//不养狗不养鸟
if (item[2] == 1 || item[2] == 0){
iterator.remove();
continue;
}

//不住红房子
if (item[1] == 0 ){
iterator.remove();
continue;
}

//抽Price烟
if (item[4] != 0){
iterator.remove();
continue;
}

//不住第一间
if (item[5] == 0 ){
iterator.remove();
continue;
}

//抽ＰＡＬＬ ＭＡＬＬ烟的人养了一只鸟
if (item[2] == 0 &amp;&amp; item[4]!=1){
iterator.remove();
continue;
}
if (item[4] == 1 &amp;&amp; item[2]!=0){
iterator.remove();
continue;
}

//抽ＢＬＵＥ　ＭＡＳＴＥＲ烟的人喝啤酒
if (item[4] == 2 &amp;&amp; item[3]!= 2){
iterator.remove();
continue;
}
if (item[3] == 2 &amp;&amp; item[4]!= 2){
iterator.remove();
continue;
}

//绿房子主人喝咖啡
if (item[3] == 0 &amp;&amp; item[1]!= 1){
iterator.remove();
continue;
}
if (item[1] == 1 &amp;&amp; item[3]!= 0){
iterator.remove();
continue;
}

//黄房子主人抽ＤＵＮＨＩＬＬ烟
if (item[4] == 3 &amp;&amp; item[1]!= 4){
iterator.remove();
continue;
}
if (item[1] == 4 &amp;&amp; item[4]!= 3){
iterator.remove();
continue;
}

//住在中间那间房子的人喝牛奶
if (item[3] == 1 &amp;&amp; item[5]!=2){
iterator.remove();
continue;
}
if (item[5] == 2 &amp;&amp; item[3]!=1){
iterator.remove();
continue;
}

}
System.out.println(GM.size());
return GM;
}
public static void main(String[] arg){
List UK = caculateUK();
List SD = caculateSD();
List DM = caculateDM();
List NW = caculateNW();
List GM = caculateGM();

List resultList = new ArrayList();

Iterator uki = UK.iterator();
UK:
while (uki.hasNext()){
int[] uk = (int[]) uki.next();
Iterator sdi = SD.iterator();

SD:
while (sdi.hasNext()){
int[] sd = (int[]) sdi.next();
//去除重复
for (int i = 1; i&lt;6; i++){
if (uk[i] == sd[i]){
continue SD;
}
}
Iterator dmi = DM.iterator();

DM:
while (dmi.hasNext()){
int[] dm = (int[]) dmi.next();
//去除重复
for (int i = 1; i&lt;6; i++){
if (sd[i] == dm[i]){
continue DM;
}
}
for (int i = 1; i&lt;6; i++){
if (uk[i] == dm[i]){
continue DM;
}
}
Iterator nwi = NW.iterator();

NW:
while (nwi.hasNext()){
int[] nw = (int[]) nwi.next();
//去除重复
for (int i = 1; i&lt;6; i++){
if (dm[i] == nw[i]){
continue NW;
}
}
for (int i = 1; i&lt;6; i++){
if (sd[i] == nw[i]){
continue NW;
}
}
for (int i = 1; i&lt;6; i++){
if (uk[i] == nw[i]){
continue NW;
}
}
Iterator gmi = GM.iterator();

GM:
while (gmi.hasNext()){
int[] gm = (int[]) gmi.next();
//去除重复
for (int i = 1; i&lt;6; i++){
if (nw[i] == gm[i]){
continue GM;
}
}
for (int i = 1; i&lt;6; i++){
if (sd[i] == gm[i]){
continue GM;
}
}
for (int i = 1; i&lt;6; i++){
if (dm[i] == gm[i]){
continue GM;
}
}
for (int i = 1; i&lt;6; i++){
if (uk[i] == gm[i]){
continue GM;
}
}

//绿房子在白房子左边
int[] green = new int[6];
if (sd[1] == 1){
green = sd;
}else if (dm[1] == 1){
green = dm;
}else if (nw[1] == 1){
green = nw;
}else if (gm[1] == 1){
green = gm;
}

int[] white = new int[6];
if (sd[1] == 2){
white = sd;
}else if (dm[1] == 2){
white = dm;
}else if (nw[1] == 2){
white = nw;
}else if (gm[1] == 2){
white = gm;
}

if ((green[5] - white[5]!=-1 )){
continue GM;
}

//抽混合烟的人住在养猫人的旁边
int[] mix = new int[6];
if (uk[4] == 4){
mix = uk;
}else if (sd[4] == 4){
mix = sd;
}else if (dm[4] == 4){
mix = dm;
}else if (nw[4] == 4){
mix = nw;
}else if (gm[4] == 4){
mix = gm;
}

int[] cat = new int[6];
if (uk[2] == 2){
cat = uk;
}else if (sd[2] == 2){
cat = sd;
}else if (dm[2] == 2){
cat = dm;
}else if (nw[2] == 2){
cat = nw;
}else if (gm[2] == 2){
cat = gm;
}

if ((mix[5] - cat[5])!=1 &amp;&amp; (cat[5] - mix[5])!=1){
continue GM;
}

//养马人住在抽ＤＵＮＨＩＬＬ烟的人旁边
int[] horse = new int[6];
if (uk[2] == 4){
horse = uk;
}else if (sd[2] == 4){
horse = sd;
}else if (dm[2] == 4){
horse = dm;
}else if (nw[2] == 4){
horse = nw;
}else if (gm[2] == 4){
horse = gm;
}

int[] dun = new int[6];
if (uk[4] == 3){
dun = uk;
}else if (sd[4] == 3){
dun = sd;
}else if (dm[4] == 3){
dun = dm;
}else if (nw[4] == 3){
dun = nw;
}else if (gm[4] == 3){
dun = gm;
}
if ((horse[5] - dun[5])!=1 &amp;&amp; (dun[5] - horse[5])!=1){
continue GM;
}

//抽混合烟的人的邻居喝矿泉水
int[] water = new int[6];
if (uk[3] == 4){
water = uk;
}else if (sd[3] == 4){
water = sd;
}else if (dm[3] == 4){
water = dm;
}else if (nw[3] == 4){
water = nw;
}else if (gm[3] == 4){
water = gm;
}
if ((mix[5] - water[5])!=1 &amp;&amp; (water[5] - mix[5])!=1){
continue GM;
}

//挪威人住在蓝房子旁边
int[] p2 = new int[6];
if (uk[5] == 1){
p2 = uk;
}else if (sd[5] == 1){
p2 = sd;
}else if (dm[5] == 1){
p2 = dm;
}else if (nw[5] == 1){
p2 = nw;
}else if (gm[5] == 1){
p2 = gm;
}

if (p2[1] != 3){
continue GM;
}



Map result = new HashMap();
result.put("uk", uk);
result.put("sd", sd);
result.put("dm", dm);
result.put("nw", nw);
result.put("gm", gm);

resultList.add(result);
}
}
}
}
}

for (Object o : resultList){
Map map = (Map)o;
Iterator it = map.entrySet().iterator();
while (it.hasNext()){
Entry en = (Entry)it.next();
int[] i = (int[])en.getValue();
if (i[0]==0) System.out.print("英国人 ");
if (i[0]==1) System.out.print("瑞典人");
if (i[0]==2) System.out.print("丹麦人 ");
if (i[0]==3) System.out.print("挪威人 ");
if (i[0]==4) System.out.print("德国人 ");

if (i[1]==0) System.out.print("红房子 ");
if (i[1]==1) System.out.print("绿房子");
if (i[1]==2) System.out.print("白房子 ");
if (i[1]==3) System.out.print("蓝房子 ");
if (i[1]==4) System.out.print("黄房子 ");

if (i[2]==0) System.out.print("鸟 ");
if (i[2]==1) System.out.print("狗 ");
if (i[2]==2) System.out.print("猫 ");
if (i[2]==3) System.out.print("鱼 ");
if (i[2]==4) System.out.print("马 ");

if (i[3]==0) System.out.print("咖啡 ");
if (i[3]==1) System.out.print("牛奶 ");
if (i[3]==2) System.out.print("啤酒 ");
if (i[3]==3) System.out.print("茶 ");
if (i[3]==4) System.out.print("矿泉水 ");

if (i[4]==0) System.out.print("Prince ");
if (i[4]==1) System.out.print("Pall Mall");
if (i[4]==2) System.out.print("Blue Master");
if (i[4]==3) System.out.print("Dunhill ");
if (i[4]==4) System.out.print("混合型 ");

if (i[5]==0) System.out.print("第一间 ");
if (i[5]==1) System.out.print("第二间");
if (i[5]==2) System.out.print("第三间 ");
if (i[5]==3) System.out.print("第四间 ");
if (i[5]==4) System.out.print("第五间 ");
System.out.println();

}
System.out.println();
}
}
}
</pre>
<p> </p>
<p>输出结果是：</p>
<p> </p>
<pre name="code" class="输出结果">25
21
33
14
33
德国人 绿房子鱼 咖啡 Prince 第四间
英国人 红房子 鸟 牛奶 Pall Mall第三间
丹麦人 蓝房子 马 茶 混合型 第二间
瑞典人白房子 狗 啤酒 Blue Master第五间
挪威人 黄房子 猫 矿泉水 Dunhill 第一间 </pre>
<p> </p>
<p> 程序随手写来，并没有刻意去追求算法效率跟书写版式，相信一定会有更优的求解。</p>
<p> </p>
</div>
<p>以前csdn上这道题有sql版本，JAVA版本的还是算了吧。</p>
12 楼 robertliudeqiang 2010-03-05  
gaoqs1984 写道
离散数学里讲过这样的，是太多判断了，以前是这个解的好像
A->B
C->!D
B->!C

==>B->D

A推理出B，C推理出，不是D
B推出不是C

那么B推出C



对对，就是离散数学讲的。 
发表评论

您还没有登录,请您登录后再发表评论

相关推荐

    IBM面试智力题IBM面试智力题IBM面试智力题

    综上所述，IBM面试中的智力题覆盖了广泛的领域，包括数学、逻辑、物理、化学、计算机科学等多个学科，旨在全面考察应聘者的综合素质和解决问题的能力。考生在准备这类题目时，不仅需要具备扎实的基础知识，还需要...

    微软的面试题及答案－超变态但是很经典

    根据提供的标题、描述以及部分内容，可以...以上题目涵盖了微软面试中常见的逻辑思维题、数学题以及编程基础题，旨在全面考察应聘者的能力。通过解答这些题目，可以帮助应聘者更好地准备微软以及其他科技公司的面试。

    华为-华为od题库练习题之24点游戏.zip

    6. **编程思维**：虽然这不是纯数学问题，但24点游戏也常被用来教授编程思维，如使用循环和条件语句来编写程序自动求解。 7. **心理素质**：高压环境下快速准确地解决问题，考察考生的心理承受能力和应对压力的能力...

    阿里巴巴2015秋招算法类机试题目（三阶魔方）源代码

    【标签】中的“阿里巴巴 笔试”表明这是一道阿里巴巴公司招聘过程中的试题，具有一定的专业性和挑战性，通常会考察应聘者的编程能力、算法理解以及问题解决能力。 【压缩包子文件的文件名称列表】中的“MagicCube”...

    逻辑推理解题策略.pdf

    【逻辑推理】是一种重要的能力测试，常见于各类企业招聘的笔试环节，旨在评估应聘者的逻辑思维及推理技能。逻辑推理题型多种多样，包括基础类、高级类、专业类和发散性四类。 **基础类：语言推理** 语言推理题，也...

    各大公司笔试面试题目

    【笔试面试】是求职过程中必不可少的一环，尤其是对于IT行业的应聘者来说，技术类和逻辑类的题目常常出现在笔试和面试中。以下是一些常见的笔试面试知识点： 1. **编程基础**：题目中的TC2.0环境下运行的C语言程序...

    算法谜题（算法谜题）

    有些则是比较新的谜题，体现了算法应用的最新趋势，其中一些谜题甚至已经成为知名IT企业的面试题，被用于考核应聘者的算法和编程能力。按照难易程度分级的谜题编排，有助于读者根据自己当前的算法能力水平选择合适的...

Magicbox
Global site tag (gtag.js) - Google Analytics