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. 실행결과

실행결과 및 답 보기..

constructing Composition table...
calculating   4 of 120 (  3.33%)...
...
calculating  64 of 120 ( 53.33%)...

house #1: Yellow, Norwegian,  Cat,   Water,  Dunhill
house #2: Blue,   German,     Horse, Tea,    Malboro
house #3: Red,    Englishman, Bird,  Milk,   Pall Mall
house #4: Green,  Portugese,  Fish,  Coffee, Camel
house #5: White,  Swede,      Dog,   Beer,   Lucky Strike
So, the owner of the fish is the Portugese

calculating  68 of 120 ( 56.67%)...
...

그렇다! 물고기는 네번째 집에 사는 포르투갈 사람이 기르는 것이다!

참 쉽죠잉~?

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