重庆妇科医院免费咨询,上海整站优化公司,佛山建设网站,博客 wordpress 登录了解题意
在一个8x8的棋盘上放置8个皇后#xff0c;使得任何两个皇后都不能处于同一行、同一列或同一斜线上。问有多少种方法可以放置这8个皇后#xff1f;
解决这个问题的目标是找到所有符合要求的皇后摆放方式#xff0c;通常使用回溯算法来求解。回溯算法会尝试所有可能…了解题意
在一个8x8的棋盘上放置8个皇后使得任何两个皇后都不能处于同一行、同一列或同一斜线上。问有多少种方法可以放置这8个皇后
解决这个问题的目标是找到所有符合要求的皇后摆放方式通常使用回溯算法来求解。回溯算法会尝试所有可能的摆放方式一旦发现某个摆放方式会导致冲突即两个皇后在同一行、同一列或同一斜线上就立即回溯到上一步尝试其他的摆放方式。
八皇后问题的解法有很多种其中一个经典解法是使用递归和剪枝。在递归过程中算法会尝试在每一行放置一个皇后并检查是否与前面放置的皇后发生冲突。如果发生冲突就回溯到上一行重新放置皇后。如果没有发生冲突就将该摆放方式加入到结果集中。为了避免重复计算可以使用一个数组来记录已经放置的皇后所在的行和列以便在回溯时跳过已经计算过的摆放方式。 放置皇后的地方置为1其余置为0. 代码如下示例 #include stdio.h
int cnt0;//解法个数
int qq[8][8]{0};
void cout_cheek(int aa[][8],int n){//输出二维数组for(int i0;in;i){for(int j0;jn;j){printf(%d ,aa[i][j]);}printf(\n);}printf(\n);
}int notdanger(int qq[][8],int n,int k){//判断某位置是否安全for(int i0;in;i){if(qq[i][k]1) return 0;//该列}for(int in,jk;i0j0;i--,j--){//左上角if(qq[i][j]1) return 0;}for(int in,jk;i0j8;i--,j){//右上角if(qq[i][j]1) return 0;}return 1;
}
void queen(int qq[][8],int n){
if(8n){cnt;printf(第%d种答案\n,cnt);cout_cheek(qq,8);}else{for(int k0;k8;k){if(notdanger(qq,n,k)){qq[n][k]1;queen(qq,n1);qq[n][k]0;}}}
}
int main(){queen(qq,0);printf(cnt%d\n,cnt);return 0;
} 递归和回溯是经典算法。
