The article is about the design of algorithm for n queen problem. The intention of this article is from an excise of an algorithm book: <<Introduction to the design and analysis of algorithms>>. This backtracking algorithm is interesting, so I decide to record the process of implementation. First, I use a double dimension array to simulate the chess board. But quickly I have found this form of representation is not so convenient especially in the check function that is used to checking whether or not current solution is promising. Because the check function is worked with the index of array, the value of array is trivial. i.e. a[0][0] = 1 represent (0,0) position of chess board has a chess and the next chess can't be position (0,1) and (0,0). So I have changed a representation of chess position by vector<pair<int,int> >. Apparently, pair<int, int> stands for (x,y). Notice that a solution of n queen require each row is different. That is, for a solution of n queen, each of pair_instance.first must distinct. This simplifies the representation further. It just needs a vector<int> to represent a chess board. So the solution of n queen problem can be viewed as a permutation of natural number from 0 to n-1. Apparently, the brute-force algorithm has efficiency 
|
本类阅读TOP10