回溯算法 --- 例题4.N皇后问题

一.问题描述

N*N棋盘上放置N个皇后使得每个皇后互不受攻击. 即任二皇后不能位于同行同列和同一斜线上.
如四皇后问题的两个解:

二.解题思路

将棋盘从左至右,从上到下编号为1,...,n,皇后编号为1,...,n.
设解为(x1, ..., xn) , xi为皇后i的列号,且xi位于第i行.
解空间:E={ (x1,..., xn) | xi∈Si, i=1,...,4}, Si={1, ..., 4},1 <= i <= n

解空间为排列树? 是的!N个皇后在N*N的棋盘中一共有C(N^2, N)种放置情况,我们需要找到其中满足条件的排列情况.

其约束集合D为:

• xi ≠ xj ,保证皇后i, j不在同一行中
• xi - i ≠ xj - j ,保证皇后i, j不在同一斜线上
• xi + i ≠ xj +j ,保证皇后i, j不在同一斜线上

后两条总结一下就是 abs(i-j) ≠ abs(x[i] - x[j])

用回溯法解N后问题时,用完全n叉树表示解空间.可行性约束Place减去不满足行,列和斜线约束的子树.

具体代码如下:

// N皇后问题回溯算法
#include
using namespace std;
class Queen
{
    friend int NQueen(int) ;
    private:
        bool Place(int k);
        void Print();
        void Backtrack(int t);
        int n;  //皇后个数
        int *x; //当前解
        long sum;   //当前已经找到的可行方案数
};
void Queen::Print()
{
    cout<<"放置方案为: ";
    for(int i=1; i<=n; i++) cout< n)
    {
        sum++;
        Print();
    }
    else
    {
        for(int i=1; i<=n; i++)  //遍历第t行每一列
        {
            x[t] = i;
            if(Place(t))  //如果第t行能够放置
            {
                Backtrack(t+1);
            }
        }
    }
}

int NQueen(int n)
{
    Queen X;
    //初始化X
    X.n = n;
    X.sum = 0;
    int *p = new int[n+1];
    for(int i=0; i<=n; i++) p[i] = 0;
    X.x = p;
    X.Backtrack(1);
    X.Print();
    delete [] p;
    return X.sum;
}
int main()
{
    cout<<"请输入皇后个数: ";
    int n;
    while(cin>>n && n)
    {
        int ans = NQueen(n);
        cout<<"放置方案数: "<