回溯法，要利用解的对称特性来优化
#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;
}