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 score_move(move, moves):
    """Assign a score to a move."""
    length = float(move[2:])  # the move length
    before = len([m for m, b in moves if m.startswith(move[0])])
    return float(before + 1) / length


def _find_solutions(board, visited, moves):
    # find possible moves and see if we get somewhere new
    possible = []
    for move, newboard in possible_moves(board):
        if is_solution(newboard):
            yield moves + [(move, newboard)]
            return
        found = visited.get(newboard)
        if found is None or found > len(moves):
            possible.append((score_move(move, moves), move, newboard))
            visited[newboard] = len(moves)
    # try highest likelyhood first
    possible.sort()
    # make each move and check recursively
    for score, move, newboard in possible:
        for solution in _find_solutions(
                newboard, visited, moves + [(move, newboard)]):
            yield solution


def find_solutions(board):
    board = clean_board(board)
    visited = {board: 0}
    for solution in _find_solutions(board, visited, []):
        yield solution