Performance Analysis of the Random Algorithm for N-Queen Problem
Qin Da · Computer Knowledge and Technology · 2013
N-Queen problem is a NP problem. By the way of Random algorithm with BackTrack, the problem is solved with a good performance. The performance graph is the shap of U. While the number of random queens is in a special range that is nar row than 20, the algorithm's performance is good. With the increasing of the number of queens below 100, the best number of random queens changes slowly from n-10 to n-17. Algorithm can solve 100-Queen in common time, far larger than pure Back Track way. Because of the BackTack expenses, it is hard to reduce the total time by Optimizing the Random algorithm. As n in creases, the algorithm time increases more and more slowly.