All N-Rooks algorithm and a linear time N-Queens solution | Hacker News Reader

All N-Rooks algorithm and a linear time N-Queens solution

logicmason.com

23 pointsxiaoma16 comments

The n-queens solution? Errr....no. Here is an even faster way of solving n-queens, in the spirit of the posting:

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.

I think you are missing the point.

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.

Author here:

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.

http://oeis.org/A000170 hints that there is no such algorithm:

"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)

Real programmers implement Knuth's dancing links (http://arxiv.org/pdf/cs.DS/0011047.pdf) and use it to solve a way larger class of problems.

Polynomial time with respect to what? The number of possible solutions grows exponentially with respect to the board size.

http://en.wikipedia.org/wiki/Exact_cover

Well that's misleading. You might as well have precomputed it and claimed you can retrieve it in O(1).

No fair precomputing with bounds known in advance on N.

> While, I haven’t found a similar recursive solution for N-Queens, I know there’s a polynomial solution out there.

How do you know that?

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)

Also: "Explicit solutions to the N-queens problem for all N": http://dl.acm.org/citation.cfm?id=122322 (paywalled)

Haskell code for a (that?) closed-form solution: https://gist.github.com/IanCal/1858601

Reply on news.ycombinator.com