アルゴリズムの経典の検索の問題--8皇后

八皇后の問題を紹介する前にdfsについて話しましょう.
DFS–深度優先検索
まず私のdfsピット問題を見てみましょう:指数型列挙

#include

using namespace std;

int n;

void dfs(int k,int choose)
{
     
    if(k==n)
    {
     
        for(int i=0;i<n;i++)
        {
     
            if(choose>>i&1) cout<<i+1<<" ";
        }
        puts("");
        return;
    }
    dfs(k+1,choose);//  
    dfs(k+1,choose|(1<<k));// 
}
int main(){
     
    freopen("data.in","r",stdin);
    freopen("data.out","w",stdout);
    cin>>n;
    dfs(0,0);


    return 0;
}
//  ：3
//  ：

//3 
//2 
//2 3 
//1 
//1 3 
//1 2 
//1 2 3 

この問題は古典的で、dfsが私たちにすべての決定(選択または選択しない)を暴力的に列挙することができることを見ることができます.もしあなたがこの問題を理解することができたら、おめでとうございます.あなたはdfsを入門しました.データ量が小さい場合、暴力dfsは間違いなく非常に優れた選択です.次は8皇后の問題のコードを直接提供します.

#include

using namespace std;

int queen[8][8];//                  ，           
int res=0;
void copy(int a[8][8],int b[8][8])
{
     
    for(int i=0;i<8;i++)
        for(int j=0;j<8;j++)
            a[i][j]=b[i][j];

}

void work(int a,int b)//  a b 
{
     
    for(int i=0;i<8;i++)
        queen[a][i]=1;
    for(int i=0;i<8;i++)
        queen[i][b]=1;
    //      ，             
    //      
    int d=a-b;
    int i=a-b,j=0;
    while(i<8&&j<8)
    {
     
        if(i>=0&&j>=0)
            queen[i][j]=1;
        i++;
        j++;
    }
    //  
    d=a+b;
    i=a+b,j=0;
    while(i>=0&&j<8)
    {
     
        if(i<8&&j>=0)
            queen[i][j]=1;
        i--;
        j++;
    }
}
void dfs(int k)
{
     
    if(k==8)
    {
     
        res++;
        return;
    }
    int i=k;
    int g[8][8];//                 
    copy(g,queen);
    for(int j=0;j<8;j++)
    {
     
        if(!queen[i][j])
        {
     
            work(i,j);
            dfs(i+1);
            copy(queen,g);//    
        }
    }
}
int main(){
     
    freopen("data.in","r",stdin);
    freopen("data.out","w",stdout);
    dfs(0);
    cout<<res<<endl;
    return 0;
}

八皇后問題の時道は非常に古典的なdfs問題で、前の問題と同じように私たちがすべての決定を列挙すればいいです.これとは異なり、各行を分析するのは簡単です.(列)あっても皇后が1人しかいないので、それと合わなければだめです.その上でdfsは効率が高すぎます.実はこの方法は枝切りとも呼ばれますが、私たちが今日議論した重点ではありません.私たちは決定をシミュレートした後、コードを書くことができます.ツールの配列は必ず関数の中に置くことを忘れないでください.それから、対角線に注意してください.これらに注意してください.この問題は簡単に解けると思います.