write a java program for the following question: Knight\'s tour problem Consider

Question

write a java program for the following question:

Knight's tour problem Consider a NxN chessboard, with the Knight moving according to Chess rules. When it moves, it can move to a square that is two squares horizontally and one square vertically, or two squares vertically and one square horizontally. The complete move therefore looks like the letter L. The Knight may move at most in 8 different cells (see Figure below) We want to find a sequence of moves for the Knight where all cells in the chessboard are visited, but each cell is touched exactly once. The starting point is arbitrary Make a solution consisting of three classes: Chessboard, KnightMove and Cell. A Chessboard has (at least) two data fields: int size to specify the size of the chessboard (i.e. number of rows/columns), andint[ [ touched to indicate whether or not a certain cell is already touched. You might want to implement methods to occupy and free cells in the chessboard. A KnightMove has (at least) one data field: int offsets to specify the Knight's starting point on the chessboard. This class should have a method with the following header: ArrayList findLegalMoves (Chessboard cb) which returns the collection of moves (i.e. a sequence of cells that can be visited by the Knight) that solves the Knight's tour problem. A Cell has (at least) two data fields: int i andint jto refer to a specific cell in the ith row and jth column of the chessboard. In the chessboard below a sequence of Knight moves is shown: (0,0), (2,1), (3,3). findLegalMoves (... returns the sequence of all moves to solve the Knight's problem.

Explanation / Answer

This Java Program is to Implement Knight’s Tour Problem.A knight’s tour is a sequence of moves of a knight on a chessboard such that the knight visits every square exactly once. If the knight ends on a square that is one knight’s move from the beginning square (so that it could tour the board again immediately, following the same path), the tour is closed, otherwise it is open. The exact number of open tours on an 8×8 chessboard is still unknown.

Backtracking Algorithm for Knight’s tour
Following is the Backtracking algorithm for Knight’s tour problem.

Here is the source code of the Java Program to Implement Knight’s Tour Problem. The Java program is successfully compiled and run on a Linux system. The program output is also shown below.

OUTPUT

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.