Anyone know if there is already a comparison of this to Knuth's DLX algorithm? I see they claim this approach will be superior to any backtracking algorithm. Empirical results would be interesting.

I'm also curious how well this generalizes.

In practice I would expect Knuth's DLX algorithm to be much faster, both for generating the first solution, and for counting all solutions (for any reasonable sized N).

There are some timing results for a (well-optimized) backtracking solver here: http://www.jsomers.com/nqueen_demo/nqueens.html

N=21 takes about 600,000 seconds on an 800MHz computer, i.e. around 500.10^12 computations.

In comparison, the algorithm in the paper has a complexity higher than 8^N, which is around 9,000,000.10^12 for N=21.

The number of solutions is growing by about an order of magnitude (sequence https://oeis.org/A000170) for each increment of N.

I like that page. Well written and amusing to see how long some of these solutions took back then. Most I ever read on this problem was Knuth's Dancing Links. My small attempt at it is here: http://taeric.github.io/DancingLinks.html

I posted your page as a submission hoping to get a discussion on it. Apologies for not asking first. Please let me know if you want me to try and remove the submission.

What do you make of this paper's claim that this method is superior to backtracking methods?