无法区分两种Python N皇后解法差异，请求技术解析

我在学习回溯法时，看到了N皇后问题的两种解决方案：第一种是生成所有排列的「朴素解法」，时间复杂度标注为O(n! * n)；第二种是增量构建解并即时回溯剪枝的方法，时间复杂度据称是O(n!)。但对比代码后，除了注释、变量名、对角线冲突的计算/记录方式这些细节差异外，我看不出两者在递归、回溯、剪枝逻辑上的本质区别，特此请求技术解析。

第一种解法（朴素排列法，效率最低） #

# Python program to find all solution of N queen problem 
# using recursion

# Function to check if placement is safe
def isSafe(board, currRow, currCol):
    for i in range(len(board)):
        placedRow = board[i]
        placedCol = i + 1
        
        # Check diagonals
        if abs(placedRow - currRow) == \
           abs(placedCol - currCol):
            return False # Not safe
          
    return True # Safe to place

# Recursive utility to solve N-Queens
def nQueenUtil(col, n, board, res, visited):
  
    # If all queens placed, add to res
    if col > n:
        res.append(board.copy())
        return
      
    # Try each row in column
    for row in range(1, n+1):
      
        # If row not used
        if not visited[row]:
          
            # Check safety
            if isSafe(board, row, col):
              
                # Mark row
                visited[row] = True
                
                # Place queen
                board.append(row)
                
                # Recur for next column
                nQueenUtil(col+1, n, board, res, visited)
                
                # Backtrack
                board.pop()
                visited[row] = False

# Main N-Queen solver
def nQueen(n):
    res = []
    board = []
    visited = [False] * (n + 1)
    nQueenUtil(1, n, board, res, visited)
    return res

if __name__ == "__main__":
    n = 4
    res = nQueen(n)
    for row in res:
        print(row)

第二种解法（剪枝回溯法，效率更高） #

# Python program to find all solutions of the N-Queens problem
# using backtracking and pruning

def nQueenUtil(j, n, board, rows, diag1, diag2, res):

    if j > n:
        # A solution is found
        res.append(board[:])
        return

    for i in range(1, n + 1):
        if not rows[i] and not diag1[i + j] and not diag2[i - j + n]:

            # Place queen
            rows[i] = diag1[i + j] = diag2[i - j + n] = True
            board.append(i)

            # Recurse to the next column
            nQueenUtil(j + 1, n, board, rows, diag1, diag2, res)

            # Remove queen (backtrack)
            board.pop()
            rows[i] = diag1[i + j] = diag2[i - j + n] = False

def nQueen(n):
    res = []
    board = []

    # Rows occupied
    rows = [False] * (n + 1)

    # Major diagonals (row + j) and Minor diagonals (row - col + n)
    diag1 = [False] * (2 * n + 1)
    diag2 = [False] * (2 * n + 1)

    # Start solving from the first column
    nQueenUtil(1, n, board, rows, diag1, diag2, res)
    return res

if __name__ == "__main__":
    n = 4
    res = nQueen(n)

    for temp in res:
        print(temp)

核心差异解析 #

咱们直接拆解两个解法的本质区别，核心在于冲突检查的效率和剪枝的即时性，这直接导致了时间复杂度的差异：

1. 冲突检查的时间复杂度天差地别

   • 第一种解法：每次判断当前位置是否安全时，isSafe函数会遍历已经放置的所有皇后（最多n个），逐个计算对角线是否冲突，单次检查的时间是O(k)（k为当前已放置的皇后数，最坏O(n)）。
   • 第二种解法：用rows、diag1、diag2三个数组提前记录行、对角线的占用状态，冲突检查只需要三次O(1)的数组查询，无需遍历任何元素。

2. 剪枝逻辑的效率差异

   • 第一种解法：先判断行未被占用，再做O(k)的对角线检查，相当于先筛选出「行安全」的候选，再逐一验证对角线，这个过程会产生很多无效的检查操作。
   • 第二种解法：把行、对角线的冲突检查合并成一次O(1)的判断，直接跳过所有存在冲突的位置，从根源上减少了进入递归的无效分支，剪枝更高效。

3. 状态记录的方式不同

   • 第一种解法：只记录了行的占用状态（visited数组），对角线冲突每次都要临时计算，没有缓存任何对角线的状态信息。
   • 第二种解法：用两个数组diag1（记录行+列相同的主对角线）和diag2（记录行-列+n相同的副对角线），把对角线的占用状态实时缓存，回溯时直接更新，避免了重复计算。

4. 时间复杂度的本质原因

   • 第一种解法的O(n! * n)：生成所有可能的行排列（共n!种），每个排列都需要做n次O(n)的冲突检查，最终时间是n! * n。
   • 第二种解法的O(n!)：由于每次冲突检查是O(1)，且剪枝提前过滤了大量无效分支，实际的递归分支数接近n!，整体时间复杂度由有效递归的次数决定，因此标注为O(n!)。

内容的提问来源于stack exchange，提问作者retpoline