얼룩말 퍼즐은 집 다섯 채가 나오는 유명한 논리 퍼즐이에요. 집은 각각 다른 색으로 칠해져 있고, 사는 주민도 서로 달라요. 주민들은 국적도 다르고, 키우는 반려동물도 다르고, 마시는 음료도 다르고, 즐기는 취미도 달라요.
퍼즐을 풀 수 있도록, 정답을 설명하는 15개의 명제가 주어져요. 하지만 모든 명제의 정보를 조합해야만 퍼즐의 정답을 찾을 수 있어요.
얼룩말 퍼즐은 제약 충족 문제(CSP)예요. 이런 문제에는 가능한 값의 집합과, 어떤 값이 유효한지 제한하는 제약 조건의 집합이 있어요. 잘 알려진 또 다른 CSP로는 스도쿠가 있어요.
이번 과제는 얼룩말 퍼즐을 풀어서 다음 두 가지 질문의 답을 찾는 거예요:
다음 15가지 문장은 모두 참이라고 알려져 있어요:
게다가 다섯 채의 집은 각각 다른 색으로 칠해져 있고, 그곳에 사는 사람들은 각각 다른 국적이고, 다른 반려동물을 키우고, 다른 음료를 마시고, 다른 취미를 가져요.
가능한 해답은 240억 가지(5!⁵ = 24,883,200,000)나 되니, 최대한 많은 해답을 걸러 내봐요.
이 연습 문제는 미리 작성된 패키지를 포함하는 첫 번째 연습 문제예요.
pkgIndex.tcl 파일이 있고, auto_path 변수에 현재 디렉터리가 포함되어 있다는 점을 눈여겨봐요.
이 덕분에 package require 명령이 패키지의 소스 파일을 찾을 수 있어요.
그다지 잘 작성된 패키지는 아니에요. 여러 출처에서 가져온 코드를 모아 둔 것뿐이거든요.
interp alias 호출은 결점을 감추고 permutations 패키지를 더 쉽게 쓸 수 있게 하려는 거예요.
참고 자료:
Exercism에 가입하고 Tcl 트랙을 연습 문제 135개, 그리고 실제 사람의 멘토링과 함께 배우고 익혀 보세요. 모두 무료예요.
가능한 풀이 240억 개 중에서 얼룩말 퍼즐의 정답을 찾아내는 여덟 가지 방법을 살펴봐요. 잘못된 순열을 최대한 빨리 걸러내는 방법부터 AC-3 알고리즘, 아주 간결한 논리 기반 풀이, 심지어 유전 알고리즘까지 다뤄요!