Programming Language: Java

Do not code a whole program in main or after main in a modular programming format.

Must write in "class" structure.

*Don't forget to comment your program.

The Knight's Tour is an ancient and famous chess puzzle.

The object is to move a knight from one square to another on an otherwise empty chess board until it has visited every square exactly once. Code a program that solves this puzzle using a depth-first search. It's best to make the board size variable so that you can attempt solutions for smaller boards. The regular 88 board can take years to solve on a desktop computer, but a 55 board takes only a minute or so. Refer to the subjects of Depth-First Search and Game Simulations . It may be easier to think of a new knight being created and remaining on the new square when a move is made. This way, a knight corresponds to a vertex, and a sequence of knights can be pushed onto the stack. When the board is completely filled with knights (the stack is full), you win. In this problem the board is traditionally numbered sequentially, from 1 at the upper-left corner to 64 at the lower-right corner (or 1 to 25 on a 55 board). When looking for its next move, a knight must not only make a legal knight's move, it must also not move off the board or onto an already-occupied (visited) square. If you make the program display the board and wait for a keypress after every move, you can watch the progress of the algorithm as it places more and more knights on the board, and then, when it gets boxed in, backtracks by removing some knights and trying a different series of moves. We'll have more to say about the complexity of this problem in the next chapter.