本文共 3230 字，大约阅读时间需要 10 分钟。

伪代码

dfs函数(x) {
        if x==n {
    //如果x等于n了，说明每行的皇后都放置完毕        //将棋盘内容的快照保存下来        return    }    for(y=0;i

python3

class Solution(object):    def solveNQueens(self, n):        # 生成N*N的棋盘，填充棋盘，每个格子默认是''.''表示没有放置皇后        arr = [["." for _ in range(n)] for _ in range(n)]  # 生成列表最好方式是采用列表推导式        res = []  # 存放最终结果        # 检查当前的行和列是否可以放置皇后        def check(x: int, y: int):            # 检查竖着的一列是否有皇后            for i in range(x):                if arr[i][y] == "Q":                    return False            # 检查左上的斜边是否有皇后            i, j = x - 1, y - 1            while i >= 0 and j >= 0:                if arr[i][j] == "Q":                    return False                i, j = i - 1, j - 1            # 检查左下的斜边是否有皇后            i, j = x - 1, y + 1            while i >= 0 and j < n:                if arr[i][j] == "Q":                    return False                i, j = i - 1, j + 1            # 检查右上的斜边是否有皇后            i, j = x + 1, y - 1            while i < n and j >= 0:                if arr[i][j] == "Q":                    return False                i, j = i + 1, j - 1            # 检查右下的斜边是否有皇后            i, j = x + 1, y + 1            while i < n and j < n:                if arr[i][j] == "Q":                    return False                i, j = i + 1, j + 1            return True        def dfs(x):            # x是从0开始计算的            # 当x==n时所有行的皇后都放置完毕，此时记录结果            if x == n:                res.append(["".join(arr[i]) for i in range(n)])                return            # 遍历每一列            for y in range(n):                # 检查[x,y]这一坐标是否可以放置皇后                # 如果满足条件，就放置皇后，并继续检查下一行                if check(x, y):                    arr[x][y] = "Q"  # 放上皇后                    dfs(x + 1)  # 搜索下一行策略                    arr[x][y] = "."  # 撤销皇后，y进入下一列搜索        dfs(0)        return resprint(len(Solution().solveNQueens(8)))

利用一个规律改进算法。之前check()是循环，效率不高。

python3

class Solution(object):    def solveNQueens(self, n):        # 生成N*N的棋盘，填充棋盘，每个格子默认是''.''表示没有放置皇后        arr = [["." for _ in range(n)] for _ in range(n)]  # 生成列表最好方式是采用列表推导式        res = []  # 存放最终结果        columns = set()        hypotenuse1 = set()        hypotenuse2 = set()        # 检查当前的行和列是否可以放置皇后        def check(x: int, y: int):            if y in columns:                return False            if x - y in hypotenuse1:                return False            if x + y in hypotenuse2:                return False            return True        def dfs(x):            # x是从0开始计算的            # 当x==n时所有行的皇后都放置完毕，此时记录结果            if x == n:                res.append(["".join(arr[i]) for i in range(n)])                return            # 遍历每一列            for y in range(n):                # 检查[x,y]这一坐标是否可以放置皇后                # 如果满足条件，就放置皇后，并继续检查下一行                if check(x, y):                    columns.add(y)                    hypotenuse1.add(x - y)                    hypotenuse2.add(x + y)                    arr[x][y] = "Q"  # 放上皇后                    dfs(x + 1)  # 搜索下一行策略                    arr[x][y] = "."  # 撤销皇后，y进入下一列搜索                    columns.remove(y)                    hypotenuse1.remove(x - y)                    hypotenuse2.remove(x + y)        dfs(0)        return resprint(Solution().solveNQueens(8))

转载地址：http://sdce.baihongyu.com/