16. 아인슈타인 퍼즐 알고리즘 (이차원 순열 응용 알고리즘)

1. 개요

아인슈타인 퍼즐이라고 불리는 문제가 있다.

이 퍼즐은 아인슈타인이 고안했고, 놀랍게도 전 세계 인구의 2%만이 풀 수 있는 문제라고 소개된다!!!

하지만 잘 살펴보면, 전 세계 인구의 2%만이 못 푸는 문제일 정도로 풀기 쉽다.

그리고 아인슈타인이 고안했다고 알려져있지만, 이는 속설일 뿐 전혀 근거없는 소리라고도 한다.

하지만 이 문제는 아인슈타인의 이름 덕분인지 무척 유명하다.

예전에 처음 봤을 때, 직접 공책에 적어가며 손으로 풀었던 기억이 있다.

하지만 이를 컴퓨터 프로그램으로 풀 생각은 못해봤는데,

프로그래밍하여 푼다는 엄두도 나지 않았는데, 

이번에 순열 알고리즘을 응용하면 이 문제를 풀 수 있다는 것을 처음 알았다.

이 방법은 무척 유용하고 재미있고, 뭔가 사고의 범위가 한 번 확장되는 계기가 되었다.

특히, 순열 알고리즘의 활용법을 제대로 익힐 수 있다.

꼭 풀어보자.

2가지 풀이법이 있는데, 

먼저 첫 번째 풀이법인 모든 경우 조사를 하게 되면 5!의 5제곱의 경우를 검사해야 하기 때문에

24,883,200,000의 경우의 수를 검사해야 한다. 이를 풀 때까지 기다리면, 1초에 100만 경우를 검사하는 컴퓨터의 경우에

약 7시간이 걸린다고 한다. 그렇기에 빠르게 풀 수 있는 2번째 방법이 있다.

두 번째 풀이법은 어떤 의미론 동적 프로그래밍과 비슷하다. 비록 이전에 계산한 결과를 사용하진 않지만 

조금의 조건을 바꾸어 검사해야 할 경우를 확 줄인다.

첫 번째 풀이법의 경우에는 순열 알고리즘을 통해 완성된 2차원 배열을 데이터로 넣어서 검사하지만,

두 번째 풀이법의 경우에는 각각의 카테고리별로 Level이란 특수한 경우를 두어, 현재 단계에서 필요한 검사만을 수행하여

이 단계를 통과해야 다음 Level 단계의 검사를 진행한다. 그리고 최종적으로 Level이 5가 되면 모든 경우를 통과했다고

판단하기에 그 때 비로소 출력한다. 

이 아인슈타인 퍼즐에서 모든 조건 검사를 통과하는 경우는 오직 1가지 경우 뿐이다.

먼저 아래의 문제를 풀어보고, 코드로 변환하자.

무척 재미있다!

2. 문제

문제의 배경

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

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

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

15개의 정보

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

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

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

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

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

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

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

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

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

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

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

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

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

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

15. '블렌드' 담배를 피우는 사람을 '물'을 마시는 사람과 이웃이다.

다음의 상황에서 얼룩말을 기르는 사람의 국적은 무엇인가?

3. 코드 및 출력

3-1) 선언

3-2) 메인

3-3) 첫 번째 알고리즘 (mPerm_Einstein(), Check_Einstein_Rule())

3-4) 두 번째 알고리즘 (mPerm_Einstein_Advanced(), Check_Einstein_Rule_Advanced())

3-5) 출력 코드

3-6) 출력

4. 정리

이 문제를 풀면서 이차원 배열을 순열로 바꾸는 법을 알았다. 결국 단계별로 순열을 진행해나가면 되는 건데.

순열이란 하나의 흐름으로만 머리가 인식하니, 역시 사고가 명확히 안 떠오른다. 사고의 범위를 넓히자.

또 하나 enum 열겨형을 통한 코드의 명확함이 가지는 강력함을 알았다.

이런 기법들을 잊지말고 잘 활용해보자.