What is the best Algorithm to find all solutions to n queens problem?

Question

You may know n queens problem but I would explain it a little.

I want to put n queen on n*n chessboard in the order that none of them can attack each other from columns , rows and diagnals.

I want to find how many answers does this question have for n*n chessboard (It is not limited to 8*8).

I want to find all solutions not just unique solutions( I think it will make algorithm more easier!).

Best means the fastest. Isn't it obvious?!

Answer 1

The key is to use backtracking. I'm not sure what language you are writing this in, but the solution in ML is very elegant. Basically, you know you will have one queen in each row, so it is a matter of finding which column each queen should be in. Place the first queen in the first possible place, then try placing the second queen in the second row. If there is no way for the second queen to be placed without being threatened by the first one, you need to go back and move the first queen to its next possible spot, then move on to the second queen again. If this is done repeatedly, a solution will be found if one exists. If you want to find all solutions, instead of stopping when one solution was found, instead add this solution to a list, and then continue as if that solution didn't work (i.e. go back and keep trying the previous queen in the next position). Hope this helps.

Answer 2

There's that word "best" again... on what basis would you like it measured? Speed would be the obvious measure - but some would say that an elegant solution would be better than a fast solution...

"Best" without criteria is simply a point of view - an opinion.

Rawlyn.

Answer 3

http://www.math.utah.edu/~alfeld/queens/queens.html
check out this page...maybe it could help