얼룩말 퍼즐은 다섯 채의 집이 나오는 유명한 논리 퍼즐이에요. 집은 각각 다른 색으로 칠해져 있어요. 집에는 서로 다른 주민이 살고 있는데, 이들은 국적도 다르고, 키우는 반려동물도 다르고, 마시는 음료도 다르고, 피우는 담배 브랜드도 달라요.
퍼즐을 풀 수 있도록, 해답을 설명하는 문장 15개가 주어져요. 하지만 모든 문장의 정보를 조합해야만 퍼즐의 해답을 찾을 수 있어요.
얼룩말 퍼즐은 제약 충족 문제(CSP)예요. 이런 제약 충족 문제에서는 가능한 값들의 집합과, 어떤 값이 유효한지 제한하는 제약 조건들의 집합이 있어요. 또 다른 유명한 제약 충족 문제로는 스도쿠가 있어요.
얼룩말 퍼즐을 풀어서 다음 두 질문의 답을 찾아봐요:
다음 15가지 사실은 모두 참이라고 알려져 있어요:
또한 다섯 채의 집은 각각 다른 색으로 칠해져 있어요. 그리고 그곳에 사는 사람들은 국적도, 기르는 동물도, 마시는 음료도, 피우는 담배 브랜드도 모두 달라요.
가능한 해답이 240억 가지(5!⁵ = 24,883,200,000)나 되니까, 최대한 많은 해답을 걸러내 봐요.