-
2021-04-21 08:16:24
这是递归版本,随后会给出其他版本
function Queens
% 8皇后问题的递归法求解
sol = 1; % 解的个数
queen = zeros(8); % 8*8的棋盘
saferows = true(1,8); % 用来表示每一行是否是安全位置
safeleftdiag = true(1,15); % 用来表示左对角是否安全,在同一个左对角上的元素满足i1+j1 = i2 + j2;
saferightdiag = true(1,15);% 用来表示左对角是否安全,在同一个右对角上的元素满足i1-j1 = i2 - j2;
trycol(1); % 检查第一列是否可以放置皇后
% 该函数用来检查第col列是否可以方位皇后
function trycol(col)
% 对行循环,一行一行的去放
for row = 1 : 8
% 检查第row行第col列的位置是否安全
if safe(row,col)
% 如果安全,该位置被占据,该行和对角不安全
[saferows(row),safeleftdiag(row + col - 1),saferightdiag(row - col + 8)]=deal(false);
queen(row,col) = 1;
% 如果是第8列,说明解完成,输出
if col == 8
fprintf('第%d个解\n',sol);
disp(queen);
sol = sol + 1;
else % 否则,去试探下一列
trycol(col + 1);
end
% 判断完该行,就去判断下一行,应该清除该行的占据信息和安全信息
[saferows(row),safeleftdiag(row + col - 1),saferightdiag(row - col + 8)]=deal(true);
queen(row,col) = 0;
end
end
end
% 该函数用来检查第row行第col列的位置是否安全
function y = safe(row,col)
% 检查该列的行,左对角,右对角是否安全
y = saferows(row) & safeleftdiag(row + col - 1) & saferightdiag(row - col + 8);
end
end
更多相关内容 -
实验四:prolog求解八皇后问题(人工智能实验报告)
2020-12-25 08:51:47包含prolog求解修八皇后问题的实验报告、源代码及试验运行截图 -
利用C语言解决八皇后问题以及解析
2021-01-01 01:59:22八皇后问题是一个古老而著名的问题。该问题是19世纪著名的数学家高斯1850年提出:在一个8*8国际象棋盘上,有8个皇后,每个皇后占一格;要求皇后之间不会出现相互“攻击”的现象,即不能有两个皇后处在同一行、同一列... -
广度优先+深度优先求解八皇后问题.zip
2019-05-31 23:01:21分别采用广度优先遍历和深度优先遍历实现八皇后的求解问题。源代码(.java)文件 -
python八皇后问题的解决方法
2020-12-23 16:30:54本文为大家分享了python八皇后问题的解决方法,供大家参考,具体内容如下 题目: 给定一个 N*N 正方形棋盘,在上面放置 N个棋子,又叫皇后,使每两个棋子都不在同一条横线上、竖线上、斜线上。一般我们都讨论8皇后... -
八皇后问题的两个高效的算法
2021-01-07 02:50:15一、 求解八皇后问题是算法中回溯法应用的一个经典案例 回溯算法也叫试探法,它是一种系统地搜索问题的解的方法。回溯算法的基本思想是:从一条路往前走,能进则进,不能进则退回来,换一条路再试。 在现实中,有... -
C语言基于回溯算法解决八皇后问题的方法
2020-08-27 08:06:21主要介绍了C语言基于回溯算法解决八皇后问题的方法,简单描述了八皇后问题,并结合实例形式分析了C语言使用回溯算法解决八皇后问题的相关操作技巧,需要的朋友可以参考下 -
C语言八皇后问题解决方法示例【暴力法与回溯法】
2020-08-28 07:55:34主要介绍了C语言八皇后问题解决方法,简单描述了八皇后问题并结合实例形式分析了C语言基于暴力法与回溯法解决八皇后的具体操作技巧,需要的朋友可以参考下 -
Python解决八皇后问题示例
2020-09-20 14:14:24主要介绍了Python解决八皇后问题,简单描述了八皇后问题的原理并结合实例形式分析了Python基于递归算法解决八皇后问题的相关操作技巧,需要的朋友可以参考下 -
八皇后问题-递归求解
2019-03-25 15:40:29八皇后问题 在国际象棋的棋盘上,按照国际象棋的规则,摆放8个皇后,使之“和平共处”。如图所示,在3-D上有一个皇后,则绿色区域中都不能再放置皇后了。 最暴力的方法就是使用八个for,但是很明显,这种方法效率...八皇后问题
在国际象棋的棋盘上,按照国际象棋的规则,摆放8个皇后,使之“和平共处”。如图所示,在3-D上有一个皇后,则绿色区域中都不能再放置皇后了。
最暴力的方法就是使用八个for,但是很明显,这种方法效率太低。
对于放置了皇后的位置,仔细观察棋盘可以发现每一列(行)只能有一个皇后,每一个主(次)对角线上也只能有一个皇后,这样需要标记:行-row,列-col,主对角线-(n+row-col),次对角线-(row+col)注意:关于对角线的一点说明:
这里以次对角线为例:数字相同的表示一条次对角线,所以对于一个8x8的棋盘来说,一共有2x8-1条次对角线。
流程图:
基于流程图,利用递归的思想,c++实现如下,这里的皇后的个数是在主函数中设置的8,个数可以改,但意义不大。。。。。
在递归回溯的过程中清空了标记,是为了继续搜索,找到所有的解。#include <iostream> #include <vector> using namespace std; class EightQueen { public: EightQueen(int nQueen) { this->nQueen = nQueen; inColumn.resize(nQueen, false); mainDiagonal.resize(2 * nQueen - 1, false); minorDiagonal.resize(2 * nQueen - 1, false); } ~EightQueen() {} int process() { int *path = new int[nQueen]; calculate(path, 0); delete[] path; return 0; } void calculate(int *path, int row) { if (row == nQueen) { solution.push_back(vector<int>(path, path + nQueen)); return; } for (int col = 0; col < nQueen; col++) { if (canLay(row, col)) {//当前位置可放置 path[row] = col;//标记放置的位置 inColumn[col] = true;//当前皇后所在列 minorDiagonal[row+col] = true;//皇后所在位置的横纵坐标之和对应的次对角线 mainDiagonal[nQueen-1+row-col] = true;//皇后所在位置的横纵坐标之和对应的主对角线 calculate(path, row + 1);//下一行上的皇后 //break;//去掉搜索所有的解! inColumn[col] = false; minorDiagonal[row+col] = false; mainDiagonal[nQueen-1+row-col] = false; } } } bool canLay(int row, int col) { return !inColumn[col] && !minorDiagonal[row + col] && !mainDiagonal[nQueen - 1 + row - col]; } void print() { for (int i = 0; i < solution.size(); i++) { cout << "solution " << i << " : " << endl; for (int row = 0; row < nQueen; row++) { for (int col = 0; col < solution[i][row]; col++) { cout << "O "; } cout << "X "; for (int col = solution[i][row]+1; col < nQueen; col++) { cout << "O "; } cout << endl; } cout << endl << endl; } } private: int nQueen; vector<bool> inColumn; vector<bool> mainDiagonal; vector<bool> minorDiagonal; vector<vector<int> > solution; }; int main() { EightQueen queen(8); queen.process(); queen.print(); return 0; }
-
python基于右递归解决八皇后问题的方法
2020-12-25 14:01:51本文实例讲述了python基于右递归解决八皇后问题的方法。分享给大家供大家参考。具体分析如下: 凡是线性回溯都可以归结为右递归的形式,也即是二叉树,因此对于只要求一个解的问题,采用右递归实现的程序要比回溯法... -
Python解决八皇后问题并输出可视化结果
2021-01-20 11:22:15八皇后问题:八皇后问题,是一个...最近在学习回溯递归的算法,所以试着用Python实现八皇后的求解问题,刚开始总是走不通,后来发现是走到死节点后,回溯需要将前一步的操作还原,这是我学习过程中一直不太好理解的一 -
C语言八皇后问题所有解
2019-11-05 17:10:45C语言求解出八皇后所有解,稍作修改可以推至n皇后问题 -
c代码-八皇后问题求解
2021-07-14 21:15:21c代码-八皇后问题求解 -
python 使用递归回溯完美解决八皇后的问题
2020-09-17 20:00:25今天小编就为大家分享一篇python 使用递归回溯完美解决八皇后的问题,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧 -
遗传算法求解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、... -
Python实现八皇后问题示例代码
2020-09-19 21:05:50主要给大家介绍了关于利用Python实现八皇后问题的相关资料,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧 -
java求解n queques 问题-八皇后问题
2018-06-06 13:14:14利用回溯法求解八皇后问题,从八皇后问题延伸到n皇后问题。利用水平,主对角线,反对角线三个数组简化算法。 使用方法: 输入要求解的n皇后数目,程序自动输出每种具体方案和总的方法数。 -
八皇后问题求解——之递归
2020-07-18 18:27:10八皇后为题概述;解决八皇后为题的步骤;完整代码。 -
八皇后求解问题
2015-06-17 17:54:28八皇后求解问题。 -
knight“八皇后”问题归朔法求解
2014-12-23 11:42:32“八皇后”问题归朔法求解。八皇后问题是一个古老而著名的问题,该问题是十九世纪著名的数学家高斯1850年提出:在8X8格的国际象棋上摆放八个皇后,使其不能互相攻击,即任意两个皇后都不能处于同一行、同一列或同一... -
Python基于生成器迭代实现的八皇后问题示例
2020-09-20 11:34:14主要介绍了Python基于生成器迭代实现的八皇后问题,简单描述了八皇后问题,并结合实例形式分析了Python基于生成器迭代解决八皇后问题的相关操作技巧,需要的朋友可以参考下 -
八皇后问题详细的解法-23页 PPT PDF版.pdf
2020-06-10 23:20:18八皇后问题详细的解法-23页 PPT PDF版.pdf -
拉斯维加斯算法解决八皇后问题
2018-10-10 17:32:56自己根据拉斯维加斯算法,写的一个用来求解八皇后问题的python程序,其中可以自定义棋盘大小,显示程序的执行时间。 -
八皇后问题求解
2014-05-06 17:04:40八皇后问题求解 c#代码例子 递归方法的完整代码 -
人工智能实验二prolog求解八皇后问题.zip
2021-01-08 14:02:25人工智能实验二prolog求解八皇后问题.zip -
C++八皇后问题递归求解
2021-12-27 15:14:15如果该行没有一个位置可以放入,说明之前摆放好的位置有问题,则返回到上一个递归即上一行继续查找新位置,以此类推。如果8行全部找完,则打印输出,打印完成后返回至上一个递归即上一行继续找是否还有合适的位置,...总体思想为一行一行进行判断,判断某一行时,从该行第一个位置开始判断是否能放棋子,如果不能则继续判断下一个位置,如果可以,则代表该行已经找到,进入下一行即进入下一个递归,重复上述操作。如果该行没有一个位置可以放入,说明之前摆放好的位置有问题,则返回到上一个递归即上一行继续查找新位置,以此类推。如果8行全部找完,则打印输出,打印完成后返回至上一个递归即上一行继续找是否还有合适的位置,直到92种全部找到。
#include<iostream> //定义棋盘大小8*8 #define ROW 8 #define COL 8 //八皇后问题递归求解 //统计数量 int num = 0; //判断r行c列位置是否可以放置棋子 bool safe(int r, int c, int** chessboard) { int i, j; //判断列方向有无棋子 for (i = 0; i < ROW; i++) { if (chessboard[i][c] != 0) { return false; } } //判断左上方有无棋子 for (i = r, j = c; i >= 0 && j >= 0; i--, j--) { if (chessboard[i][j] != 0) { return false; } } //判断右下方有无棋子 for (i = r, j = c; i < ROW && j < COL; i++, j++) { if (chessboard[i][j] != 0) { return false; } } //判断右上方有无棋子 for (i = r, j = c; i >= 0 && j < COL; i--, j++) { if (chessboard[i][j] != 0) { return false; } } //判断左下方有无棋子 for (i = r, j = c; i < ROW && j >= 0; i++, j--) { if (chessboard[i][j] != 0) { return false; } } return true; } //递归部分 void iteration(int row, int** chessinput) { int** arr = new int* [8]; for (int i = 0; i < ROW; i++) { arr[i] = new int[8]; } for (int i = 0; i < ROW; i++) { for (int j = 0; j < COL; j++) { arr[i][j] = chessinput[i][j]; } } if (row == 8)//棋盘装满后打印 { cout << "第" << num + 1 << "种结果:" << endl; for (int i = 0; i < ROW; i++) { for (int j = 0; j < COL; j++) { cout << arr[i][j] << " "; } cout << endl; } cout << endl; num++; } else//棋盘未装满,继续装填 { for (int i = 0; i < COL; i++) { if (safe(row, i, arr))//判断是否可以放置棋子 { for (int j = 0; j < COL; j++) { arr[row][j] = 0;//先将该行全部赋值为0 } arr[row][i] = 1;//再将该行安全的那一列赋值为1 iteration(row + 1, arr); } } } for (int i = 0; i < ROW; i++) { delete[] arr[i]; } delete[] arr; } int main() { int** initarr = new int* [8]; for (int i = 0; i < ROW; i++) { initarr[i] = new int[8]; } for (int i = 0; i < ROW; i++) { for (int j = 0; j < COL; j++) { initarr[i][j] = 0; } } iteration(0, initarr); for (int i = 0; i < ROW; i++) { delete[] initarr[i]; } delete[] initarr; return 0; }