题目链接：

 

这题就是搜索递归dfs+回溯更新，有多个标记数组。

难点在于：怎样标记（列标记还好，对角线标记麻烦！），是关键。

注意怎样标记需要必须想出这个规律：主对角线相减为定值（相减可能为负数，所以统一加n不影响结果）,次对角线相加为定值。到这题目就做出来了。

题目跟全排列比较像，属于一类题。

1 #include 
     
       2 #include 
      
        3 #include 
       
         4 #include 
        
          5 #include 
         
           6 using namespace std; 7 typedef long long ll; 8 typedef unsigned long long ull; 9 const int maxn=1e3+5;10 const int inf=1e9;11 int ans[maxn];12 int vis[3][maxn];//vis[0][maxn]存列,vis[1][maxn]存左下到右上对角线,vis[2][maxn]存右下到左上对角线13 int n,cnt;14 15 void so(int i)//i第几行16 {17     if(i>n)//递归出口,序列已经排好18     {19         cnt++;20         if(cnt<=3)21         {22             for(int k=1;k<=n-1;k++) cout<
          
           <<' ';23 cout<
           
            <
            
             >n;52 53 so(1);54 55 cout<
             
              <
             
            
           
          
         
        
       
      
     

再附个全排列代码

全排列很简单，就是从小到大所有情况都来一遍，以3为例跟一遍代码就明白

1 #include 
     
       2 #include 
      
        3 #include 
       
         4 #include 
        
          5 #include 
         
           6 using namespace std; 7 typedef long long ll; 8 typedef unsigned long long ull; 9 const int maxn=1e3+5;10 const int inf=1e9;11 int ans[maxn];12 int vis[maxn];//标记数组13 int n,cnt;14 15 void so(int k)16 {17     if(k>n)18     {19         for(int i=1;i<=n-1;i++) cout<
          
           <<' ';20 cout<
           
            <
            
             >n;44 45 so(1);46 47 return 0;48 }
            
           
          
         
        
       
      
     

 

完。