I am trying to solve n-queen puzzle with an additional stronger condition that no 3 queens can be on the same line.Right now my algorithm is,Generate a random permutation of [1..n].Store swaps as moves such that it reduces number of conflicts.Pick a move with non-uniform distribution on number of reduced conflicts and swap.go back to 2 unless number of conflicts is zero.Right now, I store number of conflicts for each queen in current board. Then I compute number of conflicts for each move. For that I just have to compute the conflicts of only swapped rows. Then I pick moves with a probability biased to highest reduce in conflicts. Then again I compute number of conflicts for each queen in next board.Now computing conflicts for each position takes $O({n\choose2})$ time. So to compute for all of them takes $O(n^3)$.Also there are $O({n\choose2})$ moves. So to compute conflicts for all moves needs $O({n\choose2} * 2 * {n\choose2})$ = $O(n^4)$.So my each iteration takes $O(n^4)$ time. Is there any clever way to store the configuration in data structure such that I don't have to brute force over all queens?no 3 queens on same line means if $3$ queens are at $(q^0_r, q^0_c), (q^1_r, q^1_c), (q^2_r, q^2_c)$ then $$\frac{q^0_r-q^1_r}{q^0_c-q^1_c} \neq \frac{q^0_r-q^2_r}{q^0_c-q^2_c}$$Of course diagonal, horizontal and vertical constraints are same as before.  See also the pictures at this Stack Overflow question for additional explanation.I found this problem at Hackerrank.
n-queen puzzle with no 3 queens on same line
algorithms;constraint programming