斑马谜题是一道著名的逻辑谜题:有五栋房子,每栋涂着不同的颜色。 房子里住着不同的人,他们的国籍不同,养的宠物不同,喝的饮料不同,爱好也不同。
为了帮你解出这道谜题,题目给出了 15 条线索,用来描述谜题的答案。 不过,只有把_所有_线索里的信息结合起来,你才能找到谜题的答案。
斑马谜题是一个约束满足问题(CSP)。 在这类问题中,你会得到一组可能的取值,以及一组限定哪些取值有效的约束。 另一个广为人知的约束满足问题是数独。
你的任务是解开斑马谜题,找出下面两个问题的答案:
下面这 15 条陈述都是已知为真的:
此外,这五栋房子分别刷成不同的颜色,住户的国籍各不相同,养的宠物不同,喝的饮料不同,爱好也各不相同。
一共有 240 亿(5!⁵ = 24,883,200,000)种可能的解,所以试着排除尽可能多的解吧。
每种国籍用一个字母表示。(E = Englishman,J = Japanese,N = Norwegian,S = Spaniard,U = Ukrainian)
探索从 240 亿种可能解中找出斑马谜题答案的 8 种不同方法,包括尽早排除无效排列、AC-3 算法、极其简洁的基于逻辑的解法,甚至还有遗传算法!