# -*- coding: utf-8 -*-
from copy import copy, deepcopy

rules = [
    [u"1", u"амер", None,    None,    None,    None],
    [u"2", None,    None,    u"беос", None,    u"фрил"],
    [u"3", None,    u"черн", None,    None,    None],
    [None, u"рус",  None,    u"фря",  None,    None],
    [None, u"фран", u"оран", None,    None,    None],
    [None, u"нем",  None,    None,    u"стек", None],
    [None, None,    None,    None,    u"хабр", u"сис"],
    [None, u"кит",  None,    None,    None,    u"мен"],
    [None, None,    u"син",  None,    u"твит", None],
    [None, None,    u"крас", u"вин",  None,    None],
    [None, None,    None,    u"мак",  u"фейс", None],
    ]

choices = [
    (u"1", u"2", u"3", u"4", u"5"),
    (u"амер", u"рус", u"фран", u"нем", u"кит"),
    (u"черн", u"оран", u"син", u"крас", u"зел"),
    (u"беос", u"фря", u"вин", u"лин", u"мак"),
    (u"стек", u"хабр", u"твит", u"фейс", u"дигг"),
    (u"фрил", u"сис", u"мен", u"марк", u"прог")
    ]

def print_rules(rules):
    if rules is None:
        print "-------------"
        return
    for row in rules:
        print u"".join(
            (s.ljust(6) if not s[0] == "*" else "\x1b[1;37m%s\x1b[0m" % s[1:].ljust(6))
            if s is not None else "----  " for s in row)
    print u"\n"

def constr1(l):
    for n in xrange(1, len(l) - 1):
        if l[n][4] == u"дигг" and not ((
                l[n - 1][5] == u"марк" or l[n + 1][5] == u"марк"
                ) and (
                l[n - 1][2] == u"зел" or l[n + 1][2] == u"зел")):
            return False
    return True

def constr2(l):
    for n in xrange(1, len(l)):
        if l[n][2] == u"крас" and not (l[n - 1][3] == u"лин"):
            return False
    return True

def combine_lines(line1, line2):
    res = []
    for x1, x2 in zip(line1, line2):
        if x1 is not None and x2 is not None and x1 != x2:
            print "========= Violation ========="
            print_rules([line1, line2])
            return None
        res.append(x1 or x2)
    return res

blacklisted_lines = []

def link_rules(rules):
    for row_id, row in zip(xrange(len(rules)), rules):
        for cell_id, cell in zip(xrange(len(row)), row):
            if cell is None: continue
            for row_id_2, row_2 in zip(xrange(len(rules)), rules):
                if row_id == row_id_2: continue
                if row[cell_id] == row_2[cell_id]:
                    new_row = combine_lines(row, row_2)
                    if new_row is None:
                        return None
                    rules[row_id] = new_row
                    del rules[row_id_2]
                    return link_rules(rules)
    return rules

def doit(rules_, choices):
    global blacklisted_lines
    cont = True
    print u"**** DOIT *****"
    print_rules(rules_)
    raw_input()
    while cont:
        cont = False
        for row_id, row in zip(xrange(len(rules_)), rules_):
            for cell_id, cell in zip(xrange(len(row)), row):
                if cell is None:
                    cont = True
                    tried_choices = []
                    for possible_cell_value in choices[cell_id]:
                        rules = deepcopy(rules_)
                        rules[row_id][cell_id] = "*" + possible_cell_value
                        print u"-------- TRY... ---------"
                        print_rules(rules)
                        rules[row_id][cell_id] = possible_cell_value
                        if rules[row_id] in blacklisted_lines:
                            print "Ooops, row blacklisted: "
                            print_rules([row])
                            tried_choices.append(possible_cell_value)
                            continue
                        raw_input()
                        row_backup = deepcopy(rules[row_id])
                        rules = link_rules(rules)
                        print u"/////// SIMPLIFIED /////////"
                        print_rules(rules)
                        raw_input()
                        if rules is not None:
                            c1, c2 = constr1(rules), constr2(rules)
                            print "Constraints:", c1, c2
                            if c1 and c2:
                                if rules is not None and len([i for i in reduce(
                                    list.__add__, rules, []) if i is None]) == 0:
                                    return rules
                                rules = doit(rules, choices)
                                if rules is not None and len([i for i in reduce(
                                    list.__add__, rules, []) if i is None]) == 0:
                                    return rules
                            else:
                                tried_choices.append(possible_cell_value)
                            continue
                        print "Adding row to blacklist:"
                        print_rules([row_backup])
                        blacklisted_lines.append(row_backup)
                        rules = rules_
                        tried_choices.append(possible_cell_value)
                    print_rules([choices[cell_id], tried_choices])
                    if len(tried_choices) == len(choices[cell_id]):
                        print "$$$$$$$$$$ IT'S A WRONG WAY $$$$$$$$$$"
                        raw_input()
                        return None
    return None


if __name__ == u"__main__":
    rules = doit(rules, choices)
    print "======= END! =========="
    print_rules(rules)