class Solution:

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

        table = [[False for _ in range(n)] for j in range(n)]

        result = [['.' for _ in range(n)] for j in range(n)]

        answer = 0

        checkflag = False

        def put(i, j):

            tmp = []

            tmp1 = i + j

            tmp2 = i - j

            for l in range(n):

                for m in range(n):

                    if l == i or m == j or l + m == tmp1 or l - m == tmp2:

                        if table[l][m] == False:

                            table[l][m] = True

                            tmp.append((l, m))

            result[i][j] = "Q"

            return tmp

        def remove(i, j, tmp):

            for x in tmp:

                l = x[0]

                m = x[1]

                table[l][m] = False

            result[i][j] = "."

        def valid(i, j):

            if table[i][j] is False:

                return True

        def check(i, j):

            if i == n-1:

                nonlocal answer

                answer += 1

                nonlocal checkflag

                checkflag = True

            else:

                for x in range(n):

                    backtrace(i + 1, x)

        def backtrace(row, col):

            #if result[row][col] == '.':

            if valid(row, col):

                tmp = put(row, col)

                check(row, col)

                remove(row, col, tmp)

        for t in range(n):

            backtrace(0, t)

            checkflag = False

            table = [[False for _ in range(n)] for j in range(n)]

            result = [['.' for _ in range(n)] for j in range(n)]

        return answer