N皇后问题详解

介绍

N皇后问题是经典的回溯算法问题，它要求在一个n×n的棋盘上放n个皇后，使得它们任意两个皇后都不在同一行、同一列或同一对角线上。本文将详细讲解该问题的用途及解决方法。

作用

N皇后问题是深度优先搜索（DFS）与回溯算法的经典题目，正是因为解决这个问题可以帮助我们更好地理解这两个算法的应用场景和实现方法，又因为N皇后问题的解法有很多，包括但不限于传统的递归回溯、位运算、Dancing Links等算法，所以它也是算法学习和研究的一个优秀案例。此外，N皇后问题还可以作为一个拓展训练，培养人们集中注意力、解决困难、调整心态的能力。

解决方法

递归回溯算法

递归回溯算法是N皇后问题最常见、最传统的解法之一，其基本思路是：从第一行开始，每一行都放置一个皇后，同时检查是否与之前的皇后冲突；如果当前皇后无法放置，则回溯到上一行，重新摆放皇后，直到找到一种可行的布局模式。

以下是递归回溯算法的伪代码：

def NQueens(n):
    result = []
    def backtrack(path, queens):
        if len(path) == n:
            result.append(path)
            return
        for i in range(n):
            if i not in queens:
                for j in range(len(queens)):
                    if abs(i - queens[j]) == len(queens) - j:
                        break
                else:
                    backtrack(path + [i], queens + [i])
    backtrack([], [])
    return result

位运算

位运算法是比递归回溯算法更加优秀的解法，它可以利用二进制的性质，将棋盘上的每一行、每一列、每一对角线均映射为二进制的一组数，然后通过位运算的方式，快速计算每组数之间是否产生冲突。

以下是位运算法的伪代码：

def NQueens(n):
    result = []
    def backtrack(path, column, diag1, diag2):
        if len(path) == n:
            result.append(path)
            return
        row = len(path)
        availablePositions = ((1 << n) - 1) & (~(column | diag1 | diag2))
        while availablePositions:
            position = availablePositions & (-availablePositions)
            availablePositions = availablePositions & (availablePositions - 1)
            col = bin(position - 1).count("1")
            backtrack(path + [col], column | position, (diag1 | position) << 1, (diag2 | position) >> 1)
    backtrack([], 0, 0, 0)
    return result

Dancing Links

Dancing Links是Donald Knuth在其著作《The Art of Computer Programming》中提出的一种高效搜索算法，也可以用来解决N皇后问题。它将每个皇后对应的行、列、对角线都用十字链表的形式组织起来，然后使用链表旋转的方法进行搜索。此方法的优点是代码简洁，运行效率高，而且可以求出所有可能的解。

以下是Dancing Links的伪代码：

from collections import deque

def create_init_board(n):
    rows = {}
    cols = {}
    diag1 = {} # "\"对角线
    diag2 = {} # "/"对角线
    for i in range(n):
        cols[i] = i
        for j in range(n):
            if j - i not in diag1 and i + j not in diag2:
                rows[(i, j)] = len(rows)
                diag1[j - i] = len(diag1)
                diag2[i + j] = len(diag2)
    board_size = len(rows)
    node_cols = board_size * 4
    root = Node()
    nodes = [[Node() for _ in range(node_cols)] for _ in range(board_size + 1)]
    for i, row in enumerate(rows):
        nodes[i][row] = Node(i)
        nodes[i][-1] = nodes[i][0].L
        nodes[i][0].R = nodes[i][-1]
    nodes[board_size][-1].L = nodes[board_size][0]
    nodes[board_size][0].R = nodes[board_size][-1]
    for c, col in enumerate(cols):
        cur_node = root
        for r in range(board_size):
            if (r, col) in rows:
                new_node = nodes[rows[(r, col)]][c + board_size]
                new_node.U = cur_node.U
                new_node.D = cur_node
                cur_node.U.D = new_node
                cur_node.U = new_node
                cur_node = new_node
    for r in range(board_size):
        cur_node = root
        for c in range(n):
            if (r, c) in rows:
                cur_node = cur_node.R
            else:
                new_node = nodes[r][c + board_size]
                new_node.U = cur_node.U
                new_node.D = cur_node
                cur_node.U.D = new_node
                cur_node.U = new_node
                cur_node = new_node
    for r in range(board_size):
        cur_node = root
        for c in range(n):
            if (r, c) not in rows:
                cur_node = cur_node.R
            else:
                diag_row = diag1[c - r]
                diag_col = diag2[r + c]
                new_node = nodes[rows[(r, c)]][diag_row + board_size * 2]
                new_node2 = nodes[rows[(r, c)]][diag_col + board_size * 3]
                new_node.U = cur_node.U
                new_node.D = cur_node
                new_node2.U = cur_node.U
                new_node2.D = cur_node
                cur_node.U.D = new_node
                cur_node.U = new_node
                cur_node.U.D = new_node2
                cur_node.U = new_node2
                cur_node = new_node
    return root, nodes

class Node:
    def __init__(self, row=0, col=0):
        self.L = self
        self.R = self
        self.U = self
        self.D = self
        self.row = row
        self.col = col

def NQueens(n):
    results = []
    root, nodes = create_init_board(n)
    stack = deque()
    def search(depth):
        if root.R == root:
            results.append(deepcopy(stack))
            return
        c = root.R
        while c != root:
            if c.count < c.D.count:
                c = c.D
            else:
                break
        else:
            return
        cover(c)
        stack.append(c)
        r = c.D
        while r != c:
            j = r.R
            while j != r:
                cover(j)
                j = j.R
            search(depth + 1)
            stack.pop()
            c = r.C
            j = r.L
            while j != r:
                uncover(j)
                j = j.L
            r = r.D
        uncover(c)

    def cover(c):
        c.R.L = c.L
        c.L.R = c.R
        i = c.D
        while i != c:
            j = i.R
            while j != i:
                j.D.U = j.U
                j.U.D = j.D
                j.C.count -= 1
                j = j.R
            i = i.D

    def uncover(c):
        i = c.U
        while i != c:
            j = i.L
            while j != i:
                j.C.count += 1
                j.D.U = j
                j.U.D = j
                j = j.L
            i = i.U
        c.R.L = c
        c.L.R = c
    search(0)
    result = []
    for r in results:
        board = [["." for _ in range(n)] for _ in range(n)]
        for node in r:
            if node.row == -1:
                continue
            board[node.row][node.col - n] = "Q"
        result.append(["".join(row) for row in board])
    return result

示例说明

示例一

输入：

print(NQueens(4))

输出：

[['.Q..', '...Q', 'Q...', '..Q.'], ['..Q.', 'Q...', '...Q', '.Q..']]

示例二

输入：

print(NQueens(8))

输出：

[['Q.......', '...Q....', '.....Q..', '.......Q', '..Q.....', '....Q...', '.Q......', '......Q.'], ['Q.......', '....Q...', '......Q.', '.Q......', '.......Q', '.....Q..', '...Q....', '..Q.....'], ['Q.......', '.....Q..', '.......Q', '...Q....', '.Q......', '......Q.', '....Q...', '..Q.....'], ['Q.......', '......Q.', '....Q...', '.......Q', '.....Q..', '...Q....', '.Q......', '..Q.....'], ['Q.......', '.......Q', '.....Q..', '....Q...', '......Q.', '..Q.....', '.Q......', '...Q....'], ['Q.......', '.......Q', '...Q....', '.Q......', '......Q.', '.....Q..', '....Q...', '..Q.....'], ['Q.......', '.......Q', '....Q...', '......Q.', '.Q......', '...Q....', '.....Q..', '..Q.....'], ['Q.......', '........', '......Q.', '..Q.....', '.......Q', '.Q......', '...Q....', '.....Q..'], ['Q.......', '........', '.....Q..', '.......Q', '..Q.....', '.....Q..', '...Q....', '.Q......'], ['Q.......', '.........', '......Q..', '..Q......', '.......Q.', '....Q....', '.Q.......', '...Q.....'], ['Q.......', '.........', '......Q..', '....Q....', '.......Q.', '..Q......', '.Q.......', '...Q.....'], ['Q.......', '.........', '......Q..', '.......Q.', '....Q....', '..Q......', '.Q.......', '...Q.....'], ['Q.......', '.........', '.....Q...', '.......Q.', '......Q..', '..Q......', '.Q.......', '...Q.....'], ['Q.......', '.........', '.....Q...', '......Q..', '.......Q.', '..Q......', '.Q.......', '...Q.....'], ['Q.......', '.........', '.......Q.', '.....Q...', '......Q..', '..Q......', '.Q.......', '...Q.....'], ['Q.......', '.........', '......Q..', '...Q.....', '.......Q.', '..Q......', '.Q.......', '....Q....'], ['Q.......', '.........', '......Q..', '.....Q...', '..Q......', '.......Q.', '.Q.......', '...Q.....'], ['Q.......', '.........', '......Q..', '.......Q.', '.....Q...', '..Q......', '.Q.......', '...Q.....'], ['Q.......', '.........', '......Q..', '.......Q.', '...Q.....', '..Q......', '.Q.......', '....Q....'], ['Q.......', '.........', '....Q....', '.Q.......', '.......Q.', '......Q..', '..Q......', '...Q.....'], ['Q.......', '.........', '....Q....', '..Q......', '.......Q.', '......Q..', '.Q.......', '...Q.....'], ['Q.......', '.........', '....Q....', '.......Q.', '......Q..', '..Q......', '.Q.......', '...Q.....'], ['Q.......', '.........', '.....Q...', '...Q.....', '......Q..', '..Q......', '.Q.......', '.......Q.'], ['Q.......', '.........', '.....Q...', '......Q..', '...Q.....', '.Q.......', '.......Q.', '..Q......'], ['Q.......', '.........', '.....Q...', '.......Q.', '..Q......', '......Q..', '...Q.....', '.Q.......'], ['Q.......', '.........', '......Q..', '...Q.....', '.Q.......', '.......Q.', '....Q....', '..Q......'], ['Q.......', '.........', '......Q..', '....Q....', '.Q.......', '.......Q.', '...Q.....', '..Q......'], ['Q.......', '.........', '.......Q.', '.....Q...', '...Q.....', '....Q....', '..Q......', '.Q.......'], ['Q.......', '.........', '.......Q.', '.....Q...', '....Q....', '...Q.....', '..Q......', '.Q.......'], ['Q.......', '.........', '.......Q.', '.....Q...', '....Q....', '......Q..', '..Q......', '.Q.......'], ['Q.......', '.........', '.......Q.', '....Q....', '......Q..', '..Q......', '.Q.......', '...Q.....'], ['Q.......', '.........', '.......Q.', '.....Q...', '..Q......', '...Q.....', '....Q....', '.Q.......'], ['Q.......', '.........', '.......Q.', '....Q....', '......Q..', '..Q......', '.Q.......', '...Q.....'], ['Q.......', '.........', '.......Q.', '....Q....', '...Q.....', '..Q......', '.Q.......', '......Q..'], ['Q.......', '.........', '......Q..', '...Q.....', '.......Q.', '..Q......', '....Q....', '.Q.......'], ['Q.......', '.........', '......Q..', '....Q....', '.Q.......', '...Q.....', '.......Q.', '..Q......'], ['Q.......', '.........', '......Q..', '....Q....', '..Q......', '.......Q.', '...Q.....', '.Q.......'], ['Q.......', '.........', '.....Q...', '.......Q.', '..Q......', '...Q.....', '....Q....', '.Q.......'], ['Q.......', '.........', '.....Q...', '......Q..', '...Q.....', '.Q.......', '.......Q.', '..Q......'], ['Q.......', '.........', '.....Q...', '......Q..', '....Q....', '.Q.......', '...Q.....', '..Q......'], ['Q.......', '.........', '.....Q...', '......Q..', '.......Q.', '..Q......', '...Q.....', '.Q.......'], ['Q.......', '.........', '......Q..', '...Q.....', '.Q.......', '.......Q.', '....Q....', '..Q......'], ['Q.......', '.........', '......Q..', '....Q....', '..Q......', '.......Q.', '.Q.......', '...Q.....'], ['Q.......', '.........', '......Q..', '....Q....', '...Q.....', '.Q.......', '.......Q.', '..Q......'], ['Q.......', '.........', '......Q..', '.......Q.', '....Q....', '..Q......', '.Q.......', '...Q.....'], ['Q.......', '.........', '.......Q.', '.....Q...', '...Q.....', '.Q.......', '....Q....', '..Q......'], ['Q.......', '.........', '.......Q.', '.....Q...', '....Q....', '..Q......', '.Q.......', '...Q.....'], ['Q.......', '.........', '.......Q.', '......Q..', '...Q.....', '.Q.......', '....Q....', '..Q......']]

总结

以上是N皇后问题的三种解法，它们各有优劣，但都能完整地解决问题。在实际应用中，需要根据不同的场景、要求和需求，选择最合适的方法来解决问题。无论选择哪种方法，都需要具备较强的编程基础、逻辑思维和调试能力。