Dsa Backtrack N Queens

def nq(n):
    res=[]; b=['.'*n for _ in range(n)]
    def dfs(r):
        if r==n: res.append(b[:]); return
        for c in range(n):
            if safe(r,c):
                b[r]=b[r][:c]+'Q'+b[r][c+1:]
                dfs(r+1)
                b[r]=b[r][:c]+'.'+b[r][c+1:]
    def safe(r,c):
        for i in range(r):
            if b[i][c]=='Q': return False
            if c-(r-i)>=0 and b[i][c-(r-i)]=='Q': return False
            if c+(r-i)<n and b[i][c+(r-i)]=='Q': return False
        return True
    dfs(0)
    return res

def solveNQueens(n):
    cols=set(); diag1=set(); diag2=set()
    res=[]; board=[['.']*n for _ in range(n)]
    def dfs(r):
        if r==n: res.append([''.join(row) for row in board]); return
        for c in range(n):
            d1=r-c; d2=r+c
            if c in cols or d1 in diag1 or d2 in diag2: continue
            cols.add(c); diag1.add(d1); diag2.add(d2); board[r][c]='Q'
            dfs(r+1)
            cols.remove(c); diag1.remove(d1); diag2.remove(d2); board[r][c]='.'
    dfs(0)
    return res