Solving the N-Queen problem

queen_problem.py

def get_candidate_boards(board):
    boards = []
    queen_locations = [(x, y) for x in range(len(board)) for y in range(len(board)) if board[x][y] == "Q"]
    left_diagonals  = [(x-y, 0) for (x, y) in queen_locations]
    right_diagonals = [(x+y, 0) for (x, y) in queen_locations]

    for x, y in ((x, y) for x in range(len(board)) for y in range(len(board)) if board[x][y] != "Q"):
        temp_board  = board[:x] + [board[x][:y] + ["Q"] + board[x][y+1:]] + board[x+1:]
        valid_cols  = all(col.count("Q") < 2 for col in temp_board)
        valid_rows  = all(row.count("Q") < 2 for row in zip(*temp_board))
        valid_left  = (x-y, 0) not in left_diagonals
        valid_right = (x+y, 0) not in right_diagonals
        if valid_cols and valid_rows and valid_left and valid_right:
            boards.append(temp_board)
    return boards

def solve_board(board, queens_remaining):
    if queens_remaining == 0:
        return board
    for candidate_board in get_candidate_boards(board):
        solution = solve_board(candidate_board, queens_remaining-1)
        if solution:
            return solution

def main():
    size = input("Size of board: ")
    board = [["-" for _ in range(size)] for __ in range(size)]
    solution = solve_board(board, size)
    try:
        print "\n".join([" ".join(row) for row in solution])
    except TypeError:
        print "Error: unable to find solution for board"

if __name__ == "__main__":
    main()