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.
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).
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.
4 comments
[ 3.0 ms ] story [ 16.8 ms ] threadI'm also curious how well this generalizes.
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 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.