class Solution:
    def totalNQueens(self, n: int) -> int:
        def can_place(row, col):
            return cols[col] == 0 and lu_rd[row - col] == 0 and ld_ru[row + col] == 0

        def add_solution():
            ret[0] += 1

        def add_queen(row, col):
            t = (row, col)
            queens.add(t)
            cols[col] = 1
            lu_rd[row - col] = 1
            ld_ru[row + col] = 1

        def romove_queen(row, col):
            t = (row, col)
            queens.remove(t)
            cols[col] = 0
            lu_rd[row - col] = 0
            ld_ru[row + col] = 0

        def backtrack(row=0):
            for col in range(n):
                if can_place(row, col):
                    add_queen(row, col)
                    if row + 1 == n:
                        add_solution()
                    else:
                        backtrack(row + 1)
                    romove_queen(row, col)

        cols = [0] * (n + 1)
        lu_rd = [0] * (n * 2 + 1)  # left-up to right-down
        ld_ru = [0] * (n * 2 + 1)  # left-down to right-up
        queens = set()
        ret = [0]

        backtrack()

        return ret[0]

2cb748e1fdcb35e4c03a84cbcc96b8072ff316c4
<mask token>

class Solution:
    <mask token>

class Solution:

    def totalNQueens(self, n: int) ->int:

        def can_place(row, col):
            return cols[col] == 0 and lu_rd[row - col] == 0 and ld_ru[row + col
                ] == 0

        def add_solution():
            ret[0] += 1

        def add_queen(row, col):
            t = row, col
            queens.add(t)
            cols[col] = 1
            lu_rd[row - col] = 1
            ld_ru[row + col] = 1

        def romove_queen(row, col):
            t = row, col
            queens.remove(t)
            cols[col] = 0
            lu_rd[row - col] = 0
            ld_ru[row + col] = 0

        def backtrack(row=0):
            for col in range(n):
                if can_place(row, col):
                    add_queen(row, col)
                    if row + 1 == n:
                        add_solution()
                    else:
                        backtrack(row + 1)
                    romove_queen(row, col)
        cols = [0] * (n + 1)
        lu_rd = [0] * (n * 2 + 1)
        ld_ru = [0] * (n * 2 + 1)
        queens = set()
        ret = [0]
        backtrack()
        return ret[0]

class Solution:
    def totalNQueens(self, n: int) -> int:
        def can_place(row, col):
            return cols[col] == 0 and lu_rd[row - col] == 0 and ld_ru[row + col] == 0

        def add_solution():
            ret[0] += 1

        def add_queen(row, col):
            t = (row, col)
            queens.add(t)
            cols[col] = 1
            lu_rd[row - col] = 1
            ld_ru[row + col] = 1

        def romove_queen(row, col):
            t = (row, col)
            queens.remove(t)
            cols[col] = 0
            lu_rd[row - col] = 0
            ld_ru[row + col] = 0

        def backtrack(row=0):
            for col in range(n):
                if can_place(row, col):
                    add_queen(row, col)
                    if row + 1 == n:
                        add_solution()
                    else:
                        backtrack(row + 1)
                    romove_queen(row, col)

        cols = [0] * (n + 1)
        lu_rd = [0] * (n * 2 + 1)  # left-up to right-down
        ld_ru = [0] * (n * 2 + 1)  # left-down to right-up
        queens = set()
        ret = [0]

        backtrack()

        return ret[0]
