On Aug 31st 2017. Clay Math Institute and St. Andrews have released an N-Queens Completion $1m challenge.
If the Chess Board size is NxN. and M
I have written the completion algorithm which is of the O(N * (N-M)^2 * Parallelization Constant)
The problem I'm facing is not with the algorithm per se. We consider that more or less proven i.e. P = NP, Polynomial Time.
But everytime I use some adhoc algorithm to place M queens on a NxN partial Board. The completion algorithm rejects it "Inconsistent partial board" and aborts.
The challenge says the algorithm should work on 1024x1024 boards. Which it does. But just because it solves a couple of 1024x1024 adhoc boards doesn't prove anything about the worst case scenario.
For us to claim to the world that we have a solution. We are targeting testing on atleast 1000, 1024x1024 partial boards before making an announcement of the result.
So the question is - How do we generate "randomized" "adhoc" partial NxN boards with M < N queens placed on it. to test the N-Queens completion solution.What set of partial boards will qualify as a good enough test of the solution?
Please let me know, if you need any other details.