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:

  1. 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.
  2. 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

In reply to Re: Efficient N-Queen solution with Perl by FoxtrotUniform
in thread Efficient N-Queen solution with Perl by lestrrat

Title:
Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post, it's "PerlMonks-approved HTML":


  • Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!
  • Titles consisting of a single word are discouraged, and in most cases are disallowed outright.
  • Read Where should I post X? if you're not absolutely sure you're posting in the right place.
  • Please read these before you post! —
  • Posts may use any of the Perl Monks Approved HTML tags:
    a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, details, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, summary, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr
  • You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)
            For:     Use:
    & &amp;
    < &lt;
    > &gt;
    [ &#91;
    ] &#93;
  • Link using PerlMonks shortcuts! What shortcuts can I use for linking?
  • See Writeup Formatting Tips and other pages linked from there for more info.