八皇后问题是找到一个解决方案,在棋盘的每一行放置一个皇后,使得两个皇后不能互相攻击。该问题可以使用递归来解决。在本节中,我们将介绍一种常见的算法设计技术,称为回溯来解决这个问题。回溯方法逐步搜索候选解决方案,一旦确定
就放弃该选项 候选人不可能是有效的解决方案,然后寻找新的候选人。可以使用二维数组来表示棋盘。然而,由于每一行只能有一个皇后,因此使用一维数组来表示皇后在该行中的位置就足够了。因此,您可以将 queens 数组定义为:
int[] queens = new int[8];
将j赋值给queens[i],表示皇后放置在行i和列j中。下图(a)显示了下图(b)中棋盘的queens数组的内容。
搜索从第一行开始,k = 0,其中k是正在考虑的当前行的索引。该算法检查是否可以按 _j = 0, 1, ... , 7 的顺序将皇后放置在行中的第 j_ 列中。搜索实现如下:
如果成功,它会继续在下一行中搜索皇后的位置。如果当前行是最后一行,则找到解决方案。 如果不成功,则回溯到上一行,并继续在上一行的下一列中搜索新的放置位置。 如果算法回溯到第一行并且无法在该行找到皇后的新位置,则无法找到解决方案。下面的代码给出了显示八皇后问题解决方案的程序。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
package application;
import javafx.application.Application;
import javafx.geometry.Pos;
import javafx.stage.Stage;
import javafx.scene.Scene;
import javafx.scene.control.Label;
import javafx.scene.image.Image;
import javafx.scene.image.ImageView;
import javafx.scene.layout.GridPane;
public class EightQueens extends Application {
public static final int SIZE = 8; // The size of the chess board
// queens are placed at (i, queens[i])
// -1 indicates that no queen is currently placed in the ith row
// Initially, place a queen at (0, 0) in the 0th row
private int[] queens = {-1, -1, -1, -1, -1, -1, -1, -1};
@Override // Override the start method in the Application class
public void start(Stage primaryStage) {
search(); // Search for a solution
// Display chess board
GridPane chessBoard = new GridPane();
chessBoard.setAlignment(Pos.CENTER);
Label[][] labels = new Label[SIZE][SIZE];
for(int i = 0; i = 0 && k
<p>程序调用<strong>search()</strong>(第20行)来搜索解决方案。最初,任何行中都没有放置皇后(第 16 行)。现在,搜索从第一行 <strong>k = 0</strong>(第 53 行)开始,并找到皇后的位置(第 56 行)。如果成功,将其放入该行(第 61 行)并考虑下一行(第 62 行)。如果不成功,则回溯到上一行(第 58-59 行)。</p>
<p>findposition(k)<strong> 方法从 </strong>queen[k] + 1<strong> 开始搜索在行 </strong>k<strong> 中放置皇后的可能位置(第 73 行)。它检查是否可以将皇后放置在 </strong>start<strong>, </strong>start + 1<strong>, 。 。 。 、 和 </strong>7<strong>,按此顺序(第 75-78 行)。如果可能,返回列索引(第77行);否则,返回 </strong>-1<strong>(第 80 行)。</strong>
</p>调用<p>isvalid(row, column)<strong>方法来检查在指定位置放置皇后是否会与之前放置的皇后发生冲突(第76行)。它确保没有皇后被放置在同一列(第86行)、左上角对角线(第87行)或右上角对角线(第88行),如下图所示。</strong>
</p><p><img src="https://img.php.cn/upload/article/000/887/227/172109224966560.png" alt="image description" loading="lazy" style="max-width:90%" style="max-width:90%"></p>
以上就是使用回溯法解决八皇后问题的详细内容,更多请关注其它相关文章!