C++로 풀어본 아인슈타인의 퍼즐

아인슈타인의 퍼즐이란 것이 있다.
각기 다른 다섯 채의 집에 사는 사람들에 관한 퍼즐(정확히는 수수께끼)이다.

아인슈타인이 "2%의 사람만이 이 퍼즐을 풀 수 있을 것"이라 했다는 얘기도 있는데, 뻥일 뿐이다.
사실, 아인슈타인이 이 퍼즐을 만든 사람인지도 확실하지 않다.

이 퍼즐엔 다양한 종류의 변종이 있긴 하지만, 골자는 동일하다.
서로 다른 색깔의 다섯 채의 집에 사는 각기 다른 국적의 사람이 살며, 서로 다른 동물을 기르고, 서로 다른 음료를 좋아하며, 서로 다른 담배를 핀다.
이 때 주어진 조건을 보고 누가 물고기를 기르는가를 맞추는 것이다.

5 Houses were built on one side of a small street, each painted in another color.
The houses were sold to 5 single persons, each person has another nationality.
Each of the 5 house owners prefers another drink and another type of cigarettes.
A pet is living in each house, but also they are all different.

One of the pets is a fish. Because the fish is so beautiful, everybody wants to see the fish.
But who of the 5 persons is the owner of the beautiful fish?
You can find out.


The Englishman lives in the red house.
The Swede keeps dogs.
The Norwegian lives in the first of the street.
The German drinks tea.
The Portuguese smokes Camel.

The green house is located on the left side of the white one.
The owner of the green house drinks coffee.
The owner of the yellow house smokes Dunhill.
The man, who has a cat, is living next to the man smokes Malboro.
The Norwegian lives next to the blue house.
The man in the center house drinks milk.
The man who keeps horses lives next to the Dunhill smoker.
The Malboro smoker has a neighbor who drinks water.

The Pall Mall smoker keeps birds.
The Lucky Strike smoker prefers beer.


해석 보기..


풀이 순서는 아래와 같다.

1. 국적, 집의 색깔, 애완동물, 음료, 담배를 숫자로 지정 (0~4)
2. 각 요소의 모든 조합를 배열에 저장 (5! = 120이므로 각기 120가지 상황이 가능)
3. 매 경우를 조건과 비교하여 조건에 맞으면 결과 출력


1. 각 조건을 숫자로 지정

#define ENGLISHMAN 0
#define SWEDE 1
#define NORWEGIAN 2
#define GERMAN 3
#define PORTUGESE 4

#define RED 0
#define GREEN 1
#define YELLOW 2
#define WHITE 3
#define BLUE 4

#define DOG 0
#define CAT 1
#define BIRD 2
#define FISH 3
#define HORSE 4

#define BEER 0
#define TEA 1
#define COFFEE 2
#define MILK 3
#define WATER 4

#define LSTRIKE 0
#define PMALL 1
#define CAMEL 2
#define DUNHILL 3
#define MALBORO 4


2. 5!(==120) 개의 조합 생성

int fillComposionTable(int five[][5])
{
    //five[120][5]에 모든 조합을 채우기
    //리턴값은 조합의 갯수(5!=120)
    int iPos = 0;

    for (int a=0; a<5; a++)
    {
        for (int b=0; b<5; b++)
        {
            if (a==b) continue;
            for (int c=0; c<5; c++)
            {
                if (a==c || b==c) continue;
                for (int d=0; d<5; d++)
                {
                    if (a==d || b==d || c==d) continue;
                    five[iPos][0] = a;
                    five[iPos][1] = b;
                    five[iPos][2] = c;
                    five[iPos][3] = d;
                    //a, b, c, d가 나오면 마지막 e는 계산할 필요 없음
                    //0+1+2+3+4 == 10
                    five[iPos++][4] = 10-(a+b+c+d);
                }
            }
        }
    }

    return iPos;
}


3. 조합이 조건에 맞는지 확인

bool CheckStatus(int *Color, int *Nationality, int *Pet, int *Drink, int *Cigarette)
{
    if (Nationality[ENGLISHMAN] != Color[RED]) return false;
    if (Nationality[SWEDE] != Pet[DOG]) return false;
    if (Nationality[NORWEGIAN] != 0) return false;
    if (Nationality[GERMAN] != Drink[TEA]) return false;
    if (Nationality[PORTUGESE] != Cigarette[CAMEL]) return false;

    if (Color[GREEN] - Color[WHITE] != -1) return false;
    if (Color[GREEN] != Drink[COFFEE]) return false;
    if (Color[YELLOW] != Cigarette[DUNHILL]) return false;
    int diff = Pet[CAT] - Cigarette[MALBORO];
    if (diff != -1 && diff != 1) return false;
    diff = Nationality[NORWEGIAN] - Color[BLUE];
    if (diff != -1 && diff != 1) return false;
    if (Drink[MILK] != 2) return false;
    diff = Pet[HORSE] - Cigarette[DUNHILL];
    if (diff != -1 && diff != 1) return false;
    diff = Cigarette[MALBORO] - Drink[WATER];
    if (diff != -1 && diff != 1) return false;

    if (Cigarette[PMALL] != Pet[BIRD]) return false;
    if (Cigarette[LSTRIKE] != Drink[BEER]) return false;

    return true;
}


4. (조건에 맞는 경우) 화면 출력

void PrintOutStatus(int *Color, int *Nationality, int *Pet, int *Drink, int *Cigarette)
{
    printf("\n");
    int Color_[5], Nationality_[5], Pet_[5], Drink_[5], Cigarette_[5];
    for (int i=0; i<5; i++)
    {
        Color_[Color[i]] = i;
        Nationality_[Nationality[i]] = i;
        Pet_[Pet[i]] = i;
        Drink_[Drink[i]] = i;
        Cigarette_[Cigarette[i]] = i;
    }

    for (int j=0; j<5; j++)
    {
        printf("house #%d: ", j+1);

        switch (Color_[j])
        {
        case 0:
            printf("Red,    ");
            break;
        case 1:
            printf("Green,  ");
            break;
        case 2:
            printf("Yellow, ");
            break;
        case 3:
            printf("White,  ");
            break;
        case 4:
            printf("Blue,   ");
            break;
        }
   
        switch (Nationality_[j])
        {
        case 0:
            printf("Englishman, ");
            break;
        case 1:
            printf("Swede,      ");
            break;
        case 2:
            printf("Norwegian,  ");
            break;
        case 3:
            printf("German,     ");
            break;
        case 4:
            printf("Portugese,  ");
            break;
        }

        switch (Pet_[j])
        {
        case 0:
            printf("Dog,   ");
            break;
        case 1:
            printf("Cat,   ");
            break;
        case 2:
            printf("Bird,  ");
            break;
        case 3:
            printf("Fish,  ");
            break;
        case 4:
            printf("Horse, ");
            break;
        }

        switch (Drink_[j])
        {
        case 0:
            printf("Beer,   ");
            break;
        case 1:
            printf("Tea,    ");
            break;
        case 2:
            printf("Coffee, ");
            break;
        case 3:
            printf("Milk,   ");
            break;
        case 4:
            printf("Water,  ");
            break;
        }

        switch (Cigarette_[j])
        {
        case 0:
            printf("Lucky Strike\n");
            break;
        case 1:
            printf("Pall Mall\n");
            break;
        case 2:
            printf("Camel\n");
            break;
        case 3:
            printf("Dunhill\n");
            break;
        case 4:
            printf("Malboro\n");
            break;
        }
    }

    printf("So, the owner of the fish is the ");
    switch (Nationality_[Pet[FISH]])
    {
    case 0:
        printf("Englishman");
        break;
    case 1:
        printf("Swede");
        break;
    case 2:
        printf("Norwegian");
        break;
    case 3:
        printf("German");
        break;
    case 4:
        printf("Portugese");
        break;
        }
    printf("\n\n");
}


5. main() 함수

int main(int argc, char* argv[])
{
    int five[120][5];

    printf("constructing Composition table...\n");
    fillComposionTable(five);

    int *Color, *Nationality, *Pet, *Drink, *Cigarette;

    for (int a=0; a<120; a++)
    {
        if ((a & 3) == 0) printf("calculating %3d of %3d (%6.2f%%)...\n", a+4, 120, (a+4)/120.0*100);
        Color = five[a];
        for (int b=0; b<120; b++)
        {
            Nationality = five[b];
            for (int c=0; c<120; c++)
            {
                Pet = five[c];
                for (int d=0; d<120; d++)
                {
                    Drink = five[d];
                    for (int e=0; e<120; e++)
                    {
                        Cigarette = five[e];
                       
                        if (CheckStatus(Color, Nationality, Pet, Drink, Cigarette))
                            PrintOutStatus(Color, Nationality, Pet, Drink, Cigarette);
                    }
                }
            }
        }
    }

    return 0;
}


6. 실행결과

실행결과 및 답 보기..



참 쉽죠잉~?

참고로, 노트북(Core2Duo T9500@2.6GHz)에서 돌려보니 전 루프를 다 도는데 172.672초(약 3분) 걸렸다.

Trackback 0 Comment 19
  1. Favicon of http://oktoya.net BlogIcon okto 2009.10.09 08:12 address edit & delete reply

    C++로... 반칙이라능ㅋㅋㅋ

    • Favicon of http://zockr.tistory.com BlogIcon BLUEnLIVE 2009.10.09 22:55 address edit & delete

      이게 왜 반칙이냐능.
      촛불집회 불법선언이랑 비슷한 것 같다능.

      혹 이가카 끄나풀 아니시냐능.

    • Favicon of http://oktoya.net BlogIcon okto 2009.10.11 20:20 address edit & delete

      그당시에 C++같은게 있었을리 없다능!!

    • Favicon of http://zockr.tistory.com BlogIcon BLUEnLIVE 2009.10.11 23:55 address edit & delete

      C++가 없었는데, C++로 문제를 푼 게 왜 반칙이냐능.

      기독경 나올 때 담배가 없었는데, 기독교도들 담배 피지 말란 얘기랑 비슷한 거 아니냐능. ㅋㅋ

  2. Favicon of http://zasfe.com BlogIcon zasfe 2009.10.09 09:17 address edit & delete reply

    도구사용금지 라고 안했으므로 유효?

    • Favicon of http://zockr.tistory.com BlogIcon BLUEnLIVE 2009.10.09 22:55 address edit & delete

      감사드릴 뿐... ㅎㅎ

  3. Favicon of http://minimonk.tistory.com BlogIcon 구차니 2009.10.09 09:53 address edit & delete reply

    ver.2 로는 이제 유전자 알고리즘이나, 휴리스틱이나 퍼지를 적용해서 (응?)
    그냥 98%에 속하기를 선택하렵니다 ㅋㅋ


    아차! 오늘은 한글날입니다

    • Favicon of http://zockr.tistory.com BlogIcon BLUEnLIVE 2009.10.09 22:56 address edit & delete

      좋은 생각이군요.

      퍼지 알고리즘으로 하나 만들어 트랙백 좀... (굽신굽신)

  4. Oo고목나무oO 2009.10.09 23:37 address edit & delete reply

    뭐지...-_-;;; 그런데.. 귀국 했는감?

    • Favicon of http://zockr.tistory.com BlogIcon BLUEnLIVE 2009.10.09 23:44 address edit & delete

      아냐, 한 주 남았어...
      귀국 하면 보자.

      네 선물은 런던까지 가서 샀다. ㅎㅎ

    • Oo고목나무oO 2009.10.10 03:11 address edit & delete

      오호호.. 런던표 배뚜맨 가면인가...ㅋㅋㅋ

      헛.. 혹시 명품가방? ㅋㅋㅋ

  5. 정재웅 2009.10.14 13:57 address edit & delete reply

    프로그래밍으로 푸는 것은 퍼즐에 대한 예의가 아닙니다. 머리로 풀어야죠. 방금 풀어봤는데 정답은 포르투갈인이군요.

  6. Favicon of http://un-i.tistory.com/ BlogIcon Un-i-que 2009.10.17 16:10 address edit & delete reply

    P 수준 문제인데... 이 무슨 괴상한 NP 짓입니까...=ㅁ=
    문득 생각이 났는데, 이 문제를 푸는 데 시간표 만드는 프로그램의 알고리즘이 괜찮을 것 같습니다.

    • Favicon of http://zockr.tistory.com BlogIcon BLUEnLIVE 2009.10.17 16:46 address edit & delete

      그럼 샘플 코드 좀... 굽신 굽신...

    • Favicon of http://un-i.tistory.com/ BlogIcon Un-i-que 2009.10.29 00:21 address edit & delete

      없어서 죄송합니다 :P ㅋㅋㅋㅋㅋㅋㅋ

    • Favicon of http://zockr.tistory.com BlogIcon BLUEnLIVE 2009.10.29 00:29 address edit & delete

      풋! 그럼 무효.
      이 문제는 NP 수준 문제인 거임.

    • Favicon of http://un-i.tistory.com/ BlogIcon Un-i-que 2009.10.29 20:26 address edit & delete

      헐-_-; 하지만 시간표 만드는 프로그램이 실제로 있잖습니까 ㅎㅎ 저는 그다지 찾을 생각이 없으니...(?)

  7. Favicon of http://www.naver.com BlogIcon 5분만에 풀었는뎅ㅡㅡ 2009.11.21 18:32 address edit & delete reply

    나이거 5분만에 암산으로 풀음ㅋㅋ

    • Favicon of http://zockr.tistory.com BlogIcon BLUEnLIVE 2009.11.21 18:49 address edit & delete

      네이버 사절