More Queens, More Random

Lets dig into this n-queens problem more deeply. What would it be when n is getting very large?

In last entry, a poly-algo is used for n sized up about to 300. That code is O(n^2) time complexity. Now lets imagine n can be very large, like 10,000, 100,000 or even 1,000,000. The algo would not scale very well.

The same author of the last paper proposed an almost-linear algorithm. Here is the resulting code adapted. As you can see, the content has not changed much from last code. The main difference is, in the old code we systematically check each and every pair of queens whereas in the new code pairs are chosen rather randomly. But the result changes dramatically.

Talk is cheap; show me the numbers!

$ time (echo 1; echo 30000) |./old >/dev/null

real    1m11.808s
user    1m8.447s
sys     0m0.579s

$ time (echo 1; echo 30000) |./new >/dev/null

real    0m0.436s
user    0m0.422s
sys     0m0.004s

And lets run an extreme case: 1,000,000. The old code may take way too long. But the new code:

$ time (echo 1; echo 1000000) |./new >/dev/null

real    0m31.707s
user    0m30.089s
sys     0m0.300s

Way kool.