N queen problem for n=999

I am just trying to solve a question on http://www.interviewstreet.com/challenges it about solving n queen problem for atmost n=999…and display one of the valid solutions… for example for 4-queen problem solution would be 2 4 1 3…

i tried solving it using various approaches but could not go further than n=21…

http://www.cl.cam.ac.uk/~mr10/backtrk.pdf i tried this approach too but it is taking sufficiently large amount of time…

can any one help me with this or atleast give me any idea?

2 Likes

You could do a variation on Jeff Somers’s n queens solution which can be found here. This is a heavily optimised backtracking algorithm which as far as I know is the fastest available. You would just need to tweak it to terminate after finding one solution rather than after finding all the solutions.
Just an idea, hope it helps. Be warned though the code is difficult to understand.

2 Likes

@betlista can you help?

1 Like

@ricola86 I will surely try it out… Thanks Man … I didn’t know about this algorithm :slight_smile:

1 Like