Friday, 13 January 2017

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

18.32 (Game: Knight’s Tour)
The Knight’s Tour is an ancient puzzle. The objective is to move a
knight, starting from any square on a chessboard, to every other square
once, as shown in Figure 18.15a. Note that the knight makes only
L-shaped moves (two spaces in one direction and one space in a perpendicular
direction). As shown in Figure 18.15b, the knight can move to eight squares.
Write VideoNote Search a string in a directory a program that displays the
moves for the knight, as shown in Figure 18.15c. When you click a cell, the knight
is placed at the cell. This cell will be starting point for the knight. Clicking
the Solve button to display the path for a solution.

package ToolKit;

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.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.shape.Polyline;
import javafx.stage.Stage;

import java.util.ArrayList;

public class Exercise_32 extends Application {

@Override
public void start(Stage primaryStage) throws Exception {

ChessBoardPane pane = new ChessBoardPane();

Scene scene = new Scene(pane);
primaryStage.setScene(scene);
primaryStage.setTitle("Chess Board");
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;

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

ChessBoardPane() {

GridPane gridPane = new GridPane();

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;
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);

}

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 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;
squares[y][x].placeKnight();
isTaken[y][x] = true;
}

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]) {
isSuccess = 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");
}

}

}

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