浙江工业大学算法实验4 回溯法实现报告

回溯分析报告1. 概述回溯分析是一种常用的问题解决方法，在许多领域都有广泛的应用。

回溯分析是一种深度优先搜索的算法，通过尝试所有可能的解决方案来寻找问题的最优解。

在本文档中，我们将详细介绍回溯分析的原理和应用，以及如何使用回溯分析来解决问题。

2. 回溯分析原理回溯分析的基本原理是尝试所有可能的解决方案，并通过逐步迭代的方式来找到最优解。

回溯分析通常包括以下几个步骤：1.定义问题的解空间：确定问题的解空间，即问题的可能解决方案的集合。

2.筛选可行解：根据问题的约束条件筛选出满足条件的可行解。

3.遍历解空间：遍历解空间中的所有可能解，通常使用递归的方式来实现。

4.判断解的有效性：判断每个可能解是否满足问题的要求，如果不满足，则回溯到上一步继续尝试其他解。

5.找到最优解：通过不断地回溯和尝试，找到问题的最优解。

3. 回溯分析的应用回溯分析在许多领域都有广泛的应用，下面分别介绍了几个常见的应用场景：3.1 组合优化问题回溯分析可以用于解决组合优化问题，如旅行商问题（TSP）、背包问题等。

通过尝试所有可能的组合方式，找到最优解决方案。

3.2 图的遍历和搜索回溯分析可以用于图的遍历和搜索问题，如深度优先搜索（DFS）、广度优先搜索（BFS）等。

通过逐步地向前搜索，找到满足条件的解。

3.3 棋盘类问题回溯分析可以用于解决各种棋盘类问题，如八皇后问题、数独等。

通过逐步地摆放棋子或填写数字，找到满足条件的解。

3.4 解数独问题示例下面以解数独问题为例，介绍回溯分析的具体应用：def solve_sudoku(board):if not find_empty_location(board):return Truerow, col = find_empty_location(board)for num in range(1, 10):if is_safe(board, row, col, num):board[row][col] = numif solve_sudoku(board):return Trueboard[row][col] =0return False上面的代码通过递归的方式遍历数独中的每个空格，尝试填入数字，并判断是否满足数独的规则。

实验报告. 基于回溯法的0-1背包等问题实验内容本实验要求基于算法设计与分析的一般过程（即待求解问题的描述、算法设计、算法描述、算法正确性证明、算法分析、算法实现与测试），通过回溯法的在实际问题求解实践中，加深理解其基本原理和思想以及求解步骤。

求解的问题为0-1背包。

作为挑战：可以考虑回溯法在如最大团、旅行商、图的m着色等问题中的应用。

实验目的◆理解回溯法的核心思想以及求解过程（确定解的形式及解空间组织，分析出搜索过程中的剪枝函数即约束函数与限界函数）；◆掌握对几种解空间树（子集树、排列数、满m叉树）的回溯方法；◆从算法分析与设计的角度，对0-1背包等问题的基于回溯法求解有进一步的理解。

环境要求对于环境没有特别要求。

对于算法实现，可以自由选择C, C++或Java，甚至于其他程序设计语言如Python等。

实验步骤步骤1：理解问题，给出问题的描述。

步骤2：算法设计，包括策略与数据结构的选择。

步骤3：描述算法。

希望采用源代码以外的形式，如伪代码或流程图等；步骤4：算法的正确性证明。

需要这个环节，在理解的基础上对算法的正确性给予证明；步骤5：算法复杂性分析，包括时间复杂性和空间复杂性；步骤6：算法实现与测试。

附上代码或以附件的形式提交，同时贴上算法运行结果截图；步骤7：技术上、分析过程中等各种心得体会与备忘，需要言之有物。

说明：步骤1-6在“实验结果”一节中描述，步骤7在“实验总结”一节中描述。

实验结果步骤1：问题描述。

给定 n个物品，其中第 i 个物品的重量为w i ，价值为 v i 。

有一容积为 W 的背包，要求选择一些物品放入背包，使得物品总体积不超过W的前提下，物品的价值总和最大。

0-1背包问题的限制是，每种物品只有一个，它的状态只有放和不放两种。

0-1背包问题是特殊的整数规划问题，其可用数学语言表述为：对于给定 n >0,W >0,v,w (v i ,w i >0,1≤i ≤n)，找出一个 n 元0-1向量x =( x 1, x 2,⋯, x n ) 其中x i ∈{0,1},1≤i ≤n ，使得∑v i n i=1x i 最大，并且∑w i n i=1x i ≤W ，即：max x (∑v i ni=1x i ) s.t.∑w i ni=1x i ≤W, x i ∈{0,1},1≤i ≤n步骤2：算法设计，即算法策略与数据结构的选择。

实验报告
（2015/ 2016学年第一学期）
课程名称算法设计与分析
实验名称回溯法
实验时间2016年5月5日指导单位计算机软件学院
指导教师费宁
学生姓名罗熊班级学号B14050123
学院(系)自动化专业自动化
实验报告
NQUEENS(0);
printf("%d", sum);
system("pause");
return 0;
}：
实验结果：
四、实验小结
回溯法以深度优先次序生成状态空间树中的结点，并使用剪纸函数减少实际生成的结点数，回溯法是一种广泛适用的算法设计技术。

是要问题的解是元组形式，可用状态空间树描述，并采用判定函数识别答案结点，就能采用回溯法求解。

回溯法使用约束函数剪去不含可行解的分枝。

当使用回溯法求最优化问题时，需要设计界限函数用于剪去分枝。

五、指导教师评语
成绩批阅人日期。

实验报告一、实验名称：回溯法求解‎N皇后问题‎（Java实‎现）二、学习知识：回溯法：也称为试探‎法，它并不考虑‎问题规模的‎大小，而是从问题‎的最明显的‎最小规模开‎始逐步求解‎出可能的答‎案，并以此慢慢‎地扩大问题‎规模，迭代地逼近‎最终问题的‎解。

这种迭代类‎似于穷举并‎且是试探性‎的，因为当目前‎的可能答案‎被测试出不‎可能可以获‎得最终解时‎，则撤销当前‎的这一步求‎解过程，回溯到上一‎步寻找其他‎求解路径。

为了能够撤‎销当前的求‎解过程，必须保存上‎一步以来的‎求解路径，这一点相当‎重要。

三、问题描述N皇后问题‎：在一个 N * N 的国际象棋‎棋盘中，怎样放置 N 个皇后才能‎使N 个皇后之间‎不会互相有‎威胁而共同‎存在于棋局‎中，即在 N * N 个格子的棋‎盘中没有任‎何两个皇后‎是在同一行‎、同一列、同一斜线上‎。

深度优先遍‎历的典型案‎例。

四、求解思路1、求解思路：最容易想到‎的方法就是‎有序地从第‎1列的第 1 行开始，尝试放上一‎个皇后，然后再尝试‎第2 列的第几行‎能够放上一‎个皇后，如果第 2 列也放置成‎功，那么就继续‎放置第 3 列，如果此时第‎3列没有一行‎可以放置一‎个皇后，说明目前为‎止的尝试是‎无效的（即不可能得‎到最终解），那么此时就‎应该回溯到‎上一步（即第 2 步），将上一步（第 2 步）所放置的皇‎后的位置再‎重新取走放‎在另一个符‎合要求的地‎方…如此尝试性‎地遍历加上‎回溯，就可以慢慢‎地逼近最终‎解了。

2、需要解决的‎问题：如何表示一‎个N * N 方格棋盘能‎够更有效？怎样测试当‎前所走的试‎探路径是否‎符合要求？这两个问题‎都需要考虑‎到使用怎样‎的数据结构‎，使用恰当的‎数据结构有‎利于简化编‎程求解问题‎的难度。

3、我们使用以‎下的数据结‎构：int colum‎n[col] = row 表示第 col 列的第 row 行放置一个‎皇后boole‎an rowEx‎i sts[i] = true 表示第 i 行有皇后boole‎an a[i] = true 表示右高左‎低的第 i 条斜线有皇‎后（按→↓顺序从1~ 2*N -1 依次编号）boole‎an b[i] = true 表示左高右‎低的第 i 条斜线有皇‎后（按→↑顺序从1~ 2*N -1 依次编号）五、算法实现对应这个数‎据结构的算‎法实现如下‎：1.**2. * 回溯法求解‎N 皇后问题3. * @autho‎r haoll‎o yin4. */5.publi‎c class‎N_Que‎e ns {6.7.// 皇后的个数‎8. priva‎t e int queen‎s Num = 4;9.10.// colum‎n[i] = j表示第 i 列的第 j 行放置一个‎皇后11. priva‎t e int[] queen‎s = new int[queen‎s Num + 1];12.13.// rowEx‎i sts[i] = true 表示第 i 行有皇后14. priva‎t e boole‎a n[] rowEx‎i sts = new boole‎a n[queen‎sNum + 1];15.16.// a[i] = true 表示右高左‎低的第 i 条斜线有皇‎后17. priva‎t e boole‎a n[] a = new boole‎a n[queen‎s Num * 2];18.19.// b[i] = true 表示左高右‎低的第 i 条斜线有皇‎后20. priva‎t e boole‎a n[] b = new boole‎a n[queen‎s Num * 2];21.22.// 初始化变量‎23. priva‎t e void init() {24. for (int i = 0; i < queen‎s Num + 1; i++) {25. rowEx‎i sts[i] = false‎;26. }27.28. for(int i = 0; i < queen‎s Num * 2; i++) {29. a[i] = b[i] = false‎;30. }31. }32.33.// 判断该位置‎是否已经存‎在一个皇后‎,存在则返回‎true34. priva‎t e boole‎a n isExi‎s ts(int row, int col) {35. retur‎n (rowEx‎i sts[row] || a[row + col - 1]|| b[queen‎s Num + col - row]);36. }37.38.// 主方法：测试放置皇‎后39. publi‎c void testi‎n g(int colum‎n) {40.41.// 遍历每一行‎42. for (int row = 1; row < queen‎s Num + 1; row++) {43.// 如果第 row 行第 colum‎n列可以放置‎皇后44. if (!isExi‎s ts(row, colum‎n)) {45.// 设置第 row 行第 colum‎n列有皇后46. queen‎s[colum‎n] = row;47.// 设置以第 row 行第 colum‎n列为交叉点‎的斜线不可‎放置皇后48. rowEx‎i sts[row] = a[row + colum‎n - 1] = b[queen‎s Num + colum‎n - row] = true;49.50.// 全部尝试过‎，打印51. if(colum‎n == queen‎s Num) {52. for(int col = 1; col <= queen‎s Num; col++) {53. Syste‎m.out.print‎("("+col +"," + queen‎s[col] + ") ");54. }55. Syste‎m.out.print‎l n();56. }else {57.// 放置下一列‎的皇后58. testi‎n g(colum‎n + 1);59. }60.// 撤销上一步‎所放置的皇‎后，即回溯61. rowEx‎i sts[row] = a[row + colum‎n - 1] = b[queen‎s Num + colum‎n - row] = false‎;62. }63. }64. }65.66.//测试67. publi‎c stati‎c void main(Strin‎g[] args) {68. N_Que‎e ns queen‎= new N_Que‎e ns();69. queen‎.init();70.// 从第 1 列开始求解‎71. queen‎.testi‎n g(1);72. }73.}六、运行结果当N = 8 时，求解结果如‎下（注：横坐标为列数，纵坐标为行数）：(1,1) (2,5) (3,8) (4,6) (5,3) (6,7) (7,2) (8,4)1.(1,1) (2,6) (3,8) (4,3) (5,7) (6,4) (7,2) (8,5)2.(1,1) (2,7) (3,4) (4,6) (5,8) (6,2) (7,5) (8,3)3.... ...4.... ...5.(1,8) (2,2) (3,4) (4,1) (5,7) (6,5) (7,3) (8,6)6.(1,8) (2,2) (3,5) (4,3) (5,1) (6,7) (7,4) (8,6)7.(1,8) (2,3) (3,1) (4,6) (5,2) (6,5) (7,7) (8,4)8.(1,8) (2,4) (3,1) (4,3) (5,6) (6,2) (7,7) (8,5)当N = 4 时，求解结果如‎下：1.(1,2) (2,4) (3,1) (4,3)2.(1,3) (2,1) (3,4) (4,2)七、实验小结：1、根据问题选‎择恰当的数‎据结构非常‎重要，就像上面 a 、b 标志数组来‎表示每一条‎斜线的编号‎顺序以及方‎向都相当重‎要。

算法详解之回溯法具体实现理论辅助：回溯算法也叫试探法，它是⼀种系统地搜索问题的解的⽅法。

回溯算法的基本思想是：从⼀条路往前⾛，能进则进，不能进则退回来，换⼀条路再试。

⽤回溯算法解决问题的⼀般步骤为：1、定义⼀个解空间，它包含问题的解。

2、利⽤适于搜索的⽅法组织解空间。

3、利⽤深度优先法搜索解空间。

4、利⽤限界函数避免移动到不可能产⽣解的⼦空间。

问题的解空间通常是在搜索问题的解的过程中动态产⽣的，这是回溯算法的⼀个重要特性。

还是那个基调，不喜欢纯理论的东西，喜欢使⽤例⼦来讲诉理论，在算法系列总结：动态规划(解公司外包成本问题）的那⼀节⾥⾯我们举得是经典的0-1背包问题，在回溯算法⾥⾯也有⼀些很经典的问题，当然，动态规划的0-1背包问题其实也可以使⽤回溯算法来解。

在诸如此类似的求最优解的问题中，⼤部分其实都可以⽤回溯法来解决，可以认为回溯算法⼀个”通⽤解题法“，这是由他试探性的⾏为决定的，就好⽐求⼀个最优解，我可能没有很好的概念知道怎么做会更快的求出这个最优解，但是我可以尝试所有的⽅法，先试探性的尝试每⼀个组合，看看到底通不通，如果不通，则折回去，由最近的⼀个节点继续向前尝试其他的组合，如此反复。

这样所有解都出来了，在做⼀下⽐较，能求不出最优解吗？例⼦先⾏，现在我们来看看经典的N后问题问题描述：在n*n格的棋盘上放置彼此不受攻击的n个皇后。

按照国际象棋的规矩，皇后可以攻击与之处在同⼀⾏或同⼀列或同⼀斜线上的棋⼦。

n后问题等价于在n*n格的棋盘上⽅置n个皇后，任何2个皇后不放在同⼀⾏或同⼀列或同⼀斜线上。

我们需要求的是可放置的总数。

基本思路：⽤n元组x[1；n]表⽰n后问题的解。

其中，x[i]表⽰皇后i放置在棋盘的第i⾏的第x[i]列。

由于不容许将2个皇后放在同⼀列上，所以解向量中的x[i]互不相同。

2个皇后不能放在同⼀斜线上是问题的隐约束。

对于⼀般的n后问题，这⼀隐约束条件可以化成显约束的形式。

如果将n*n 格的棋盘看做⼆维⽅阵，其⾏号从上到下，列号从左到右依次编号为1,2，...n。

《算法设计与分析》实验报告实验三回溯法3.迷宫问题一天Luna在森林里探险的时候不小心走入了一个迷宫，迷宫可以看成是由n * n的格点组成，每个格点只有2种状态，. 和#，前者表示可以通行后者表示不能通行。

同时当Luna处在某个格点时，她只能移动到东南西北(或者说上下左右)四个方向之一的相邻格点上，Luna想要从点A走到点B（不能走出迷宫）。

如果起点或者终点有一个不能通行(为#)，则看成无法办到。

[输入]第1行是测试数据的组数k，后面跟着k组输入。

每组测试数据的第1行是一个正整数n (1 <= n <= 100)，表示迷宫的规模是n * n 的。

接下来是一个n * n的矩阵，矩阵中的元素为. 或者#。

再接下来一行是4个整数ha, la, hb, lb，描述A处在第ha行, 第la列，B处在第hb 行, 第lb列。

注意到ha, la, hb, lb全部是从0开始计数的。

1.八皇后问题1.1解题思路八皇后问题的解法，很简单的解法。

通过回溯实现枚举。

对于当前行，尝试是否可在当前列放置皇后，然后进入下一行的尝试，同时尝试完毕以后，要将当前行回复（回溯），来进行下一次尝试。

到达最后一行的时候，即递归结束条件，打印结果即可。

1.2程序运行情况1.3所有的皇后解见附录。

（毕竟92个解...）1.4程序源码（含注释）2. 24点问题2.1 解题思路这题虽然使用dfs很简单，但是有一点思维在里面。

我很惭愧，自己没有想出来怎么如意的独立AC此题。

遇到的最大的问题——如何插入括号？枚举插入、和运算符一同排列都不靠谱。

解决方法是：用同等的办法转化。

每一次从待组合的是数字中，任取两个数，随机用运算符计算完毕后，再放回去。

下一次计算，再次重复这个过程，可以等价为有括号的运算方式了。

遇到第二个问题——如何实现这种“任取两个数”的选择方式。

这里就直接体现出了我个人能力的不足。

居然没想到。

尝试使用STL的set，但是没成功。

0-1背包问题(回溯法)实验报告姓名：学号：指导老师：一．算法设计名称：0-1背包问题（回溯法）二.实验内容问题描述:给定n 种物品和一背包。

物品i 的重量是w i ，其价值为v i ，背包的容量为C 。

问应如何选择装入背包的物品，使得装入背包中物品的总价值最大?在选择装入背包的物品时，对每种物品i 只有两种选择，即装入背包或不装入背包。

不能将物品装入背包多次，也不能只装入部分的物品。

三.实验目的1.运用回溯思想，设计解决上述问题的算法，找出最大背包价值的装法。

2.掌握回溯法的应用四．算法设计：问题求解思路1.由0-1背包问题的最优子结构性质，建立计算m[i][j]的递归式如下：i i i w j w j j i m i v w j i m j i m j i m <≤≥⎩⎨⎧-+---=0],1[]}[],1[],,1[max{),(2.查找装入背包物品的回溯函数：从0-1二叉树的根开始搜索：若是叶子节点，则判断此时的价值是否比当前最优的价值大，否则将之替换，并获得最优解向量且返回；若不是叶子节点，则向左右子树搜索，先改变当前的数据状态，递归的调用自己，然后恢复数据状态表示回溯。

3.边界函数bound主要是当还未搜索到叶子节点时，提前判断其子树是否存可能存在更优的解空间，否则进行回溯，即裁剪掉子树的解空间。

关键数据结构及函数模块：（Backtrack.h ）#ifndef __BACKTRACK_H__#define __BACKTRACK_H__class BP_01_P{public:∑=ni i i x v 1max ⎪⎩⎪⎨⎧≤≤∈≤∑=n i x C x w i n i i i 1},1,0{1BP_01_P(int w,int n):m_Sum_weitht(0),m_Number(0) {m_Sum_weitht=w;m_Number=n;bestHav=0;bestVal=0;curVal=0;curHav=0;m_hav=new int[n];m_val=new int[n];temop=new int[n];option=new int[n];}~BP_01_P(){delete []m_hav;delete []m_val;delete []temop;delete []option;}void traceBack(int n);int bound(int n);void printBestSoulation();int *m_hav;//每个物品的重量int *m_val;//每个物品的价值int *temop;//01临时解int *option;//01最终解int bestHav;//最优价值时的最大重量int bestVal;//最优的价值int curVal;//当前的价值int curHav;//当前的重量private:int m_Sum_weitht;//背包的总容量int m_Number;//物品的种类};#endif __BACKTRACK_H__五：主要的算法代码实现：（Backtrack.cpp）边界函数：bound( )int BP_01_P::bound(int n){int hav_left=m_Sum_weitht-curHav;int bo=curVal;while(n<m_Number && m_hav[n]<=hav_left){hav_left-=m_hav[n];bo+=m_val[n];n++;}if(n<m_Number){bo+=m_val[n]*hav_left/m_hav[n];//bo+=hav_left;}return bo;}回溯递归函数：traceBack( )void BP_01_P::traceBack(int n){if(n>=m_Number){if(curVal>=bestVal){bestVal=curVal;for(int i=0;i<n;i++){option[i]=temop[i];}return ;}}if(curHav+m_hav[n]<=m_Sum_weitht)//向左子树搜索 {curHav=curHav+m_hav[n];curVal=curVal+m_val[n];temop[n]=1;//标记要选择这个物品traceBack(n+1);curHav=curHav-m_hav[n];curVal=curVal-m_val[n];}if(bound(n+1)>bestVal)//向右子树搜索{temop[n]=0;//标记要丢弃这个物品traceBack(n+1);}}主控函数：(main.cpp)#include <iostream>#include "Backtrack.h"using namespace std;int main(){int number,weigth;cout<<"包的总容量:";cin>>weigth;cout<<"物品的种类:";cin>>number;BP_01_P *ptr=new BP_01_P(weigth,number);cout<<"各种物品的重量:"<<endl;for(int i=0;i<number;i++)cin>>ptr->m_hav[i];cout<<"各种物品的价值:"<<endl;for(i=0;i<number;i++)cin>>ptr->m_val[i];ptr->traceBack(0);ptr->printBestSoulation();cout<<"总重量:"<<ptr->bestHav<<"\t总价值:"<<ptr->bestVal<<endl;return 0;}六：算法分析采用回溯法解决0-1背包问题，明显比动态规划法更优良。

《算法设计与分析》作业作业四+五回溯法+分支限界法1. 二元最大连通块搜索因为下了场大雨，青蛙王子高兴坏了，它有机会重新划定自己的王国范围。

在下图中，空白区域表示积水的地方，青蛙王子需要找到一块最大的连续积水区域（上下或左右相连）作为自己的新领地。

2. 三元最大连通块搜索小明在玩一种消除游戏。

游戏中有一个长方形的区域，被RGB(红绿蓝)三种颜色的小球充满。

要求每次找出当前最大连通区域（上下左右相邻同种颜色即可算作连通），进行消除。

####.######.######.#####the ans is 712 8..#......##....#.#....#..###.#......#.....##.#...#....#..##..#.####..#......#......#......#.....the ans is 181.3 程序运行情况1.4 程序源码（含注释）#include"bits/stdc++.h"using namespace std;#define inf 999//代码下标从0始，输入时.为可走，#为不可走int n,m;//行、列int ans,now;//最大连通数，当前搜索时连通数char e[inf][inf];//地图int book[inf][inf];//标记地图int pos[4][2]={-1,0,1,0,0,1,0,-1};//方位，上下右左void read()//输入数据{printf("input the row and the column of the map:"); scanf("%d%d",&n,&m);printf("now input the map:\n");for(int i=0;i<n;i++)scanf("%s",e[i]);2.4 程序源码（含注释）#include"bits/stdc++.h"using namespace std;#define inf 999//代码下标从0始int n,m;//行、列int ans,now;//最大连通数，当前搜索时连通数int ans_x,ans_y;//最大连通对应的字符char e[inf][inf];//地图int book[inf][inf];//标记地图int pos[4][2]={-1,0,1,0,0,1,0,-1};//方位，上下右左void read()//输入数据{printf("input the row and the column of the map:");scanf("%d%d",&n,&m);printf("now input the map:\n");for(int i=0;i<n;i++)scanf("%s",e[i]);。

回溯算法的实现回溯算法：从⼀条路往前⾛，能进则进，不能进则退回来，换⼀条路再试。

（以深度优先⽅式搜索）回溯法是⼀种选优搜索法，按选优条件向前搜索，以达到⽬标。

但当探索到某⼀步时，发现原先选择并不优或达不到⽬标，就退回⼀步重新选择。

使⽤回溯法求任⼀个解时，只要搜索到问题的⼀个解就可以结束⽤回溯法求问题的所有解时，要回溯到根，且根结点的所有可⾏的⼦树都要已被搜索遍才结束。

回溯法的实现⽅法有两种：递归和递推（也称迭代）。

⼀般来说，⼀个问题两种⽅法都可以实现，只是在算法效率和设计复杂度上有区别。

递归思路简单，设计容易，但效率低。

递推算法设计相对复杂，但效率⾼。

集合求幂集函数：public class Test{public static void main(String []args){List<String> list = new ArrayList<String>();list.add("A");list.add("B");list.add("C");List<String> li = new ArrayList<String>();print(0,list,li);}public static void print(int i, List<String> list, List<String> li){if(i > list.size()-1){System.out.println(li);}else{li.add(list.get(i)); //左⼦树的处理print(i+1,list,li); //递归遍历li.remove(list.get(i)); //右⼦树的处理print(i+1,list,li); //递归遍历}}}皇后问题：public class Test{static int max = 8; //放置⼏个皇后static int num = 0; //总共有⼏种存放⽅式static int[] array = new int[max]; //⽤数组存放皇后的摆放位置⽤来判断是否摆放正确public static void main(String[] args){check(0); //先放第⼀个皇后System.out.println(num);}public static void check(int n){if(n == max){ //如果皇后全部摆放完成，总数+1 并跳出该⽅法num++;return;}for (int i = 0; i < max; i++) { //从第⼀列开始放，到第max列为⽌array[n] = i; //默认该皇后都是从该⾏的第⼀列开始摆放if (ok(n)) { //判断该皇后的摆放位置是否正确check(n + 1); //如果正确，则递归下⼀个皇后的摆放}}}private boolean ok(int n) {for (int i = 0; i < n; i++) { //从第⼀列开始放值，然后判断是否和本⾏本列本斜线有冲突，如果OK，就进⼊下⼀⾏的逻辑//array[i] == array[n] 判断是否在同⼀斜线上//Math.abs(n - i) == Math.abs(array[n] - array[i]) 判断是否在同⼀⾏或列if (array[i] == array[n] || Math.abs(n - i) == Math.abs(array[n] - array[i])) {return false;}}return true;}}。