Python（算法综合）问题 E: 一山不容二虎——n皇后问题

问题 E: 一山不容二虎——n皇后问题

题目描述

在 n×n 的棋盘上放置彼此不受攻击的 n 个皇后。
按照国际象棋的规则，皇后可以攻击与 之在同一行、同一列、同一斜线上的棋子。
设计算法在 n×n 的棋盘上放置 n 个皇后，使其彼 此不受攻击。

输入

输入t，表示有t组样例
请输入皇后的个数 n

输出

输出能排列的方案数

样例输入

1
4

样例输出

2

提示

n<=10

解答：

def dfs(row):  # 行
    global count
    # 遍历每一列
    for col in range(n):
        # 观察列和上下对象线是否没有被标记
        if flag[col] == 0 and d1[col + row] == 0 and d2[row - col + n - 1] == 0:
            pace[row] = col  # 下点
            # 标记1
            flag[col] = 1
            d1[col + row] = 1
            d2[row - col + n - 1] = 1
            # 如果不是最后一行，一直寻找
            if row < n - 1:
                dfs(row + 1)
            else:
                count += 1
            flag[col] = 0
            d1[col + row] = 0
            d2[row - col + n - 1] = 0


n1 = int(input())
for i in range(n1):
    n = int(input())
    # 1.定义皇后的位置 pace[0]=2 ->第一行第三个的位置
    pace = [0 for _ in range(n)]
    # 2.标记列
    flag = [0 for _ in range(n)]
    # 3.上下对角线
    d1 = [0 for _ in range(2 * n - 1)]
    d2 = [0 for _ in range(2 * n - 1)]
    count = 0
    dfs(0)
    print(count)

答案不唯一，必定有更加优化的解法欢迎分享