OP presented a linear time algorithm. You did not. The point of algorithms is solving problems where the input can change - here it's n, the size of the board. Your solution, as stated, works only for a specific n. It's not an algorithm, at least by common definitions.
You could adapt the solution to handle some finite number of possible inputs with:
n_queens_answer = [ ... array of answers...]; for (int i = 0; i < n_queens_answer[n].length; i++) { place_queen(n_queens_answer[n][i]);
This is also missing the point - obviously every finite function can be written with a lookup table. The point of algorithms is solving problems with potentially infinitely many possible inputs. In fact, time complexity terms such as "linear time" usually mean asymptotic complexity, where the time for any finite number of inputs is irrelevant. Every algorithm could be said to take linear time - even constant time - if you limit allowed length of the input! That's not useful. Even though real world computers have limited memory, the asymptotic behavior, theoretically irrelevant to practice, usually agrees with reality.
In the case of n-queens, finding a pattern that solves the problem for arbitrary n does solve the puzzle. That might be disappointing or contradict intuition, but that's how computer science works. We want an asymptotically fast algorithm that outputs a correct answer, it does not matter that the answer is dull.
I put some effort into finding the linear time single N-Queen solutions. I didn't know any of them when I started. Especially the case of N mod 6 eq. 3 took some thought.
Just to make the point more clear, solutions to the N-rook problem are in bijection with permutations of n. The bijection is that each element of the permutation tells you what column that rook should go in (and it'd fairly easy to see why this works). E.g. the "trivial" solution given with rooks on the diagonal corresponds to the identity permutation (1 2 3 ... n) since that permutation puts rook i in column i.
Thanks for adding some explanation! The All N-Rooks solution was much more interesting than the single N-Queens one, but it's not as easy to understand.
I think JulianWasTaken is hinting that your solution is exactly a recursive solution to generate all permutations (google "recursively generate permutations"). This is because any N-rook solution is just a reordering of the columns of the trivial solution.
It may be interesting for you to try to come up with a different solution, where the basic operation is to swap adjacent columns - and try to minimize the number of swaps.
Yes, the solution for any N is all permutations. I realized that the morning after writing the recursive algorithm I shared. It was pretty fun trying to come up with a recursive step to generate all queens for N, given all queens for N-1. Even now I can't say for sure that no such recursive step exists.
Please note that the linear solution to N-Queens is only giving a single solution for a board.
If I remember right, there is a number of similar linear-time solutions for N-Queens that use a very simple pattern. I don't think this approach is extendable to finding all the solutions - I'm quite interested in seeing a polynomial-time algorithm that can generate all possible solutions to a board.
"Strong conjecture : there is a constant c around 2.54 such that a(n) is asymptotic to n!/c^n"
That would imply that a(n) grows faster than polynomial. That, in turn, would mean that merely counting the number of solutions cannot be done in polynomial time.
N-Queens, by the way, becomes simple once you realize that you cannot have two queens at (p,q) and (r,s) if any of the following is true:
p = r
q = s
p-q = r-s
p+q = r+s
(The first two check for horizontal and vertical attacks, last two for diagonal ones)
I saw some research talking about polynomial complexity for N-Queens come up in a google search. If someone has published a paper about a problem like this generally means that the time-complexity they're writing about doable but very hard.
I didn't click any of the links though, since I wanted to keep working the problem.
"A polynomial time algorithm for the N-Queens problem": http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.57.4... (haven't completely read it, but I think they waive their hands too much when argumenting that their algorithm will not get stuck too often)
n_queens_answer = [ ... array of answers...]; for (int i = 0; i < n_queens_answer.length; i++) { place_queen(n_queens_answer[i]);
See what I did there? Wow! Totally linear time in the number of queens!
Remarkably, when you already know the answer to a problem, it is generally not difficult to solve it quickly.
Replicating an observed pattern is not the same as solving a problem.