0. Problem

To get all the solutions, we should start with an empty board and add more queens wherever we can. We can only have 1 queen per row, so an efficient method is to place them row-by-row:

To solve the problem, we'll just consider placing a queen in every possible column given the row that we're on. Our function needs to keep track of the current configuration of the board, and what row it's on.

visitAll(board, row)

1. Recursion

The function should consider adding a queen to each possible square on this row. And then it should do the same thing on the next row. Here's pseudocode:

visitAll(board, row) = (
    for queen in (all allowed positions in the current row):
        visitAll(board + queen, row + 1)
)

2. Base case

Eventually the function will go past the last row on the board. At that point we've placed all $\small\texttt{n}$ queens, so we should add the board to our solutions.

if row == n:
    solns.append(board)
    return

3. Code

Here's the full code. Just combine the recursion and the base case, and optimize by using Backtracking, which just means we make all our parameters into global variables.

def solveNQueens(n):
    # global parameters
    # `cols`, `ldiags`, and `rdiags` are just parameters that help for faster lookups
    board = set() # queen locations in (row, col) form
    row = 0
    cols = set() # |     occupied columns
    ldiags = set() # /   occupied left diagonals:  row + col
    rdiags = set() # \   occupied right diagonals: row - col

    solns = []
    
    
    def visitAll():
        nonlocal row

        # base case
        if row == n:
            solns.append([[1 if (row,col) in board else 0 for col in range(n)] for row in range(n)])
            return

        # recursion
        for col in range(n): 
            if not(col in cols or row+col in ldiags or row-col in rdiags): 
                board.add((row,col))
                cols.add(col) 
                ldiags.add(row+col) 
                rdiags.add(row-col)
                row += 1

                visitAll()

                row -= 1
                rdiags.remove(row-col)
                ldiags.remove(row+col)
                cols.remove(col)
                board.remove((row,col))
    visitAll()
    return solns

Time Complexity $O(n^n)$. We just iterated through every possible board we might consider. There are $n$ queens and roughly $n$ positions we consider for each queen, which is roughly $n^n$ boards total.

Space Complexity $O(n^n)$. The returned array has $n^n$ boards in it (a very rough estimate), and each board takes up $n^2$ memory. This gives $O(n^n \cdot n^2) = O(n^n)$ memory. We also use some space for the Call Stack and the global parameters, but both are negligible compred to the final output.

Call Stack Complexity The Call Stack gets $n$ calls deep, and each call uses $O(1)$ space.