-
2022-04-06 11:12:41
这是求解8皇后问题有多少种不同的放法
#include<iostream> using namespace std; #pragma warning(disable:4996) // 8皇后问题 int ans = 0; bool col[10], x1[20], x2[20]; // x1 x2表示两条对角线上的位置 bool check(int r, int i) { return !col[i] && !x1[r + i] && !x2[r - i + 8]; } void dfs(int r) { if (r == 8) { ans++; return; } for (int i = 0; i < 8; i++) { if (check(r,i)) //判断该位置是否能放 { col[i] = x1[r + i] = x2[r - i + 8] = true; //能放,就设为true dfs(r + 1); //从下一行开始 col[i] = x1[r + i] = x2[r - i + 8] = false; //放完之后需要恢复原来的值 } } } int main() { dfs(0); //从第0行开始搜索 cout << ans << endl; return 0; }
更多相关内容 -
遗传算法求解8皇后问题的python实现
2021-05-23 11:32:08使用python实现遗传算法,求解8皇后问题,流程如下 1、随机初始化100个个体 2、随机选择5个个体,挑选2个作为parents 3、parents结合生成children 4、children以0.8的概率变异,变异方法是随机交换2个染色体位置 5、... -
8皇后问题输出所有解的点阵图
2018-05-09 19:04:33c语言的代码,解决8皇后问题,输出为棋盘式的0,1点阵图,有需要可下载 -
8皇后问题的解法实例代码
2020-12-26 07:36:02#define MAX 200#define Empty 0#define Full 1#define N 8 unsigned char qipan[N][N][N]={MAX};//初始化8张棋盘表示每下一步的void input(int i);int count = 0; int main(){ input(0); getchar(); return 0;}... -
python+pygame实现可视化8皇后问题/N皇后问题.zip
2021-11-18 10:45:33本人课程作业,下载后安装需要的python包即可实现带有可视化的N皇后问题,并附有实验报告(程序内容介绍、代码介绍、代码原理结构、以及可改进之处)很适合有课程需要的大学生以及自学人士 -
Python基于回溯法子集树模板实现8皇后问题
2020-09-21 04:39:54主要介绍了Python基于回溯法子集树模板实现8皇后问题,简单说明了8皇后问题的原理并结合实例形式分析了Python回溯法子集树模板解决8皇后问题的具体实现技巧,需要的朋友可以参考下 -
极好的8皇后问题的算法解析
2013-10-17 08:57:12极好的8皇后问题的算法解析,有非常详细的解释和代码 -
利用C语言解决八皇后问题以及解析
2021-01-01 01:59:22八皇后问题是一个古老而著名的问题。该问题是19世纪著名的数学家高斯1850年提出:在一个8*8国际象棋盘上,有8个皇后,每个皇后占一格;要求皇后之间不会出现相互“攻击”的现象,即不能有两个皇后处在同一行、同一列... -
8皇后问题算法实现
2015-12-14 15:01:188皇后问题算法实现,基于Java的8皇后问题 -
java 编程8皇后问题
2013-11-30 15:48:298皇后问题复杂性描述,输入一定方格个数,即可输出最好的排列方式。 -
算法设计-回溯法——8皇后问题
2020-12-10 14:31:45要求用回溯法求解 8-皇后问题,使放置在 8*8 棋盘上的 8 个皇后彼此不受攻击,即:任 何两个皇后都不在同一行、同一列或同一斜线上。请输出 8 皇后问题的所有可行解。 问题分析 在解决八皇后问题时,如果采用穷举法...算法介绍
回溯法:
回溯法又称试探法。回溯法的基本做法是深度优先搜索,是一种组织得井井有条的、能避免不必要重复搜索的穷举式搜索算法。
回溯算法的基本思想:从一条路往前走,能进则进,不能进则退回来,换一条路再试。问题实例
问题描述:
题目:
要求用回溯法求解 8-皇后问题,使放置在 8*8 棋盘上的 8 个皇后彼此不受攻击,即:任 何两个皇后都不在同一行、同一列或同一斜线上。请输出 8 皇后问题的所有可行解。问题分析
在解决八皇后问题时,如果采用穷举法,则需要列举8^8种情形。采用回溯法,则是对解空间使用深度优先遍历的方式找到可行解,然后用限制条件来缩小解空间。
伪代码:
①设一数组 x[],下标代表第几行,值代表该行中的那一位置。设一变量k,代表此时在下第几行。
②设一个判断是否符合条件(不同列,不在对角线上)的函数,利用列不能相同,列之差与行之差不能相同判断,不符合条件的直接跳过(缩小解空间)
③利用for循环,将符合条件的可行解放入x [ ] 中,当x [ ]填满后,输出,此时一种方案结束。
④利用递归,直到所有可行方案输出,结束。代码:
#include <iostream> #include <cmath> using namespace std; int num=0; bool Wzhi(int k,int i,int *x) { for(int j=0;j<k;j++) //j此时代表第几行 if( (i==x[j] )||( abs(k-j) == abs(i-x[j]) )) // 判断是否同一列 判断是否在对角线上(利用两直角边长度相同) { return false; } return true; } void Bhh (int k,int n,int *x) { for(int i=0;i<n;i++) { if(Wzhi(k,i,x)) { x[k]=i; if(k==n-1) { for(int i=0;i<n;i++) { cout<<x[i]<<" "; } num++; cout<<endl; } else { Bhh(k+1,n,x); } } } } void Bhh (int n,int *x) { Bhh(0,n,x); } int main() { int x[8];//下标代表第几行,值代表放在该行哪个位置 int n=8; for(int i=0;i<n;i++) { x[i]=-1; } Bhh(8,x); cout<<"共计有"<<num<<"种组合"<<endl; }
结果:
解决该问题的关键是利用for循环作深度优先遍历,对第k行的每一格进行逐一判断,判断该格是否满足0 ~ k-1 行不同列,不在对角线的条件,不满足直接舍弃,否则利用递归继续选择合适的位置。
记录整理一些学习中的问题,如果有不恰当和错误的地方,欢迎批评指正~
-
8皇后问题 Haskell
2018-10-26 23:12:14Haskell语言解决八皇后问题,质量很高,程序简单清晰, -
8皇后问题全部图解
2015-08-27 11:25:558皇后问题的回朔算法非常精巧,有点震撼.就做了个图解程序。程序是swing做的可运行jar文件。做的时候用的jdk7.编码utf-8. -
回溯法——8皇后问题
2020-12-09 21:13:45回溯法——8皇后问题 一、实验内容 1.问题描述 要求用回溯法求解8 —— 皇后问题,是放置在8*8棋盘上的8个皇后彼此不收攻击,即:任何两个皇后都不在同一行、同一列和同一斜线上。 请输出8皇后问题所有可行解。 2、...回溯法——8皇后问题
一、实验内容
1.问题描述
要求用回溯法求解8 —— 皇后问题,是放置在8*8棋盘上的8个皇后彼此不收攻击,即:任何两个皇后都不在同一行、同一列和同一斜线上。
请输出8皇后问题所有可行解。
2、要求
(1)写出问题分析过程
(2)写出程序代码
(3)写出程序运行结果
二、程序代码package huisu; public class Queen { /* * 一共有多少个皇后(此时设置为8皇后在8*8棋盘,可以修改此值为N皇后 */ int max= 8; static long sum=0; /* * 该数组保存结果,第一个皇后摆在array[0]列,第二个摆在array[1]列, */ int [] array = new int[max]; public static void main(String[] args) { new Queen().check(0); System.out.println("一共有:"+sum+"个可行解"); } /* * n代表当前是第几个皇后 * @param n * 皇后n在array[n]列 */ private void check(int n) { //终止条件是最后一行已经摆完,由于每摆一步都会教研是否有冲突,所以就进行下一行逻辑 if(n==max) { sum++; print(); return; } for(int i=0;i<max;i++) { array[n] = i; if(judge(n)) { check(n+1); } } } private boolean judge(int n) { for(int i=0;i<n;i++) { if(array[i] == array[n] || Math.abs(n-i) == Math.abs(array[n] - array[i] )) { return false; } } return true; } private void print() { for(int i=0; i < array.length;i++) { System.out.print(array[i]+1+" "); } System.out.println(); } }
三、程序运行结果
-
Python解决八皇后问题示例
2020-09-20 14:14:24主要介绍了Python解决八皇后问题,简单描述了八皇后问题的原理并结合实例形式分析了Python基于递归算法解决八皇后问题的相关操作技巧,需要的朋友可以参考下 -
8皇后问题七届源代码
2015-05-19 11:42:29博客http://blog.csdn.net/zhyh1435589631/article/details/45842823的配套源代码,使用于N皇后问题的求解,C++方式实现 -
N-Queens:关于N皇后问题的Android游戏(8皇后问题的广义形式)
2021-06-21 18:37:14N-皇后 N皇后问题上的Android游戏(8皇后问题的广义形式) -
8皇后问题c++代码
2012-11-21 20:47:02很简单,很好用的代码,用于解决八皇后问题(八皇后问题,是一个古老而著名的问题,是回溯算法的典型例题。该问题是十九世纪著名的数学家高斯1850年提出:在8X8格的国际象棋上摆放八个皇后,使其不能互相攻击,即... -
8皇后问题java图形界面实现
2015-08-29 11:36:138皇后问题java版的图形界面演示,swing做的可运行jar文件。看了回朔算法,简洁的让人震撼,很有感触,就做了个图形演示界面。 -
python8皇后问题
2015-09-01 14:31:48用python解决的8皇后问题,版本是python3.4 -
【递归入门】n皇后 问题(原始的8皇后问题)
2019-09-17 22:16:07这就是著名的八皇后问题。 输入 一个整数n( 1 < = n < = 10 ) 输出 每行输出对应一种方案,按字典序输出所有方案。每种方案顺序输出皇后所在的列号,相邻两数之间用空格隔开。如果一组可行方案都没有,输出...题目描述
会下国际象棋的人都很清楚:皇后可以在横、竖、斜线上不限步数地吃掉其他棋子。如何将8个皇后放在棋盘上(有8 * 8个方格),使它们谁也不能被吃掉!这就是著名的八皇后问题。
输入
一个整数n( 1 < = n < = 10 )
输出
每行输出对应一种方案,按字典序输出所有方案。每种方案顺序输出皇后所在的列号,相邻两数之间用空格隔开。如果一组可行方案都没有,输出“no solute!”
样例输入
4
样例输出
2 4 1 3
3 1 4 2分析
n皇后问题实际上是一个全排列+筛选的问题,n皇后会生成一个数组,数组下标表示第几列,而数组内容表示第几行,比如四皇后排列2413表示如图所示
n皇后的是否合法的判断条件是是否有两个皇后在一条对角线上。是否在对角线上,可以通过判断,两个皇后的行列位置差是否相等,即两者行相减的绝对值和列相减的绝对值是否相等,来判断是否在对角线上。
因此,这道题的思路是给出n个数的所有排列组合,然后对这些全排列进行判断,合法的话,计数器+1,打印出排列顺序。代码
#include <iostream> #include <algorithm> #include <cmath> using namespace std; int arr[10]={0}; bool isLegal(int arr[],int n)//判断是否合法 { for(int i=1;i<=n;i++) { for(int j=i+1;j<=n;j++) { if(abs(i-j)==abs(arr[i]-arr[j]))//判断是否在对角线上 return false; } } return true; } void showArray(int arr[],int n)//输出排列结果 { for(int i=1;i<=n;i++) { cout<<arr[i]<<" "; } cout<<endl; } int main(){ int n; while(cin>>n) { int cnt=0; for(int i=1;i<=n;i++) { arr[i]=i; } do{ if(isLegal(arr,n)){ cnt++; showArray(arr,n); } }while(next_permutation(arr+1,arr+n+1));//全排列 if(cnt==0) cout<<"no solute!"<<endl; } return 0; }
-
8皇后问题 8皇后问题 8皇后问题
2008-11-16 16:30:358皇后问题 8皇后问题 8皇后问题 -
数据结构课程设计报告-8皇后问题.doc
2021-10-06 07:51:29数据结构课程设计报告-8皇后问题.doc -
数据结构课程设计报告_8皇后问题.doc
2021-10-04 22:14:55数据结构课程设计报告_8皇后问题.doc -
【doc】用回溯和概率相结合的算法讨论8皇后问题.doc
2022-05-08 19:26:22【doc】用回溯和概率相结合的算法讨论8皇后问题.doc -
自学Java day6 解决8皇后问题 从jvav到架构师
2022-04-01 21:34:348皇后问题是一种经典算法问题。 问题表述为:在8×8格的国际象棋上摆放8个皇后,使其不能互相攻击,即任意两个皇后都不能处于同一行、同一列或同一斜线上,问有多少种摆法。高斯认为有76种方案。1854年在柏林的象棋... -
C实现8皇后问题拓展至n皇后问题
2013-11-19 17:01:488皇后问题和由他推广得到的N皇后问题。题目来源于国际象棋的玩法,因为皇后所在的位置可以纵向、横向、两个斜向四个方向的“捕捉”,所以8皇后问题就是要求如何布置8个皇后在8*8的棋盘上而使他们互相无法“捕捉”。... -
java 8皇后问题
2015-08-29 10:58:01java解决8皇后问题,swing做的图形演示界面。看了回朔算法,简洁的让人震撼,很有感触,就做了个演示界面。