### 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