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 indicating view it at South. Respectively label North, East and West on the chess board like map. Then we have solutions: 6304125 E; 4152630 W; 4205316 N and solutions generated 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∩o≠{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 contradicting 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 equal to an element c in o. Then using symmetry 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<class T>
struct output_reverse_functor : public unary_function<T,void>
{
output_reverse_functor(int d_less_one):n(0),dim(d_less_one){}
void operator()(const T& p)
{
cout<<"("<<n<<","<<dim-p<<")"<<" ";
n++;
}
int n,dim;
};
template<bool with_output>
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<int>());
cout<<endl;
for_each(array.begin(), array.end(), output_reverse_functor<int>(n-1));
cout<<endl;
}
else
{
number_solution+=2;
}
}
......
};
template<bool T>
void BackTracking(chess_board_delegation<T>& c)
{
......
for(int j=0; j<c.n; 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 queen problem. That is, be a classical algorithm, this should be almost fastest and it still has room for structure optimization of this algorithm.
How to utilize the “1 generates others