赞
踩
在 n × n n\times n n×n的棋盘上摆放 n n n个皇后,使任意两个皇后都不能处于同一行、同一列或同一斜线上
下以求解4皇后问题为例,分析4皇后问题的排列树以及回溯过程:
搜索及回溯过程:
解空间树:
①用数组x[]存放皇后的位置,x[k]表示第k个皇后放置的位置
②先在第一行放置第1个皇后,然后依2、3、…、n的次序放置其他皇后,当第n个皇后放置好后产生一个可行解(为得到所有解,还需要继续试探第n个皇后的下一个位置)
③试探每个皇后的位置都是从第1列开始的
④当第k个皇后试探了所有列都不能放置时,则回溯到第k-1个皇后,试探第k-1个皇后的下一个位置:如果第k-1个皇后的列号x[k-1]<n,则将其移到下一列,继续试探;否则,再回溯到第k-2个皇后,依次类推
⑤放置第k个皇后应与前面已经放置的k-1个皇后不发生冲突
⑥若第1个皇后的所有位置回溯完毕,则算法结束
#include<stdio.h> #include<math.h> #include<string> //考察皇后k放置在x[k]列是否发生冲突 int Place(int k, int x[]) { for (int i = 1; i < k; i++) /* x[k] == x[i]:是否在同列 Math.abs(k - i) == Math.abs(x[k] - x[i]):是否在同一斜线 */ if (x[k] == x[i] || fabs(k - i) == fabs(x[k] - x[i])) return 1; //冲突则返回1 return 0; } /* 求解n皇后问题 */ //非递归算法 void Queens(int n, int x[]) { int i = 1; //i表示当前行,也表示放置第i个皇后 x[i] = 0; //x[i]是当前列,每个新考虑的皇后初始位置置为0列 while (i >= 1) { //尚未回溯到头,循环 x[i]++; //原位置后移动一列 while (x[i] <= n && Place(i, x) == 1) //发生冲突,试探下一个位置(i, x[i]) x[i]++; if (x[i] <= n) { //为第i个皇后找到了一个合适位置(i, x[i]) if (i == n) { //若放置了所有皇后,输出一个解 for (int k = 1; k <= n; k++) printf("%d ", x[k]); printf("\n"); } else { //若皇后没有放置完 i++; //转向下一行,即开始下一个新皇后的放置 x[i] = 0; //每个新考虑的皇后初始位置置为0列 } } else i--; //若第i个皇后找不到合适的位置,则回溯到上一个皇后 } } //递归算法 void Queens(int i, int x[], int n){ if(i > n){ for (int k = 1; k <= n; k++) //n个皇后都放置好,输出 printf("%d ", x[k]); printf("\n"); }else for(int j = 1; j <= n; j++){ //每层均有n种放法 x[i] = j; //放置皇后t在第i列即x[t] if(Place(i, x) == 0) //不冲突,考察皇后t放置在x[t]列是否发生冲突 Queens(i+1, x, n); //继续递归放置下一个皇后 } } void main() { int n; printf("请输入皇后个数:"); scanf_s("%d", &n); int *x = (int *)malloc(sizeof(int)*(n+1)); //非递归调用 Queens(n, x); //递归调用 //Queens(1, x, n); }
该算法中每个皇后都要试探n列,共n个皇后,其解空间是一棵子集树,每个结点可能有n棵子树,对应的算法时间复杂度为
O
(
n
n
)
O(n^n)
O(nn)
利用显示约束排除两个皇后在同一行或同一列的方法,解空间树就是一棵排列树,因此共有
n
!
n!
n!个叶子结点,所以算法的时间复杂度可以降为
O
(
n
!
)
O(n!)
O(n!)
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。