def adjoin_position(row, col, rest):
    return pair(pair(row, col), rest)
empty_board = None
def accumulate(op, initial, sequence):
    return (initial if is_none(sequence)
            else op(head(sequence),
                    accumulate(op, initial, tail(sequence))))
def is_safe(k, positions):
    first_row = head(head(positions))
    first_col = tail(head(positions))
    def check(pos, so_far):
        row = head(pos)
        col = tail(pos)
        return (so_far
                and first_row - first_col != row - col
                and first_row + first_col != row + col
                and first_row != row)
    return accumulate(check, True, tail(positions))
def map(fun, items):
    return (None if is_none(items)
            else pair(fun(head(items)),
                      map(fun, tail(items))))
def filter(predicate, sequence):
    return (None if is_none(sequence)
            else pair(head(sequence),
                      filter(predicate, tail(sequence)))
            if predicate(head(sequence))
            else filter(predicate, tail(sequence)))
def append(list1, list2):
    return (list2 if is_none(list1)
            else pair(head(list1), append(tail(list1), list2)))
def flatmap(f, seq):
    return accumulate(append, None, map(f, seq))
def enumerate_interval(low, high):
    return (None if low > high
            else pair(low,
                      enumerate_interval(low + 1, high)))
def queens(board_size):
    def queen_cols(k):
        return (llist(empty_board) if k == 0
                else filter(lambda positions: is_safe(k, positions),
                            flatmap(lambda rest_of_queens:
                                      map(lambda new_row:
                                            adjoin_position(new_row, k,
                                                            rest_of_queens),
                                          enumerate_interval(1, board_size)),
                                    queen_cols(k - 1))))
    return queen_cols(board_size)
def length(items):
    return (0 if is_none(items)
            else 1 + length(tail(items)))
print(length(queens(8)))


# expected: 92
