怎样学习做网站的编程,虚拟云电脑,深圳网站建设定制开发 超凡科技,住房建设部网站1213#xff1a;八皇后问题
时间限制: 1000 ms 内存限制: 65536 KB 【题目描述】 在国际象棋棋盘上放置八个皇后#xff0c;要求每两个皇后之间不能直接吃掉对方。
【输入】 (无)
【输出】 按给定顺序和格式输出所有八皇后问题的解#xff08;见样例#xff09;。
题目…1213八皇后问题
时间限制: 1000 ms 内存限制: 65536 KB 【题目描述】 在国际象棋棋盘上放置八个皇后要求每两个皇后之间不能直接吃掉对方。
【输入】 (无)
【输出】 按给定顺序和格式输出所有八皇后问题的解见样例。
题目要求不能是同一列、同一行、同一斜线两个方向的对角线
思路
一个8*8的矩阵用一个二维数组可以储存结果也可以用一维数组下标为n表示n行皇后的列数从第一个开始搜索搜索时判断在这一行之前的数是否有同一列、同一斜线由于是for循环搜索每次搜索就是一个同一行确定一个皇后所以不存在同一行的冲突 用二维数组的话同一列统一斜线最简单的就是用三个for循环去找同一列和对角线是否冲突但是不太聪明的样子如果用一维数组的话不难发现只要一个for循环去判断是否该值和前面几行的值是否冲突就行。至于对角线不难发现两行的差和两列的差的绝对值不相同则不可能冲突即abs(a[i]-a[l])abs(i-l) 一共有92种放置方式但是可以分为按列放置先看第一列皇后放在哪一行再看第二列皇后放在哪一行和按行放置先看第一行皇后放在哪一列再看第二行皇后放在哪一列按行放置和按列放置最终结果排列有差异但是内容一致仔细观察会发现其实两种结果就是矩阵的转置即可得到而当一维数组储存列数时矩阵转置只需要下标和数组值对换就行 代码示例
#includebits/stdc.h
using namespace std;
int n8,num1;
int a[9]{0};
void dfs(int l);
int check(int l);//判断同一列/同一行/一条斜线上是否已经有皇后传入参数为第几行
void print();
int main(){dfs(1);return 0;
}
void print(){
// 按行输出
// for(int i1;in;i){
// for(int j1;jn;j){
// if(ja[i]) cout1 ;
// else cout0 ;
// }
// coutendl;
// }//按列输出 ,按列实质就是矩阵倒置由于是一维数组储存 所以只需要将第n行m行转化为第m列的n行即可 int b[9];for(int i1;in;i){b[a[i]]i; }for(int i1;in;i){for(int j1;jn;j){if(jb[i]) cout1 ;else cout0 ;}coutendl;}}
void dfs(int l){//先判断是否需要结束该次遍历if(ln1){coutNO. numendl;print();num;return ;}else{//先循环遍历,i表示第几列 for(int i1;in;i){a[l]i;//直接先赋值否则会出错 他会往下继续判断然后再搜索下一行如果该位置判断有问题会回退到上一行if(check(l)){ //判断 dfs(l1);}}return;}
}
int check(int l){for(int i1;il;i){ //即在l-1行才确定皇后的位置后面的就不需要遍历判断了 if((a[i]a[l])||(abs(a[i]-a[l])abs(i-l))) { //a[l]表示的当前行所在列数 return 0;}} return 1;
}问题实质为搜索、回溯
搜索与回溯 该搜索问题的实质是深度优先的算法且为左根右为了求得问题的解先选择某一种可能情况开始搜索在搜索过程中一旦发现原来的选择是错误的就退回一步重新选择继续向下搜索如此反复进行直至得到解或证明无解。 最终搜索的结果得到一个二叉树。而向下搜索的和回溯都可以利用递归去实现。 回溯是回到上一步然后再向下搜索所以是基于第一次选择的条件下搜索直到所有情况搜索完才会换到另外的选择继续搜索 以下是二叉树搜索的过程根节点表示满足条件的 结果4次搜索完成
