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.
I'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.