n后问题-回溯法-白红宇

n后问题-回溯法

阅读量：6006 次

发布时间：2019-06-20

本文共 1963 字，大约阅读时间需要 6 分钟。

问题描述：

　　在n*n的棋盘上放置彼此不受攻击的n个皇后。按国际象棋的规则，皇后可以与之处在同一行或者同一列或同一斜线上的棋子。

　　n后问题等价于在n*n格的棋盘上放置n皇后，任何2个皇后不放在同一行或同一列的斜线上。

算法设计：

　　|i-k|=|j-l|成立，就说明2个皇后在同一条斜线上。可以设计一个place函数，测试是否满足这个条件。

　　1 当i>n时，算法搜索至叶节点，得到一个新的n皇后互不攻击放置方案，当前已找到的可行方案sum加1.

　　2 当i<=n时，当前扩展结点Z是解空间中的内部结点。该结点有x[i]=1,2,3....n共n个儿子节点。

　　　　对当前扩展结点Z的每个儿子节点，由place检察其可行性。并以深度优先的方式递归地对可行子树，或剪去不可行子树。

算法描述：　

#include 
     
      #include 
      
       using namespace std;class Queen{    friend int nQueen(int);private:    bool Place(int k);    void Backtrack(int t);    int n,        * x;    long sum;};bool Queen::Place(int k){    for(int j=1;j
       
        n)        sum++;    else        for(int i=1;i<=n;i++)        {            x[t] = i;            if(Place(t))                Backtrack(t+1);        }}int nQueen(int n){    Queen 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);    delete [] p;    cout<
        
         <

执行结果：

迭代回溯：

数组x记录了解空间树中从根到当前扩展结点的路径，这些信息已包含了回溯法在回溯时所需要的信息。利用数组x所含的信息，可将上述回溯法表示成非递归形式，进一步省去O(n)递归栈空间。

　　n后问题的非递归迭代回溯法Backtrack可描述如下：

#include 
     
      #include 
      
       using namespace std;class Queen{    friend int nQueen(int);private:    bool Place(int k);    void Backtrack(void);//.........    int n,        * x;    long sum;};bool Queen::Place(int k){    for(int j=1;j
       
        0)    {        x[k]+=1;        while( (x[k]<=n) && !(Place(k)) )//k还不是最后的叶子结点，且位置没有冲突            x[k] += 1;        if(x[k] <= n)            if(k == n)//k是叶子结点                sum++;            else            {                k++;                x[k] = 0;            }        else            k--;    }}int nQueen(int n){    Queen 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();//......    delete [] p;    cout<
        
         <

执行结果：

转载于:https://my.oschina.net/u/204616/blog/545135

你可能感兴趣的文章