How to get the queens problem to be solven even faster?

Question

I am trying http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&category=315&problem=2136 but I'm running in to the problem of my program not being fast enough, I am timing it on my own computer by letting it count how many possibilities there are without restrictions and my program is able to calculate it within 5 seconds for up to 14, with 15 it's about 25 seconds..

I'm keeping track of which diagonals, columns and rows are taken using an array so calculating whether as position is taken takes linear time, I'm using backtracking per column like has been explained so I'm kind of running out of ideas, does anyone have a hint they can give me?

Answer 1

Same problem here. First optimalization for me was to just place one queen per column. Second was to keep track of which rows and which 'diagonal rows' were already used, where the coordinate of the first diagonal row is calculated with x+y, the second with x-y.

Answer 2

I had this problem too and used the same technique. After using bits in an integer (with binary operators), instead of a boolean array, my program finished in time (about 4.8 seconds).

But I'm interested how people managed to solve it in less then a second. I think they do something like pre-generating, but I'm not sure about that.