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.