N-Queens

class Solution:
    def solveNQueens(self, n: int) -> List[List[str]]:
        solutions = []
        def isplaceok(board, N, col):
            for i in range(N): # for each queen already placed
                if (board[i] == col) or (board[i] - i == col - N) or (board[i] + i == col + N):
                    return False # place can be attacked
            return True # no attacks; place is ok

        def printsolution(board):
            solutions.append(board[:]) #shallow copy
            for i in range(n):
                for j in range(n):
                    print("X" if board[i] == j else "-", end="")
                print("")
            print("\n")

        def addqueen(board, N):
            if N >= n: # all queens have been placed
                printsolution(board)
            else: # try place the Nth queen
                for col in range(n):
                    if isplaceok(board, N, col):
                        print(board)
                        board[N] = col # place nth queen at column c
                        addqueen(board, N+1)

        addqueen([-1]*n, 0)
        print(solutions)
        return [
            ["." * c + "Q" + "." * (n - c - 1) for c in sol]
            for sol in solutions
        ]

def solveNQueens(self, n: int):
    solutions = []
    def render_board(cols, n):
        board = []
        for col in cols:
            row = ["." for _ in range(n)]
            row[col] = "Q"
            board.append("".join(row))
        return board

    def backtrack(row, cols, diag1, diag2, board):
        if row == n:
            solutions.append(board[:])
            return


        for col in range(n):
            if col in cols or row - col in diag1 or row + col in diag2:
                continue

            cols.add(col)
            diag1.add(row - col)
            diag2.add(row + col)
            board.append(col)

            backtrack(row+1, cols, diag1, diag2,board)

            board.pop()
            cols.remove(col)
            diag1.remove(row - col)
            diag2.remove(row + col)

    backtrack(0, set(), set(), set(), [])

    return [render_board(sol,n) for sol in solutions]