`

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

编程算法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



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

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

相关推荐

    大公司面试智力题集锦

    大公司面试智力题集锦

    一道智力题的实现

    * 爱因斯坦出的智力题 * 这道题你能做的出来的你的智商的排名在世界前200 * 1、在一条街上，有5座房子，喷了5种颜色。 * 2、每个房里住着不同国籍的人 * 3、每个人喝不同的饮料，抽不同品牌的香烟，养不同...

    笔试面试智力题（史上最全版）

    智力题是许多企业在招聘过程中用来评估应聘者逻辑思维、问题解决能力和创新思维的重要工具。这些题目通常涵盖了数学、逻辑推理、语言理解、空间想象等多个领域，对提升个人综合素质有着显著作用。 在找工作的过程中...

    面试常见智力题（逻辑分析题及答案）

    面试常见智力题是指在面试过程中经常出现的智力题目，这类题目旨在考察应聘者的逻辑思维能力、解决问题能力和创新能力等。这些题目通常具有很高的难度和挑战性，要求应聘者具备快速思考和解决问题的能力。 二、逻辑...

    笔试 面试 智力题 求职

    在求职过程中，笔试和面试是两个至关重要的环节，智力题的出现则往往能评估候选人的逻辑思维、问题解决和创新能力。这些题目不仅测试了应聘者的专业知识，还考察了他们在压力下的反应速度和应对复杂问题的能力。下面...

    Java编程常用的智力题

    "Java编程常用的智力题" 以下是对给定文件信息的详细分析和知识点总结： 1. 逻辑推理 逻辑推理是 Java 编程员面试中经常被问到的智力题之一。例如，问题 1 中要求你在 7 天内付费给工人，每天结束时给他们一段...

    校园招聘面试题面经汇总——华为，中兴，腾讯，迅雷，智力题，以及一些外企

    在IT行业的校园招聘中，企业通常会通过一系列的面试题来评估应聘者的技能、思维能力和潜在价值。华为、中兴、腾讯、迅雷等知名企业，以及一些外企，都有各自的面试策略和偏好，这些公司在面试过程中可能会涉及到的...

    面试智力题（含答案）

    面试智力题集锦 ...本资源摘要信息涵盖了多种类型的面试智力题，旨在考查应聘者的逻辑思维能力、数学计算能力、问题解决能力、逻辑思维能力、空间想象能力、数学证明能力和概率论知识等多方面的能力。

    笔试智力题大全(不全你砍我)

    《全面解析：笔试智力题大全》 在求职过程中，笔试智力题是许多企业用来筛选优秀人才的重要环节。这些题目旨在测试应聘者的逻辑思维能力、问题解决技巧以及创新性思考。本篇文章将围绕“笔试智力题大全”这一主题，...

    程序员算法大全算法数据结构智力题

    通过解决智力题，程序员可以锻炼自己的思维敏捷性，提升编程技巧，并更好地适应实际工作中的挑战。 "程序员算法大全"很可能包含了大量的编程练习题，覆盖了各种难度级别的算法和数据结构问题。这些问题可能涉及到...

    计算机笔试面试常见的智力题

    笔试常见的智力题:你让工人为你工作7天，给工人的回报是一根金条。金条平分成相连的7段;为什么下水道的盖子是圆的;有7克、2克砝码各一个，天平一只，如何只用这些物品三次将140克的盐 分成50、90克各一份;

    各大名企笔试面试智力题附答案汇总

    在IT行业的求职过程中，尤其是针对知名企业，笔试和面试往往包含了各种智力题，旨在考察候选人的逻辑思维、问题解决和创新能力。这份"各大名企笔试面试智力题附答案汇总"电子书是一个宝贵的资源，可以帮助求职者熟悉...

    经典智力题（程序员必看）

    十分经典的智力题，许多大公司如微软、IBM的采用过的面试题。可以很好的煅炼逻辑能力。难度非常大，智商低的别下载。

    100道面试智力题，要参加面试的一定要看

    100道智力趣题，面试中容易出现的智力题，也可以用于笔试中的智力题部分

    70道之智力题，开发大脑智力

    这些智力题涵盖了许多不同的主题，包括数学、逻辑推理、概率计算和策略制定。让我们逐一解析这些题目中的知识点： 1. **5升与6升水壶取3升水**：这是一个典型的数学问题，涉及到模运算和容斥原理。通过倒水和测量，...

    变态智力题大全.docx

    变态智力题大全.docx

    全球五百强IT名企智力题精选

    首先，我们来分析智力题2（猜牌问题）。这个问题涉及到了信息的不完整性与推理。P先生知道点数而不知道花色，Q先生知道花色而不知道点数，通过对话中的信息推断出牌面。解题思路涉及排除法和逻辑推理，首先排除了...

    面试智力题 (附答案面试智力题 (附答案))

    面试智力题（附答案） 本资源摘要信息涵盖了 25 个面试智力题，每个问题都具有很高的挑战性和逻辑性。这些问题涵盖了逻辑推理、数学计算、语言理解和空间想象等多方面的能力。 以下是对每个问题的详细解释和答案：...

    程序员算法大全算法数据结构智力题 C/C++

    本资源"程序员算法大全算法数据结构智力题 C/C++"聚焦于C和C++语言，提供了丰富的算法和数据结构实例，以及一些智力挑战题，帮助程序员提升这方面的能力。 首先，我们来详细探讨算法。算法是一系列明确的指令，用于...

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