八皇后问题是找到一个解决方案，在棋盘的每一行放置一个皇后，使得两个皇后不能互相攻击。该问题可以使用递归来解决。在本节中，我们将介绍一种常见的算法设计技术，称为回溯来解决这个问题。回溯方法逐步搜索候选解决方案，一旦确定
就放弃该选项候选人不可能是有效的解决方案，然后寻找新的候选人。
可以使用二维数组来表示棋盘。然而，由于每一行只能有一个皇后，因此使用一维数组来表示皇后在该行中的位置就足够了。因此，您可以将 queens 数组定义为：
int[] queens = new int[8];
将j赋值给queens[i]，表示皇后放置在行i和列j中。下图(a)显示了下图(b)中棋盘的queens数组的内容。
搜索从第一行开始，k = 0，其中k是正在考虑的当前行的索引。该算法检查是否可以按 _j = 0, 1, … , 7 的顺序将皇后放置在行中的第 j_ 列中。搜索实现如下：
AI建筑知识问答
用人工智能ChatGPT帮你解答所有建筑问题
22 查看详情 如果成功，它会继续在下一行中搜索皇后的位置。如果当前行是最后一行，则找到解决方案。如果不成功，则回溯到上一行，并继续在上一行的下一列中搜索新的放置位置。如果算法回溯到第一行并且无法在该行找到皇后的新位置，则无法找到解决方案。
下面的代码给出了显示八皇后问题解决方案的程序。
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 < SIZE; i++) for(int j = 0; j < SIZE; j++) { chessBoard.add(labels[i][j] = new Label(), i, j); labels[i][j].setStyle("-fx-border-color: black"); labels[i][j].setPrefSize(55, 55); } // Display queens Image image = new Image("file:C:/Users/Paul/development/MyJavaFX/src/application/image/lo.jpg"); for(int i = 0; i = 0 && k < SIZE) { // Find a position to place a queen in the kth row int j = findPosition(k); if(j < 0) { queens[k] = -1; k--; // back track to the previous row } else { queens[k] = j; k++; } } if(k == -1) return false; // No solution else return true; // A solution is found } public int findPosition(int k) { int start = queens[k] + 1; // Search for a new placement for(int j =start; j < SIZE; j++) { if(isValid(k, j)) return j; // (k, j) is the place to put the queen now } return -1; } /** Return true is a queen can be placed at (row, column) */ public boolean isValid(int row, int column) { for(int i = 1; i <= row; i++) if(queens[row - i] == column // Check column || queens[row - i] == column - i // Check upleft diagonal || queens[row - i] == column + i) // Check upright diagonal return false; // There is a conflict return true; // No conflict }}
程序调用search()（第20行）来搜索解决方案。最初，任何行中都没有放置皇后（第 16 行）。现在，搜索从第一行 k = 0（第 53 行）开始，并找到皇后的位置（第 56 行）。如果成功，将其放入该行（第 61 行）并考虑下一行（第 62 行）。如果不成功，则回溯到上一行（第 58-59 行）。
findposition(k) 方法从 queen[k] + 1 开始搜索在行 k 中放置皇后的可能位置（第 73 行）。它检查是否可以将皇后放置在 start, start + 1, 。 。 。 、 和 7，按此顺序（第 75-78 行）。如果可能，返回列索引（第77行）；否则，返回 -1（第 80 行）。
调用
isvalid(row, column)方法来检查在指定位置放置皇后是否会与之前放置的皇后发生冲突（第76行）。它确保没有皇后被放置在同一列（第86行）、左上角对角线（第87行）或右上角对角线（第88行），如下图所示。
以上就是使用回溯法解决八皇后问题的详细内容，更多请关注创想鸟其它相关文章！
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至 chuangxiangniao@163.com 举报，一经查实，本站将立刻删除。
发布者：程序猿，转转请注明出处：https://www.chuangxiangniao.com/p/514488.html
微信扫一扫 
支付宝扫一扫 
