广州市官网网站建设公司,小学网站源码php,wordpress流媒体插件,开发app的公司挣钱吗1、问题描述
在棋盘上放置 8 个皇后#xff0c;使得它们互不攻击#xff0c;此时每个皇后的攻击范围为同行同列和同对角线#xff0c;要求找出所有解#xff0c;如下图所示。 左图为皇后的攻击范围#xff0c;右图为一个可行解。
2、分析
最简单的思路是把问题转化为 “…1、问题描述
在棋盘上放置 8 个皇后使得它们互不攻击此时每个皇后的攻击范围为同行同列和同对角线要求找出所有解如下图所示。 左图为皇后的攻击范围右图为一个可行解。
2、分析
最简单的思路是把问题转化为 “从 64 个格子中选一个子集”使得 “子集中恰好 8 个格子且任意两个选出的格子都不在同一行、同一列或同一个对角线上”。这正是子集枚举问题。然而64个格子的子集有264 个太大了这并不是一个很好的模型。
第二个思路是把问题转化为 “从 64 个格子中选 8 个格子”这是组合生成问题。根据组合数学有 C 64 8 4.426 × 1 0 9 C_{64}^8 4.426 \times 10^9 C6484.426×109 种方案比第一种方案优秀但仍然不够好。
经过思考不难发现以下事实恰好每行每列各放置一个皇后。如果用 C[x] 表示第 x 行皇后的列编号则问题变成了全排列生成问题。 而 0 ~ 7 的排列一共只有 8! 40320个枚举量不会超过它。
提示在编写递归枚举程序之前需要深入分析问题对模型精雕细琢。一般还应对解答树的结点数有一个粗略的估计作为评价模型的重要依据如下图所示。 图中给出四皇后问题的完整解答树。它只有 17 个结点比 4! 24 小。之所以会这样是因为有些结点无法继续扩展。如在 (0,2,*,*) 中第2行无论将皇后放到哪里都会和第 0 行和第1行中已放好的皇后发生冲突其他还未放置的皇后更是如此。
在这种情况下递归函数将不再递归调用它自身而是返回上一层调用这种现象称为回溯backtracking。
提示当把问题分成若干步骤并递归求解时如果当前步骤没有合法的选择则函数将返回上一级递归调用这种现象称为回溯。正是因为这个原因递归枚举算法常被称为回溯法应用十分普遍。
下面的程序简洁地求解了八皇后问题。在主程序中读入 n n n并为 t o t tot tot 清零然后调用 search(0)即可得到解的个数 tot。
void search(int cur) {if (cur n) //递归边界只要走到了这里所有皇后必然不冲突tot; else {for (int i 0; i n; i) {int ok 1;C[cur] i; //尝试把第cur行的皇后放到第i列for (int j 0; j cur; j) { //检查是否和前面的皇后冲突if (C[cur] C[j] || cur - C[cur] j - C[j] || cur C[cur] j C[j]) {ok 0;break;}}if (ok) search(cur 1); //如果合法继续递归}}
}注意既然是逐行放置的则皇后肯定不会横向攻击因此只需检查是否纵向和斜向攻击即可。条件 “cur - C[cur] j - C[j] || cur C[cur] j C[j]” 用来判断皇后 (cur, C[cur]) 和 (j, C[j]) 是否在同一条对角线上。其原理可用下图来说明。 结点数似乎很难进一步减少了但程序效率可以继续提高利用二维数组 vis[2][] 直接判断当前尝试的皇后所在的列和两个对角线是否已有其他皇后。注意到主对角线标识 y − x y-x y−x 可能为负存取时要加上 n n n。
void search(int cur) {if(cur n) tot;else {for(int i 0; i n; i) {if(!vis[0][i] !vis[1][curi] !vis[2][cur-in]) { //利用二维数组直接判断C[cur] i; //如果不用打印解整个C数组都可以省略vis[0][i] vis[1][curi] vis[2][cur-in] 1; //修改全局变量search(cur1);vis[0][i] vis[1][curi] vis[2][cur-in] 0; //切记一定要改回来}}}
}上面程序有个极其关键的地方vis 数组的使用。vis数组的确切含义表示已经放置的皇后占据了哪些列、主对角线和副对角线。将来放置的皇后不应该修改这些值——至少“看上去没有修改”。一般地如果在回溯法中修改了辅助的全局变量则一定要及时把它们恢复原状除非故意保留所做修改。 另外在调用之前一定要把 vis 数组清空。
提示如果在回溯法中使用了辅助的全局变量则一定要及时把它们恢复原状。特别地若函数有多个出口则需在每个出口处恢复被修改的值。
3、完整代码
n皇后问题生成-测试法
#includecstdio
using namespace std;int C[50], tot 0, n 8, nc 0;void search(int cur) {int i, j;nc;if(cur n) {for(i 0; i n; i)for(j i1; j n; j)if(C[i] C[j] || i-C[i] j-C[j] || iC[i] jC[j]) return;tot;} else {for(i 0; i n; i) {C[cur] i;search(cur1);}}
}int main() {scanf(%d, n);search(0);printf(%d\n, tot);printf(%d\n, nc);return 0;
}n皇后问题普通回溯法
#includecstdio
using namespace std;int C[50], tot 0, n 8, nc 0;void search(int cur) {int i, j;nc;if(cur n) {tot;} else { for(i 0; i n; i) {int ok 1;C[cur] i;for(j 0; j cur; j) {if(C[cur] C[j] || cur-C[cur] j-C[j] || curC[cur] jC[j]) {ok 0;break;}}if(ok) search(cur1);}}
}int main() {scanf(%d, n);search(0);printf(%d\n, tot);printf(%d\n, nc);return 0;
}n皇后问题优化的回溯法
#includecstdio
#includecstring
using namespace std;int C[50], vis[3][50], tot 0, n 8, nc 0;void search(int cur) {int i, j;nc;if(cur n) {tot;} else for(i 0; i n; i) {if(!vis[0][i] !vis[1][curi] !vis[2][cur-in]) {C[cur] i;vis[0][i] vis[1][curi] vis[2][cur-in] 1;search(cur1);vis[0][i] vis[1][curi] vis[2][cur-in] 0;}}
}int main() {scanf(%d, n);memset(vis, 0, sizeof(vis));search(0);printf(%d\n, tot);printf(%d\n, nc);return 0;
}
