首页 > 代码库 > 回溯法——n后问题

回溯法——n后问题

2024-07-04 18:22:21   227人阅读

问题描述:

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

盲目的迭代枚举：

 1 /*
 2  *作者：xymaqingxiang
 3  *说明：八皇后——盲目迭代法
 4  *分析：通过8重循环模拟搜索空间中的8^8个状态，从中找出满足约束条件的可行性方案
 5  *日期：2014-05-15
 6  */
 7 #include <iostream>
 8 #include <cstdlib>
 9 using namespace std;
10 bool place(int a[],int n)
11 {
12 for(int i=2;i<=n;i++)
13 {
14     for(int j=1;j<=i-1;j++)
15     {
16         if ((a[i]==a[j])||(abs(a[i]-a[j])==i-j))//不同列和不同斜线约束
17         {
18             return false;//位置冲突
19         }
20     }
21 }
22 return true;//不冲突
23 }
24 
25 void queens()
26 {
27     int a[9];
28     int count = 0;
29     //每个皇后都从第一列位置开始判断
30     for(a[1]=1;a[1]<=8;a[1]++)
31     {
32         for(a[2]=1;a[2]<=8;a[2]++)
33         {
34             for(a[3]=1;a[3]<=8;a[3]++)
35             {
36                 for(a[4]=1;a[4]<=8;a[4]++)
37                 {
38                     for(a[5]=1;a[5]<=8;a[5]++)
39                     {
40                         for(a[6]=1;a[6]<=8;a[6]++)
41                         {
42                             for(a[7]=1;a[7]<=8;a[7]++)
43                             {
44                                 for(a[8]=1;a[8]<=8;a[8]++)
45                                 {
46                                     if(!place(a,8))   //判断位置的合法性
47                                         continue;
48                                     else
49                                     {
50                                         for(int i=1;i<=8;i++)  
51                                         {
52                                             cout<<a[i];        //打印满足约束的可行性放置方案
53                                         }
54                                         cout<<endl;
55                                         count++;
56                                     }
57                                 }
58                             }
59                         }
60                     }
61                 }
62             }
63 
64         }
65     }
66     cout<<count<<endl;
67 }
68 
69 void main()
70 {
71     queens();
72     system("pause");
73 }
盲目枚举——nQueen
 1 /*
 2  *作者：xymaqingxiang
 3  *说明：八皇后——盲目迭代法
 4  *分析：通过8重循环模拟搜索空间中的8^8个状态，从中找出满足约束条件的可行性方案，但是这样会走很多冤枉路，而回溯的思想就是——走不通则掉头
 5         所以在下面的算法实现中，每进行一个皇后位置的讨论就立刻进行位置的检查，不满足则结束本路径，回头走下一路径，这样便能减少很多冤枉路。
 6         本算法虽可读性良好，但仍局限于解决8皇后问题，对于解决任何N皇后问题还要修改程序结构，不能把皇后个数n作为参数传递给函数，不具有普遍性。
 7         而且程序中出现了大量的for循环，而且for循环的结构很相似，自然让我们想到迭代回溯，即下面我们要讨论的递归回溯和非递归回溯
 8  *日期：2014-05-15
 9  */
10 #include <iostream>
11 #include <cstdlib>
12 using namespace std;
13 bool place(int a[ ],int n)
14 {//多次被调用，只需一重循环 
15     for(int i=1;i<=n-1;i++)
16     {
17         if((abs(a[i]-a[n])==n-i)||(a[i]==a[n]))
18             return false;
19     }      
20     return true;
21 }
22 
23 void queens()
24 {
25     int a[9];
26     int count = 0;
27     for(a[1]=1;a[1]<=8;a[1]++)
28     {
29         for(a[2]=1;a[2]<=8;a[2]++)
30         {
31             if (!place(a,2))  continue;
32             for(a[3]=1;a[3]<=8;a[3]++)
33             {
34                 if (!place(a,3))  continue;
35                 for(a[4]=1;a[4]<=8;a[4]++)
36                 {
37                     if (!place(a,4))  continue;
38                     for(a[5]=1;a[5]<=8;a[5]++)
39                     {
40                         if (!place(a,5))  continue;
41                         for(a[6]=1;a[6]<=8;a[6]++)
42                         {
43                             if (!place(a,6))  continue;
44                             for(a[7]=1;a[7]<=8;a[7]++)
45                             {
46                                 if (!place(a,7))  continue;
47                                 for(a[8]=1;a[8]<=8;a[8]++)
48                                 {
49                                     if (!place(a,8))  
50                                         continue;
51                                     else
52                                     {
53                                         for(int i=1;i<=8;i++)  
54                                         {
55                                             cout<<a[i];
56                                         }
57                                         cout<<endl;
58                                         count++;
59                                     }
60                                 }
61                             }
62                         }
63                     }
64                 }
65             }
66 
67         }
68     }
69     cout<<count<<endl;
70 }
71 
72 void main()
73 {
74     queens();
75     system("pause");
76 }
改进版盲目枚举——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：————子集树（仅仅隐藏掉行约束）——规定好行位置，列位置从第一列开始讨论

 1 #include <iostream>
 2 #include <cstdlib>
 3 using namespace std;
 4 class Queen{
 5     friend int nQueen(int);
 6 private:
 7     bool Place(int k);
 8     void Backtrack(int t);
 9     int n,　　　　//皇后个数
10         * x;　　　//当前解空间
11     long sum;　　 //当前已找到的可行方案数
12 };
13 bool Queen::Place(int k)　　//位置检查，满足约束则返回true，否则返回false
14 {
15     for(int j=1;j<k;j++)　　　　//检查k个皇后不同列和不同斜线的约束语句
16         if((abs(k-j)==abs(x[j]-x[k]))||(x[j]==x[k]))
17             return false;
18     return true;
19 }
20 void Queen::Backtrack(int t)
21 {
22     if(t>n)
23         sum++;　　//搜索至叶结点，即讨论完最后一个皇后的位置，得到一个新的不受攻击放置方案，可行方案数加 1
24     else
25         for(int i=1;i<=n;i++)
26         {
27             x[t] = i;　　　　　　　　//确定第 i 个皇后的列位置
28             if(Place(t))　　　　　　//检查放置位置是否满足约束条件
29                 Backtrack(t+1);　　//深度优先搜索可行子树
30         }
31 }
32 int nQueen(int n)
33 {
34     Queen X;　　//定义并初始化X的信息
35     X.n = n;
36     X.sum = 0;
37     int *p = new int [n+1];
38     for(int i=0;i<=n;i++)
39         p[i] = 0;
40     X.x = p;
41     X.Backtrack(1);
42     delete [] p;
43     cout<<X.sum<<endl;
44     return X.sum;
45 }
46 int main()
47 {
48     nQueen(4);
49     nQueen(2);
50     nQueen(3);
51     return 0;
52 }

迭代回溯：

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

具体的算法描述为：

 1 #include <iostream>
 2 #include <cstdlib>
 3 using namespace std;
 4 class Queen{
 5     friend int nQueen(int);
 6 private:
 7     bool Place(int k);
 8     void Backtrack(void);//.........
 9     int n,
10         * x;
11     long sum;
12 };
13 bool Queen::Place(int k)　　//位置检查函数，满足约束返回true，不满足返回false
14 {
15     for(int j=1;j<k;j++)
16         if( ( abs(k-j) == abs(x[j]-x[k]) ) ||( x[j] == x[k] ) )
17             return false;
18     return true;
19 }
20 void Queen::Backtrack(void)//非递归实现
21 {
22     x[1] = 0;　　//x[1]赋初值为0
23     int k = 1;　　//从第一个皇后开始讨论
24     while(k>0)
25     {
26         x[k]+=1;　　//x[1]赋初值为0，加1后，表示首先从第一列开始放
27         while( (x[k]<=n) && !(Place(k)) )//k还不是最后的叶子结点，且位置没有冲突，满足Place函数的约束————x[k]代表列的位置，没有超出列的限制
28             x[k] += 1;　　//在没有超出列的限制且不满足Place函数位置约束时，列后移
29         if(x[k] <= n)　　//没有超出列的限制范围
30             if(k == n)    //k是叶子结点，已经讨论到最后一个皇后
31                 sum++;　　//可行方案数加1
32             else
33             {　　//未到达叶子节点(最后一个皇后)，且已经为当前的皇后找到合适的位置，k++后处理下一个皇后的放置位置
34                 k++;　　　　//考虑下一个皇后的放置位置
35                 x[k] = 0;　　//初始位置之前赋值为0
36             }
37         else
38             k--;　　//由于已经超出列的限制范围，且当前正考虑的皇后没有找到合适的位置，则前一个皇后的位置后移，重新来过
39     }
40 }
41 int nQueen(int n)
42 {
43     Queen X;
44     X.n = n;
45     X.sum = 0;
46     int *p = new int [n+1];
47     for(int i=0;i<=n;i++)
48         p[i] = 0;
49     X.x = p;
50     X.Backtrack();//......
51     delete [] p;
52     cout<<X.sum<<endl;
53     return X.sum;
54 }
55 int main()
56 {
57     nQueen(4);
58     nQueen(2);
59     nQueen(3);
60     return 0;
61 }

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

 1 #include <iostream>
 2 #include <cstdlib>
 3 using namespace std;
 4 class Queen{
 5     friend int nQueen(int);
 6 private:
 7     bool Place(int k);
 8     void swap(int t,int i,int *x);
 9     void Backtrack(int t);
10     int n, //皇后个数
11         * x;//当前解空间
12     long sum;//当前已找到的可行方案数
13 };
14 bool Queen::Place(int k)//位置检查，满足约束则返回true，否则返回false
15 {
16     for(int j=1;j<k;j++)//检查k个皇后不同列和不同斜线的约束语句
17         if((abs(k-j)==abs(x[j]-x[k]))||(x[j]==x[k]))
18             return false;
19     return true;
20 }
21 void Queen::swap(int t,int i,int *x)
22 {
23     int k;
24     k=x[t];
25     x[t]=x[i];
26     x[i]=k;
27 }
28 
29 void Queen::Backtrack(int t)
30 {
31     if(t>n)
32     {
33         for(int i=1;i<=n;i++)　　//方案数加1前，先打印符合要求的排列组合
34             cout<<x[i];
35         cout<<endl;
36         sum++;//搜索至叶结点，即讨论完最后一个皇后的位置，得到一个新的不受攻击放置方案，可行方案数加 1
37     }
38     else
39         for(int i=t;i<=n;i++)//控制分支数目，每次都要减一，初始值从t开始而非1
40         {
41             swap(t,i,x);//交换位置，得到一种新的排列————轮岗ing
42             if(Place(t))//检查放置位置是否满足约束条件
43                 Backtrack(t+1);//深度优先搜索可行子树
44             swap(t,i,x);//调回原位置（初始排列组合）———— 众神归位
45         }
46 }
47 int nQueen(int n)
48 {
49     Queen X;//定义并初始化X的信息
50     X.n = n;
51     X.sum = 0;
52     int *p = new int [n+1];
53     for(int i=1;i<=n;i++)
54         p[i] = i;　　//给x[i]赋初值，必须是其排列的一种
55     X.x = p;
56     X.Backtrack(1);
57     cout<<X.sum<<endl;
58     delete [] p;
59     return X.sum;
60 }
61 int main()
62 {
63     nQueen(4);
64     nQueen(2);
65     nQueen(3);
66     system("pause");
67     return 0;
68 }


联系
我们