An AI course that I took a couple years ago had a
"fastest N-queens solver" competition as one of the
assignments. I took a look around the net and found
some papers on N-queens solutions... the best one I
found was O(n), on average. IIRC, it had two steps:
- From left to right, place queens randomly on the
columns. Keep trying to place a given queen until
you don't have any conflicts. Do this about 2n times.
- Pick two queens that have conflicts, and swap their
columns. (There were a bunch of heuristics here for
picking the "right" queens -- IIRC, I ignored them.)
This is, apparently, O(n) in the average case. The proof
was a bit too hairy for me to really follow, though.
(For the record, this solution took third place.) The
two fastest n-queens solvers were analytic: rather than
optimizing a board until finding a solution, they just
calculated where to place each queen. Sounds cool, but I
could never find any information on their solutions.
The point is, if your algorithm is faster (better time
complexity) than his, it doesn't matter if you write it in
QBasic and he uses hand-tuned assembly... just crank up N
until your curve beats his. Fast algorithms are the best
kind of optimization, whether you write them in baby-Perl
or golf-Perl.
--
:wq