enum HouseStatus { Invalid, Underfull, Valid };

enum Attrib { C, M, D, A, S };


enum Colors { Red, Green, White, Yellow, Blue };
enum Mans { English, Swede, Dane, German, Norwegian };
enum Drinks { Tea, Coffee, Milk, Beer, Water };
enum Animals { Dog, Birds, Cats, Horse, Zebra };
enum Smokes { PallMall, Dunhill, Blend, BlueMaster, Prince };


void printHouses(int ha[5][5]) {
    const char *color[] =  { , , , ,  };
    const char *man[] =    { , , , ,  };
    const char *drink[] =  { , , , ,  };
    const char *animal[] = { , , , ,  };
    const char *smoke[] =  { , , , ,  };

    printf(,
           , , , , , );

    for (int i = 0; i < 5; i++) {
        printf(, i);
        if (ha[i][C] >= 0)
            printf(, color[ha[i][C]]);
        else
            printf(, );
        if (ha[i][M] >= 0)
            printf(, man[ha[i][M]]);
        else
            printf(, );
        if (ha[i][D] >= 0)
            printf(, drink[ha[i][D]]);
        else
            printf(, );
        if (ha[i][A] >= 0)
            printf(, animal[ha[i][A]]);
        else
            printf(, );
        if (ha[i][S] >= 0)
            printf(, smoke[ha[i][S]]);
        else
            printf();
    }
}


int checkHouses(int ha[5][5]) {
    int c_add = 0, c_or = 0;
    int m_add = 0, m_or = 0;
    int d_add = 0, d_or = 0;
    int a_add = 0, a_or = 0;
    int s_add = 0, s_or = 0;

    
    if (ha[2][D] >= 0 && ha[2][D] != Milk)
        return Invalid;

    
    if (ha[0][M] >= 0 && ha[0][M] != Norwegian)
        return Invalid;

    for (int i = 0; i < 5; i++) {
        
        if (ha[i][C] >= 0) {
            c_add += (1 << ha[i][C]);
            c_or |= (1 << ha[i][C]);
        }
        if (ha[i][M] >= 0) {
            m_add += (1 << ha[i][M]);
            m_or |= (1 << ha[i][M]);
        }
        if (ha[i][D] >= 0) {
            d_add += (1 << ha[i][D]);
            d_or |= (1 << ha[i][D]);
        }
        if (ha[i][A] >= 0) {
            a_add += (1 << ha[i][A]);
            a_or |= (1 << ha[i][A]);
        }
        if (ha[i][S] >= 0) {
            s_add += (1 << ha[i][S]);
            s_or |= (1 << ha[i][S]);
        }

        
        if ((ha[i][M] >= 0 && ha[i][C] >= 0) &&
            ((ha[i][M] == English && ha[i][C] != Red) || 
             (ha[i][M] != English && ha[i][C] == Red)))  
            return Invalid;

        
        if ((ha[i][M] >= 0 && ha[i][A] >= 0) &&
            ((ha[i][M] == Swede && ha[i][A] != Dog) ||
             (ha[i][M] != Swede && ha[i][A] == Dog)))
            return Invalid;

        
        if ((ha[i][M] >= 0 && ha[i][D] >= 0) &&
            ((ha[i][M] == Dane && ha[i][D] != Tea) ||
             (ha[i][M] != Dane && ha[i][D] == Tea)))
            return Invalid;

        
        if ((i > 0 && ha[i][C] >= 0  ) &&
            ((ha[i - 1][C] == Green && ha[i][C] != White) ||
             (ha[i - 1][C] != Green && ha[i][C] == White)))
            return Invalid;

        
        if ((ha[i][C] >= 0 && ha[i][D] >= 0) &&
            ((ha[i][C] == Green && ha[i][D] != Coffee) ||
             (ha[i][C] != Green && ha[i][D] == Coffee)))
            return Invalid;

        
        if ((ha[i][S] >= 0 && ha[i][A] >= 0) &&
            ((ha[i][S] == PallMall && ha[i][A] != Birds) ||
             (ha[i][S] != PallMall && ha[i][A] == Birds)))
            return Invalid;

        
        if ((ha[i][S] >= 0 && ha[i][C] >= 0) &&
            ((ha[i][S] == Dunhill && ha[i][C] != Yellow) ||
             (ha[i][S] != Dunhill && ha[i][C] == Yellow)))
            return Invalid;

        
        if (ha[i][S] == Blend) {
            if (i == 0 && ha[i + 1][A] >= 0 && ha[i + 1][A] != Cats)
                return Invalid;
            else if (i == 4 && ha[i - 1][A] != Cats)
                return Invalid;
            else if (ha[i + 1][A] >= 0 && ha[i + 1][A] != Cats && ha[i - 1][A] != Cats)
                return Invalid;
        }

        
        if (ha[i][S] == Dunhill) {
            if (i == 0 && ha[i + 1][A] >= 0 && ha[i + 1][A] != Horse)
                return Invalid;
            else if (i == 4 && ha[i - 1][A] != Horse)
                return Invalid;
            else if (ha[i + 1][A] >= 0 && ha[i + 1][A] != Horse && ha[i - 1][A] != Horse)
                return Invalid;
        }

        
        if ((ha[i][S] >= 0 && ha[i][D] >= 0) &&
            ((ha[i][S] == BlueMaster && ha[i][D] != Beer) ||
             (ha[i][S] != BlueMaster && ha[i][D] == Beer)))
            return Invalid;

        
        if ((ha[i][M] >= 0 && ha[i][S] >= 0) &&
            ((ha[i][M] == German && ha[i][S] != Prince) ||
             (ha[i][M] != German && ha[i][S] == Prince)))
            return Invalid;

        
        if (ha[i][M] == Norwegian &&
            ((i < 4 && ha[i + 1][C] >= 0 && ha[i + 1][C] != Blue) ||
             (i > 0 && ha[i - 1][C] != Blue)))
            return Invalid;

        
        if (ha[i][S] == Blend) {
            if (i == 0 && ha[i + 1][D] >= 0 && ha[i + 1][D] != Water)
                return Invalid;
            else if (i == 4 && ha[i - 1][D] != Water)
                return Invalid;
            else if (ha[i + 1][D] >= 0 && ha[i + 1][D] != Water && ha[i - 1][D] != Water)
                return Invalid;
        }

    }

    if ((c_add != c_or) || (m_add != m_or) || (d_add != d_or)
        || (a_add != a_or) || (s_add != s_or)) {
        return Invalid;
    }

    if ((c_add != 0b11111) || (m_add != 0b11111) || (d_add != 0b11111)
        || (a_add != 0b11111) || (s_add != 0b11111)) {
        return Underfull;
    }

    return Valid;
}


int bruteFill(int ha[5][5], int hno, int attr) {
    int stat = checkHouses(ha);
    if ((stat == Valid) || (stat == Invalid))
        return stat;

    int hb[5][5];
    memcpy(hb, ha, sizeof(int) * 5 * 5);
    for (int i = 0; i < 5; i++) {
        hb[hno][attr] = i;
        stat = checkHouses(hb);
        if (stat != Invalid) {
            int nexthno, nextattr;
            if (attr < 4) {
                nextattr = attr + 1;
                nexthno = hno;
            } else {
                nextattr = 0;
                nexthno = hno + 1;
            }

            stat = bruteFill(hb, nexthno, nextattr);
            if (stat != Invalid) {
                memcpy(ha, hb, sizeof(int) * 5 * 5);
                return stat;
            }
        }
    }

    
    return Invalid;
}


int main() {
    int ha[5][5] = {{-1, -1, -1, -1, -1}, {-1, -1, -1, -1, -1},
                    {-1, -1, -1, -1, -1}, {-1, -1, -1, -1, -1},
                    {-1, -1, -1, -1, -1}};

    bruteFill(ha, 0, 0);
    printHouses(ha);

    return 0;
}