The n-queens puzzle is the problem of placing n queens on an n x n chessboard such that no two queens attack each other. Given an integer n, return the number of distinct solutions to the n-queens puzzle.

solveNQueens.py

class Solution:
    def solveNQueens(self, n: int) -> List[List[str]]:
        res = []
        def canPlace(board, n, row, col):
            # col
            for i in range(row):
                if board[i][col]:
                    return False

            # left diagonal
            r, c = row, col

            while r >= 0 and c >= 0:
                if board[r][c]:
                    return False

                r -= 1
                c -= 1

            # right
            r, c = row, col
            while r >= 0 and c < n:
                if board[r][c]:
                    return False
                r -= 1
                c += 1

            return True
        
        def push(board, n):
            temp = []
            for i in range(n):
                curr = ""
                for j in range(n):
                    if board[i][j] == "":
                        curr += "."
                    else:
                        curr += board[i][j]
                temp.append(curr)
            res.append(temp)
        
        def helper(board, n, row):
            # base case
            if row == n:
                push(board, n)
                return
            
            # recursive case
            for col in range(n):
                if canPlace(board, n, row, col):
                    board[row][col] = "Q"
                    success = helper(board, n, row + 1)
                    
                    if success:
                        return True
                        
                    # backtrack
                    board[row][col] = ""
            return False
        
        board = [["" for _ in range(n)] for _ in range(n)]
        
        helper(board, n, 0)
        
        return res