算法(八)-回溯法-N皇后问题

问题描述：

算法思想：

代码实现：

#include <iostream>

using namespace std;

class Queen
{
    friend int nQueen(int);//求解八皇后

private:
    bool place(int);//判断落子是否合适
    void backTrack(int);//回溯查找可行解
private:
    int n;//皇后的个数
    int *x;//当前解
    long sum;//当前已找到的可行方案数
    char **answer;//可行解
};

bool Queen::place(int k)
{
    for(int i = 1; i < k; i++) if((abs(k-i) == abs(x[i]-x[k])) || (x[i] == x[k])) return false; return true; } void Queen::backTrack(int t) { if(t > n)
    {
        sum++;
        cout<<"这是第 "<<sum<<" 种解"<<endl;
        for(int i = 1; i <= n; i++)
        {
            for(int j = 1; j <= n; j++)
            {
                    cout<<answer[i][j];
            }
            cout<<endl;
        }
    }
    else
        for(int i = 1; i <= n; i++)
        {
            x[t] = i;
            answer[t][i] = 'O';
            if(place(t))
                backTrack(t+1);
            answer[t][i] = '+';
        }
}

int nQueen(int n)
{
    Queen queen;
    queen.n = n;
    queen.sum = 0;
    int *p = new int[n+1];

    //初始化可行解 answer = q
    char **q = new char*[n+1];
    for(int i = 0; i <= n; i++)
        q[i] = new char[n+1];
    for(int i = 0; i <= n; i++)
        for(int j = 0; j <= n; j++)
            q[i][j] = '+';

    for(int i = 0; i <= n; i++)
        p[i] = 0;

    queen.x = p;
    queen.answer = q;
    queen.backTrack(1);
    delete[] p;
    for(int i = 0; i <= n; i++)
        delete[] q[i];
    delete[] q;
    return queen.sum;
}

int main()
{
    cout<<"请输入有几个皇后"<<endl; int n; cin >> n;
    int sumQueen = nQueen(n);
    cout<<"有 "<<sumQueen<<" 可行解"<<endl;
    system("pause");
    return 0;
}