斑馬謎題是一個著名的邏輯謎題,其中有 5 棟房子,每棟漆成不同的顏色。 這些房子住著不同的居民,他們各有不同的國籍、養不同的寵物、喝不同的飲料,也有不同的嗜好。
為了幫你解開謎題,題目會給你 15 則描述解答的敘述。 不過,唯有把_全部_敘述裡的資訊結合起來,你才能找出這個謎題的解答。
斑馬謎題是一種限制滿足問題(CSP)。 在這類問題中,你會有一組可能的值,以及一組限制條件,決定哪些值是有效的。 另一個知名的 CSP 是數獨。
你的任務是解開斑馬謎題,找出以下兩個問題的答案:
以下 15 個陳述都是已知為真:
此外,這五棟房子各漆成不同的顏色,居民們的國籍、養的寵物、喝的飲料和從事的嗜好也各不相同。
可能的解有 240 億種(5!⁵ = 24,883,200,000),所以試著盡可能排除掉越多解越好。
請實作ZebraPuzzle類別中的waterDrinker和zebraOwner方法。這兩個方法都必須回傳字串,內容分別是斑馬謎題的兩個問題「誰喝水?」和「誰養斑馬?」的答案。每個答案都會是居民國籍的其中一個:Englishman、Spaniard、Ukrainian、Norwegian 或 Japanese。
當然,如果你偷看測試程式、看它預期的解答,大可以直接寫出兩個只有單一敘述的函式。不過,目標是開發出一套演算法,運用謎題給定的事實與限制條件,判斷出這兩個正確答案。
探索從 240 億種可能解法中找出斑馬謎題解答的 8 種不同方法,包括盡早忽略無效排列、AC-3 演算法、非常簡潔的邏輯解法,甚至基因演算法!