def empty_board(board_size):
    return {(x, y): 0 for x in range(1, board_size + 1) for y in range(1, board_size + 1)}


def empty_history():
    return []


class IllegalMoveError(ValueError):
    pass


class ChessState:
    def __init__(self, board=None, history=empty_history(), predecessor=None, board_size=8):
        self.__board_size = board_size
        self.__history = history
        if board is not None:
            self.__board = board
        else:
            self.__board = empty_board(board_size)
        self.__predecessor = predecessor
        self._bool_board_cache = None
        self._bool_board_mirrored_cache = None

    def put(self, x, y, direction):
        positions = self.move_positions(x, y, direction)

        if not self.possible(x, y, direction):
            raise IllegalMoveError

        board = self.__board.copy()
        for pos in positions:
            board[pos] = len(self.__history) + 1

        return ChessState(board=board,
                          history=self.__history + [positions],
                          board_size=self.__board_size,
                          predecessor=self)

    def undo(self):
        return self.__predecessor

    def move_positions(self, x, y, direction):
        if direction not in ['down', 'right']:
            raise ValueError
        if direction == 'down':
            mps = [(x, y), (x, y + 1), (x, y + 2)]
        else:  # right
            mps = [(x, y), (x + 1, y), (x + 2, y)]
        for pos in mps:
            if pos not in self.__board:
                raise IndexError
        return mps

    def possible(self, x, y, direction):
        try:
            for pos in self.move_positions(x, y, direction):
                if self.__board[pos]:
                    return False
        except IndexError:
            return False

        return True

    def board(self):
        return self.__board.copy()

    def history(self):
        return self.__history.copy()

    def predecessor(self):
        return self.__predecessor.copy()

    def board_size(self):
        return self.__board_size

    def board_label(self):
        s = ''
        for x in range(1, self.__board_size + 1):
            s += '{'
            for y in range(1, self.__board_size + 1):
                if self.__board[(x, y)]:
                    s += str(self.__board[(x, y)])
                if y < self.__board_size:
                    s += '|'
            s += '}'
            if x < self.__board_size:
                s += '|'
        return s

    def bool_board(self):
        if self._bool_board_cache is None:
            self._bool_board_cache = {x: self.__board[x] != 0 for x in self.__board}

        return self._bool_board_cache

    def bool_board_mirrored(self):
        if self._bool_board_mirrored_cache is None:
            self._bool_board_mirrored_cache = [
                {self.bool_board()[x, self.__board_size + 1 - y] for (x, y) in self.bool_board()},
                {self.bool_board()[self.__board_size + 1 - x, y] for (x, y) in self.bool_board()},
                {self.bool_board()[self.__board_size + 1 - x, self.__board_size + 1 - y] for (x, y) in self.bool_board()},
            ]
        return self._bool_board_mirrored_cache

    def symmetric_to(self, other):
        if self.bool_board() == other.bool_board():
            return True
        # # no gain
        # for board in other.bool_board_mirrored():
        #     if self.bool_board() == board:
        #         return True
        return False

    def next_move(self):
        # try to find a move where no direction is possible
        for x in range(1, self.__board_size + 1):
            for y in range(1, self.__board_size + 1):
                if (x == 1) and (y == 1):
                    continue
                if self.board()[x, y]:
                    continue
                left_full = x == 1 or self.board()[x - 1, y]
                top_full = y == 1 or self.board()[x, y - 1]
                if not self.possible(x, y, 'down') and not self.possible(x, y, 'right') and left_full and top_full:
                    return x, y

        # try to find a move where only one direction is possible
        for x in range(1, self.__board_size - 1):
            for y in range(1, self.__board_size - 1):
                if (x == 1) and (y == 1):
                    continue
                if self.board()[x, y]:
                    continue
                left_full = x == 1 or self.board()[x - 1, y]
                top_full = y == 1 or self.board()[x, y - 1]
                if not self.possible(x, y, 'down') and left_full and top_full:
                    return x, y
                if not self.possible(x, y, 'right') and left_full and top_full:
                    return x, y

        # just take the next move in this row
        for y in range(1, self.__board_size + 1):
            for x in range(1, self.__board_size + 1):
                if (x == 1) and (y == 1):
                    continue
                if self.board()[x, y]:
                    continue
                return x, y

        return None, None