- Prepare
- Algorithms
- NP Complete
- Spies, Revised
- Discussions
Spies, Revised
Spies, Revised
+ 0 comments Minimum conflict algorithm was very slow for me. But I could optimize it using intensive parallelism and an observation to count straight line conflicts.
The observation is, if and are two lattice points, then an other lattice point on the straight line would have this form,
where and .Using this would reduce number of iteration in huge factor. Parallelism helps because most of the work in each iteration is independent.
Using this, I was able to find a solution within one hour.
+ 3 comments The problem indicates that the definition of the queens seeing each other diagnonally is "lie in a line inclined 45 degrees or 135 degrees to the base of board." then the example of an invalid solution is:
7
1 3 5 7 2 4 6
This is not right. The sequence "1 3 5 7" represent a 26.565 degree line, not a 45 degree line. This is because the slope is 2 columns to each 1 row. A 45 degree line would have a slope of 1 column for each row, or a sequence like:
7
1 2 3 4 7 6 5
Please confirm that the scoring engine checks strictly for a 45 degree line, or does it check for three queens sequenced with the same slope line? If it shecks for the same slope line, does that imply the following sequence is also wrong:
7
1 4 7 2 5 3 6
??
+ 2 comments I wrote a quick hill-climber and can get solutions for any size relatively quickly. However, I seem to missing something very very simple. I'm messing up on how to submit these.
I even tried submitting the example solution and it is judged incorrect. In other words, this doesn't work.
print "13"
print "1 3 12 10 7 2 11 5 8 13 9 4 6"What am I missing?
+ 1 comment This solution is not accepted:
9 5 2 4 9 7 3 1 6 8
Corresponding board is:
* * * * S * * * * * S * * * * * * * * * * S * * * * * * * * * * * * * S * * * * * * S * * * * S * * * * * * S * * * * * * * * * * * * * S * * * * * * * * * * S *
I dont see why?
+ 2 comments I contacted support about this, will update when I hear back.
Anyone see the problem? Looks good to me. All my solutions are being rejected and I can't find a problem with any of them.
S * * * * * * * * * * * * S * * * * * * * * * * * * * * S * * * * * S * * * * * * * * * * * * S * * * * * * * * * * * S * * S * * * * * * * * * * * * S * * * * * S * * * * * * * * * * * * * * S * * * 10 1 4 9 5 8 10 3 6 2 7
Sort 97 Discussions, By:
Please Login in order to post a comment