八皇后问题

题目：八皇后问题
思路：就用回溯法。
这个算法类似动态规划的思想。

代码如下：

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

// 八皇后问题
// 回溯法的典型代表，初学计算机的时候，这个算法算是比较难的了，现在看来真是一般的计算问题。

int g_nCount;
struct coordinate
{
    int x;
    int y;

    coordinate(int n1, int n2) : x(n1), y(n2) {}
};

void PrintXYSeq(coordinate xy)
{
    cout << "[" << xy.x << "," << xy.y << "]" << " ";
}

bool CheckXY(vector<vector<int> > & vecMatrix, int row, int col)
{
    return vecMatrix[row][col] == 0;
}

void ModifyXY(vector<vector<int> > & vecMatrix, int row, int col, int nLen, bool bFlag)
{
    int base = 1;
    if (bFlag)  base = 1;
    else base = -1;
    for (int i=0; i<nLen; ++i) {
        vecMatrix[row][i] += base;
    }

    for (int i=0; i<nLen; ++i) {
        vecMatrix[i][col] += base;
    }

    for (int i=row,j=col; i>=0 && j>=0; --i, --j) {
        vecMatrix[i][j] += base;        
    }
    for (int i=row,j=col; i>=0 && j<nLen; --i, ++j) {
        vecMatrix[i][j] += base;        
    }
    for (int i=row,j=col; i<nLen && j<nLen; ++i, ++j) {
        vecMatrix[i][j] += base;        
    }
    for (int i=row,j=col; i<nLen && j>=0; ++i, --j) {
        vecMatrix[i][j] += base;        
    }
}

void GenerateSeq(vector<coordinate> & vecSeq, int row, int col, int nLen, vector<vector<int> > & vecMatrix)
{
    if (row == nLen) {
        for_each(vecSeq.begin(), vecSeq.end(), PrintXYSeq);
        cout << endl;
        ++g_nCount;
        return ;
    }

    for (int i=col; i<nLen; ++i) {
        if (CheckXY(vecMatrix, row, i)) {
            ModifyXY(vecMatrix, row, i, nLen, true);
            vecSeq.push_back(coordinate(row, i));
            GenerateSeq(vecSeq, row+1, 0, nLen, vecMatrix);
            vecSeq.pop_back();
            ModifyXY(vecMatrix, row, i, nLen, false);
        }
    }
}

void Output()
{
    const int nLen = 8;
    vector<vector<int> > vecMatrix(nLen, vector<int>(nLen, 0));
    vector<coordinate> vecSeq;

    GenerateSeq(vecSeq, 0, 0, nLen, vecMatrix);

}

int main(int argc, char ** argv)
{
    Output();
    cout << g_nCount << endl;
    return 0;
}

上面我使用的方法应该是算快的了，给个效率更高的八皇后问题