爱因斯坦谜题(DFS+JAVA)
·
有 5 幢房子，每幢房子颜色不同，里面住的 主人国籍不同，喝的饮料不同，抽的烟不同，养的宠物不同。
已知条件：
英国人住在红房子里。
瑞典人养狗。
丹麦人喝茶。
绿房子在白房子的左边（相邻左边）。
绿房子的主人喝咖啡。
抽 Pall Mall 烟的人养鸟。
黄房子的主人抽 Dunhill 烟。
住在中间房子的人喝牛奶。
挪威人住在第一幢房子。
抽 Blends 烟的人住在养猫的人隔壁。
养马的人住在抽 Dunhill 烟的人隔壁。
抽 Blue Master 烟的人喝啤酒。
德国人抽 Prince 烟。
挪威人住在蓝房子隔壁。
抽 Blends 烟的人有一个喝水的邻居。
问题：谁养鱼？
package 上课练习;
import java.io.*;
import java.util.*;
public class Main {
// 定义所有可能的属性值
static final String[] COLORS = {"红", "蓝", "绿", "黄", "白"};
static final String[] NATIONALITIES = {"英", "瑞", "丹", "挪", "德"};
static final String[] DRINKS = {"茶", "咖啡", "牛奶", "啤酒", "水"};
static final String[] CIGARETTES = {"Pall Mall", "Dunhill", "Blends", "Blue Master", "Prince"};
static final String[] PETS = {"狗", "鸟", "猫", "马", "鱼"};
static class House {
String color;
String nationality;
String drink;
String cigarette;
String pet;
}
public static void main(String[] args) {
House[] houses = new House[5];
for (int i = 0; i < 5; i++) {
houses[i] = new House();
}
// 记录已使用的属性值
Set<String> usedColors = new HashSet<>();
Set<String> usedNationalities = new HashSet<>();
Set<String> usedDrinks = new HashSet<>();
Set<String> usedCigarettes = new HashSet<>();
Set<String> usedPets = new HashSet<>();
// 应用确定性约束
houses[0].nationality = "挪"; // 挪威人住第一间
usedNationalities.add("挪");
houses[2].drink = "牛奶"; // 第三间喝牛奶
usedDrinks.add("牛奶");
boolean solved = solveOptimized(houses, 0, usedColors, usedNationalities,
usedDrinks, usedCigarettes, usedPets);
if (solved) {
printSolution(houses);
} else {
System.out.println("无解！");
}
}
private static boolean solveOptimized(House[] houses, int houseIndex,
Set<String> usedColors, Set<String> usedNationalities,
Set<String> usedDrinks, Set<String> usedCigarettes,
Set<String> usedPets) {
if (houseIndex == 5) {
return true; // 所有约束已在填充时检查
}
House house = houses[houseIndex];
// 优化搜索顺序：先填充确定性高的属性
// 1. 填充颜色
for (String color : COLORS) {
if (usedColors.contains(color)) continue;
// 应用颜色相关约束
if (color.equals("黄") && houseIndex != 0) continue; // 黄房子是第一间
if (houseIndex == 4 && color.equals("白")) continue; // 白房子不能是最后一间(因为绿房子在它左边)
house.color = color;
usedColors.add(color);
// 2. 填充国籍 (已填充挪威人)
if (house.nationality == null) {
for (String nationality : NATIONALITIES) {
if (usedNationalities.contains(nationality)) continue;
// 应用国籍相关约束
if (nationality.equals("挪") && houseIndex != 0) continue;
house.nationality = nationality;
usedNationalities.add(nationality);
// 3. 填充饮料 (已填充牛奶)
if (house.drink == null) {
for (String drink : DRINKS) {
if (usedDrinks.contains(drink)) continue;
// 应用饮料相关约束
if (drink.equals("牛奶") && houseIndex != 2) continue;
if (color.equals("绿") && !drink.equals("咖啡")) continue;
house.drink = drink;
usedDrinks.add(drink);
// 4. 填充香烟
for (String cigarette : CIGARETTES) {
if (usedCigarettes.contains(cigarette)) continue;
// 应用香烟相关约束
if (color.equals("黄") && !cigarette.equals("Dunhill")) continue;
if (nationality.equals("德") && !cigarette.equals("Prince")) continue;
house.cigarette = cigarette;
usedCigarettes.add(cigarette);
// 5. 填充宠物
for (String pet : PETS) {
if (usedPets.contains(pet)) continue;
// 应用宠物相关约束
if (cigarette.equals("Pall Mall") && !pet.equals("鸟")) continue;
if (nationality.equals("瑞") && !pet.equals("狗")) continue;
house.pet = pet;
usedPets.add(pet);
// 检查相邻约束
if (checkAdjacentConstraints(houses, houseIndex)) {
// 递归填充下一个房子
if (solveOptimized(houses, houseIndex + 1,
usedColors, usedNationalities,
usedDrinks, usedCigarettes, usedPets)) {
return true;
}
}
// 回溯
usedPets.remove(pet);
house.pet = null;
}
// 回溯
usedCigarettes.remove(cigarette);
house.cigarette = null;
}
// 回溯
usedDrinks.remove(drink);
house.drink = null;
}
} else {
// 已经填充了饮料(牛奶)，只需检查相关约束
if (color.equals("绿") && !house.drink.equals("咖啡")) {
usedNationalities.remove(nationality);
house.nationality = null;
continue;
}
// 4. 填充香烟
for (String cigarette : CIGARETTES) {
if (usedCigarettes.contains(cigarette)) continue;
// 应用香烟相关约束
if (color.equals("黄") && !cigarette.equals("Dunhill")) continue;
if (nationality.equals("德") && !cigarette.equals("Prince")) continue;
house.cigarette = cigarette;
usedCigarettes.add(cigarette);
// 5. 填充宠物
for (String pet : PETS) {
if (usedPets.contains(pet)) continue;
// 应用宠物相关约束
if (cigarette.equals("Pall Mall") && !pet.equals("鸟")) continue;
if (nationality.equals("瑞") && !pet.equals("狗")) continue;
house.pet = pet;
usedPets.add(pet);
// 检查相邻约束
if (checkAdjacentConstraints(houses, houseIndex)) {
// 递归填充下一个房子
if (solveOptimized(houses, houseIndex + 1,
usedColors, usedNationalities,
usedDrinks, usedCigarettes, usedPets)) {
return true;
}
}
// 回溯
usedPets.remove(pet);
house.pet = null;
}
// 回溯
usedCigarettes.remove(cigarette);
house.cigarette = null;
}
}
// 回溯
usedNationalities.remove(nationality);
house.nationality = null;
}
} else {
// 已经填充了国籍(挪威人)，处理其他属性
// 3. 填充饮料 (已填充牛奶)
if (house.drink == null) {
for (String drink : DRINKS) {
if (usedDrinks.contains(drink)) continue;
// 应用饮料相关约束
if (drink.equals("牛奶") && houseIndex != 2) continue;
if (color.equals("绿") && !drink.equals("咖啡")) continue;
house.drink = drink;
usedDrinks.add(drink);
// 4. 填充香烟
for (String cigarette : CIGARETTES) {
if (usedCigarettes.contains(cigarette)) continue;
// 应用香烟相关约束
if (color.equals("黄") && !cigarette.equals("Dunhill")) continue;
if (house.nationality.equals("德") && !cigarette.equals("Prince")) continue;
house.cigarette = cigarette;
usedCigarettes.add(cigarette);
// 5. 填充宠物
for (String pet : PETS) {
if (usedPets.contains(pet)) continue;
// 应用宠物相关约束
if (cigarette.equals("Pall Mall") && !pet.equals("鸟")) continue;
if (house.nationality.equals("瑞") && !pet.equals("狗")) continue;
house.pet = pet;
usedPets.add(pet);
// 检查相邻约束
if (checkAdjacentConstraints(houses, houseIndex)) {
// 递归填充下一个房子
if (solveOptimized(houses, houseIndex + 1,
usedColors, usedNationalities,
usedDrinks, usedCigarettes, usedPets)) {
return true;
}
}
// 回溯
usedPets.remove(pet);
house.pet = null;
}
// 回溯
usedCigarettes.remove(cigarette);
house.cigarette = null;
}
// 回溯
usedDrinks.remove(drink);
house.drink = null;
}
} else {
// 已经填充了饮料(牛奶)，只需检查相关约束
if (color.equals("绿") && !house.drink.equals("咖啡")) {
usedColors.remove(color);
house.color = null;
continue;
}
// 4. 填充香烟
for (String cigarette : CIGARETTES) {
if (usedCigarettes.contains(cigarette)) continue;
// 应用香烟相关约束
if (color.equals("黄") && !cigarette.equals("Dunhill")) continue;
if (house.nationality.equals("德") && !cigarette.equals("Prince")) continue;
house.cigarette = cigarette;
usedCigarettes.add(cigarette);
// 5. 填充宠物
for (String pet : PETS) {
if (usedPets.contains(pet)) continue;
// 应用宠物相关约束
if (cigarette.equals("Pall Mall") && !pet.equals("鸟")) continue;
if (house.nationality.equals("瑞") && !pet.equals("狗")) continue;
house.pet = pet;
usedPets.add(pet);
// 检查相邻约束
if (checkAdjacentConstraints(houses, houseIndex)) {
// 递归填充下一个房子
if (solveOptimized(houses, houseIndex + 1,
usedColors, usedNationalities,
usedDrinks, usedCigarettes, usedPets)) {
return true;
}
}
// 回溯
usedPets.remove(pet);
house.pet = null;
}
// 回溯
usedCigarettes.remove(cigarette);
house.cigarette = null;
}
}
}
// 回溯
usedColors.remove(color);
house.color = null;
}
return false;
}
// 检查相邻约束
private static boolean checkAdjacentConstraints(House[] houses, int currentIndex) {
// 绿房子在白房子左边且相邻
if (currentIndex > 0 && houses[currentIndex-1].color != null
&& houses[currentIndex-1].color.equals("绿")
&& houses[currentIndex].color != null && houses[currentIndex].color.equals("白")) {
// 检查绿房子喝咖啡
if (!houses[currentIndex-1].drink.equals("咖啡")) return false;
}
// 挪威人住在蓝房子隔壁
if (currentIndex > 0 && houses[currentIndex-1].nationality != null
&& houses[currentIndex-1].nationality.equals("挪")
&& houses[currentIndex].color != null && houses[currentIndex].color.equals("蓝")) {
return true;
}
if (currentIndex < 4 && houses[currentIndex+1].nationality != null
&& houses[currentIndex+1].nationality.equals("挪")
&& houses[currentIndex].color != null && houses[currentIndex].color.equals("蓝")) {
return true;
}
// 抽Blends的人住在养猫的人隔壁
if (houses[currentIndex].cigarette != null && houses[currentIndex].cigarette.equals("Blends")) {
boolean hasCatNeighbor = false;
if (currentIndex > 0 && houses[currentIndex-1].pet != null
&& houses[currentIndex-1].pet.equals("猫")) hasCatNeighbor = true;
if (currentIndex < 4 && houses[currentIndex+1].pet != null
&& houses[currentIndex+1].pet.equals("猫")) hasCatNeighbor = true;
if (!hasCatNeighbor) return false;
}
// 养马的人住在抽Dunhill的人隔壁
if (houses[currentIndex].pet != null && houses[currentIndex].pet.equals("马")) {
boolean hasDunhillNeighbor = false;
if (currentIndex > 0 && houses[currentIndex-1].cigarette != null
&& houses[currentIndex-1].cigarette.equals("Dunhill")) hasDunhillNeighbor = true;
if (currentIndex < 4 && houses[currentIndex+1].cigarette != null
&& houses[currentIndex+1].cigarette.equals("Dunhill")) hasDunhillNeighbor = true;
if (!hasDunhillNeighbor) return false;
}
// 抽Blends的人有一个喝水的邻居
if (houses[currentIndex].cigarette != null && houses[currentIndex].cigarette.equals("Blends")) {
boolean hasWaterNeighbor = false;
if (currentIndex > 0 && houses[currentIndex-1].drink != null
&& houses[currentIndex-1].drink.equals("水")) hasWaterNeighbor = true;
if (currentIndex < 4 && houses[currentIndex+1].drink != null
&& houses[currentIndex+1].drink.equals("水")) hasWaterNeighbor = true;
if (!hasWaterNeighbor) return false;
}
return true;
}
private static void printSolution(House[] houses) {
System.out.println("房子编号 | 颜色 | 国籍 | 饮料 | 香烟 | 宠物");
System.out.println("-----------------------------------------------");
for (int i = 0; i < 5; i++) {
House house = houses[i];
System.out.printf("%d | %-3s | %-3s | %-4s | %-10s | %s%n",
i + 1,
house.color,
house.nationality,
house.drink,
house.cigarette,
house.pet);
}
}
}
Agent 垂直技术社区，欢迎活跃、内容共建。
更多推荐
1
0- 0
已为社区贡献1条内容
所有评论(0)