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.