Since we're traversing by row, we just need to keep hashtables of columns, and diagonals used. In storing diagonals, we can use the pattern where all down-to-up( / ) cells will have a distinct row + col sum for each diagonal. For up-to-down diagonal cells ( \ ) I just reduce the position to the most up-left position and store that.
def solveNQueens(self, n): def backtrack(r, C, U, D, board, n, res): if r == n: res.append([''.join(r) for r in board]) else: for c in range(n): u, d = r + c, (r-c, 0) if r > c else (0, c-r) if c not in C and u not in U and d not in D: board[r][c] = 'Q' C.add(c); U.add(u); D.add(d) backtrack(r+1, C, U, D, board, n, res) C.remove(c); U.remove(u); D.remove(d) board[r][c] = '.' if not n: return  board = [["." for _ in range(n)] for _ in range(n)] res =  backtrack(0, set(), set(), set(), board, n, res) return res