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.