5
$\begingroup$

Problem:

I am trying to solve the $N$-Queens problem using Constraint Satisfaction and Heuristic Repair (also known as Min-Conflicts). I wrote a program to do this for any given $N$ queens and $N * N$ board.

I observed that a solution should be found in $N$ passes or less (since we need to find $N$ non-conflicting locations, for which we might need to rearrange all queens at most $N$ times in one pass).

I noticed that, given a random start, some starting states would not be able to resolve to a solution. This was due to circular behaviour where two or three queens would alternate positions, always moving to positions where:

$$conflict(new-pos) \le conflict(old-pos)$$

but never decreasing global conflicts.

The presence of these states seems to increase as $N$ increases. So 64-queens seems more likely to have "cycles" than 4-queens (which never seems to have cycles).

I would like to know how I can reason about these difficult states, and what extension of the algorithm could be made such that the algorithm will always obtain a solution, provided one exists?

What I have tried so far:

  • I have tried to randomise the board state after $N$ unsuccessful passes. This probably guarantees an eventual solution, but does not solve the fact that the likelihood of these states seems to increase exponentially, and so a solution becomes intractable quickly.

For those interested you can find my program here. It is not fantastically documented, but it is not terribly long, and I believe most of the names are self-documenting.

$\endgroup$

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.