遡及法によるN皇后問題解決C言語

問題の説明:
八皇后問題はチェスを背景にした問題である.×8のチェス盤には8人の皇后が置かれており、どの皇后も他の皇后を直接食べることができませんか?この目的を達成するために、両皇后も同じ横行、縦行、斜線にあってはならない.
遡及法:
遡及法は探査法とも呼ばれる.遡及法の基本的な方法は深さ優先探索である.つまり、一つの道を前にして、入ることができれば入るが、入ることができなければ戻ってきて、道を変えてからやってみる.
ソース:

#include
#include
int x[9]={
     0};
bool PLACE(int k)//   k         
{
    int i=1;
    while(i<k)
    {
        if(x[i]==x[k]||fabs(x[i]-x[k])==fabs(i-k))
            return false;
        i++;
    }
    return true;
}
void NQUEENS(int n)
{
    int i,k=1; //k     
    x[1]=0;//x[k]  k        
    while(k>0)
    {
        x[k]++;
        while(x[k]<=n&&!PLACE(k))//     ，      
          x[k]++;
        if(x[k]<=n)
        {
            if(k==n)//  x[]
            {
                for(i=1;i<=n;i++)
                    printf("x[%d]:%d  ",i,x[i]);
                printf("
");
            }

            else//     
            {
                k++; x[k]=0;
            }
        }
        else k--;//   ，   
    }
    return ;
}
int main()
{
    NQUEENS(8);
    return 0;
}

 
転載先:https://www.cnblogs.com/yuyu-blog/p/9046670.html