52.N-Queens II

52.N-Queens II My Submissions
Question
Total Acceepted: 39648 
Total Submissions: 103386 
Difficulty: ハード
Follow up for N-Queens proble.
Now,instead outputting board configrations,return the total number of distinct solution.
Subscribe to see which companies asked this question
ハイドTags
 
Backtrocing
Show Simiar Probles
分析:
八皇后問題です.最も典型的な遡及法問題です.
順番に1からNの皇后まで並べて、すべての皇后のありかの行はすべて第1列から第N列まで試して並べます:一回並べて検査しますとすでに並べた皇后と衝突するかどうか、もし衝突しないで次の皇后を並べ続けるならば、もし衝突した後の皇后はすべて現在の皇后の位置で引き続き並べ続けるならば、すぐ前の皇后の次の位置に帰って引き続き並べます.

class Solution {
public:
    //         ,      ，a[1]=2，  1     2 
    bool isConflict(int a[], int n)//a    ，n       
    {  
        int i = 0, j = 0;  
        for (i = 2; i <= n; ++i)  
        for (j = 1; j <= i - 1; ++j) 
        if ((a[i] == a[j]) || (abs(a[i] - a[j]) == i - j))//1：     ；2：         
            return false;   //     
        return true;//      
    } 
    //N    ：    （   ）   
    void QueensN(int a[],int k,int n) //  k：     k      
    {  
        int i = 0;  
        if (k > n)      //k>n： k>n               
        {  
            ++cnt;  
        }  
        else   //N                    
        {  
            for (i = 1; i <= n; ++i)//   k    （    ）   
            { //          ，      ，        ,     ，        (  )   
                a[k] = i;  
                if (isConflict(a, k))  
                    QueensN(a,k + 1,n);//   ,           
            }  
        }  
        return;  
    } 
    int totalNQueens(int n) {
        cnt=0;
        int a[9]={0};
        QueensN(a,1,n);
        return cnt;
    }
private:
    int cnt;
};

注:このブログはEbowTangのオリジナルです.その後も引き続き本文を更新します.転載する場合は、必ず本条情報をコピーしてください.
原文の住所:http://blog.csdn.net/ebowtang/article/details/50585984
作者のブログ:http://blog.csdn.net/ebowtang