알고리즘 #2_Einstein's puzzle(아인슈타인 퍼즐)_[Python을 이용한 CSP algorithm]

안녕하세요.

이번에는 python을 이용한 CSP algorithm 중 하나인 Einstein's puzzle(아인슈타인 퍼즐) 해결 코드를 작성해 보겠습니다.

먼저 아인슈타인 퍼즐에 대해 소개해 드릴게요.

아인슈타인의 퍼즐은 아래와 같은 문제입니다.

* 문제의 배경

1. 색깔이 서로 다른 5채의 집이 일렬로 지어져 있다.

2. 각 집에는 서로 다른 국적의 사람이 살고 있다.

3. 다섯 사람은 서로 다른 음료를 마시고, 서로 다른 담배를 피며, 서로 다른 동물을 기른다.

* 15개의 정보

1. 영국인은 빨간 집에서 산다.

2. 스웨덴인은 개를 기른다.

3. 덴마크인은 차를 마신다.

4. 초록집은 하얀집의 왼쪽 집이다.

5. 초록집에 사는 사람은 커피를 마신다.

6. 펠몰 담배를 피는 사람은 새를 기른다.

7. 노란집에 사는 사람은 던힐 담배를 피운다.

8. 한 가운데 집에 사는 사람은 우유를 마신다.

9. 노르웨이 인은 첫번째 집에 산다.

10. 블렌드 담배를 피우는 사람은 고양이를 기르는 사람 옆 집에 산다.

11. 말을 기르른 사람은 던힐 담배를 피우는 사람 옆 집에 산다.

12. 블루매스터 담배를 피는 사람은 맥주를 마신다.

13. 독일인은 프린스 담배를 피운다.

14. 노르웨이인은 파란 집 옆 집에 산다.

15. 블렌드 담배를 피우는 사람은 생수를 마시는 사람과 이웃이다.

위의 문제 배경과 15개의 정보가 있을때, '물고기를 기르는 사람의 국적은 무엇인가'?

(문제 출처: https://web.stanford.edu/~laurik/fsmbook/examples/Einstein%27sPuzzle.html)

이론적인 문제 풀이 방식은 아래와 같은 순서로 풀이가 가능합니다.

먼저 15개의 정보 중에서 확실히 알 수 있는 사실들을 이용한다. 15개의 정보 중에서 8번, 9번, 14번의 정보는 순서대로 하여 확실히 특정 사실을 알 수 있는 정보이다. 세가지 정보를 이용하면 위의 표와 같이 알 수 있다.

두번째로는 특정 조건들을 결합하여 이용한다. 먼저 4번 정보와 5번 정보를 이용하였다. 4번 정보를 통해 초록집은 하얀 집의 왼쪽 집임을 만족시켜야 한다. 4번 정보를 다르게 해석하면, 초록집의 오른쪽 집은 하얀 집이다. 즉, 1번, 2번, 5번은 초록집이 될 수 없다. 그리고 5번 정보를 이용하면 초록 집은 3번이 될 수 없다. 따라서 남은 것은 4번뿐이므로 초록집은 4번이다. 또한 4번 집사람은 커피를 마시고 5번집은 하얀집이다. 다음 1번 정보를 확인하면, 2,4,5번 집은 이미 색이 있으므로 빨간집이 아니며 1번집은 노르웨이사람이 살고 있으므로 1번도 아니다. 즉 3번 집이 빨간집이며 영국사람이 산다. 이어서 남은 1번은 자연스럽게 노란색 집이되며 7번 정보를 통해 1번집 사람은 던힐담배를 피운다. 또한 11번 정보를 통해 2번 집 사람은 말을 기른다.

이제 주어진 조건들을 응용하여 추리한다. 3번 정보와 12번 정보를 해석한다. 현재 남은 음료는 생수, 차, 맥주이다. 3번 정보에서 덴마크인이 차를 마신다고 하였으므로 노르웨이인은 생수 또는 맥주를 마실 것이다. 12번 정보에서 블루매스터 담배를 피우는 사람은 맥주를 마신다고 하였는데, 노르웨이인은 던힐 담배를 피우므로 맥주를 마시지 않는다. 즉 노르웨이인은 생수를 마신다. 또한 15번 정보를 통해서 2번 집 사람은 블렌드 담배를 피운다.

다시 12번 정보를 확인한다. 2번 집 사람은 차 또는 맥주를 마실 텐데 12번 정보에서 블루매스터 담배를 피는 사람이 맥주를 마신다고 하였다. 2번 집 사람은 블렌드 담배를 피우므로 맥주를 마시지 않고 차를 마신다. 그리고 남은 맥주는 당연히 5번 집 사람이 마시고, 5번 집 사람은 블루매스터 담배를 핀다. 이어서 3번 정보를 통해 차를 마시는 2번 집 사람은 덴마크인이다. 

마지막으로 남은 조건들로 추리를 완성한다. 먼저 13번 정보를 확인한다. 독일인은 4번 또는 5번집에 살텐데 5번 집 사람은 블루매스터 담배를 핀다. 따라서 13번 정보를 통해 독일인은 4번집에 살며 프린스 담배를 피운다. 이어서 5번집 사람은 스웨덴인이며, 3번집 사람은 펠몰담배를 핀다.

다음 6번 정보를 통해 펠몰담배를 피는 3번집 사람은 새를 기른다. 또한 2번 정보를 통해 5번 집에 사는 스웨덴인은 개를 기른다.

마지막으로 10번 정보를 통해서 3번 집사람은 이미 새를 키우는 것을 알았으므로 1번집 사람이 고양이를 기른다. 최종적으로 남은 4번집 사람은 물고기를 기른다.

이렇게 해서 아인슈타인의 퍼즐을 해결할 수 있습니다.

이러한 문제를 CSP(Constraint Satisfaction Problems: 제약조건 만족문제)라고 합니다.

아인슈타인 퍼즐을 해결하기 위해 2가지 정도의 알고리즘을 생각해볼 수 있습니다.

첫번째로는, 모든 경우의 수(5^25 or (5!)^5 둘 다 매우 큰 수 입니다...)를 고려하여 그 중 하나를 꺼내 정보와 비교하는 방법.

해당 방법은, 모든 경우의 수를 (5!)^5 으로 고려했을때 경우의 수가 약 240억개 입니다.

우리들의 컴퓨터로는 해결하기가 매우 힘들 수 있죠..

그래서 생각한 것이 두번째 알고리즘 입니다.

두번째 알고리즘은 각각을 카테고리 또는 조건으로 나누어 해결하는 방법입니다.

즉, A라는 조건을 다수의 배열 중 만족하는 배열을 찾아내는 것이 아니라 다수의 배열을 선언하기 전에 A라는 조건을 먼저 대입하고

이를 만족하는 배열 a가 있다면 a를 다음 조건, B에 대입하여 확인해나갑니다.

이렇게 해결을 진행하면 결국 DFS 방법으로 해결방법을 찾아나간다는 것을 아실 수 있습니다.

python으로 코드를 작성하기 위해 검색하던 중, python에서 제공하는 강력한 함수를 찾았습니다.

바로, python-constraint 함수 입니다.

함수에 대한 추가적인 사항은 아래 링크를 참고하시면 좋을 것 같습니다.

https://labix.org/python-constraint

https://pypi.python.org/pypi/python-constraint

python-constraint 함수를 통해, 직접 변수를 설정하고 제약조건을 추가하여 문제를 해결할 수 있습니다.

생각보다 code가 매우 간단해질 수 있어서 꼭 한번 다시 공부해보고 싶은 함수입니다.

추가적인 질문 이나 궁금사항은 댓글로 달아주시거나 이메일 주세요!

전체적인 python code와 실행결과는 아래와 같습니다.

# Houses
# 1 2 3 4 5
 
from constraint import *
problem = Problem()
 
nationality = ["영국", "스웨덴", "독일", "노르웨이", "덴마크"]
pet = ["개", "고양이", "새", "말", "물고기"]
cigarette = ["던힐", "블렌드", 
"펠몰", "프린스", "블루매스터"]
colour = ["빨강", "초록", "노랑", "파랑", "하양"]
beverage = ["커피", "우유", "맥주", "생수", "차"]
 
criteria = nationality + pet + cigarette + colour + beverage
problem.addVariables(criteria,[1,2,3,4,5])
 
problem.addConstraint(AllDifferentConstraint(), nationality)
problem.addConstraint(AllDifferentConstraint(), pet)
problem.addConstraint(AllDifferentConstraint(), cigarette)
problem.addConstraint(AllDifferentConstraint(), colour)
problem.addConstraint(AllDifferentConstraint(), beverage)
 
problem.addConstraint(lambda e, r: e == r, ["영국","빨강"])#1
problem.addConstraint(lambda s, d: s == d, ("스웨덴","개"))#2
problem.addConstraint(lambda c, g: c == g, ("커피","초록"))#5
problem.addConstraint(lambda u, t: u == t, ("덴마크","차"))#3
problem.addConstraint(lambda g, i: g-i == 1, ("하양","초록"))#4
problem.addConstraint(lambda o, s: o == s, ("펠몰","새"))#6
problem.addConstraint(lambda k, y: k == y, ("던힐","노랑"))#7
problem.addConstraint(InSetConstraint([3]), ["우유"])#8
problem.addConstraint(InSetConstraint([1]), ["노르웨이"])#9
problem.addConstraint(lambda c, f: abs(c-f) == 1, ("블렌드","고양이"))#10
problem.addConstraint(lambda k, h: abs(k-h) == 1, ("던힐","말"))#11
problem.addConstraint(lambda l, o: l == o, ["블루매스터","맥주"])#12
problem.addConstraint(lambda j, p: j == p, ["독일","프린스"])#13
problem.addConstraint(lambda k, h: abs(k-h) == 1, ("노르웨이","파랑"))#14
 
solution = problem.getSolutions()[0]
 
for i in range(1,6):
  for x in solution:
    if solution[x] == i:
      print (str(i), x)