骑士游历回溯java
时间: 2023-12-31 22:24:16 浏览: 51
以下是一个使用回溯算法实现骑士游历的Java代码示例:
```java
import java.util.ArrayList;
import java.util.List;
public class KnightTour {
private static final int BOARD_SIZE = 8;
private static final int[] ROW_MOVES = {2, 1, -1, -2, -2, -1, 1, 2};
private static final int[] COL_MOVES = {1, 2, 2, 1, -1, -2, -2, -1};
public static void main(String[] args) {
int[][] chessboard = new int[BOARD_SIZE][BOARD_SIZE];
int startRow = 0;
int startCol = 0;
int moveNumber = 1;
chessboard[startRow][startCol] = moveNumber;
List<int[]> path = new ArrayList<>();
path.add(new int[]{startRow, startCol});
if (solveKnightTour(chessboard, startRow, startCol, moveNumber + 1, path)) {
System.out.println("Knight tour path:");
for (int[] position : path) {
System.out.println("(" + position[0] + ", " + position[1] + ")");
}
} else {
System.out.println("No solution found.");
}
}
private static boolean solveKnightTour(int[][] chessboard, int row, int col, int moveNumber, List<int[]> path) {
if (moveNumber > BOARD_SIZE * BOARD_SIZE) {
return true; // 所有位置都已经访问过
}
for (int i = 0; i < ROW_MOVES.length; i++) {
int nextRow = row + ROW_MOVES[i];
int nextCol = col + COL_MOVES[i];
if (isValidMove(chessboard, nextRow, nextCol)) {
chessboard[nextRow][nextCol] = moveNumber;
path.add(new int[]{nextRow, nextCol});
if (solveKnightTour(chessboard, nextRow, nextCol, moveNumber + 1, path)) {
return true;
}
// 回溯
chessboard[nextRow][nextCol] = 0;
path.remove(path.size() - 1);
}
}
return false;
}
private static boolean isValidMove(int[][] chessboard, int row, int col) {
return row >= 0 && row < BOARD_SIZE && col >= 0 && col < BOARD_SIZE && chessboard[row][col] == 0;
}
}
```
相关推荐
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)