[华为机试练习题]22.N皇后

题目

皇后是国际象棋中威力最大的棋子。在下面所示的棋盘上，皇后可以攻击位于箭头所覆盖位置的所有棋子。我们能不能把N个皇后放在棋盘(N×N)上，它们中的任何一个都无法攻击其余的皇后?请编写程序找出一共有几种方法。

详细描述：

接口说明
原型：
intPlaceQueenMethodNum(int n);
输入参数：
    int n: 皇后的个数

返回值：
        int: 放置n皇后方案的个数
练习阶段:    初级

代码

/*---------------------------------------
    *   日期：2015-06-30
    *   作者：SJF0115
    *   题目：N皇后
    *   来源：华为上机
    -----------------------------------------*/
    #include <iostream>
    #include <vector>
    #include "OJ.h"
    using namespace std;

    // 判断皇后是否在同一对角线上
    bool Check(vector<int> colIndex,int N){
        bool a,b;
        for(int i = 0;i < N;++i){
            for(int j = i+1;j < N;++j){
                a = (i - j == colIndex[i] - colIndex[j]);
                b = (j - i == colIndex[i] - colIndex[j]);
                if(a || b){
                    return false;
                }//if
            }//for
        }//for
        return true;
    }
    // 全排列
    void Permutation(vector<int> &colIndex,int N,int index,int &count,vector<bool> &visited){
        if(index == N){
            // 判断皇后是否在同一对角线上
            if(Check(colIndex,N)){
                ++count;
            }//if
            return;
        }//if
        for(int i = 0;i < N;++i){
            // 判断是否访问过
            if(!visited[i]){
                colIndex[index] = i;
                visited[i] = true;
                Permutation(colIndex,N,index+1,count,visited);
                visited[i] = false;
            }//if
        }//for
    }

    /*
    功能: 求解放置8皇后方案的个数。
    输入：
        无
    返回：
        int：放置8皇后方案的个数
    */

    int PlaceQueenMethodNum(int N)
    {
        if(N < 0){
            return -1;
        }//if
        int count = 0;
        // colIndex[i]表示位于第i行的皇后列号
        vector<int> colIndex(N,0);
        vector<bool> visited(N,false);
        // 全排列
        Permutation(colIndex,N,0,count,visited);
        return count;
    }

代码二

/*---------------------------------------
    *   日期：2015-06-30
    *   作者：SJF0115
    *   题目：N皇后
    *   来源：华为上机
    -----------------------------------------*/
    #include <iostream>
    #include <vector>
    #include <algorithm>
    #include "OJ.h"
    using namespace std;

    // 判断皇后是否在同一对角线上
    bool Check(vector<int> colIndex,int N){
        bool a,b;
        for(int i = 0;i < N;++i){
            for(int j = i+1;j < N;++j){
                a = (i - j == colIndex[i] - colIndex[j]);
                b = (j - i == colIndex[i] - colIndex[j]);
                if(a || b){
                    return false;
                }//if
            }//for
        }//for
        return true;
    }
    /*
    功能: 求解放置8皇后方案的个数。
    输入：
        无
    返回：
        int：放置8皇后方案的个数
    */
    int PlaceQueenMethodNum(int N){
        int count = 0;
        // colIndex[i]表示位于第i行的皇后列号
        vector<int> colIndex;
        for(int i = 0;i < N;++i){
            colIndex.push_back(i);
        }//for
        if(Check(colIndex,N)){
            ++count;
        }//if
        // 全排列
        while (next_permutation(colIndex.begin(), colIndex.end())){
            if(Check(colIndex,N)){
                ++count;
            }//if
        }//while
        return count;
    }