from collections import defaultdict
import random


def colored_row(row):
    blue_color = "\033[94m"
    green_color = "\033[92m"
    yellow_color = "\033[93m"
    red_color = "\033[91m"
    end_color = "\033[0m"
    colored_number = {0: blue_color + "0" + end_color,
                      1: green_color + "1" + end_color,
                      2: yellow_color + "2" + end_color,
                      3: red_color + "3" + end_color}
    return [colored_number.get(c, c) for c in row]

class Board():

    def __init__(self, columns, clicks=0, prevs=[]):
        self.columns = columns
        self.clicks = clicks
        self.prevs = prevs

        self.win = len(columns) == 0

    def _equal(self, cell1, cell2):
        col1, row1 = cell1
        col2, row2 = cell2
        if col2 >= 0 and row2 >=0 and col2 < len(self.columns) and row2 < len(self.columns[col2]) and self.columns[col1][row1] == self.columns[col2][row2]:
            return True
        return False

    def _get_group(self, group, check):
        new = set()
        vec = [(0, 1), (0, -1), (-1, 0), (1, 0)]
        for cell in check:
            for r, c in vec:
                cell2 = (cell[0] + c, cell[1] + r)
                if cell2 not in group and self._equal(cell, cell2):
                    new.add(cell2)

        group.update(new)
        if new:
            return self._get_group(group, new)
        else:
            return group

    def _get_iter_groups(self):
        groups = []
        checked = set()
        for col, column in enumerate(self.columns):
            for row in range(len(column)):
                cell = (col, row)
                if cell not in checked:
                    new_group = self._get_group({cell}, {cell})
                    checked.update(new_group)
                    yield new_group

    def iter_next_boards(self):
        for group in self._get_iter_groups():
            if len(group) == 1: continue
            columns = tuple(tuple(cell for r, cell in enumerate(column) if (c, r) not in group) for c, column in enumerate(self.columns))
            columns = tuple(c for c in columns if c)
            prevs = self.prevs + [self]
            yield Board(columns, self.clicks + 1, prevs)


    def super_print(self):
        for b in self.prevs:
            max_c = max(len(c) for c in b.columns)
            filled_cols = []
            for col in b.columns:
                fill_col = list(col) + [" "]*(max_c - len(col))
                fill_col.reverse()
                filled_cols.append(fill_col)
            for row in zip(*filled_cols):
                print " ".join(map(str, colored_row(row)))
            print "-"*50


def posible(b):
    counter = defaultdict(int)
    for col in b.columns:
        for cell in col:
            counter[cell]+=1
    return not any(v==1 for v in counter.values())

# Azul = 0
# Verde = 1
# Amarillo = 2
# Rojo = 3
def get_board():
    game = ["100113123333021",
            "033130023203023",
            "201333303320102",
            "300202232102021",
            "333322112303022",
            "000232202321133",
            "201123202211202",
            "311301111033022",
            "233022111321322"]
    game = zip(*[map(int, r) for r in game])
    return Board(game)

BOARDS_BY_LEVEL = 1500

def bfs_win():
    clicks = 0
    prev = [get_board()]
    while prev:
        print "{} clicks, {} boards".format(clicks, len(prev))
        if any(b.columns == tuple(tuple()) for b in prev):
            gan = [b for b in prev if b.columns == tuple(tuple())][0]
            gan.super_print()
            print "WIN", clicks
            break
        clicks += 1
        new_currs = []
        cols = set()
        for p in prev:
            for b in p.iter_next_boards():
                if posible(b) and b.columns not in cols:
                    new_currs.append(b)
                    cols.add(b.columns)
        prev = sorted(new_currs, key=lambda x: sum(len(c) for c in x.columns))[:BOARDS_BY_LEVEL]

if __name__ == "__main__":
    bfs_win()