分别用递归和回溯求解N皇后问题

N皇后问题是指在N*N的棋盘上放置N个皇后，使得皇后之间互相不能攻击（即任意两个皇后不在同一行、同一列或同一对角线上）。

解法1：递归

递归的思路是在每个位置尝试放置皇后，如果放置后不冲突，则递归到下一行继续放置。如果放置后冲突，则回溯到上一行，重新选择位置。

具体实现如下：

def solveNQueens(n):
    # 初始化棋盘
    board = [['.' for j in range(n)] for i in range(n)]
    res = []

    def backtrack(row):
        # 找到解
        if row == n:
            res.append([''.join(row) for row in board])
            return

        for col in range(n):
            if not is_conflict(row, col):
                board[row][col] = 'Q'
                backtrack(row + 1)
                board[row][col] = '.'

    def is_conflict(row, col):
        # 检查列冲突
        for i in range(row):
            if board[i][col] == 'Q':
                return True
        # 检查左上方对角线冲突
        i, j = row - 1, col - 1
        while i >= 0 and j >= 0:
            if board[i][j] == 'Q':
                return True
            i, j = i - 1, j - 1
        # 检查右上方对角线冲突
        i, j = row - 1, col + 1
        while i >= 0 and j < n:
            if board[i][j] == 'Q':
                return True
            i, j = i - 1, j + 1

        return False

    backtrack(0)
    return res

解法2：回溯

回溯的思路是枚举每个位置的状态，如果状态合法，则递归到下一层继续枚举。如果状态不合法，则回溯到上一层，重新选择状态。

具体实现如下：

def solveNQueens(n):
    # 初始化棋盘
    board = [['.' for j in range(n)] for i in range(n)]
    res = []

    def is_conflict(row, col):
        # 检查列冲突
        for i in range(row):
            if board[i][col] == 'Q':
                return True
        # 检查左上方对角线冲突
        i, j = row - 1, col - 1
        while i >= 0 and j >= 0:
            if board[i][j] == 'Q':
                return True
            i, j = i - 1, j - 1
        # 检查右上方对角线冲突
        i, j = row - 1, col + 1
        while i >= 0 and j < n:
            if board[i][j] == 'Q':
                return True
            i, j = i - 1, j + 1

        return False

    def backtrack(row):
        # 找到解
        if row == n:
            res.append([''.join(row) for row in board])
            return

        for col in range(n):
            if not is_conflict(row, col):
                board[row][col] = 'Q'
                backtrack(row + 1)
                board[row][col] = '.'

    backtrack(0)
    return res

两种方法本质上是一样的，只是递归的写法可能更加简洁。在实际使用中，需要根据具体情况选择使用哪种方法。