N Queens (Leetcode 51)

Problem Link: https://leetcode.com/problems/n-queens/

class Solution:
    def solveNQueens(self, n: int) -> List[List[str]]:
        
        ans=[]
        board=[["." for i in range(n)] for j in range(n)]
        # Watch Neetcode's video for this
        
        col=set()
        posDiag=set() # r+c
        negDiag=set() # r-c
        
        def recursion(r,n):
            
            if(r==n):
                copy=[]
                
                for i in range(n):
                    temp=""
                    for j in range(n):
                        temp=temp+board[i][j]
                    copy.append(temp)
                    
                ans.append(copy)
                return
            
            for j in range(n):
                
                # Unsafe place
                if(j in col or r+j in posDiag or r-j in negDiag):
                    continue
                
                # Safe place
                else:
                    col.add(j)
                    posDiag.add(r+j)
                    negDiag.add(r-j)
                    board[r][j]="Q"
                    
                    recursion(r+1,n)
                    
                    col.remove(j)
                    posDiag.remove(r+j)
                    negDiag.remove(r-j)
                    board[r][j]="."
        
        recursion(0,n)
        return ans