题目描述

blablabla

样例

blablabla

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

Python3 non-backtrack

n = int(input().strip())

pos = [-1]*n #index of pos is Row and content is Col

def check(pos, k, j): 
    for i in range(k):
        if pos[i] == j or abs(i - k) == abs(pos[i] - j):
            return False
    return True

def dfs(k, n):
    if k == n:
        temp = []
        for i in range(n):
            cur = ''
            for j in range(n):
                if pos[i] == j:
                    cur += 'Q'
                else:
                    cur += '.'
            print(cur)
        print()

    else:
        for j in range(n):
            if check(pos, k, j):
                pos[k] = j
                dfs(k+1, n)
if __name__ == "__main__":
    dfs(0 ,n)

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

Y神代码翻译 BT

n  = int(input().strip())
N = 2*n
col = [False]*n
dg = [False]*N
udg = [False]*N
g = [['.' for _ in range(n)] for _ in range(n)]

def dfs(u):
    if u == n:
        for i in range(n):
            print(''.join(g[i]))
        print()
        return
    else:
        for i in range(n):
            if not col[i] and not dg[u + i] and not udg[n - u + i]:
                g[u][i] = 'Q'
                col[i] = dg[u + i] = udg[n - u + i] = True
                dfs(u+1)
                col[i] = dg[u + i] = udg[n - u + i] = False
                g[u][i] = '.'

if __name__ == "__main__":
    dfs(0)