2
$\begingroup$

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,

  1. Generate a random permutation of [1..n].
  2. Store "swaps" as "moves" such that it reduces number of conflicts.
  3. Pick a "move" with non-uniform distribution on number of reduced conflicts and swap.
  4. 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.

$\endgroup$
  • 1
    $\begingroup$ This reminds me of simulated annealing, a little bit. $\endgroup$ – Auberon Oct 12 '16 at 12:48
  • $\begingroup$ How hard is this problem? (is it NP-hard?) $\endgroup$ – Auberon Oct 12 '16 at 12:56
  • 1
    $\begingroup$ Yea. I am going to apply simulated annealing. But I want to reduce the running time to find the costs for each move at each iterations before implementing SA. And the problem is NP-complete I think since the problem is featured in Hackerrank in NP-complete section. $\endgroup$ – rnbguy Oct 12 '16 at 13:17
  • $\begingroup$ You could, instead of computing the increase/decrease of conflicts of each move from the current solution and then deciding which you will accept as your next solution, go over your moves one by one and decide at that moment stochastically if you will accept that move or if you will compute the next move (as is done most of the times in SA). $\endgroup$ – Auberon Oct 12 '16 at 18:04
  • $\begingroup$ ah okay. I will implement that and post a follow up here. thanks $\endgroup$ – rnbguy Oct 12 '16 at 18:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.