八皇后 r囧r小猫 2022-08-24 14:25 185阅读 0赞 /*************************** # Queen 八皇后问题 :递归实现 1. 从第一行开始递归 2. 然后枚举当前行中的每一列, 3. 如果可以放置皇后,则递归放置下一行 4. 当放置到第8行时,说明8个皇后全部安全放置,输出 # time:2014-2-9 11:03:20 # Time: MS Memory: K # Author: zyh ***************************/ #include<stdio.h> int n,cnt; // n: 棋盘的行列数; cnt: 可以放置的 种数 /* int row : 当前行 int col : 当前列 int (*chess)[8] : 当前棋盘数组 */ bool place(int row,int col, int (*chess)[8]){ // 判断同一列是否已经有皇后 for(int i = 0; i < row; i++) if(chess[i][col]) return 0; // 判断同一斜线对角线是否已经有皇后 for(int i = row-1,j = 1; i >= 0; i--,j++) if( (col-j>=0 && chess[i][col-j]) || (col+j<8 && chess[i][col+j])) return 0; return 1; } /* int r : 当前行 int (*chess)[8] :棋盘数组 */ void eightQueen(int r,int (*chess)[8] ) { // 放置到第8行时输出 if(r == 8){ printf("\n第%d种:\n",cnt++); for(int i = 0; i < n; i++){ for(int j = 0; j < n; j++) printf("%d ",chess[i][j]); putchar('\n'); } return; } //枚举当前行的每一列 for(int i = 0; i < n; i++){ //如果可以放,继续递归下一行 if( place(r,i,chess)) { chess[r][i] = 1; eightQueen(r+1,chess); chess[r][i] = 0; } } } int main() { int chess[8][8]={0}; n = 8; cnt = 1; eightQueen(0,chess); return 0; } /*************************** # Queen 八皇后问题 :回溯 用一维数组来表示八个皇后的位置 X[8]; X[i] 代表第i个皇后所在的列(第i个皇后在第i行,不用考虑在同一行的约束) 1. 第i个皇后 与 第 j 个皇后 同一列: x[i] == x[j]; 2. 第i个皇后 与 第 j 个皇后 同一斜线: x[i]+i == x[j]+j || x[i]-i == x[j]-j ; 即 abs(i-j) == abs(x[i]-x[j]) # time:2014-02-09 13:25:03 # Author: zyh ***************************/ #include<stdlib.h> #include<stdio.h> int n,cnt; // n: 棋盘的行列数; cnt: 可以放置的 种数 int x[10]; //cur: 开始放置第cur个皇后 void dfs(int cur){ //得到一种解法,cnt++ if(cur==8){ cnt ++; return; } //枚举每一列 for(int i=0; i<n; i++){ x[cur] = i; int ok = 1; //与前面放置的 cur-1个皇后比较,看是否可以放置 for(int j=0; j<cur; j++){ if(x[cur]==x[j] || abs(cur-j) == abs(x[cur]-x[j])) {ok = 0;break;} } if(ok) dfs(cur+1); } } int main() { n = 8; cnt = 0; dfs(0); printf("共有 %d 种解法.\n",cnt); //92种 return 0; }
相关 八皇后 八皇后问题介绍 八皇后问题,是一个古老而著名的问题,是回溯算法的典型案例。该问题是国际西洋棋棋手马克斯·贝瑟尔于1848年提出:在8×8格的国际象棋上摆放八个皇后,使其不 ゝ一世哀愁。/ 2022年12月24日 12:57/ 0 赞/ 122 阅读
相关 八皇后 八皇后 求解思路 可以将八皇后看成全排列问题,因为每次都是在某一行选择某个位置,所以不需要考虑行的问题。每次只需要求出当前行的棋子所在列。所以可以化为全排列问 左手的ㄟ右手/ 2022年10月01日 11:44/ 0 赞/ 172 阅读
相关 八皇后 / Queen 八皇后问题 :递归实现 1. 从第一行开始递归 2. 然后枚举当前行中的每一列, 3. 如果可以 r囧r小猫/ 2022年08月24日 14:25/ 0 赞/ 186 阅读
相关 八皇后 编写出八皇后的算法->递归算法 include <stdio.h> int nCount=0; int noDanger(int row,int 深藏阁楼爱情的钟/ 2022年08月08日 05:15/ 0 赞/ 19 阅读
相关 八皇后 八皇后问题是一个古老而著名的问题,是回溯算法的典型案例。该问题是国际西洋棋棋手马克斯·贝瑟尔于1848年提出:在8×8格的国际象棋上摆放八个皇后,使其不能互相攻击,即任意两个皇 女爷i/ 2022年07月29日 10:52/ 0 赞/ 205 阅读
相关 八皇后 package 搜索; import java.io.BufferedReader; import java.io.IOException; 一时失言乱红尘/ 2022年07月12日 12:14/ 0 赞/ 192 阅读
相关 八皇后问题 回溯法求解八皇后问题 n皇后问题:n皇后问题是指在一个n\n的国际象棋棋盘上放置n个皇后,使得这n个皇后两两不在同一行,同一列,同一条对角线上,求合法的方案数。 如 小灰灰/ 2022年06月11日 08:49/ 0 赞/ 274 阅读
相关 八皇后问题 枚举法 include<iostream> using namespace std; int a[9]; int check(int n, 蔚落/ 2022年06月06日 00:38/ 0 赞/ 228 阅读
相关 八皇后问题 在国际象棋中,皇后是最强大的一枚棋子,可以吃掉与其在同一行、列和斜线的敌方棋子.八皇后问题是这样一个问题:将八个皇后摆在一张8\8的国际象棋棋盘上,使每个皇后都无法吃掉别的皇 Bertha 。/ 2022年05月18日 05:58/ 0 赞/ 226 阅读
相关 八皇后问题 八皇后问题,以国际象棋为背景:如何能够在 8×8 的国际象棋棋盘上放置八个皇后,使得任何一个皇后都无法直接吃掉其他的皇后?为了达到此目的,任意两个皇后都不能处于 叁歲伎倆/ 2021年09月25日 15:34/ 0 赞/ 460 阅读
还没有评论,来说两句吧...