万网注册的域名怎么建设网站,WordPress底部添加版权注明,响应式网站如何做的,杭州vi设计策划N皇后问题 一、问题描述二、示例2.1 四皇后的2个可行解2.2 过程图示 三、问题分析3.1涉及到的概念递归回溯 3.2 分析 四、 代码实现4.1 实现思路宏观#xff1a;微观#xff1a; 4.2 递归函数NS图4.3 代码 一、问题描述
1、按照国际象棋的规则#xff0c;皇后可以攻击与之处… N皇后问题 一、问题描述二、示例2.1 四皇后的2个可行解2.2 过程图示 三、问题分析3.1涉及到的概念递归回溯 3.2 分析 四、 代码实现4.1 实现思路宏观微观 4.2 递归函数NS图4.3 代码 一、问题描述
1、按照国际象棋的规则皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。 2、n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上并且使皇后彼此之间不能相互攻击。
二、示例
2.1 四皇后的2个可行解 2.2 过程图示
以四皇后为例展示寻找一种可行解的过程
三、问题分析
3.1涉及到的概念
递归
自己调自己,在方法中调用方法本身。 使用递归需要注意 1、递归要有出口不能是死循环死循环会造成栈溢出。 2、递归次数不宜过多过多也会有栈溢出的问题。
回溯
回溯法是一种解决问题的算法它会尝试每一种可能的解决方案来找到最佳解。
3.2 分析
回溯法一般通过递归实现。在n皇后问题中我们可以从第一行开始每行放置皇后检查该皇后是否与之前的皇后冲突如果没有则放置下一行的皇后如果发现无解则回溯到上一行重新尝试。
回溯用递归的方式去控制for嵌套的层数4×4递归4层每一层有一个for循环遍历每一层对应的位置。时间复杂度和嵌套for循环一致。
四、 代码实现
4.1 实现思路
宏观
使用深度搜索的方法按照先行后列的顺序查看每一个位置是否满足条件。
微观
定义二维数组表示棋盘定义一个变量n表示几个皇后定义一个方法用来判断当前摆放的皇后是否与之前的皇后冲突同列、左上方右上方)冲突返回0否则返回1表示此位置可以放置皇后。定义一个递归函数尝试在当前行放置皇后。
这里给一个回溯代码模板
if(终止条件){收集结果return;
}for(遍历本层集合中的元素){处理节点递归回溯撤销处理结果
}4.2 递归函数NS图 4.3 代码
package com.lsn.NQueen;public class NQueens {// 定义一个二维数组表示棋盘int[][] board;// 定义一个变量表示几个皇后int n;// 构造函数初始化棋盘和npublic NQueens(int n) {board new int[n][n];this.n n;}// 判断当前摆放的皇后是否与之前的皇后冲突public boolean isSafe(int row, int col) {int i, j;// 检查当前列是否有皇后for (i 0; i row; i) {if (board[i][col] 1) {return false;}}// 检查左上方是否有皇后for (i row, j col; i 0 j 0; i--, j--) {if (board[i][j] 1) {return false;}}// 检查右上方是否有皇后for (i row, j col; i 0 j n; i--, j) {if (board[i][j] 1) {return false;}}// 如果都没有冲突则返回truereturn true;}// 递归函数尝试在当前行放置皇后public boolean solve(int row) {// 如果所有行都已经摆放完毕则返回true终止条件收集结果if (row n) {return true;}// 尝试在当前行的每一列放置皇后单层逻辑处理节点for (int col 0; col n; col) {// 判断当前位置是否安全if (isSafe(row, col)) {// 如果安全则将皇后放置在当前位置board[row][col] 1;// 递归调用solve函数尝试在下一行放置皇后if (solve(row 1)) {return true;}// 如果下一行无法放置皇后则回溯到当前行重新尝试放置皇后撤销处理节点的情况board[row][col] 0;}}// 如果当前行的每一列都无法放置皇后则返回falsereturn false;}// 打印棋盘public void printBoard() {for (int i 0; i n; i) {for (int j 0; j n; j) {System.out.print(board[i][j] );}System.out.println();}}public static void main(String[] args) {// 创建一个NQueens对象并初始化规模为8NQueens nQueens new NQueens(3);// 调用solve函数尝试解决N皇后问题if (nQueens.solve(0)) {// 如果找到了解则打印棋盘nQueens.printBoard();} else {// 如果没有找到解则打印无解System.out.println(No solution found.);}}
}
