Recall that the Knight (it looks like a horse) can move in the shape of the letter, 'L', in any direction whatsoever. For example, if the Knight rests at the square marked X below, it can legally move to any of the positions marked by asterisks:
+--+--+--+--+--+ | | *| | *| | +--+--+--+--+--+ | *| | | | *| +--+--+--+--+--+ | | | X| | | +--+--+--+--+--+ | *| | | | *| +--+--+--+--+--+ | | *| | *| | +--+--+--+--+--+Here is an example of a ``tour'' of a 3x3 board by the Knight, which starts at the upper left corner of the board and attempts to visit each square exactly once:
+--+--+--+ | 1| 6| 3| +--+--+--+ | 4| | 8| +--+--+--+ | 7| 2| 5| +--+--+--+The numbers display the positions the Knight occupied during its tour. Note that the center square was not visited; indeed, it is impossible for a Knight to reach the center of a 3x3 board. Thus, the above tour is the best that can be found.
When started, the program generates a dialog that asks the user to enter the board size, which must be a positive integer. (If the user does not type a positive integer, the program stops.) The program prints in the command window a board showing a maximal tour. There might be several distinct tours, all of which are maximal. Your program need print only one maximal tour.
This problem is a classic example of a game-playing search, where all move sequences must be enumerated to find a best solution to the game. In this way, it closely resembles the string-permutation program presented in lecture.
0,0 0,1 1,1 ... 0,n
1,0 1,1 1,2 ... 1,n
2,0 2,1 2,2 ... 2,n
...
n,0 n,1 n,2 ... n,n
The Knight begins at position 0,0. One possible next move for it
is 1,2; another is 2,1.
With this coding, you can state precisely the moves
by a Knight.
To save time, you should use class Board, which has much of the machinery you need to do this assignment. You can download class Board at www.cis.ksu.edu/~schmidt/300f04/Assign/Assn3/Tour Here is its API specification:
| Constructor Summary | |
Board(int size)
Constructor Board initializes this board and places the knight in the upper left corner (at the x,y coordinates of 0,0). |
|
| Method Summary | |
int |
getCount()
getCount returns the number of spaces that the Knight has occupied so far on this board |
int |
getX()
getX returns the Knight's current x-coordinate on this board |
int |
getY()
getY returns the Knight's current y-coordinate on this board |
Board |
makeDuplicate()
makeDuplicate makes an exact copy of this board and returns it as a new object. |
boolean |
move(int newX,
int newY)
move makes the Knight move to the new position, (newX,newY), if possible, on this board. |
void |
printBoard()
printBoard prints this chessboard on the display, where the integers in the printed grid display the Knight's sequence of moves |
Here is a small test program that shows how to use the class:
package Tour;
public class Test
{ public static void main(String[] args)
{ Board b = new Board(5); // make a 5-by-5 board
System.out.println("The new board looks like this:");
b.printBoard();
System.out.println("The knight rests at " + b.getX() + "," + b.getY());
System.out.println();
// now, let's move the knight down the board and print what happens:
boolean on_the_board = true;
System.out.println("Now we move the knight:");
while ( on_the_board )
{ int nextX = b.getX() + 2;
int nextY = b.getY() + 1;
// try to move the knight:
on_the_board = b.move(nextX, nextY);
System.out.println("The result of the move is: ");
b.printBoard();
System.out.println("The knight rests at " + b.getX() + "," + b.getY());
System.out.println();
}
// let's make a duplicate board and play with it:
Board c = b.makeDuplicate(); // this is a new board !
boolean ok = c.move(c.getX() - 1, c.getY() - 2);
System.out.println("Let's compare the two boards:");
System.out.println("Board b is:");
b.printBoard();
System.out.println();
System.out.println("Board c is:");
c.printBoard();
}
}