RED = 'R'
BLACK = 'B'
EMPTY = 'X'

COLUMN = 7
ROW = 6
COLUMN = 4
ROW = 4

def flip(color):
    if color == RED:
        return BLACK
    return RED

class Board:
    def __init__(self, s = None, turn = RED, depth = 0, parent = None):
        self._board = s or EMPTY * COLUMN * ROW
        self._turn = turn
        self._depth = depth
        self._parent = parent

    def __repr__(self):
        return self._board

    def __eq__(self, other):
        if isinstance(other, Board):
            return self._board == other._board
        return False

    def __hash__(self):
        return hash(self._board)

    def copy(self):
        return Board(s = self._board, turn = self._turn, depth = self._depth, parent = self._parent)

    def get(self, x, y):
        if 0 <= x and x < COLUMN and 0 <= y and y < ROW:
            return self._board[COLUMN * y + x]

    def get_column(self, x):
        if 0 <= x and x < COLUMN:
            values = ''.join([self.get(x, i) for i in range(ROW)])
            return values

    def set(self, x, y, v):
        if 0 <= x and x < COLUMN and 0 <= y and y < ROW:
            new_board = self._board[:COLUMN * y + x] + v + self._board[COLUMN * y + x + 1:]
            self._board = new_board

    def draw(self):
        chopped = reversed([self._board[i:i+COLUMN]
                for i in range(0, COLUMN * ROW, COLUMN)])
        print('\n'.join(chopped))

    def valid_moves(self):
        columns = [self.get_column(i) for i in range(COLUMN)]
        moves = []
        for i, column in enumerate(columns):
            j = 0
            while j < ROW:
                if column[j] == EMPTY:
                    moves.append((i, j))
                    break
                j += 1
        return moves

    def children(self):
        moves = self.valid_moves()
        children = []
        for move in moves:
            child = self.copy()
            child._turn = flip(self._turn)
            child._depth = self._depth + 1
            child._parent = self
            child.set(move[0], move[1], self._turn)
            children.append(child)
        return children

    def check_victory(self):
        # vertical
        for i in range(COLUMN):
            n = 0
            for j in range(ROW):
                if self.get(i, j) == self._turn:
                    n += 1
                else:
                    n = 0
                if n == 4:
                    return True

        # horizontal
        for j in range(ROW):
            n = 0
            for i in range(COLUMN):
                if self.get(i, j) == self._turn:
                    n += 1
                else:
                    n = 0
                if n == 4:
                    return True

        # diagonal
        right = [(0,2), (0,1), (0,0), (1,0), (2,0), (3,0)]
        left =  [(6,2), (6,1), (6,0), (5,0), (4,0), (3,0)]

        for start in right:
            n = 0
            i, j = start
            while i < ROW and j < COLUMN:
                if self.get(i, j) == self._turn:
                    n += 1
                else:
                    n = 0
                if n == 4:
                    return True
                i += 1
                j += 1

        for start in left:
            n = 0
            i, j = start
            while 0 <= i and j < COLUMN:
                if self.get(i, j) == self._turn:
                    n += 1
                else:
                    n = 0
                if n == 4:
                    return True
                i -= 1
                j += 1

        return False


board = Board() # s = 'RXXXXXRXRXXXXXXXRXXXXXXXXXXXXXXXXXXXXXXXXX', turn = RED)
from collections import deque
children = deque([board])

last = 0
while True:
    if len(children) == 0:
        break
    child = children.popleft()
    if child._depth > 8:
        last = child
        break
    for child in child.children():
        children.append(child)

last.draw()