8^HN Queens Revisited

I once wrote a blog entry about 8 queens problem using backtrack. Backtrack is good for small n generating all solutions for n-queens problem. But what if the n is getting large? It performs very bad, since it runs exponentially (try n = 27 for this code).

Here is an interesting problem Who needs 8 Queens when you can have N. Note that we are to find one solution that satisfies the no-attacks requirements, not all the solutions as a backtrack does.

Dont panic. Read this paper: A Polynomial Time Algorithm for the N-Queens Problem. Oh dude, it is AMAZING (read: power of algorithms). In short, it utilizes a randomized approach with gradient-based heuristic local search. For a random permutation, swap where there is a reduction of attacking-conflicts. Besides, there are also other good (small) tips. It really broadened my algo knowledge base and it's not only for this particular n-queens problem but can be generalized for other searching problems. Kool.

Here is the final implementaion according to this paper. It runs very fast.