在每行和每列中设置一个不能相互交叉的元素(想想国际象棋)

def solve_n_queens(n):
    result = []
    board = [['.' for _ in range(n)] for _ in range(n)]
    backtrack(board, 0, result)
    return result

def backtrack(board, row, result):
    n = len(board)
    if row == n:
        result.append([''.join(row) for row in board])
        return
    
    for col in range(n):
        if is_valid(board, row, col):
            board[row][col] = 'Q'
            backtrack(board, row+1, result)
            board[row][col] = '.'

def is_valid(board, row, col):
    n = len(board)

    # 检查同一列是否有相同元素
    for i in range(row):
        if board[i][col] == 'Q':
            return False

    # 检查左上方是否有相同元素
    i = row - 1
    j = col - 1
    while i >= 0 and j >= 0:
        if board[i][j] == 'Q':
            return False
        i -= 1
        j -= 1

    # 检查右上方是否有相同元素
    i = row - 1
    j = col + 1
    while i >= 0 and j < n:
        if board[i][j] == 'Q':
            return False
        i -= 1
        j += 1

    return True