主页 / user-13824855

retpoline's questions

Martin Hope
retpoline
Asked: 2025-04-26 16:31:41 +0800 CST
  • 6

在阅读回溯相关知识的过程中，我找到了 geeksforgeeks.org 上一个关于 n 皇后问题解决方案的页面。第一个解决方案被称为“朴素方法”，它可以生成所有可能的排列，其效率最低，为 O(n! * n)。第二个解决方案是“我们不是生成所有可能的排列，而是逐步构建解决方案，这样做可以确保每一步部分解决方案都有效。如果发生冲突，我们会立即回溯，这有助于避免不必要的计算。” 据说它的复杂度是 O(n!)。

分析代码时，除了注释、一些变量名、对角线冲突的计算/记录方式以及其他一些没有区别的琐碎事情（例如使用 [:] 而不是 .copy()）之外，我根本看不出两者之间的区别（在递归/回溯/修剪方面）。

第一个解决方案（效率最低）：

#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)
python