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.

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:

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.

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.

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.