四皇后问题、八皇后问题(递归、回溯法
问题要求思路算法结果四皇后执行过程八皇后结果
问题
四皇后问题是一张四乘四的棋盘,在棋盘中放四颗棋子,要求如下:任意两个皇后都不能处在同一行、同一列 任意两个皇后都不能处在同一斜线上(主斜线、反斜线)。 四皇后是八皇后的衍生版本,其原理都是一样的。八皇后说的是在8×8的国际棋盘上摆放8个皇后,使其不能互相攻击,即任意两个皇后都不能处于同一行、同一列或同一斜线上,问有多少种摆法?八皇后一共有92种解法。而四皇后是在一个4×4的棋盘上摆放4个皇后。
要求
任意两个皇后都不能处在同一行、同一列任意两个皇后都不能处在同一斜线上(主斜线、反斜线)
思路
定义一个数组a[20],a[i]=j表示第i个皇后放在第i行第j列。函数issafe()用于判断当前位置是否可选(在同一列、同一斜线,返回0;否则,返回1,表示可选函数search()用于输出结果并判断,用到了递归中的回溯法。
![在这里插入图片描述](https://img-blog.csdnimg.cn/20200503230412736.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzgwOTU0NQ==,size_16,color_FFFFFF,t_70)
算法
#include
using namespace std;
int a[20]={-1},flag=0,count=0;//判断当前位置是否可选(在同一列、同一斜线,返回0;否则,返回1,表示可选
int issafe(int row,int col)//row表示当前将要选的行,cow表示当前将要选的列
{
for(int k=0;k if(i-1==n-1&&flag)
{
++count;
for(int t=0;t
//cout
int n;
cin>>n;
search(0,n);
cout |