N皇后问题

N皇后问题_牛客题霸_牛客网

问题简述

N 皇后问题是指在 n * n 的棋盘上要摆 n 个皇后，
要求：任何两个皇后不同行，不同列也不在同一条斜线上，
求给一个整数 n ，返回 n 皇后的摆法数。

思路：DFS

• 定义 book[i]=j 表示第 i 行、第 j 列放了一个“皇后”；

• DFS 每一行，检查该行的每个点 (i,j) 是否与已经放置的点 (i_,j_) 是否共行、共列、共斜线；

  • 检查是否共斜线：abs(斜率) != 1

• 【DFS 找方法数】初始化全局变量 ret=0 记录可行的方法数，能顺利走到递归基就 +1；

Python（推荐）

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
# 
# @param n int整型 the n
# @return int整型
#
class Solution:
    def Nqueen(self , n: int) -> int:
        # book[i] = j 表示第 i 行的“皇后”放在了第 j 列
        book = [-1] * n
        
        def valid(i, j):
            """验证当前点 (i,j) 与所有已经放置的点 (i_,j_) 是否共列或共斜线"""
            for i_ in range(i):
                j_ = book[i_]
                # 如果共列或共斜线，因为 i_ < i，所以不会共行
                if j == j_ or abs(i - i_) == abs(j - j_):
                    return False
            return True
        
        # 记录找到的方法数
        self.ret = 0
        
        def dfs(i):
            """深度优先遍历每一行"""
            if i == n:  # 找到一种摆法
                self.ret += 1
                return
            
            for j in range(n):  # 遍历第 i 行的每个点 (i, j)
                if valid(i, j):  # 验证当前点 (i, j) 是否能放
                    book[i] = j
                    dfs(i + 1)
                    # book[i] = -1  # 这里不需要回溯，因为 valid 只会遍历 book[0:i-1]
        dfs(0)
        return self.ret

优化：最优时间复杂度就是 $O(n^n)$，但是可以利用位运算优化常数项（核心利用二进制状态压缩优化 valid 的判断）；

因为 Python 中的位运算跟其他语言略有区别，下面的代码用 C++ 完成；

C++

class Solution {
    int ret = 0;  // 记录找到的方法数

    void dfs(int c, int l, int r, int limit) {
        if (c == limit) {  // 列都填满了，说明找到了一种摆法
            ret += 1;
            return;
        }
        // 当前行可以摆放的位置
        int pos = limit & (~(c | l | r));
        while (pos) {
            // 找到 pos 中最右侧的 1
            int R1 = pos & (~pos + 1);
            dfs(c | R1,  // 增加一个列限制
                (l | R1) << 1,  // 加一个 左斜线的限制
                (r | R1) >> 1,  // 加一个 右斜线的限制
                limit);  // limit 不变
            pos -= R1;  // 把最右的 1 清 0
        }
    }

public:
    int Nqueen(int n) {
        // limit 的后 n 位为 1，因为 n <= 9，所以 int 就够了
        // limit 的作用是限制有效位置，该值全程不会改变
        int limit = (1 << n) - 1;
        dfs(0, 0, 0, limit);  // 初始全 0，表示都没有限制
        return ret;
    }
};