Java语言程序设计基础篇_编程练习题***18.32 (游戏:骑士的旅途)

题目：***18.32 (游戏:骑士的旅途)

习题思路

代码示例

输出结果

题目：***18.32 (游戏:骑士的旅途)

骑士的旅途是一个古老的谜题，它的目的是使骑从棋盘上的任意一个正方形开始移动，经过其他的每个正方形一次，如图18-15a 所示。注意，骑士只能做L形的移动(两个空格在一个方向上而一个空格在垂直的方向上)。如图18-15b 所示，骑士可以移动到八个正方形的位置。编写一个程序，显示骑士的移动，如图 18-15C 所示。当单击一个单元格的时候，骑士被放置在该单元格中。该单元格作为骑士的起始点。单击Solve按钮显示作为解答的路径。

习题思路

界面设置：
- 使用BorderPane作为主布局，中心放置一个Board（自定义的Pane），用于绘制棋盘和骑士的移动路径。
- 在底部添加一个按钮btSolve，用于触发求解过程。
- 舞台（Stage）和场景（Scene）的设置，包括尺寸和标题。
棋盘和骑士的初始化：
- 在Board类中，通过draw方法绘制棋盘（网格线）和初始位置的骑士（红色圆圈）。
- 骑士的初始位置（startX和startY）默认为(0, 0)，但可通过鼠标点击棋盘上的任意格子来设置新的起始位置。
求解逻辑：
- 使用一个二维布尔数组moves来记录棋盘上的格子是否已被访问过。
- solvePuzzle方法是一个递归函数，用于尝试不同的移动路径，直到找到一种能够遍历所有格子并返回起点的解决方案。
- 在每一步尝试中，通过lookAheadCount方法评估每个可能的下一步移动，并选择看起来最有前景的（即下一步后能够访问最多新格子的）移动。
- 使用回溯法，如果当前路径无法找到解决方案，则撤销上一步的选择，尝试其他可能的移动。
用户交互：
- 点击棋盘上的格子设置新的起始位置，并清空之前的移动历史。
- 点击“Solve”按钮触发求解过程，并在找到解决方案后重新绘制棋盘，显示骑士的移动路径。
移动历史记录：
- 使用ArrayList<Point2D>来记录骑士的移动历史，以便在求解过程中回溯和重新绘制路径。
- 提供resetMoves、addMove和removeLastMoveHistory方法来管理移动历史记录。
棋盘绘制：
- 在Board类的draw方法中，除了绘制棋盘网格和骑士外，还根据移动历史记录绘制骑士的移动路径。

代码示例

编程练习题18_32TheKnightJourney.java

package chapter_18;  import java.util.ArrayList;
import java.util.List;
import javafx.application.Application;
import javafx.geometry.Point2D;
import javafx.geometry.Pos;  
import javafx.scene.Scene;  
import javafx.scene.control.Button;  
import javafx.scene.layout.BorderPane;  
import javafx.scene.layout.HBox;  
import javafx.scene.layout.Pane;  
import javafx.scene.paint.Color;  
import javafx.scene.shape.Circle;
import javafx.scene.shape.Line;
import javafx.stage.Stage;  public class 编程练习题18_32TheKnightJourney extends Application {  private static final int SIZE = 8;private int startX = 0;private int startY = 0;private ArrayList<Point2D> moves = null;public static void main(String[] args) {  Application.launch(args);  }  @Override  public void start(Stage primaryStage) throws Exception {BorderPane pane = new BorderPane();Board board = new Board();pane.setCenter(board);Button btSolve = new Button("Solve");pane.setBottom(btSolve);BorderPane.setAlignment(btSolve, Pos.CENTER);Scene scene = new Scene(pane,400,400);primaryStage.setTitle("");primaryStage.setScene(scene);primaryStage.show();board.draw();btSolve.setOnAction(e -> {boolean[][] moves = new boolean[SIZE][SIZE];moves[startX][startY] = true;resetMoves();addMove(startX,startY);solvePuzzle(moves,1,startX,startY);board.draw();});}private boolean solvePuzzle(boolean[][] moves,int numberMoves,int x,int y) {int nextX = 0;int nextY = 0;int bestMoveX = 0;int bestMoveY = 0;int bestMoveX2 = 0;int bestMoveY2 = 0;int minMoveCount = SIZE;int moveCount = 0;for(int i = 2;i >= -2;i += -4) {for(int j = 1;j >= -1;j += -2) {nextX = x + i;nextY = y + j;if(nextX >= 0&&nextX <= SIZE-1&&nextY >= 0&&nextY <= SIZE-1&&!moves[nextX][nextY]) {moveCount = lookAheadCount(moves,nextX,nextY);if(moveCount <= minMoveCount) {minMoveCount = moveCount;bestMoveX2 = bestMoveX;bestMoveY2 = bestMoveY;bestMoveX = nextX;bestMoveY = nextY;}}nextX = x + j;nextY = y + i;if(nextX >= 0&&nextX <= SIZE-1&&nextY >= 0&&nextY <= SIZE-1&&!moves[nextX][nextY]) {moveCount = lookAheadCount(moves,nextX,nextY);if(moveCount <= minMoveCount) {minMoveCount = moveCount;bestMoveX2 = bestMoveX;bestMoveY2 = bestMoveY;bestMoveX = nextX;bestMoveY = nextY;}}}}moves[bestMoveX][bestMoveY] = true;addMove(bestMoveX,bestMoveY);numberMoves++;if(numberMoves == (SIZE * SIZE))return true;if(moveCount > 0&&solvePuzzle(moves, numberMoves, bestMoveX, bestMoveY))return true;moves[bestMoveX][bestMoveY] = false;moves[bestMoveX2][bestMoveY2] = true;removeLastMoveHistory();addMove(bestMoveX2,bestMoveY2);if(moveCount > 1&&solvePuzzle(moves, numberMoves, bestMoveX2, bestMoveY2)) {return true;}moves[bestMoveX2][bestMoveY2] = false;removeLastMoveHistory();numberMoves--;return false;}private int lookAheadCount(boolean[][] moves,int x,int y) {int maxCount = 0;for(int i = -2;i<=2;i+=4) {for(int j = -1;j <= 1;j += 2) {int nextX = x + i;int nextY = y + j;if(nextX >= 0&&nextX <= SIZE-1&&nextY >=0 && nextY <= SIZE-1&&!moves[nextX][nextY]) {maxCount++;}nextX = x + j;nextY = y + i;if(nextX >= 0&&nextX <= SIZE-1&&nextY >= 0&&nextY <= SIZE-1&&!moves[nextX][nextY])maxCount++;}}return maxCount;}public void resetMoves() {moves = new ArrayList(63);}public void addMove(int x,int y) {moves.add(new Point2D(x, y));}public void removeLastMoveHistory() {moves.remove(moves.size()-1);}private class Board extends Pane{Circle theKnight = new Circle();Board(){this.setOnMouseClicked(e ->{startX = (int)(e.getX()/(getWidth()/SIZE));startY = (int)(e.getY()/(getHeight()/SIZE));resetMoves();draw();});}protected void draw() {this.getChildren().clear();this.getChildren().add(theKnight);theKnight.setCenterX(startX * getWidth()/SIZE +15);theKnight.setCenterY(startY * getHeight()/SIZE + 15);theKnight.setRadius(5);theKnight.setFill(Color.RED);for(int i = 1;i <= SIZE;i++) {this.getChildren().add(new Line(0,i*getHeight()/SIZE,getWidth(),i*getHeight()/SIZE));			                     this.getChildren().add(new Line(i*getWidth()/SIZE,0,i*getWidth()/SIZE,getHeight()));}if(moves != null) {for(int i = 1;i < moves.size();i++) {Point2D p1 = moves.get(i - 1);Point2D p2 = moves.get(i);this.getChildren().add(new Line(p1.getX()*(getWidth()/SIZE)+(getWidth()/SIZE/2),p1.getY()*(getHeight()/SIZE)+(getHeight()/SIZE/2),p2.getX()*(getWidth()/SIZE)+(getWidth()/SIZE/2),p2.getY()*(getHeight()/SIZE)+(getHeight()/SIZE/2)));}}}}
}