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분) 걸렸다.