[回溯法] 四皇后问题

您所在的位置:网站首页 回溯法求解n皇后问题实验报告 [回溯法] 四皇后问题

[回溯法] 四皇后问题

2023-07-26 00:07| 来源: 网络整理| 查看: 265

四皇后问题、八皇后问题(递归、回溯法 问题要求思路算法结果四皇后执行过程八皇后结果

问题

四皇后问题是一张四乘四的棋盘,在棋盘中放四颗棋子,要求如下:任意两个皇后都不能处在同一行、同一列 任意两个皇后都不能处在同一斜线上(主斜线、反斜线)。 四皇后是八皇后的衍生版本,其原理都是一样的。八皇后说的是在8×8的国际棋盘上摆放8个皇后,使其不能互相攻击,即任意两个皇后都不能处于同一行、同一列或同一斜线上,问有多少种摆法?八皇后一共有92种解法。而四皇后是在一个4×4的棋盘上摆放4个皇后。

要求 任意两个皇后都不能处在同一行、同一列任意两个皇后都不能处在同一斜线上(主斜线、反斜线) 思路 定义一个数组a[20],a[i]=j表示第i个皇后放在第i行第j列。函数issafe()用于判断当前位置是否可选(在同一列、同一斜线,返回0;否则,返回1,表示可选函数search()用于输出结果并判断,用到了递归中的回溯法。

在这里插入图片描述

算法 #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


【本文地址】


今日新闻


推荐新闻


CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3