解题思路

这题思路与数独「37. 解数独」一致都是回溯，重点是编码实现
本题与下一题代码完全一致
详细实现及思路注解见代码和注释

51. N 皇后

52. N皇后 II

代码

class Solution:
    def solveNQueens(self, n: int) -> List[List[str]]:
        chessboard = [['.' for _ in range(n)] for _ in range(n)]
        result = []
        # 为行号，表示放置第i+1个皇后
        # j为列号，表示该行j之前的位置已经尝试过，回溯时从j开始考察
        i = j = 0
        trace = []
        while True:
            find = False
            for j in range(j, n):
                if eligible(chessboard, i, j):
                    chessboard[i][j] = 'Q'
                    trace.append(j)
                    find = True
                    break
            if find:  # 本行找到一个有效位置，行号+1，列从0开始
                i += 1
                if i == n:
                    result.append([''.join(row) for row in chessboard])
                j = 0
            else:  # 本行发现冲突，回溯到上一行，列号来自trace栈顶
                i -= 1
                if i < 0: break
                j = trace.pop()
                chessboard[i][j] = '.'
                j += 1
        return result


def eligible(board, x, y):
    """
    检查如果board[x][y]放置皇后以后会不会有纵横斜四个方向的冲突
    小技巧：所有行都处理完以后（已经放置满N个皇后）返回False引导继续回溯处理剩余有效方案
    """
    if x == len(board): return False  # 到最后一行继续回溯，找到所有情况
    for i in range(len(board)):  # x行
        if board[x][i] == 'Q': return False
    for j in range(len(board)):  # y列
        if board[j][y] == 'Q': return False
    i, j = x, y
    while i >= 0 and j >= 0:
        if board[i][j] == 'Q': return False
        i -= 1
        j -= 1
    i, j = x+1, y+1
    while i < len(board) and j < len(board):
        if board[i][j] == 'Q': return False
        i += 1
        j += 1
    i, j = x+1, y-1
    while i < len(board) and j >= 0:
        if board[i][j] == 'Q': return False
        i += 1
        j -= 1
    i, j = x-1, y+1
    while i >= 0 and j < len(board):
        if board[i][j] == 'Q': return False
        i -= 1
        j += 1
    return True

效果图