## Friday, 13 January 2017

### Chapter 18 Exercise 33, Introduction to Java Programming, Tenth Edition Y. Daniel LiangY.

18.33 (Game: Knight’s Tour animation)
Write a program for the Knight’s Tour problem. Your program should let the
user move a knight to any starting knight and click the Solve button to animate
a knight moving along the path.

public class MyPoint {

public double x;
public double y;

public MyPoint(double x, double y) {
this.x = x;
this.y = y;
}

public MyPoint() {
this(0,0);
}

public double x() {
return x;
}

public void setX(double x) {
this.x = x;
}

public double y() {
return y;
}

public void setY(double y) {
this.y = y;
}

public double distance(double x, double y) {
return Math.sqrt((this.x - x) * (this.x - x) + (this.y - y) * (this.y - y));
}

public double distance(MyPoint point) {

return distance(point.x, point.y);
}

public MyPoint getCenterPoint(MyPoint p) {

return new MyPoint((p.x + this.x) / 2, (p.y + this.y) / 2);
}

public static MyPoint getCenterPoint(double x1, double y1, double x2, double y2) {
return new MyPoint((x1 + x2) / 2, (y1 + y2) / 2);
}

/** Return true if this point is on the left side of the
*  directed line from p0 to p1 */
public boolean leftOfTheLine(MyPoint p0, MyPoint p1) {

return leftOfTheLine(p0.x, p0.y, p1.x, p1.y, x, y);
}

/** Return true if this point is on the same
*  line from p0 to p1 */
public boolean onTheSameLine(MyPoint p0, MyPoint p1) {

return onTheSameLine(p0.x, p0.y, p1.x, p1.y, x, y);

}

/** Return true if this point is on the right side of the
*  directed line from p0 to p1 */
public boolean rightOfTheLine(MyPoint p0, MyPoint p1) {

return rightOfTheLine(p0.x, p0.y, p1.x, p1.y, x, y);

}

/** Return true if this point is on the
*  line segment from p0 to p1 */
public boolean onTheLineSegment(MyPoint p0, MyPoint p1) {

return onTheLineSegment(p0.x, p0.y, p1.x, p1.y, x, y);

}

/** Return true if point (x2, y2) is on the left side of the
*  directed line from (x0, y0) to (x1, y1) */
public static boolean leftOfTheLine(double x0, double y0, double x1, double y1, double x2, double y2){

return (x1 - x0) * (y2 - y0) - (x2 - x0) * (y1 - y0) > 0;
}
/** Return true if point (x2, y2) is on the same
*  line from (x0, y0) to (x1, y1) */
public static boolean onTheSameLine(double x0, double y0, double x1, double y1, double x2, double y2) {

return (x1 - x0) * (y2 - y0) - (x2 - x0) * (y1 - y0) == 0;
}
/** Return true if point (x2, y2) is on the
*  line segment from (x0, y0) to (x1, y1) */
public static boolean onTheLineSegment(double x0, double y0, double x1, double y1, double x2, double y2) {

double position = (x1 - x0) * (y2 - y0) - (x2 - x0) * (y1 - y0);

return position <= 0.0000000001 && ((x0 <= x2 && x2 <= x1) || (x0 >= x2 && x2 >= x1));
}

/** Return true if point (x2, y2) is on the right side of the
*  directed line from (x0, y0) to (x1, y1) */
public static boolean rightOfTheLine(double x0, double y0, double x1, double y1, double x2, double y2){

return (x1 - x0) * (y2 - y0) - (x2 - x0) * (y1 - y0) < 0;
}

@Override
public String toString() {
return "(" + x + ", " + y + ")";
}

}


import javafx.animation.PathTransition;
import javafx.application.Application;
import javafx.geometry.Insets;
import javafx.geometry.Pos;
import javafx.scene.Scene;
import javafx.scene.control.Button;
import javafx.scene.control.Label;
import javafx.scene.image.Image;
import javafx.scene.layout.*;
import javafx.scene.paint.Color;
import javafx.scene.shape.Line;
import javafx.scene.shape.Polyline;
import javafx.stage.Stage;
import javafx.util.Duration;

import java.util.ArrayList;

public class Exercise_33 extends Application {

public static void main(String[] args) {
Application.launch(args);
}

@Override
public void start(Stage primaryStage) throws Exception {
ChessBoardPane pane = new ChessBoardPane();

primaryStage.setScene(new Scene(pane));
primaryStage.setTitle("Knight's Tour");
primaryStage.show();
}

public class ChessBoardPane extends Pane {

ChessSquare[][] squares = new ChessSquare[8][8];
boolean[][] isTaken = new boolean[8][8];
Polyline polyline = new Polyline();
ArrayList<MyPoint> availablePath = new ArrayList<>(8);
int[] currentP = new int[2];
int firstX;
int firstY;
boolean isFirstMove = true;
ChessSquare knight = new ChessSquare(true);

PathTransition path = new PathTransition();
Line line = new Line();

Button btnReset = new Button("Reset");
Button btnSolve = new Button("Solve Using Brute-Force");

ChessBoardPane() {

GridPane gridPane = new GridPane();
knight.setMinSize(80, 80);
knight.placeKnight();
boolean isBlack = false;
for (int i = 0; i < squares.length; i++) {
for (int j = 0; j < squares[i].length; j++) {

gridPane.add(squares[i][j] = new ChessSquare(isBlack), j, i);
squares[i][j].setPrefSize(80, 80);
int x = j;
int y = i;
squares[i][j].setOnMouseClicked(e -> {

if (isFirstMove) {
firstX = x;
firstY = y;
currentP[0] = x;
currentP[1] = y;
isFirstMove = false;
squares[y][x].placeKnight();

setPoint(x, y);
} else {
playerMove(x, y);
}

});
isBlack = !isBlack;
}
isBlack = !isBlack;
}

btnReset.setOnMouseClicked(e -> completeReset());
btnSolve.setOnMouseClicked(e -> solve());
BorderPane borderPane = new BorderPane(gridPane);
HBox hBox = new HBox(20, btnReset, btnSolve, new Label("Solving using brute force may take a minute..."));
hBox.setAlignment(Pos.BASELINE_CENTER);
borderPane.setBottom(hBox);

toggleKnight();
polyline.setStroke(Color.RED);
line.setStroke(Color.ORANGE);
}

private void playerMove(int x, int y) {
if (isValidMove(x, y)) {
squares[currentP[1]][currentP[0]].leavePathMark();
setPoint(x, y);
currentP[0] = x;
currentP[1] = y;
}

}

private void toggleKnight() {
line.setVisible(!line.isVisible());
knight.setVisible(!knight.isVisible());
}

private void completeReset() {
resetChessBoard();
isFirstMove = true;
}

private void resetChessBoard() {
isTaken = new boolean[8][8];
for (ChessSquare[] square : squares) {
for (ChessSquare aSquare : square) {
aSquare.reset();
}
}
polyline.getPoints().clear();
}

private void solve() {
resetChessBoard();
setPoint(firstX, firstY); // draw first point
boolean isSuccess = false;

while (!isSuccess) {
isSuccess = move(firstX, firstY);
if (!isSuccess) {
resetChessBoard();
}
}

}

private void setPoint(int x, int y) {
double x1 = x * 80.0 + 50;
double y1 = y * 80.0 + 50;
isTaken[y][x] = true;
int last = polyline.getPoints().size() - 1;
if (last >= 3) {
line.setStartX(polyline.getPoints().get(last - 3));
line.setStartY(polyline.getPoints().get(last - 2));
line.setEndX(polyline.getPoints().get(last - 1));
line.setEndY(polyline.getPoints().get(last));

path.setPath(line);
path.setNode(knight);
path.setCycleCount(1);
path.setDuration(Duration.seconds(1));
toggleKnight();
path.play();

path.setOnFinished(e -> {
squares[y][x].placeKnight();
toggleKnight();
});
}
}

private boolean isValidMove(int x, int y) {
return (!isTaken[y][x] && (currentP[1] == y - 2 && x == currentP[0] - 1 ||  // 2 up 1 left
currentP[1] == y - 1 && currentP[0] == x - 2 || // 1 up 2 left
currentP[1] == y - 2 && currentP[0] == x - 1 || // 2 up 1 right
currentP[1] == y - 1 && currentP[0] == x + 2 || // 1 up 2 right
currentP[1] == y + 2 && currentP[0] == x - 1 || // 2 down 1 left
currentP[1] == y + 1 && currentP[0] == x - 2 || // 1 down 2 left
currentP[1] == y + 1 && currentP[0] == x + 2 || // 1 down 2 right
currentP[1] == y + 2 && currentP[0] == x + 1));  // 2 down 1 right
}

private boolean move(int x, int y) {

availablePath.clear();
if (x >= 1 && y >= 2 && !isTaken[y - 2][x - 1]) // 2 up 1 left
availablePath.add(new MyPoint(x - 1, y - 2));
if (x >= 2 && y >= 1 && !isTaken[y - 1][x - 2]) // 1 up 2 left
availablePath.add(new MyPoint(x - 2, y - 1));
if (x <= 6 && y >= 2 && !isTaken[y - 2][x + 1]) // 2 up 1 right
availablePath.add(new MyPoint(x + 1, y - 2));
if (x <= 5 && y >= 1 && !isTaken[y - 1][x + 2]) // 1 up 2 right
availablePath.add(new MyPoint(x + 2, y - 1));
if (x >= 1 && y <= 5 && !isTaken[y + 2][x - 1]) // 2 down 1 left
availablePath.add(new MyPoint(x - 1, y + 2));
if (x >= 2 && y <= 6 && !isTaken[y + 1][x - 2]) // 1 down 2 left
availablePath.add(new MyPoint(x - 2, y + 1));
if (x <= 5 && y <= 6 && !isTaken[y + 1][x + 2]) // 1 down 2 right
availablePath.add(new MyPoint(x + 2, y + 1));
if (x <= 6 && y <= 5 && !isTaken[y + 2][x + 1]) // 2 down 1 right
availablePath.add(new MyPoint(x + 1, y + 2));

if (availablePath.size() > 0) {
MyPoint p = availablePath.get((int) (Math.random() * availablePath.size()));
setPoint((int) p.x, (int) p.y);
return move((int) p.x, (int) p.y);

}

return isSuccess();
}

private boolean isSuccess() {

boolean isSuccess = true;
for (int i = 0; i < isTaken.length; i++) {
for (int j = 0; j < isTaken[i].length; j++) {
if (!isTaken[i][j]) {
return false;
}
}
}
return isSuccess;
}

private class ChessSquare extends Pane {

boolean isBlack;

ChessSquare(boolean isBlack) {
this.isBlack = isBlack;
reset();

}

private void reset() {
if (isBlack) {
setStyle("-fx-border-color: black; -fx-background-color: black");

} else {
setStyle("-fx-border-color: black; -fx-background-color: gray");
}
}

private void placeKnight() {
setStyle("-fx-border-color: black;");
setBackground(
new Background(
new BackgroundImage(
new Image("image/knight.jpg"), null, null, null,
new BackgroundSize(100, 100, true, true, true, true))));
}

private void leavePathMark() {
setStyle("-fx-border-color: black; -fx-background-color: blue");
}

}

}
}