爱因斯坦问题的解法

题目是这样的:

 

有5个不同国籍的人，住在5所颜色不同的一排房子里，养不同的宠物，抽不同的烟，喝不同的饮料，有以下提示：

1 英国人住在红房子里

2 瑞典人养了一条狗

3 丹麦人喝茶

4 绿房子在白房子左边

5绿房子主人喝咖啡

6抽PALL MALL烟的人养了一只鸟

7黄房子的主人抽DUNHILL烟

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

9挪威人住第一间房子

10抽混合烟的人住在养猫人的旁边

11养马人住在抽DUNHILL烟的人的旁边

12抽BLUE MASTER烟的人喝啤酒

13德国人抽PEINCE烟

14挪威人住在蓝房子旁边

15抽混合烟的人的邻居喝矿泉水

问:谁养鱼?

 

 

 

public class House implements Cloneable{
 
    public int order;
    public String color="";
    public String people="";
    public String drink="";
    public String smoke="";
    public String pet="";
    
    public House(int order) {
       super();
       this.order = order;
    }
    public House(){
    }
    public House(String color, String people, String drink,
           String smoke, String pet) {
    
       this.color = color;
       this.people = people;
       this.drink = drink;
       this.smoke = smoke;
       this.pet = pet;
    }
    
    public String toString() {
       String str=order+".["+color+"],["+people+"],["+drink+"],["+smoke+"],["+pet+"]";
       return str;
    }
    public int getOrder() {
       return order;
    }
    public void setOrder(int order) {
       this.order = order;
    }
    public String getColor() {
       return color;
    }
    public void setColor(String color) {
       this.color = color;
    }
    public String getPeople() {
       return people;
    }
    public void setPeople(String people) {
       this.people = people;
    }
    public String getDrink() {
       return drink;
    }
    public void setDrink(String drink) {
       this.drink = drink;
    }
    public String getSmoke() {
       return smoke;
    }
    public void setSmoke(String smoke) {
       this.smoke = smoke;
    }
    public String getPet() {
       return pet;
    }
    public void setPet(String pet) {
       this.pet = pet;
    }
    @Override
    protected Object clone() throws CloneNotSupportedException {
       // TODO Auto-generated method stub
       return super.clone();
    }
}

 

 

import static java.lang.System.out;

import java.lang.reflect.Field;
import java.lang.reflect.Method;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.Iterator;
import java.util.List;
import java.util.Map;

public class Result {
	private final static String PEOPLE_ENGLISH = "英国人"; // "英国人", "瑞典人",
	// "丹麦人","挪威人", "德国人"
	private final static String PEOPLE_SWEEDEN = "瑞典人";
	private final static String PEOPLE_DANMARK = "丹麦人";
	private final static String PEOPLE_NORWAY = "挪威人";
	private final static String PEOPLE_GERMEN = "德国人";

	private final static String COLOR_RED = "红"; // "红", "白", "绿", "黄", "蓝"
	private final static String COLOR_WHITE = "白";
	private final static String COLOR_GREEN = "绿";
	private final static String COLOR_YELLOW = "黄";
	private final static String COLOR_BLUE = "蓝";

	private final static String DRINK_TEA = "茶"; // "茶", "咖啡", "牛奶", "啤酒",
	// "矿泉水"
	private final static String DRINK_COFFEE = "咖啡";
	private final static String DRINK_MILK = "牛奶";
	private final static String DRINK_BEER = "啤酒";
	private final static String DRINK_WATER = "矿泉水";

	private final static String SMOKE_PALL = "PALL MALL"; // "PALL MALL",
	// "DUNHILL",
	// "混合烟","BLUE MASTER", "PEINCE"
	private final static String SMOKE_DUNHILL = "DUNHILL";
	private final static String SMOKE_MIXTRUE = "混合烟";
	private final static String SMOKE_MASTER = "BLUE MASTER";
	private final static String SMOKE_PRINCE = "PEINCE";

	private final static String PET_DOG = "狗"; // "狗", "鸟", "猫", "马", "鱼"
	private final static String PET_BIRD = "鸟";
	private final static String PET_CAT = "猫";
	private final static String PET_HORSE = "马";
	private final static String PET_FISH = "鱼";

	private static List<House> houseList = new ArrayList<House>();
	private static List<House> conList = new ArrayList<House>();
	private static House house1 = new House(1);
	private static House house2 = new House(2);
	private static House house3 = new House(3);
	private static House house4 = new House(4);
	private static House house5 = new House(5);

	static {
		houseList.add(house1);
		houseList.add(house2);
		houseList.add(house3);
		houseList.add(house4);
		houseList.add(house5);
	}

	public static void clear() {
		for (int i = 0; i < houseList.size(); i++) {
			House h = houseList.get(i);
			h.color = "";
			h.drink = "";
			h.people = "";
			h.pet = "";
			h.smoke = "";
		}
	}

	private static void init() {
		house1.people = PEOPLE_NORWAY;
		house2.color = COLOR_BLUE;
		house3.drink = DRINK_MILK;
	}

	private static void compare(boolean check) throws Exception {
		
		boolean tempcheck=false;
		for (int i = 0; i < houseList.size(); i++) {

			for (int j = i; j < houseList.size(); j++) {
				House hi = houseList.get(i);
				House hj = houseList.get(j);
				
				if(check){
					tempcheck=(hi.order+1 <hj.order);
				}else{
					tempcheck=(hi.order+1==hj.order);
				}

				if ("".equals(hi.color) && "".equals(hj.color)
						&&tempcheck) { //
					hi.color = COLOR_GREEN;
					hj.color = COLOR_WHITE;
					for (int k = 0; k < houseList.size(); k++) {

						for (int m = 0; m < houseList.size(); m++) {
							House hk = houseList.get(k);
							House hm = houseList.get(m);

							if (hk.order == hm.order + 1 || hm.order == hk.order + 1) {
								if ("".equals(hk.pet) && "".equals(hm.smoke)) {
									hk.pet = PET_HORSE;
									hm.smoke = SMOKE_DUNHILL; // 养马人住在抽DUNHILL烟的人的旁边

									for (int n = 0; n < houseList.size(); n++) {

										for (int p = 0; p < houseList.size(); p++) {
											House hn = houseList.get(n);
											House hp = houseList.get(p);

											if (hn.order == hp.order + 1 || hp.order == hn.order + 1) {
												if ("".equals(hn.smoke)
														&& "".equals(hp.pet)) {
													hn.smoke = SMOKE_MIXTRUE;
													hp.pet = PET_CAT; // 抽混合烟的人住在养猫人的旁边
													for (int q = 0; q < houseList
															.size(); q++) {
														House hq = houseList
																.get(q);
														if ((((hn.order == hq.order - 1) || (hn.order == hq.order + 1)) && ""
																.equals(hq.drink))) { // 抽混合烟的人的邻居喝矿泉水
															hq.drink = DRINK_WATER;
															//printResult();
															getResult(getList(houseList),getList(houseList),0,0);
															hq.drink = "";
														}
													}

													hn.smoke = "";
													hp.pet = "";
												}
											}
										}
									}
									hk.pet = "";
									hm.smoke = "";
								}
							}
						}
					}
					clear();
					init();
				}
			}
		}
	}

	private static void getResult(List tempList, List<House> tempList1,
			int start, int num) throws Exception {
		if(num==conList.size()) {
		out.println("====================");
		for (int i = 0; i < tempList1.size(); i++) {
			House house = tempList1.get(i);
			out.println(house);
		}
		out.println("====================");
		return;
	   }
		
		for (int k = start; k < conList.size(); k++) {
			House hk = conList.get(k);
			Map<String, String> maps = getFields(hk);
			Iterator iterator = maps.entrySet().iterator();
			String str = "";

			while (iterator.hasNext()) {
				Map.Entry<String, String> entry = (Map.Entry) iterator.next();
				String key = entry.getKey();
				String value = entry.getValue();
				if (!"".equals(value)) {
					str += key + ",";
				}
			}
			boolean tcheck = true; // 判断条件是否符合
			for (int i = 0; i < tempList.size(); i++) {
				House house = tempList1.get(i);
				Map<String, String> houseMaps = getFields(house);
				// 把所有非空元素的拿出来
				String[] strs = str.split(",");
				if (strs.length > 0) {
					int c = 0;
					for (int m = 0; m < strs.length; m++) {
						String temp = (String) house.getClass().getField(
								strs[m]).get(house); // 得到当前节点元素的值
						String temp1 = (String) hk.getClass().getField(strs[m])
								.get(hk); // 得到当前条件的元素的值
						// 如果当前节点的值不为空以及两个条件不相等，说明该条件不符合,否则符合条件
						if (!"".equals(temp) && !temp.equals(temp1)) {
							tcheck = false;
							break;
						}else tcheck=true;
						
					}
					if (tcheck) {
						for (int m = 0; m < strs.length; m++) {
							String temp = (String) hk.getClass().getField(
									strs[m]).get(hk); // 条件的值
							if (c != strs.length) {
								setValueByField(house, strs[m], temp); // 更新条件的值
							}
						}
						num++;
						getResult(getList(tempList1), getList(tempList1), 
								k + 1, num);
						for (int m = 0; m < strs.length; m++) {
							
							if (c != strs.length) {
								setValueByField(house, strs[m], ""); // 还原条件的值
							}
						}
						num--;
					}
				}
			}
			if(tcheck) return;
		}
		return;
	}


   /**
    * 克隆list
    * @param list
    * @return
    * @throws Exception
    */
	private static List<House> getList(List<House> list) throws Exception {
		List<House> tempList = new ArrayList<House>();
		for (int j = 0; j < list.size(); j++) {
			House hou = (House) (list.get(j).clone());
			tempList.add(hou);
		}
		return tempList;
	}

	//设置当前类的字段为field的值为value
	private static void setValueByField(Object obj, String field, Object value) {

		try {
			String firstW = field.substring(0, 1);
			String methodName = "set" + firstW.toUpperCase()
					+ field.substring(1);
			Class c = obj.getClass();
			Method[] ms = c.getMethods();
			for (Method m : ms) {
				if (m.getName().equals(methodName)
						&& m.getParameterTypes().length == 1) {
					Object[] params = { value };
					try {
						m.invoke(obj, params);
						return;
					} catch (IllegalArgumentException e) {
						e.printStackTrace();
					} catch (IllegalAccessException e) {
						e.printStackTrace();
					}
				}
			}
			Field[] fs = c.getFields();
			for (Field f : fs) {
				if (f.getName().equals(field)) {
					try {
						f.set(obj, value);
						return;
					} catch (IllegalArgumentException e) {
						e.printStackTrace();
					} catch (IllegalAccessException e) {
						e.printStackTrace();
					}
				}
			}
		} catch (Exception e) {
			e.printStackTrace();
		}

	}

	// 判断条件
	private static void initCondition() {
		House house1 = new House(COLOR_RED, PEOPLE_ENGLISH, "", "", "");// 英国人住在红房子里
		House house2 = new House("", PEOPLE_SWEEDEN, "", "", PET_DOG); // 瑞典人养了一条狗
		House house3 = new House("", PEOPLE_DANMARK, DRINK_TEA, "", ""); // 丹麦人喝茶
		House house5 = new House(COLOR_GREEN, "", DRINK_COFFEE, "", ""); // 绿房子主人喝咖啡
		House house6 = new House("", "", "", SMOKE_PALL, PET_BIRD); // // MALL烟的人养了一只鸟
		House house7 = new House(COLOR_YELLOW, "", "", SMOKE_DUNHILL, ""); // 黄房子的主人抽DUNHILL烟
		House house12 = new House("", "", DRINK_BEER, SMOKE_MASTER, ""); // 抽BLUE MASTER烟的人喝啤酒
		House house13 = new House("", PEOPLE_GERMEN, "", SMOKE_PRINCE, ""); // 德国人抽PEINCE烟
		House house16 = new House("", "", "", "", PET_FISH);  //鱼
		conList.add(house1);
		conList.add(house2);
		conList.add(house3);
		conList.add(house5);
		conList.add(house6);
		conList.add(house7);
		conList.add(house12);
		conList.add(house13);
		conList.add(house16);
	}

    /**
     * 根据当前类得到所有的String类型的成员
     * @param obj
     * @return
     */
	private static Map<String, String> getFields(Object obj) {
		Map<String, String> map = new HashMap<String, String>();
		try {
			Class cls = obj.getClass();
			Field[] fields = cls.getDeclaredFields();

			Method method;
			Object o = cls.newInstance();

			for (int i = 0; i < fields.length; i++) {
				String fieldName = fields[i].getName();
				String first = fieldName.substring(0, 1);
				String upFisrt = first.toUpperCase();
				String geter = "get" + upFisrt + fieldName.substring(1);
				method = cls.getMethod(geter, new Class[] {});
				Object invoke = method.invoke(obj, new Object[] {});
				if (invoke instanceof String)
					map.put(fieldName, (String) method.invoke(obj,
							new Object[] {}));
			}
		} catch (Exception e) {
		}
		return map;

	}

	public static void main(String[] args) throws Exception {
		boolean check=false; //false为相邻,true为不相邻
		init();
		initCondition();
		compare(check);
	}

}