enum Country
{
    england,
    swit,
    germany,
    norway,
    denmark
};
enum Color
{
    green,
    white,
    red,
    yellow,
    blue
};
enum Drink
{
    coffee,
    tea,
    water,
    milk,
    redbull
};
enum Cigarette
{
    pm,
    du,
    bm,
    dr,
    hr
};
enum Animal
{
    dog,
    cat,
    horse,
    bird,
    fish
};
enum Enum
{
    country,
    color,
    drink,
    cigarette,
    animal
};

int a[120][5] = {{0, 1, 2, 3, 4},
                 {0, 1, 2, 4, 3},
                 {0, 1, 3, 2, 4},
                 {0, 1, 3, 4, 2},
                 {0, 1, 4, 3, 2},
                 {0, 1, 4, 2, 3},
                 {0, 2, 1, 3, 4},
                 {0, 2, 1, 4, 3},
                 {0, 2, 3, 1, 4},
                 {0, 2, 3, 4, 1},
                 {0, 2, 4, 3, 1},
                 {0, 2, 4, 1, 3},
                 {0, 3, 2, 1, 4},
                 {0, 3, 2, 4, 1},
                 {0, 3, 1, 2, 4},
                 {0, 3, 1, 4, 2},
                 {0, 3, 4, 1, 2},
                 {0, 3, 4, 2, 1},
                 {0, 4, 2, 3, 1},
                 {0, 4, 2, 1, 3},
                 {0, 4, 3, 2, 1},
                 {0, 4, 3, 1, 2},
                 {0, 4, 1, 3, 2},
                 {0, 4, 1, 2, 3},
                 {1, 0, 2, 3, 4},
                 {1, 0, 2, 4, 3},
                 {1, 0, 3, 2, 4},
                 {1, 0, 3, 4, 2},
                 {1, 0, 4, 3, 2},
                 {1, 0, 4, 2, 3},
                 {1, 2, 0, 3, 4},
                 {1, 2, 0, 4, 3},
                 {1, 2, 3, 0, 4},
                 {1, 2, 3, 4, 0},
                 {1, 2, 4, 3, 0},
                 {1, 2, 4, 0, 3},
                 {1, 3, 2, 0, 4},
                 {1, 3, 2, 4, 0},
                 {1, 3, 0, 2, 4},
                 {1, 3, 0, 4, 2},
                 {1, 3, 4, 0, 2},
                 {1, 3, 4, 2, 0},
                 {1, 4, 2, 3, 0},
                 {1, 4, 2, 0, 3},
                 {1, 4, 3, 2, 0},
                 {1, 4, 3, 0, 2},
                 {1, 4, 0, 3, 2},
                 {1, 4, 0, 2, 3},
                 {2, 1, 0, 3, 4},
                 {2, 1, 0, 4, 3},
                 {2, 1, 3, 0, 4},
                 {2, 1, 3, 4, 0},
                 {2, 1, 4, 3, 0},
                 {2, 1, 4, 0, 3},
                 {2, 0, 1, 3, 4},
                 {2, 0, 1, 4, 3},
                 {2, 0, 3, 1, 4},
                 {2, 0, 3, 4, 1},
                 {2, 0, 4, 3, 1},
                 {2, 0, 4, 1, 3},
                 {2, 3, 0, 1, 4},
                 {2, 3, 0, 4, 1},
                 {2, 3, 1, 0, 4},
                 {2, 3, 1, 4, 0},
                 {2, 3, 4, 1, 0},
                 {2, 3, 4, 0, 1},
                 {2, 4, 0, 3, 1},
                 {2, 4, 0, 1, 3},
                 {2, 4, 3, 0, 1},
                 {2, 4, 3, 1, 0},
                 {2, 4, 1, 3, 0},
                 {2, 4, 1, 0, 3},
                 {3, 1, 2, 0, 4},
                 {3, 1, 2, 4, 0},
                 {3, 1, 0, 2, 4},
                 {3, 1, 0, 4, 2},
                 {3, 1, 4, 0, 2},
                 {3, 1, 4, 2, 0},
                 {3, 2, 1, 0, 4},
                 {3, 2, 1, 4, 0},
                 {3, 2, 0, 1, 4},
                 {3, 2, 0, 4, 1},
                 {3, 2, 4, 0, 1},
                 {3, 2, 4, 1, 0},
                 {3, 0, 2, 1, 4},
                 {3, 0, 2, 4, 1},
                 {3, 0, 1, 2, 4},
                 {3, 0, 1, 4, 2},
                 {3, 0, 4, 1, 2},
                 {3, 0, 4, 2, 1},
                 {3, 4, 2, 0, 1},
                 {3, 4, 2, 1, 0},
                 {3, 4, 0, 2, 1},
                 {3, 4, 0, 1, 2},
                 {3, 4, 1, 0, 2},
                 {3, 4, 1, 2, 0},
                 {4, 1, 2, 3, 0},
                 {4, 1, 2, 0, 3},
                 {4, 1, 3, 2, 0},
                 {4, 1, 3, 0, 2},
                 {4, 1, 0, 3, 2},
                 {4, 1, 0, 2, 3},
                 {4, 2, 1, 3, 0},
                 {4, 2, 1, 0, 3},
                 {4, 2, 3, 1, 0},
                 {4, 2, 3, 0, 1},
                 {4, 2, 0, 3, 1},
                 {4, 2, 0, 1, 3},
                 {4, 3, 2, 1, 0},
                 {4, 3, 2, 0, 1},
                 {4, 3, 1, 2, 0},
                 {4, 3, 1, 0, 2},
                 {4, 3, 0, 1, 2},
                 {4, 3, 0, 2, 1},
                 {4, 0, 2, 3, 1},
                 {4, 0, 2, 1, 3},
                 {4, 0, 3, 2, 1},
                 {4, 0, 3, 1, 2},
                 {4, 0, 1, 3, 2},
                 {4, 0, 1, 2, 3}};

bool pass()
{
    //cout << "hello" << endl;
    for (int j = 0; j < 5; j++)
    {
        //英国人，红色房
        if (result[country][j] == england && result[color][j] != red)
            return false;

        //瑞典人，养狗
        if (result[country][j] == swit && result[animal][j] != dog)
            return false;

        //丹麦人喝茶
        if (result[country][j] == denmark && result[drink][j] != tea)
            return false;

        //绿房子在白房子左边
        if (result[color][j] == green && j == 5)
            return false;
        if (result[color][j] == green && result[color][j + 1] != white)
            return false;

        //绿房子主人喝咖啡
        if (result[color][j] == green && result[drink][j] != coffee)
            return false;

        //抽pm烟的人养鸟
        if (result[cigarette][j] == pm && result[animal][j] != bird)
            return false;

        //黄色房子抽du
        if (result[color][j] == yellow && result[cigarette][j] != du)
            return false;

        //中间房子喝牛奶
        if (result[drink][2] != milk)
            return false;

        //挪威人住在一号房
        if (result[country][0] != norway)
            return false;

        //混合烟住在养猫人旁边
        if (result[cigarette][j] == hr)
        {
            if (j == 0 && result[animal][j + 1] != cat)
                return false;
            if (j == 5 && result[animal][j - 1] != cat)
                return false;
            if (result[animal][j - 1] != cat && result[animal][j + 1] != cat)
                return false;
        }

        //养马人住在抽du人旁边,抽bm的人住在养马人的旁边
        if (result[cigarette][j] == du || result[cigarette][j] == bm)
        {
            if (j == 0 && result[animal][j + 1] != horse)
                return false;
            if (j == 5 && result[animal][j - 1] != horse)
                return false;
            if (result[animal][j - 1] != horse && result[animal][j + 1] != horse)
                return false;
        }
        

        //德国人抽dr
        if (result[country][j] == germany && result[cigarette][j] != dr)
            return false;

        //挪威人旁边是蓝房子
        if (result[country][j] == norway)
        {
            if (j == 0 && result[color][j + 1] != blue)
                return false;
            if (j == 5 && result[color][j - 1] != blue)
                return false;
            if (result[color][j - 1] != blue && result[color][j + 1] != blue)
                return false;
        }

        //抽混合烟的邻居喝矿泉水
        if (result[cigarette][j] == hr)
        {
            if (j == 0 && result[drink][j + 1] != water)
                return false;
            if (j == 5 && result[drink][j - 1] != water)
                return false;
            if (result[drink][j - 1] != water && result[drink][j + 1] != water)
                return false;
        }

    }
    return true;
}

bool dfs(int row)
{
    if (pass())
    {
        Print();
        return true;
    }
    if (row >= 5)
        return false;
    for (int i = 0; i < 120; i++)
    {
        for (int j = 0; j < 5; j++)
            result[row][j] = a[i][j];

        if (dfs(row + 1))
            return true;
    }

    return false;
}

void Print()
{
    for (int j = 0; j < 5; j++)
    {
        if (result[animal][j] == fish)
        {
            if (result[country][j] == england)
                out << "England" << endl;
            else if (result[country][j] == swit)
                out << "Swit" << endl;
            else if (result[country][j] == germany)
                out << "Germany" << endl;
            else if (result[country][j] == norway)
                out << "Norway" << endl;
            else if (result[country][j] == denmark)
                out << "Denmark" << endl;
        }
    }
    //  country,
    // color,
    // drink,
    // cigarette,
    // animal
    for (int i = 0; i < 5; i++)
    {

        if (i == country)
            for (int j = 0; j < 5; j++)
            {
                if (result[i][j] == england)
                    out << "England,";
                else if (result[i][j] == swit)
                    out << "Swit,";
                else if (result[i][j] == germany)
                    out << "Germany,";
                else if (result[i][j] == norway)
                    out << "Norway,";
                else if (result[i][j] == denmark)
                    out << "Denmark,";
            }

        // green,
        // white,
        // red,
        // yellow,
        // blue
        //*
        else if (i == color)
            for (int j = 0; j < 5; j++)
            {
                if (result[i][j] == green)
                    out << "green,";
                else if (result[i][j] == white)
                    out << "white,";
                else if (result[i][j] == red)
                    out << "red,";
                else if (result[i][j] == yellow)
                    out << "yellow,";
                else if (result[i][j] == blue)
                    out << "blue,";
            }
        //*/
        // coffee,
        // tea,
        // water,
        // milk,
        // redbull
        else if (i == drink)
            for (int j = 0; j < 5; j++)
            {
                if (result[i][j] == coffee)
                    out << "coffee,";
                else if (result[i][j] == tea)
                    out << "tea,";
                else if (result[i][j] == water)
                    out << "water,";
                else if (result[i][j] == milk)
                    out << "milk,";
                else if (result[i][j] == redbull)
                    out << "redbull,";
            }

        // pm,
        // du,
        // bm,
        // dr,
        // hr
        else if (i == cigarette)
            for (int j = 0; j < 5; j++)
            {
                if (result[i][j] == pm)
                    out << "pm,";
                else if (result[i][j] == du)
                    out << "du,";
                else if (result[i][j] == bm)
                    out << "bm,";
                else if (result[i][j] == dr)
                    out << "dr,";
                else if (result[i][j] == hr)
                    out << "hr,";
            }
        // dog,
        // cat,
        // horse,
        // bird,
        // fish
        else if (i == animal)
            for (int j = 0; j < 5; j++)
            {
                if (result[i][j] == dog)
                    out << "dog,";
                else if (result[i][j] == cat)
                    out << "cat,";
                else if (result[i][j] == horse)
                    out << "horse,";
                else if (result[i][j] == bird)
                    out << "bird,";
                else if (result[i][j] == fish)
                    out << "fish,";
            }
        out << endl;
    }
}

int main()
{
    /*
    //打表
    out.open("1.txt", ios::out);
    int a[5];
    for (int i = 0; i < 5; i++)
        a[i] = i;
    Perm(0, 5, a);
    //*/

    //*

    out.open("1.txt", ios::out);

    clock_t start, end;
    start = clock();

    //初始化
    for (int i = 0; i < 5; i++)
        for (int j = 0; j < 5; j++)
            result[i][j] = j;

    //*
    if (dfs(0))
        out << "true" << endl;
    else
        out << "false" << endl;

    end = clock();
    out << "time:  ";
    out << end - start << endl;
    //*/

    out.close();

    return 0;
}