八皇後問題(DFS)

 例題1：百練 2754

描述

會下國際象棋的人都很清楚：皇後可以在橫、豎、斜線上不限步數地吃掉其他棋子。如何将8個皇後放在棋盤上（有8 * 8個方格），使它們誰也不能被吃掉！這就是著名的八皇後問題。對于某個滿足要求的8皇後的擺放方法，定義一個皇後串a與之對應，即a=b1b2...b8，其中bi為相應擺法中第i行皇後所處的列數。已經知道8皇後問題一共有92組解（即92個不同的皇後串）。給出一個數b，要求輸出第b個串。串的比較是這樣的：皇後串x置于皇後串y之前，當且僅當将x視為整數時比y小。

輸入

第1行是測試資料的組數n，後面跟着n行輸入。每組測試資料占1行，包括一個正整數b(1 <= b <= 92)

輸出

輸出有n行，每行輸出對應一個輸入。輸出應是一個正整數，是對應于b的皇後串。

樣例輸入

2
1
92
      

樣例輸出

15863724
84136275      

分析：主要是滿足條件分析：

其中A[cur]==A[j]是判斷皇後是否會縱向攻擊：

其中cur-A[cur]==j-A[j]||cur+A[cur]==j+A[j]語句的意思是：皇後(cur,A[cur])和皇後(j,A[j])是否在同一對角線上：

判斷的原理如圖所示：

1	2	3	4	5	6	7
-1	1	2	3	4	5	6
-2	-1	1	2	3	4	5
-3	-2	-1	1	2	3	4
-4	-3	-2	-1	1	2	3
-5	-4	-3	-2	-1	1	2
-6	-5	-4	-3	-2	-1	1
-7	-6	-5	-4	-3	-2	-1

(a) 格子（x,y）的y-x值标志了主對角線

1	2	3	4	5	6	7
1	2	3	4	5	6	7	8
2	3	4	5	6	7	8	9
3	4	5	6	7	8	9	10
4	5	6	7	8	9	10	11
5	6	7	8	9	10	11	12
6	7	8	9	10	11	12	13
7	8	9	10	11	12	13	14

 (b)格子（x,y）的y+x值标志了副對角線

用x表示行，y表示列，則有x1=cur,y1=A[cur]：X2=j;y2=A[j];

根據圖中的數值關系，可知在同一主對角線滿足：cur-A[cur]==j-A[j]；在同一副對角線滿足：cur+A[cur]==j+A[j]

#include<iostream>
using namespace std;
int A[10],num=1,B[100][10];
int DFS(int cur)
{   if(cur==8)
    {  for(int i=0;i<8;i++)  
         B[num][i]=A[i];
       num++;
    }
    else 
    for(int i=0;i<8;i++)
    {  int flag=1;
       A[cur]=i+1;
       for(int j=0;j<cur;j++)
         if(A[cur]==A[j]||cur-A[cur]==j-A[j]||cur+A[cur]==j+A[j]) {flag=0;break;} 
       if(flag) DFS(cur+1);
    }
}
int main()
{   int n,m;
    cin>>n;
    DFS(0);
    while(n--)
    {  cin>>m;
       for(int i=0;i<8;i++)
         cout<<B[m][i];
       cout<<endl;
    } 
    return 0;
}
           

題2：Tyvj 1080(N皇後)，需要剪枝利用use[2][]直接判斷目前的皇後所在列和兩個對角線是否有其他的皇後，注意主對角線标志y-x可能為負，是以存儲的時候要+n。

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int MAX=15;
#define CLR(arr,val) memset(arr,val,sizeof(arr))
int n,sum,A[MAX],use[MAX][2*MAX];
void DFS(int cur)
{   if(cur==n)
    {   sum++;
        if(sum<=3)
        {   for(int i=0;i<n;i++)
                printf("%d ",A[i]);
            printf("\n");    
        }
    }
    else
    {   for(int i=0;i<n;i++)
            if(!use[0][i]&&!use[1][cur+i]&&!use[2][cur-i+n])//use[0][i]判讀目前皇後所在列是否存在其它皇後
            {   A[cur]=i+1;
                use[0][i]=use[1][cur+i]=use[2][cur-i+n]=1; //used[1][cur+i]為副對角線
                DFS(cur+1);  
                use[0][i]=use[1][cur+i]=use[2][cur-i+n]=0; //use[2][cur-i+n]為主對角線 
            }
    }
}
int main()
{   while(scanf("%d",&n)!=EOF)
    {   sum=0;
        DFS(0);
        CLR(use,0);
        printf("%d\n",sum);
    }
    return 0;
}