Alecs' Blog Did you ever go clear..

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.

05 Apr 2006

Fork me on GitHub