Java Programming: The Knight’s Tour

The Knight’s Tour is a classic problem in mathematics. From any position on an 8x8 chessboard, the knight can move in up to 8 different positions (in an “L” shape)

The knight may not move to a place that is off the board.In the Knight’s Tour problem, the knight is placed on a given square of the board –it doesn’t matter which one it starts on. The problem then, is to find a path where the knight can travel to every other square on the board without touching the same square more than 1 time.When the knight is on the final square, if it can attack the original square where it started, the tour is known as an“open tour” whereas if it cannot attack the original square,the tour is known as a “closed tour”.In this assignment, you are to write a problem that uses a brute force recursive algorithm to find as many Knight’s Tour paths (open or closed) as possible.

How It’s Done:To start with, you will need to model the game board using a linked grid. To do this, you will need to modify the Node class that was previously written so that it has an integer data item and can link up, down, left and right.The default data item for a Node will be 0.Then you will need to design a class called Board that will represent the chessboard. The constructor of the Board class will set up the entire board all at once –there is no need to push Nodes to the board.Once this is done, you will need to write a method that will display the board using its integer data item. At this point, every item should be a zero.

Once this is done, you will need to write a recursive algorithm called Tour that will have a Node as a parameter. The Tour method will check a set of available paths and Tour to each of those paths. When the Tour method goes to each Node, it will assign a number to the Node to indicate which step the Tour algorithm is currently on. If there are no available Nodes to visit, the Tour algorithm will reset the Node value to be zero and end. If the Tour method ever assigns a number of 64 to a Node, then it has found a complete path and will display the board.Please note that finding a solution in this way can take a VERY LONG TIME. It is recommended that you test the program using a 5x5 board and only try it on an 8x8 when you are sure it is working

This material may consist of step-by-step explanations on how to solve a problem or examples of proper writing, including the use of citations, references, bibliographies, and formatting. This material is made available for the sole purpose of studying and learning - misuse is strictly forbidden.

public class Nodes {

private int data;
private Nodes left;
private Nodes right;
private Nodes up;
private Nodes down;

public Nodes() {
this.left = null;
this.right = null;
this.up = null;
this.down = null;
}

public int getData() {
return data;
}

public void setData(int data) {
this.data = data;
}

public Nodes getLeft() {
return left;
}

public void setLeft(Nodes left) {
this.left = left;
}

public Nodes getRight() {
return right;
}...