def clean_board(board):
    """Check that the board is valid."""
    # check that each row has the same length
    if not all(len(board[0]) == len(row) for row in board[1:]):
        raise ValueError('each row should be the same length')
    # TODO: check that each cell is either a capital letter, r or a period
    # TODO: check that each "car" is 2 or 3 characters long
    # TODO: check that each "car" is purely horizontal or vertical
    # TODO: check that there is a "r" "car"
    return tuple(board)


def split_row(row):
    """Split the row in parts of equal characters."""
    value = ''
    for c in row:
        if value and c != value[0]:
            yield value
            value = ''
        value += c
    if value:
        yield value


def possible_row_moves(row):
    """Find the possible moves within a row."""
    # split in parts
    parts = list(split_row(row))
    for i in range(len(parts)):
        # see if we have some empty space
        if parts[i][0] == '.':
            # see if there is a horizontal car before this space
            if i > 0 and len(parts[i - 1]) > 1:
                # we have space to move any "cars" before to the right
                space = parts[i]
                car = parts[i - 1]
                for l in range(1, len(space) + 1):
                    newrow = ''.join(
                        parts[:i - 1] +
                        ['.' * l] + [car] + ['.' * (len(space) - l)] +
                        parts[i + 1:])
                    yield (
                        '%sR%d' % (car[0], l), newrow)
            # see if there is a horizontal car after this space
            if i < len(parts) - 1 and len(parts[i + 1]) > 1:
                # we have space to move any "cars" after this to the left
                space = parts[i]
                car = parts[i + 1]
                for l in range(1, len(space) + 1):
                    newrow = ''.join(
                        parts[:i] +
                        ['.' * (len(space) - l)] + [car] + ['.' * l] +
                        parts[i + 2:])
                    yield (
                        '%sL%d' % (car[0], l), newrow)


def transpose_board(board):
    return tuple(''.join(x) for x in zip(*board))


def transpose_move(move):
    if move[1] == 'L':
        return move[:1] + 'U' + move[2:]
    else:
        return move[:1] + 'D' + move[2:]


def possible_moves(board):
    """Yield possible moves on the board.

    Each move consists of a tuple:
      move (e.g. AR1, BU2)
      new board
    """
    # go over horizontal cars
    for row in range(len(board)):
        for move, newrow in possible_row_moves(board[row]):
            yield (move, board[:row] + tuple([newrow]) + board[row + 1:])
    # go over vertical cars
    board = transpose_board(board)
    for row in range(len(board)):
        for move, newrow in possible_row_moves(board[row]):
            yield (
                transpose_move(move),
                transpose_board(board[:row] + tuple([newrow]) + board[row + 1:]))


def is_solution(board):
    """Check whether the board is a solution (i.e. the red car is on the
    most right column)."""
    return any(row[-1] == 'r' for row in board)


def find_solutions(board):
    board = clean_board(board)
    visited = set([board])
    queue = []
    queue.insert(0, [('', board)])
    while queue:
        moves = queue.pop()
        board = moves[-1][1]
        # find possible moves and see if we get somewhere new
        possible = []
        for move, newboard in possible_moves(board):
            if is_solution(newboard):
                yield moves[1:] + [(move, newboard)]
            elif newboard not in visited:
                queue.insert(0, moves + [(move, newboard)])
                visited.add(newboard)