Java程序实现爱因斯坦逻辑推理题
我最近是有点闲的,感觉越来越模糊,看不清前方的路,何处何从... ...
无聊...于是做起同事发过来的一道爱因斯坦逻辑推理题.
题目如下:??
????有五个具有五种不同颜色的房间；??
????每个房间里分别住着一个不同国籍的人；??
????每个人都在喝一种特定品牌的饮料，抽一特定品牌的香烟，养一特定的宠物；??
????没有任意两个人在抽相同品牌的香烟，或喝相同品牌的饮料，或养相同的宠物。??
????爱因斯坦给出了如下线索：??
????1．英国人住在红色的房子里；??
????2．瑞典人养狗；??
????3．丹麦人喝茶；??
????4．绿房子紧挨着白房子，在白房子的左边；??
????5．绿房子的主人喝咖啡；????
????6．抽PallMall牌香烟的人养鸟；??
????7．黄色房子里的人抽Dunhill牌香烟；??
????8．住在中间那个房子里的人喝牛奶；??
????9．挪威人住在第一个房子里(最左边)；??
????10．抽Blends香烟的人和养描的人相邻；??
????11．养马的人和抽Dunhill牌香烟的人相邻；??
????12．抽BlueMaster牌香烟的人喝啤酒；??
????13．德国人抽Prince牌香烟；??
????14．挪威人和住蓝房子的人相邻；??
?? 15．抽Blends香烟的人和喝矿泉水的人相邻；
????问: 谁养鱼?
JAVA程序实现如下:
package einstein;
import java.util.ArrayList;
import java.util.Arrays;
public class Subject {
/**
??* @huanxisu
??*/
String[] color;
String[] nationality;
String[] drink;
String[] pet;
String[] cigarette;
ArrayList colors;
ArrayList nationalities;
ArrayList drinks;
ArrayList pets;
ArrayList cigarettes;
boolean flag = false;
// 初始化，为方便将用数字12345分别对应
public Subject() {
??// color = new String[] { "Yellow", "Red", "Green", "White", "Blue" };
??color = new String[] { "1", "2", "3", "4", "5" };
??// nationality = new String[] { "NorWay", "English", "German",
??// "Sweden","Denmark" };
??nationality = new String[] { "1", "2", "3",
????"4","5" };
??// drink = new String[] { "Water", "Tea", "Beer", "Milk", "Coffee" };
??drink = new String[] { "1", "2", "3", "4", "5" };
??// pet = new String[] { "Dog", "Cat", "Bird", "Horse", "Fish" };
?? pet = new String[] { "1", "2", "3", "4", "5" };
??// cigarette = new String[] { "PallMall", "DunHill",
??// "Blends","BlueMarster", "Prince" };
?? cigarette = new String[] { "1", "2",
???? "3","4", "5" };
}
public ArrayList getResult() {
??Arrange a=new Arrange();
??// 颜色，国籍，饮料，宠物，香烟取得各自的全排列。
??colors = (ArrayList) a.arrange(Arrays.asList(color),"",5);
??nationalities = (ArrayList) a.arrange(Arrays.asList(nationality),"",5);
??drinks = (ArrayList)a.arrange(Arrays.asList(drink),"",5);
??pets = (ArrayList) a.arrange(Arrays.asList(pet),"",5);
??cigarettes = (ArrayList)a.arrange(Arrays.asList(cigarette),"",5);
??// Result用来存放答案
??ArrayList Result = new ArrayList();
??// 对各自的全排列每次取一种排列
??String[] s1 = null;
??String[] s2 = null;
??String[] s3 = null;
??String[] s4 = null;
??String[] s5 = null;
??// 五个嵌套的for循环，涵盖所有可能的组合
??for (int i = 0; i < 120; i++) {
?? s1 = (String[]) colors.get(i);
?? if (!s1[1].equals("5"))// 挪威人住蓝色房子旁边
????continue;
?? if (s1[0].equals("3") || s1[1].equals("3")
???? || s1[4].equals("3"))// 绿色房子在白色房子的左面
????continue;
?? for (int j = 0; j < 120; j++) {
????flag = false;
????s2 = (String[]) nationalities.get(j);
????if (!s2[0].equals("1"))// 挪威人住第一间房子
???? continue;
????for (int d1 = 0; d1 < 5; d1++) {
???? if (!(s1[d1].equals("2") && s2[d1].equals("2")))// 英国人住在红房子里
???? {
??????if (d1 == 4) {
?????? flag = true;
?????? break;
??????}
??????continue;
???? } else
??????break;
????}
????if (flag)
???? continue;
????for (int k = 0; k < 120; k++) {
???? flag = false;
???? s3 = (String[]) drinks.get(k);
???? if (s3[0].equals("5") || s3[1].equals("5")
?????? || s3[4].equals("5"))// 绿房子主人喝咖啡
??????continue;
???? if (!s3[2].equals("4"))// 住在中间那间房子的人喝牛奶
??????continue;
???? for (int d2 = 0; d2 < 5; d2++) {
??????if (!(s2[d2].equals("5") && s3[d2].equals("2")))// 丹麦人喝茶
??????{
?????? if (d2 == 4) {
????????flag = true;
????????break;
?????? }
?????? continue;
??????} else
?????? break;
???? }
???? if (flag)
??????continue;
???? for (int l = 0; l < 120; l++) {
??????flag = false;
??????s4 = (String[]) pets.get(l);
??????for (int d3 = 0; d3 < 5; d3++) {
?????? if (!(s2[d3].equals("4") && s4[d3]
???????? .equals("1")))// 瑞典人养了一条狗
?????? {
????????if (d3 == 4) {
???????? flag = true;
???????? break;
????????}
????????continue;
?????? } else
????????break;
??????}
??????if (flag)
?????? continue;
??????for (int m = 0; m < 120; m++) {
?????? flag = false;
?????? s5 = (String[]) cigarettes.get(m);
?????? for (int d4 = 0; d4 < 5; d4++) {
????????if (!(s5[d4].equals("1") && s4[d4]
??????????.equals("3")))// 抽PallMall烟的人养了一只鸟
????????{
???????? if (d4 == 4) {
??????????flag = true;
??????????break;
???????? }
???????? continue;
????????} else
???????? break;
?????? }
?????? if (flag)
????????continue;
?????? for (int d5 = 0; d5 < 5; d5++) {
????????if (!(s1[d5].equals("1") && s5[d5]
??????????.equals("2")))// 黄房子主人抽DunHill 烟
????????{
???????? if (d5 == 4) {
??????????flag = true;
??????????break;
???????? }
???????? continue;
????????} else
???????? break;
?????? }
?????? if (flag)
????????continue;
?????? for (int d6 = 0; d6 < 5; d6++) {// 抽Blends的人住在养猫人的旁边
????????flag = false;
????????if (d6 == 0) {
???????? if (s5[0].equals("3")) {
??????????if (!s4[1].equals("2")) {
?????????? flag = true;
?????????? break;
??????????}
??????????break;
???????? }
???????? if (s4[0].equals("2")) {
??????????if (!s5[1].equals("3")) {
?????????? flag = true;
?????????? break;
??????????}
??????????break;
???????? }
???????? continue;
????????}
????????if (d6 > 0 && d6 < 4) {
???????? if (s5[d6].equals("3")) {
??????????if (!(s4[d6 - 1].equals("2") || s4[d6 + 1]
????????????.equals("2"))) {
?????????? flag = true;
?????????? break;
??????????} else
?????????? break;
???????? }
???????? if (s4[d6].equals("2")) {
??????????if (!(s5[d6 - 1].equals("3") || s5[d6 + 1]
????????????.equals("3"))) {
?????????? flag = true;
?????????? break;
??????????} else
?????????? break;
???????? }
???????? continue;
????????}
????????if (d6 == 4) {
???????? if (s5[4].equals("3")) {
??????????if (!s4[3].equals("2")) {
?????????? flag = true;
?????????? break;
??????????}
??????????break;
???????? }
???????? if (s4[4].equals("2")) {
??????????if (!s5[3].equals("3")) {
?????????? flag = true;
?????????? break;
??????????}
??????????break;
???????? }
???????? flag = true;
???????? break;
????????}
?????? }
?????? System.out.println(flag);
?????? if (flag)
????????continue;
?????? for (int d7 = 0; d7 < 5; d7++) {
????????if (!(s5[d7].equals("4") && s3[d7]
??????????.equals("3")))// 抽BlueMarster烟的人喝啤酒
????????{
???????? if (d7 == 4) {
??????????flag = true;
??????????break;
???????? }
???????? continue;
????????} else
???????? break;
?????? }
?????? if (flag)
????????continue;
?????? for (int d8 = 0; d8 < 5; d8++) {
????????if (!(s2[d8].equals("3") && s5[d8]
??????????.equals("5")))// 德国人抽Prince烟
????????{
???????? if (d8 == 4) {
??????????flag = true;
??????????break;
???????? }
???????? continue;
????????} else
???????? break;
?????? }
?????? if (flag)
????????continue;
?????? for (int d9 = 0; d9 < 5; d9++) {// 养马人住在DunHill烟的人旁边
????????flag = false;
????????if (d9 == 0) {
???????? if (s5[0].equals("2")) {
??????????if (!s4[1].equals("4")) {
?????????? flag = true;
?????????? break;
??????????}
??????????break;
???????? }
???????? if (s4[0].equals("4")) {
??????????if (!s5[1].equals("2")) {
?????????? flag = true;
?????????? break;
??????????}
??????????break;
???????? }
???????? continue;
????????}
????????if (d9 > 0 && d9 < 4) {
???????? if (s5[d9].equals("2")) {
??????????if (!s4[d9 - 1].equals("4")
????????????&& !s4[d9 + 1].equals("4")) {
?????????? flag = true;
?????????? break;
??????????} else
?????????? break;
???????? }
???????? if (s4[d9].equals("4")) {
??????????if (!s5[d9 - 1].equals("2")
????????????&& !s5[d9 + 1]
??????????????.equals("2")) {
?????????? flag = true;
?????????? break;
??????????} else
?????????? break;
???????? }
???????? continue;
????????}
????????if (d9 == 4) {
???????? if (s5[4].equals("2")) {
??????????if (!s4[3].equals("4")) {
?????????? flag = true;
?????????? break;
??????????}
??????????break;
???????? }
???????? if (s4[4].equals("4")) {
??????????if (!s5[3].equals("2")) {
?????????? flag = true;
?????????? break;
??????????}
??????????break;
???????? }
???????? flag = true;
???????? break;
????????}
?????? }
?????? if (flag)
????????continue;
?????? for (int d10 = 0; d10 < 5; d10++) {// 抽Blends的人的邻居喝矿泉水
????????flag = false;
????????if (d10 == 0) {
???????? if (s5[0].equals("3")) {
??????????if (!s3[1].equals("1")) {
?????????? flag = true;
?????????? break;
??????????}
??????????break;
???????? }
???????? if (s3[0].equals("1")) {
??????????if (!s5[1].equals("3")) {
?????????? flag = true;
?????????? break;
??????????}
??????????break;
???????? }
???????? continue;
????????}
????????if (d10 > 0 && d10 < 4) {
???????? if (s5[d10].equals("3")) {
??????????if (!s3[d10 - 1].equals("1")
????????????&& !s3[d10 + 1].equals("1")) {
?????????? flag = true;
?????????? break;
??????????} else
?????????? break;
???????? }
???????? if (s3[d10].equals("1")) {
??????????if (!s5[d10 - 1].equals("3")
????????????&& !s5[d10 + 1]
??????????????.equals("3")) {
?????????? flag = true;
?????????? break;
??????????} else
?????????? break;
???????? }
???????? continue;
????????}
????????if (d10 == 4) {
???????? if (s5[4].equals("3")) {
??????????if (!s3[3].equals("1")) {
?????????? flag = true;
?????????? break;
??????????}
??????????break;
???????? }
???????? if (s3[4].equals("1")) {
??????????if (!s5[3].equals("3")) {
?????????? flag = true;
?????????? break;
??????????}
??????????break;
???????? }
???????? flag = true;
???????? break;
????????}
?????? }
?????? if (flag)
????????continue;
?????? else {//能到达这里的就是符合所有条件的正确答案
????????Result.add(s1);
????????Result.add(s2);
????????Result.add(s3);
????????Result.add(s4);
????????Result.add(s5);
????????return Result;
?????? }
??????}
???? }
????}
?? }
??}
??return Result;
}
}
采用递归实现全排列的类(Arrange):
package einstein;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
public class Arrange {
/**
??* @huanxisu
??*/
List allList = new ArrayList();;
//递归实现全排列
public List arrange(List str, String prefix, int length) {
??if (prefix.length() == length) {
?? String[] s = new String[] { prefix.substring(0, 1),
???? prefix.substring(1, 2), prefix.substring(2, 3),
???? prefix.substring(3, 4), prefix.substring(4) };
?? allList.add(s);//得到一种排列就添加
??}
??for (int i = 0; i < str.size(); i++) {
?? List temp = new LinkedList(str);
?? arrange(temp, prefix + temp.remove(i), length);
??}
??return allList;
}
}
测试程序：
package einstein;
import java.util.ArrayList;
import java.util.Date;
public class Test {
/**
??* @huanxisu
??*/
public static void main(String[] args) {
??Subject subject = new Subject();
??ArrayList arr = subject.getResult();
??System.out.println(arr.size());
??//将数字替换为之前对应的内容
??String[] s1=(String[])arr.get(0);
??String[] s2=(String[])arr.get(1);
??String[] s3=(String[])arr.get(2);
??String[] s4=(String[])arr.get(3);
??String[] s5=(String[])arr.get(4);
??System.out.print("{");
??for(int i=0;i<5;i++){
?? String temp;
?? if(s1[i].equals("1"))
????temp="Yellow";
?? else if(s1[i].equals("2"))
????temp="Red";
?? else if(s1[i].equals("3"))
????temp="Green";
?? else if(s1[i].equals("4"))
????temp="White";
?? else temp="Blue";
?? System.out.print(temp+" ");
??}
??System.out.println("}");
??System.out.print("{");
??for(int i=0;i<5;i++){
?? String temp;
?? if(s2[i].equals("1"))
????temp="NorWay";
?? else if(s2[i].equals("2"))
????temp="English";
?? else if(s2[i].equals("3"))
????temp="German";
?? else if(s2[i].equals("4"))
????temp="Sweden";
?? else temp="Denmark";
?? System.out.print(temp+" ");
??}
??System.out.println("}");
??System.out.print("{");
??for(int i=0;i<5;i++){
?? String temp;
?? if(s3[i].equals("1"))
????temp="Water";
?? else if(s3[i].equals("2"))
????temp="Tea";
?? else if(s3[i].equals("3"))
????temp="Beer";
?? else if(s3[i].equals("4"))
????temp="Milk";
?? else temp="Coffee";
?? System.out.print(temp+" ");
??}
??System.out.println("}");
??System.out.print("{");
??for(int i=0;i<5;i++){
?? String temp;
?? if(s4[i].equals("1"))
????temp="Dog";
?? else if(s4[i].equals("2"))
????temp="Cat";
?? else if(s4[i].equals("3"))
????temp="Bird";
?? else if(s4[i].equals("4"))
????temp="Horse";
?? else temp="Fish";
?? System.out.print(temp+" ");
??}
??System.out.println("}");
??System.out.print("{");
??for(int i=0;i<5;i++){
?? String temp;
?? if(s5[i].equals("1"))
????temp="PallMall";
?? else if(s5[i].equals("2"))
????temp="DunHill";
?? else if(s5[i].equals("3"))
????temp="Blends";
?? else if(s5[i].equals("4"))
????temp="BlueMarster";
?? else temp="Prince";
?? System.out.print(temp+" ");
??}
??System.out.println("}");
??/**调试程序，以下输出的结果为数字代替
??for (Object o : arr) {
?? System.out.print("{");
?? for (String s : (String[]) o) {
????System.out.print(s + " ");
?? }
?? System.out.println("}");
??}
??*/
}
}
运行Test测试程序，结果如下：
{Yellow Blue Red Green White }
{NorWay Denmark English German Sweden }
{Water Tea Milk Coffee Beer }
{Cat Horse Bird Fish Dog }
{DunHill Blends PallMall Prince BlueMarster }
当然，这不是性能最好的程序，希望发现不足的地方可以互相学习。
