题目描述

n-皇后问题是指将 n 个皇后放在 n∗n 的国际象棋棋盘上，使得皇后不能相互攻击到，即任意两个皇后都不能处于同一行、同一列或同一斜线上。

现在给定整数n，请你输出所有的满足条件的棋子摆法。

输入格式
共一行，包含整数n。

输出格式
每个解决方案占n行，每行输出一个长度为n的字符串，用来表示完整的棋盘状态。

其中”.”表示某一个位置的方格状态为空，”Q”表示某一个位置的方格上摆着皇后。

每个方案输出完成后，输出一个空行。

注意：行末不能有多余空格。

输出方案的顺序任意，只要不重复且没有遗漏即可。

数据范围
1≤n≤9

样例

输入样例：
4
输出样例：
.Q..
...Q
Q...
..Q.

..Q.
Q...
...Q
.Q..

算法1

按全排列搜索

python 代码

def dfs(u):
    if u==n:
        for i in range(n):
            for j in range(n):
                print(g[i][j],end='')
            print()
        print()
        return
    for i in range(n):          #u是行，i是列
        if col[i] == False and dg[i+u]==False and udg[n-u+i]==False:
            g[u][i] = 'Q'
            col[i] = dg[i+u]=udg[n-u+i]=True
            dfs(u+1)
            col[i] =dg[i+u]=udg[n-u+i]=False        #回溯
            g[u][i]='.'


if __name__ == "__main__":
    n = int(input())
    N = 2*n
    g = [['.']*N for _ in range(N)]
    col = [False]*N
    dg = [False]*N
    udg = [False]*N
    dfs(0)

算法2

按每个格子放或不放皇后枚举

blablabla

时间复杂度

参考文献

C++ 代码

blablabla