回溯法，要利用解的對(duì)稱特性來(lái)優(yōu)化
#include?<stdio.h>
#include?<string.h>
#include?<stdlib.h>
typedef?int?bool;
#define?true?1
#define?false?0?
int?pos[13];
bool?row_status[13];
int?total?=?0;
int?n;
void?backtracing(int?depth);
void?solve()
{
#ifndef?_DEBUG
????freopen("checker.in","r",stdin);
????freopen("checker.out","w",stdout);
#endif
????memset(pos,0,sizeof(pos));?
????memset(row_status,0,sizeof(row_status));
????scanf("%d",&n);
????int?p;?
????int?t?=?n/2;
????for(p=0;p<t;++p){
????????pos[0]?=?p;
????????row_status[p]?=?true;
????????backtracing(1);
????????row_status[p]?=?false;
????}
????if(total<3){
????????for(p=t;p<n;++p){
????????????pos[0]?=?p;
????????????row_status[p]?=?true;
????????????backtracing(1);
????????????row_status[p]?=?false;
???????????}
????}else{
????????total+=total;
????????if(n%2!=0){
????????????pos[0]=t;
????????????row_status[t]?=?true;
????????????backtracing(1);
????????????row_status[t]?=?false;
????????}
????}
????printf("%d\n",total);
}
bool?isok(int?depth,int?p)
{
????int?i;
????if(row_status[p])
????????return?false;
????for(i=0;i<depth;++i){
????????if(abs(pos[i]-p)==abs(depth-i)?)
????????????return?false;
????}
????return?true;
}
void?backtracing(int?depth)
{
????if(depth==n){
???????total++;?
???????if(total<=3){
???????????int?i;
???????????for(i=0;i<n;++i){
???????????????if(i==0){
????????????????????printf("%d",pos[i]+1);
???????????????}else{
????????????????????printf("?%d",pos[i]+1);?
???????????????}
???????????}
???????????printf("\n");
???????}
????}else{
????????int?i;
????????for(i=0;i<n;++i){
????????????if(?isok(depth,i)?){
????????????????pos[depth]?=?i;
????????????????row_status[i]=true;
????????????????backtracing(depth+1);
????????????????row_status[i]=false;
????????????}
????????}
????}
}
int?main(int?argc,char?*argv[])
{
??solve();
??return?0;
}