第一种搜索方式：按行搜索

def dfs(u):
    if u==n:    # 1.判断dfs停止条件：如果遍历到第n行
        for i in range(n):
            print("".join(g[i]))
        print()
        return
    for i in range(n):    # 2.遍历状态：从小到大遍历寻找第i列
        if not cols[i] and not dg[n+i-u] and not udg[u+i]:    # 3.判断能否更新
            g[u][i] = "Q"                            # 4. 更新状态
            cols[i] = dg[n+i-u] = udg[u+i] = True    # 更新状态
            dfs(u+1)    # 5.递归dfs
            cols[i] = dg[n+i-u] = udg[u+i] = False   # 6. 回溯，恢复现场
            g[u][i] = "."    # 回溯，恢复现场


# 1.输入示例
n = int(input().strip())

# 2.初始化结果数组和状态数组
g = [["." for i in range(n)] for j in range(n)]
cols = [False for i in range(n)]    # 标记列是否被标记过
dg = [False for i in range(2*n)]   # 标记正对角线是否标记过皇后
udg = [False for i in range(2*n)]    # 标记反对角线是否标记过皇后

# 3.开始dfs搜索
dfs(0)

第二种搜索方式：按网格搜索（python超时）

def dfs_2(x, y, s):
    if y==n:    # 当y==n时，自动转到下一行
        x+=1;y=0
    if x>=n:    # ！出错：判断条件(x>=n)和(s==n)不同同时放在一个if后面，否则放x>=n且s!=n时，没有遇到return语句，导致x无限增大超出栈容量
        if s==n:
            for i in range(n):
                print("".join(g[i]))
            print()
        return
    # ！！！注意：枚举放皇后和不放皇后两种选择
    dfs_2(x, y + 1, s)

    if not rows[x] and not cols[y] and not dg[n+x-y] and not udg[x+y]:
#         print(x,y,s)
        g[x][y]="Q"
        rows[x] = cols[y] = dg[n+x-y] = udg[x+y] = True
        dfs_2(x,y+1,s+1)
        g[x][y]="."
        rows[x] = cols[y] = dg[n+x-y] = udg[x+y] = False


# 1.输入示例
n = int(input().strip())

# 2.初始化结果数组和状态数组
g = [["." for i in range(n)] for j in range(n)]
rows = [False for i in range(n)]    # 标记列是否被标记过
cols = [False for i in range(n)]    # 标记列是否被标记过
dg = [False for i in range(2*n)]   # 标记正对角线是否标记过皇后
udg = [False for i in range(2*n)]    # 标记反对角线是否标记过皇后

# 3.开始dfs搜索
dfs_2(0,0,0)