I have tried to utilizing the "1 generates others
7 "characteristic of n queen problem. Finally, I found that it must have the knowledge of relationship between n and numbers of solutions. The program runs as the manner of generate all relative solutions of one solution that has been found by backtracking, this backtracking will terminated when one solution has been found. Using this solution to generating others solutions that is relative. The method to generating all relative solutions is easy, but difficult in terminate the loop because it is hard to know the relationship between n and numbers of all solutions. More important, it is very difficult to proving the correctness of this method. that is, it is unclear that whether or not all solutions will be found even the relationship is known (for the sake of "propagation" of solutions). It Seems induction is a good idea, but I think induction can not begin rect for n queens. How? The general method is converting it to numbers and deals it with algebra. Apparently, convert the intrinsic meaning of n queen problem to numbers is very hard and it seems that n queen problem can be solved directly when the converting Method Is KNown (FA CAN Be Applied).
Following is the codes, and there is another problem in this method:. How to choose the "target" solution to generating others 7 solutions If all solutions in charge of the "target", the speed of this algorithm will be considerable slow (remind the number of solutions relating to n). In addition, a special data structure is required to storing solutions and support mechanism for finding. I use a three dimension array (vector_instance [i] stores all solutions (column number form) beginning with i, Vector_instance [i] [j] stores one solution, vector_instance [i] [j] [k] is the element of a solution), But I think l b ketter.four functors to Convert The Directions, SE Means Convert South Direction To East Direction.
The PrinciPle IS: S (x, y) n (x, y) == (n, n); e (x, y) w (x, y) == (n, n); s (x, y) == e (y, nx).
Template
Struct functor_se: public unary_function
{
Functor_se (INT D): array_dim (d-1) {}
Void Operator () (T & P)
{
SWAP (P.First, P.second);
p. Second = array_dim-p.second;
}
Int Array_dim;
}
Template
Struct Functor_ew: Public Unary_Function
{
Functor_EW (INT D): Array_dim (D-1) {}
Void Operator () (T & P)
{
P.First = array_dim-p.first;
p. Second = array_dim-p.second;
}
Int Array_dim;
}
Template
Struct functor_wn: public unary_function
{
Functor_wn (INT D): array_dim (d-1) {}
Void Operator () (T & P)
{
SWAP (P.First, P.second);
P.First = array_dim-p.first;
}
Int Array_dim;
}
THESE FORR FUNCTORS HAVEEN Used in for_each to modify a Vector That Contains Pairs of chesses. The Others Codes have been omitted.
