[python版]: # n-皇后问题

样例

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

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

第一种搜索顺序：知道每一行只有一个皇后

第一种搜索顺序 每一行只有一个皇后，当前i行，放置（i,j）
确定回溯状态，第i行
确定递归出口
展开当前第i行的j列活节点

def dfs(i):
    if i == n:
        #print('g',g)
        for row in g:
            print(''.join(row))
        print()
        return
    for j in range(n):
        #print(i, j, i + j, n - i + j-1)
        if not col[j] and not dg[i + j] and not undg[n - i + j-1]:
            g[i][j] = 'Q'
            col[j], dg[i + j], undg[n - i + j-1] = True, True, True
            dfs(i + 1)
            col[j], dg[i + j], undg[n - i + j-1] = False, False, False
            g[i][j] = '.'


n = int(input())
g = [['.'] * n for i in range(n)]
col = [False] * n
dg = [False] * (2 * n - 1)
undg = [False] * (2 * n - 1)
dfs(0)