Wednesday, June 09, 2004

N-queens solution

Have you'll heard about the 8-queens problem, I think most CS guys are familiar with it. I was generally trying to brush up with C++, so I thought I'd try to generate the solutions to the 8-queens problem (there are 92 of them). Then I thought if I'm going for a solver might as well make it a generic one and so I wrote the following code to solve n-queens for any given n.

The source code can be found here : Windows & Linux

It was really a lot of fun!! For 8 queens, I got the execution time down from 435 seconds to 213 seconds to 20 seconds!!!

As far as I know, the code will generate solutions for any n, considering some critical resource doesn't get exhausted. I tested it for 9 queens which has 352 solutions, it generated all 352 of them! So it should work!!

Dinesh.

No comments: