解锁棋盘之谜：探索N皇后问题的全方位解决策略【python 力扣51题】

输入: n = 4
输出: [
 ["..Q.",  // 解法 1
  "Q...",
  "...Q",
  ".Q.."],
 ["Q...",  // 解法 2
  "..Q.",
  "Q...",
  "...Q"]
]

输入：n = 1
输出：[["Q"]]

def solveNQueens(n):
    def backtrack(row, diagonals, anti_diagonals, cols, state):
        # Base case - a valid solution is found
        if row == n:
            board = build_board(state)
            solutions.append(board)
            return
        
        for col in range(n):
            curr_diagonal = row - col
            curr_anti_diagonal = row + col
            
            # If the queen is not placeable
            if (col in cols or curr_diagonal in diagonals or curr_anti_diagonal in anti_diagonals):
                continue
            
            # "Add" queen to the board
            cols.add(col)
            diagonals.add(curr_diagonal)
            anti_diagonals.add(curr_anti_diagonal)
            state.append(col)
            
            # Move on to the next row with the updated state
            backtrack(row + 1, diagonals, anti_diagonals, cols, state)
            
            # "Remove" queen from the board (backtrack)
            cols.remove(col)
            diagonals.remove(curr_diagonal)
            anti_diagonals.remove(curr_anti_diagonal)
            state.pop()
    def build_board(state):
        board = []
        for i in range(n):
            row = ['.' for _ in range(n)]
            row[state[i]] = 'Q'
            board.append(''.join(row))
        return board
    solutions = []
    backtrack(0, set(), set(), set(), [])
    return solutions
# 示例调用
print(solveNQueens(4))

def solveNQueens(n):
    def backtrack(row, cols, diag1, diag2, state):
        if row == n:
            board = build_board(state)
            solutions.append(board)
            return
        
        available_positions = (~(
cols | diag1 | diag2)) & ((1 << n) - 1)
        
        while available_positions:
            position = available_positions & -available_positions
            col = bin(position).count('0') - 1
            state.append(col)
            backtrack(row + 1, cols | position, (diag1 | position) << 1, (diag2 | position) >> 1, state)
            state.pop()
            available_positions &= available_positions - 1
    def build_board(state):
        board = []
        for i in range(n):
            row = ['.' for _ in range(n)]
            row[state[i]] = 'Q'
            board.append(''.join(row))
        return board
    solutions = []
    backtrack(0, 0, 0, 0, [])
    return solutions
# 示例调用
print(solveNQueens(4))

def solveNQueens(n):
    def backtrack(row):
        if row == n:
            solutions.append(["".join(row) for row in board])
            return
        
        for col in range(n):
            if not (cols[col] or diag1[row + col] or diag2[row - col + n - 1]):
                board[row][col] = 'Q'
                cols[col] = diag1[row + col] = diag2[row - col + n - 1] = True
                backtrack(row + 1)
                board[row][col] = '.'
                cols[col] = diag1[row + col] = diag2[row - col + n - 1] = False
    board = [["."]*n for _ in range(n)]
    cols = [False]*n
    diag1 = [False]*(2*n-1)
    diag2 = [False]*(2*n-1)
    solutions = []
    backtrack(0)
    return solutions
# 示例调用
print(solveNQueens(4))

def solveNQueens(n):
    def dfs(queens, xy_diff, xy_sum):
        p = len(queens)
        if p==n:
            result.append(queens)
            return None
        for q in range(n):
            if q not in queens and p-q not in xy_diff and p+q not in xy_sum: 
                dfs(queens+[q], xy_diff+[p-q], xy_sum+[p+q])
    result = []
    dfs([], [], [])
    return [ ["."*i + "Q" + "."*(n-i-1) for i in sol] for sol in result]
# 示例调用
print(solveNQueens(4))

def solveNQueens(n):
    stack = [(0, [], [], [])]  # (row, queens, xy_diff, xy_sum)
    results = []
    while stack:
        row, queens, xy_diff, xy_sum = stack.pop()
        if row == n:
            board = build_board(queens)
            results.append(board)
        else:
            for col in range(n):
                if col not in queens and row - col not in xy_diff and row + col not in xy_sum:
                    stack.append((row + 1, queens + [col], xy_diff + [row - col], xy_sum + [row + col]))
    
    return results
def build_board(queens):
    n = len(queens)
    board = []
    for i in queens:
        board.append('.' * i + 'Q' + '.' * (n - i - 1))
    return board
# 示例调用
print(solveNQueens(4))