Python 算法教程（50）：N 皇后问题详解

Python 算法 2 月前 0 6

前言

N 皇后问题是回溯算法的经典应用，在面试中出现频率极高。

一、问题描述

在 N×N 的棋盘上放置 N 个皇后，使得它们互不攻击（不在同一行、列、对角线）。

二、回溯框架

def solveNQueens(n):
    def backtrack(row):
        if row == n:
            solutions.append(board[:])
            return
        for col in range(n):
            if isValid(row, col):
                placeQueen(row, col)
                backtrack(row + 1)
                removeQueen(row, col)
    
    solutions = []
    board = ["." * n for _ in range(n)]
    backtrack(0)
    return solutions

三、完整性检查

def isValid(self, row, col):
    # 检查列
    for i in range(row):
        if self.board[i][col] == "Q":
            return False
    # 检查左上对角线
    i, j = row - 1, col - 1
    while i >= 0 and j >= 0:
        if self.board[i][j] == "Q":
            return False
        i -= 1
        j -= 1
    # 检查右上对角线
    i, j = row - 1, col + 1
    while i >= 0 and j < self.n:
        if self.board[i][j] == "Q":
            return False
        i -= 1
        j += 1
    return True