Finally we will start the recursion with the board and an empty res
result list. res
will be the answer of our problem, so we can directly return it.
This is the most well-known algorithm for solving N-Queen problem. The time complexity is O(n^2)
because we are selecting if we can put or not put a Queen at that place. The space is the board size times the result. Note that, even though it seems that the time complexity is huge, it is actually not. The maximum value of n
will be only 100
.