回溯法——n后问题

问题描述:

　　在n*n的棋盘上放置彼此不受攻击的n个皇后。按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。n后问题等价于在n*n格的棋盘上放置n个皇后，任何2个皇后不放在同一行或同一列或同一斜线。

盲目的迭代枚举：

 /*

  *作者：xymaqingxiang

  *说明：八皇后——盲目迭代法

  *分析：通过8重循环模拟搜索空间中的8^8个状态，从中找出满足约束条件的可行性方案

  *日期：2014-05-15

  */

 #include <iostream>

 #include <cstdlib>

 using namespace std;

 bool place(int a[],int n)

 {

 for(int i=;i<=n;i++)

 {

     for(int j=;j<=i-;j++)

     {

         if ((a[i]==a[j])||(abs(a[i]-a[j])==i-j))//不同列和不同斜线约束

         {

             return false;//位置冲突

         }

     }

 }

 return true;//不冲突

 }

 void queens()

 {

     int a[];

     int count = ;

     //每个皇后都从第一列位置开始判断

     for(a[]=;a[]<=;a[]++)

     {

         for(a[]=;a[]<=;a[]++)

         {

             for(a[]=;a[]<=;a[]++)

             {

                 for(a[]=;a[]<=;a[]++)

                 {

                     for(a[]=;a[]<=;a[]++)

                     {

                         for(a[]=;a[]<=;a[]++)

                         {

                             for(a[]=;a[]<=;a[]++)

                             {

                                 for(a[]=;a[]<=;a[]++)

                                 {

                                     if(!place(a,))   //判断位置的合法性

                                         continue;

                                     else

                                     {

                                         for(int i=;i<=;i++)

                                         {

                                             cout<<a[i];        //打印满足约束的可行性放置方案

                                         }

                                         cout<<endl;

                                         count++;

                                     }

                                 }

                             }

                         }

                     }

                 }

             }

         }

     }

     cout<<count<<endl;

 }

 void main()

 {

     queens();

     system("pause");

 }

盲目枚举——nQueen

 /*

  *作者：xymaqingxiang

  *说明：八皇后——盲目迭代法

  *分析：通过8重循环模拟搜索空间中的8^8个状态，从中找出满足约束条件的可行性方案，但是这样会走很多冤枉路，而回溯的思想就是——走不通则掉头

         所以在下面的算法实现中，每进行一个皇后位置的讨论就立刻进行位置的检查，不满足则结束本路径，回头走下一路径，这样便能减少很多冤枉路。

         本算法虽可读性良好，但仍局限于解决8皇后问题，对于解决任何N皇后问题还要修改程序结构，不能把皇后个数n作为参数传递给函数，不具有普遍性。

         而且程序中出现了大量的for循环，而且for循环的结构很相似，自然让我们想到迭代回溯，即下面我们要讨论的递归回溯和非递归回溯

  *日期：2014-05-15

  */

 #include <iostream>

 #include <cstdlib>

 using namespace std;

 bool place(int a[ ],int n)

 {//多次被调用，只需一重循环

     for(int i=;i<=n-;i++)

     {

         if((abs(a[i]-a[n])==n-i)||(a[i]==a[n]))

             return false;

     }

     return true;

 }

 void queens()

 {

     int a[];

     int count = ;

     for(a[]=;a[]<=;a[]++)

     {

         for(a[]=;a[]<=;a[]++)

         {

             if (!place(a,))  continue;

             for(a[]=;a[]<=;a[]++)

             {

                 if (!place(a,))  continue;

                 for(a[]=;a[]<=;a[]++)

                 {

                     if (!place(a,))  continue;

                     for(a[]=;a[]<=;a[]++)

                     {

                         if (!place(a,))  continue;

                         for(a[]=;a[]<=;a[]++)

                         {

                             if (!place(a,))  continue;

                             for(a[]=;a[]<=;a[]++)

                             {

                                 if (!place(a,))  continue;

                                 for(a[]=;a[]<=;a[]++)

                                 {

                                     if (!place(a,))

                                         continue;

                                     else

                                     {

                                         for(int i=;i<=;i++)

                                         {

                                             cout<<a[i];

                                         }

                                         cout<<endl;

                                         count++;

                                     }

                                 }

                             }

                         }

                     }

                 }

             }

         }

     }

     cout<<count<<endl;

 }

 void main()

 {

     queens();

     system("pause");

 }

改进版盲目枚举——nQueen

　　以上两种算法虽可读性良好，但仍局限于解决8皇后问题，对于解决任何N皇后问题还要修改程序结构，不能把皇后个数n作为参数传递给函数，不具有普遍性。而且程序中出现了大量的for循环，而且for循环的结构很相似，自然让我们想到迭代回溯，即下面我们要讨论的递归回溯和非递归回溯。

算法分析：

　　用n元组x[1:n]表示n后问题的解，其中x[i]表示皇后 i 放在棋盘的第 i 行的第x[i]列。

　　不同行：事先规定好 i 号皇后只能放置在 i 行上，这样就解决了同行的问题。

　　不同列：解向量中的x[i]互不相同，即x[i]!=x[j]，如此便实现了不同列的限制。

　　不同斜线：最终任意两个皇后的位置(i,x[i])和(j,x[j])不在同一斜线，即斜率的绝对值不能为1，也就是|j-i|!=|x[j]-x[i]|。

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

　　下面具体解n后问题的回溯法中，递归函数Backtrack(1)实现对整个解空间的回溯搜索。Backtrack(i)搜索解空间中的第 i 层子树。类Queen的数据成员记录解空间结点信息，以减少传给Backtrack的参数。sum记录当前已找到的可行方案数。

　　在算法Backtrack中：

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

　　　　2 、当i<=n时，当前扩展结点Z是解空间中的内部结点。该结点有x[i]=1,2,3....n共n个儿子结点。对当前扩展结点Z的每一个儿子结点，由Place检察其可行性，并以深度优先的方式递归地对可行子树搜索，或剪去不可行子树。

算法描述1：————子集树（仅仅隐藏掉行约束）——规定好行位置，列位置从第一列开始讨论

 #include <iostream>

 #include <cstdlib>

 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)　　//位置检查，满足约束则返回true，否则返回false

 {

     for(int j=;j<k;j++)　　　　//检查k个皇后不同列和不同斜线的约束语句

         if((abs(k-j)==abs(x[j]-x[k]))||(x[j]==x[k]))

             return false;

     return true;

 }

 void Queen::Backtrack(int t)

 {

     if(t>n)

         sum++;　　//搜索至叶结点，即讨论完最后一个皇后的位置，得到一个新的不受攻击放置方案，可行方案数加 1

     else

         for(int i=;i<=n;i++)

         {

             x[t] = i;　　　　　　　　//确定第 i 个皇后的列位置

             if(Place(t))　　　　　　//检查放置位置是否满足约束条件

                 Backtrack(t+);　　//深度优先搜索可行子树

         }

 }

 int nQueen(int n)

 {

     Queen X;　　//定义并初始化X的信息

     X.n = n;

     X.sum = ;

     int *p = new int [n+];

     for(int i=;i<=n;i++)

         p[i] = ;

     X.x = p;

     X.Backtrack();

     delete [] p;

     cout<<X.sum<<endl;

     return X.sum;

 }

 int main()

 {

     nQueen();

     nQueen();

     nQueen();

     return ;

 }

迭代回溯：

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

具体的算法描述为：

 #include <iostream>

 #include <cstdlib>

 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)　　//位置检查函数，满足约束返回true，不满足返回false

 {

     for(int j=;j<k;j++)

         if( ( abs(k-j) == abs(x[j]-x[k]) ) ||( x[j] == x[k] ) )

             return false;

     return true;

 }

 void Queen::Backtrack(void)//非递归实现

 {

     x[] = ;　　//x[1]赋初值为0

     int k = ;　　//从第一个皇后开始讨论

     while(k>)

     {

         x[k]+=;　　//x[1]赋初值为0，加1后，表示首先从第一列开始放

         while( (x[k]<=n) && !(Place(k)) )//k还不是最后的叶子结点，且位置没有冲突，满足Place函数的约束————x[k]代表列的位置，没有超出列的限制

             x[k] += ;　　//在没有超出列的限制且不满足Place函数位置约束时，列后移

         if(x[k] <= n)　　//没有超出列的限制范围

             if(k == n)    //k是叶子结点，已经讨论到最后一个皇后

                 sum++;　　//可行方案数加1

             else

             {　　//未到达叶子节点(最后一个皇后)，且已经为当前的皇后找到合适的位置，k++后处理下一个皇后的放置位置

                 k++;　　　　//考虑下一个皇后的放置位置

                 x[k] = ;　　//初始位置之前赋值为0

             }

         else

             k--;　　//由于已经超出列的限制范围，且当前正考虑的皇后没有找到合适的位置，则前一个皇后的位置后移，重新来过

     }

 }

 int nQueen(int n)

 {

     Queen X;

     X.n = n;

     X.sum = ;

     int *p = new int [n+];

     for(int i=;i<=n;i++)

         p[i] = ;

     X.x = p;

     X.Backtrack();//......

     delete [] p;

     cout<<X.sum<<endl;

     return X.sum;

 }

 int main()

 {

     nQueen();

     nQueen();

     nQueen();

     return ;

 }

算法描述2：————排列树（隐藏掉行和列约束）——>规定好行位置的同时，列位置从j（不同于上一个皇后的列）开始讨论

 #include <iostream>

 #include <cstdlib>

 using namespace std;

 class Queen{

     friend int nQueen(int);

 private:

     bool Place(int k);

     void swap(int t,int i,int *x);

     void Backtrack(int t);

     int n, //皇后个数

         * x;//当前解空间

     long sum;//当前已找到的可行方案数

 };

 bool Queen::Place(int k)//位置检查，满足约束则返回true，否则返回false

 {

     for(int j=;j<k;j++)//检查k个皇后不同列和不同斜线的约束语句

         if((abs(k-j)==abs(x[j]-x[k]))||(x[j]==x[k]))

             return false;

     return true;

 }

 void Queen::swap(int t,int i,int *x)

 {

     int k;

     k=x[t];

     x[t]=x[i];

     x[i]=k;

 }

 void Queen::Backtrack(int t)

 {

     if(t>n)

     {

         for(int i=;i<=n;i++)　　//方案数加1前，先打印符合要求的排列组合

             cout<<x[i];

         cout<<endl;

         sum++;//搜索至叶结点，即讨论完最后一个皇后的位置，得到一个新的不受攻击放置方案，可行方案数加 1

     }

     else

         for(int i=t;i<=n;i++)//控制分支数目，每次都要减一，初始值从t开始而非1

         {

             swap(t,i,x);//交换位置，得到一种新的排列————轮岗ing

             if(Place(t))//检查放置位置是否满足约束条件

                 Backtrack(t+);//深度优先搜索可行子树

             swap(t,i,x);//调回原位置（初始排列组合）———— 众神归位

         }

 }

 int nQueen(int n)

 {

     Queen X;//定义并初始化X的信息

     X.n = n;

     X.sum = ;

     int *p = new int [n+];

     for(int i=;i<=n;i++)

         p[i] = i;　　//给x[i]赋初值，必须是其排列的一种

     X.x = p;

     X.Backtrack();

     cout<<X.sum<<endl;

     delete [] p;

     return X.sum;

 }

 int main()

 {

     nQueen();

     nQueen();

     nQueen();

     system("pause");

     return ;

 }

回溯法——n后问题的相关教程结束。