Given a solution and image the chess board is transparent. Another solution can be got immediately by turn this chess board (left-right turn). That is, look the solution from other side of chess board. It can be implementing in the manner of computing haft solutions and store these solution in a container in the algorithm. to output all solutions, just output all solutions in container and output others by reversely access the container elements. But things will not so easy. in fact it is almost impossible to utilize this feature when I found that the symmetry solutions generated from one solution can be eight at most and the distribution of symmetry solutions is not regular. For example, 7 queen problem, 0531642 is a solution and because chess board can be viewed from four directions. SO Label This Solution with South. RespectiveLabel North, East and West On The Cones Board Like Map. The inside.................... enerated by reverse above four solutions: 2461350 RS; 5214036 RE; 0362514 RW; 6135024 RN Although these 8 solutions are distinct, not all solutions generated with this method will be distinct For example, 4 queen problem, there are only 2 solutions for.. It. apparently, utilizing feature of n Queen Problem To Generating Solutions Has Repetition.
The method of avoid repetitions is to storing all generated solutions and checking whether a given solution is a repetition or not. Because the number of solutions is huge, so store it and find a key in it is inefficient. But it is not the most important problem when I thinking how to terminate the recurrence that is exploring chess board to generating a repeated solution. I think it is impossible because it is difficult to known relation of two consecutive solutions. In backtracking algorithm, to utilizing this feature completely is impossible. But then it is still possible to utilizing feature of left-right symmetry. That is, if a solution is found, use symmetry can generate another solution. Implementing this by limiting the j from 0 to ceiling (n / 2) in situation of cur_i = = 0. Note That IT HAS NOT Repetitions Even N Is Odd.i Prove IT by ContraDiction: Let Set O {...} INDICATE SOLUTIONS COMPUTED by limiting J; set s {...} indicate Symmetry Solutions Of O {...}. Apparently Elements in O {...} can NOT Be duplicated, so assuming:
1) s Has duplicated elements;
2) S∩ ≠ {EMPTY}.
For situation 1): because the relation of elements in o and s is one map to one Using symmetry feature to mapping two duplicated elements to set o respectively It is conclude that o has two duplicated elements obtained from set s by symmetry That... Is ContraDreating with condition, so this situation is eliminated.
For Situation 2): Consider a Solution IN o Denoted by a, it's symmetry in s Denoted by b. If b is equmetry on c to getting d in s. Note That D == a Because Equivalence of B and C. (i use b (c) to Denoting B and C Is Equivalence) At here, o = {... a, c ...}, s = {... b, a (d) ...}. Appling Symmetry Again ON A (D) TO Getting B (e) in set o. Then O = {... a, c, b (e) ...}, Because B And C Is Equivalence, O Has Duplicated Elements, That's ContraDict with assumption. so Proving is accomplished.to Output The Symmetry Solution Just Needs to Subtract Each Number By N-1.
The Codes:
Template
Struct Output_reverse_functor: public unary_function
{
Output_reverse_functor (int d_less_one): n (0), DIM (D_SS_ONE) {}
Void Operator () (Const T & P)
{
COUT << "(" << n << "," << DIM-P << ")" << "
N ;
}
INT N, DIM;
}
Template
Class Chess_Board
{
......
INT CEILING_N;
Chess_Board (): ... // Constructor
{
...
IF (N% 2 == 0) // Even
CEILING_N = N / 2-1; // Subtract 1 To Fit Array Index
Else
CEILING_N = N / 2; // Subtract 1 To Fit Array Index
...
}
Void write ()
{
IF (with_output == true)
{
NUMBER_SOLUTION = 2;
FOR_EACH (Array.begin (), Array.end (), Output_functor
Cout << Endl;
FOR_EACH (Array.begin (), Array.end (), Output_reverse_functor
Cout << Endl;
}
Else
{
NUMBER_SOLUTION = 2;
}
}
......
}
Template
Void BackTracking (Chess_Board_delegation
{
......
For (int J = 0; j { IF (c.cur_i == 0 && j> c.ceiling_n) Return; IF (c.legal_pos (j) == false) ...... } Till now, performance has been improved double times. I believe this is almost fastest backtracking algorithm for n queen problem. Of course performance still can be improved further. But it can not be a large factor unless there is new discovery in number theory about n .. How to utilize the "1 generates Others 7 "feature in algorithm? It can be utilized in non backtracking algorithm. If the" propagation "of solutions can reach to all solutions, that is, it can generate all solutions by a given solution, this method is self-contained. Or else IT HAS TO RETURN TO The BackTracking Form IMPLENTATION. BECAUSE IT IS Unclear WHETHER OR Not All Solutions HAS been generated.
