[Java] N queens

Given a NxN board and N queens, count how many placements exist where no queen blocks another.

This is an extension of a problem known as eight queens, which feels like dynamic programming, but is slightly different from the usual approach of finding a recursion, then caching.

The reason is that the solutions are NOT incremental. Finding a solution for a smaller N is NOT expanded to a bigger N, therefore we can't reuse already computed work. And usually when we do DP, we cache something, but in this case there is no possibility.

A key insight in solving the problem efficiently comes from trying the problem on paper: each row can't contain more than one queen.

Seems obvious but the implication is clear, assuming we'd like to place a queen in a certain cell in a given row, we must inspect lower rows to determine whether that leads to a solution AND we must inspect previous rows to verify no already placed queen blocks us on our column or either diagonal.

This also means, the main loop is NOT a loop on both rows and columns, rather it's a loop on columns which then recursively calls the same code on the next row.

We also keep a global counter that we increase only when we managed to place the last queen successfully.

Once we have explored what happens when placing a queen in a specific cell, we remove the queen from there, and try placing it on another cell on the same row, then repeat the process.

In the end, we will have explored all possibilities.

This leads to a O(N^2) space complexity and with regards to time we have to do some analysis.

For each column (N) we execute the following (summed, not multiplied):

- check valid placement: three subsequent loops on one dimension only (previous rows, two diagonals going from cell to top left and top right), so total is O(N)

- recurse on next row (N) ONLY if placement is valid

And since we have N rows, we would repeat this N times. Worst case we would be doing Nx(NxN-1) work assuming for each cell in the first row, we evaluate the whole matrix from the next row onward.

However, the key point justifying why complexity is different is that we do NOT recurse unless placement is valid. The check of valid placement costs O(N) and is repeated for each column so a total would be O(N^2) and that is repeated for each row along with the main recursion.

This means, recursion only happens when the queen we'd like to evaluate is in a valid position. For N queens there are only X such possibilities, which would be our upper bound. Definitely it is NOT O(N!)

For example counting how many times we invoke our recursion (enter the recursive function) with my code, I got:

17 times for N = 4 - factorial is 24

54 times for N = 5 - factorial is 120

which is not factorial but also I am not sure about what exactly it is.

According to the book "Elements of programming interviews in Java" page 287, it seems this approach gives a O(N! / (c^N)) without a clear explanation though:

The time complexity is lower bounded by the number of nonattacking placements.
No exact form is known for this quantity as a function of n, but it is conjectured to
tend to n!/c^n, where c is about 2.54, which is super-exponential.

You can check my implementation of nQueens on my Gist along with some tests in NQueensJTests.