CS 302 Programming Assignment 2: Knight's Tour

Due date: Friday, October 26 at 7:00 pm (CSL time)

Last modified: Thursday, October 18, 2007

10/18/2007	Bug fixed in the Grid class concerning improper use of class constants. An upadated P2.jar is available.
10/16/2007	Bug fixed in the KnightApp stub.
10/15/2007	Minor revisions in the GameBoardTester description.
10/14/2007	Program released.

In this assignment you will be implementing a game called Knight’s Tour. The Knight’s Tour is a mathematical puzzle involving a chess board and a knight figure. The goal of the game is to visit every square of an empty chessboard with a knight figure exactly once following the rules of chess.

• Writing more complex Java classes
• Using Java decision-making constructs
• Using relational and logical operators
• Defining and using of class constants
• Processing console input
• Writing a toString method to use with console output

• The Knight's Tour game
• Classes you will write
• Classes we provide
• Documentation
• Questions to answer
• Assignment requirements

If you have not played chess before, or even seen a chessboard, do not fear. Here is a detailed description of the game and its components:

• The game is played on a chessboard, which usually is an 8x8 lattice of squares with alternating colors. In the Knight's Tour various boards can be used: 8x8, 5x5, etc. You can see an example of such a board below.
• A knight is a chess figure that can perform only one type of move: two squares to the front and one to the side. It can perform this move in any direction, as long as it stays on the board. A complete Knight move, therefore, resembles the letter 'L', as shown here.
• In the Knight’s Tour game, the Knight starts on one square and "tours" the board using only valid Knight moves. Every time a knight moves, its previous location is marked as visited (see Figure 1 below).
• The goal of the game is to visit every square exactly once. In other words, visit all the squares of the board while never stepping on a square that has been already visited.

You can play an online version of the game here. Try to play it, and you'll see that it's not that simple (if you have never played chess before it might be an especially good idea to practice). Figure 1 shows a few states of the game. You can see a full animation of the Knight’s Tour here.

                
Figure 1:  A knight at the start of the game, after two moves and at having finished the game*.

The Knight's Tour problem is actually more complicated than it may seem. Many variations of it exist, for smaller and bigger chessboards. In fact, for chessboards of size 3x3 or 4x4, no solution exists! It turns out to have some deep mathematical underpinnings and is an instance of a general Hamiltonian path problem in Graph Theory. We will not go into the mathematics of the puzzle, instead we will simply implement a Knight’s Tour game and let a user play it. If you are interested, you can read more about the game on Wikipedia.

Your version of the game will be text-based. The knight will always start at the lower left corner of the board (coordinates (1,1)). The player will supply a destination for the knight to move to (entering the row and column), and a new screen will be shown on every move. Once again, you will not write a program to solve the puzzle, you will only implement it as a game and let a human player solve it.

*From Wikipedia, The Free Encyclopedia. Retrieved 11:05, October 5, 2007, from http://en.wikipedia.org/wiki/Image:Knights-Tour-Animation.gif

For this assignment you will create four classes:

• the Square class - an instantiable class
• the GameBoardclass - an instantiable class
• the KnightApp class - an application class
• the GameBoardTester class - a test class

The Square class is used to represent individual squares on the chess grid. Each square keeps track of its color and its status (FREE, OCCUPIED, or VISITED). Note that this class has three public symbolic constants that will also be used in other classes. In our implementation of the game the color of the square does not matter (since the game has a text-based interface). However, the square still keeps track of the color, in case we wanted to reuse this class for a future graphical implementation of the game.

Public Interface:

• static final int FREE Symbolic constant representing a free square (not visited, not occupied by the knight).
• static final int OCCUPIED Symbolic constant representing a square occupied by the knight.
• static final int VISITED Symbolic constant representing a square that's been visited by the knight.
  
• public Square(boolean isWhite, int status) Creates a new square which can be either white or black and have a status of FREE, OCCUPIED, or VISITED.
  
• public int getStatus() Returns the status of the square which is either FREE, OCCUPIED, or VISITED.
  
• public void setStatus(int status) Sets the status of the square. If the status is invalid (i.e., not FREE, OCCUPIED, or VISITED), then setStatus sets the status of the square to FREE.
  
• public boolean isWhite() Returns true if the square is white and false otherwise.
  
• public String toString() Returns the string representation of the square. This is used to draw the square on the board. By default it should return "K" for an occupied square, "x" for a visited square and " " for a free square.
  

The GameBoard class is used to represent the board and its current state. Each gameboard keeps track of its grid, the coordinates of the knight, and the number of squares that have been visited.

Public Interface:

• public GameBoard(int height, int width) Creates a new board of the given height and width. Precondition: the height and width given are valid (i.e., positive integer values in the range allowed by the Grid class).
  
• public boolean solved() Returns true if the puzzle has been solved and false otherwise.
  
• public void print()
Prints the game board (using the appropriate method from the supplied Grid class).

• public int numberOfSquaresVisited() Returns the number of squares visited in the game. The square that the knight is currently on should be considered visited as well.
  
• public boolean validDestination(int row, int column) Returns true if the given coordinates represent a valid destination for the knight to move to. In order to be valid, the destination has to be located on board (i.e., within the boundaries of the board), has to be in the range of the knight's valid moves, and has to be free.
  
• public boolean moveStillPossible() Returns true if a move is still possible on the board, false otherwise. (Hint: you may want to utilize the validDestination method).
  
• public void moveKnight(int row, int column) Moves the knight from its current location to the row and column supplied.   Precondition: the row and column supplied must indicate a valid knight move. This means you need to determine if the move is valid before calling this method.
  

Here is a sample run of KnightApp. Here is an excerpt from another run (we don't show the whole game to save space). Please make sure that you follow the game in the format that we present here. The wording of your prompts can be different, but make sure that each input is read from a separate line (e.g., you should prompt the user for the destination row and column on separate lines as shown, and not, say, on a single line).

You may assume that the user enters integer values when prompted.  You may also assume that the integer values entered by the user for the dimensions of the chess board are in the appropriate range.  You may not assume that the integer values entered by the user for the row and column of a move are valid.

The GameBoardTester class tests the GameBoard class (by thoroughly testing every method (except for print()) and constructor of the GameBoard class). Note that we are not requiring you to turn in a SquareTester class although you should still make sure to test your Square class. Now that you know about if statements, we are requiring you to write your test class in a little different way than you did for programming assignment 1. Instead of printing out the expected results and the actual results and then having a human being look at the output and verify that the actual results are correct, you will have your test class do the checking and only print out something if there is a problem. In other words, you should use if statements to compare the actual results of a test with the expected results; if the results don't match, then print out information indicating the test that was performed, the expected results, and the actual results. If the expected results and actual results match, then don't print out anything except what was tested.

Classes we provide

The following classes are provided to you in the P2.jar file, which you should download and add to your Eclipse project. If you do not remember how to add external jars from lab, here is a quick reminder: right click on your project in Eclipse → Properties → Java Build Path → Libraries → Add External Jars.

Grid

The Grid class is used to represent a chess grid. Take a look at its Javadoc. Note: this class depends on your Square class. Make sure that it functions properly before you use the Grid class.

Public Interface:

• public Grid(int height, int width) Creates a grid of FREE squares (the grid consists of "height x width" instances of the Square class). Legal ranges of height and width are between 1 and 99.
• public int getGridHeight() Returns the height of the grid.
• public int getGridWidth() Returns the width of the grid.
• public Square getSquare(int row, int column) Returns a reference to the Square object at the specified row and column of the grid (note: rows and columns are counted starting from 1, the lower left coordinate of the Grid is (1, 1)).
• public void printGrid() Prints the current state of the grid to the console. Uses the toString() method to obtain a textual representation of each square.
• public void resetGrid() Resets the grid to the state it was in when originally created.

FileReader

The FileReader class is used to allows you to put all the commands in a text file (one command per line) and then run the game in a batch instead of typing the commands on the keyboard one by one. We provide this class for you to make it more convenient to test your program as you develop it, and therefore you should only use this class for testing. Take a look at its Javadoc. An example of a text file that runs successfully on our version of the game can be found here. You should create your own test files to test other features of the game, e.g., how are bad moves from the user handled (off the board, invalid knight moves, moves to visited locations, moves to itself)? How does your program handle a non-solvable puzzle (e.g., a 3x3 board)?

Public Interface:

• static Scanner getFileScanner(String filename) A static method that constructs and returns a file scanner object for a supplied file name. The scanner can be used in the same way as the keyboard scanner.

For this assignment you are required to generate javadoc documentation (i.e., the html files) for your Square and GameBoard classes. See the section on Generating documentation in Lab 3 for information on how to use Eclipse to generate Javadoc webpages from your source files. Don't forget to look at your Javadoc documentation before you turn it in to ensure that it is what you expect! Although you will not submit Javadoc for KnightApp, it should still be commented in Javadoc style.

Make sure also to follow the CS 302 standards for style as well as commenting.

This section lists several questions that should deepen your understanding of the assignment.  Create a text-only file named questions.txt and answer these questions.

Be sure to include the descriptive information listed below as well as the answers to each question:

Assignment Number:
Assignment Name:
Date Completed:

Partner 1 Name:
Partner 1 Login:
Partner 1 Lecturer's Name:
Partner 1 Lab Section:

Partner 2 Name:
Partner 2 Login:
Partner 2 Lecturer's Name:
Partner 2 Lab Section:

1. The moveKnight(int row, int column) method in the GameBoard class has a precondition that the row and column given have to indicate a valid knight move. Suppose we removed this precondition. Do you think that would be a good design decision? How would you modify the moveKnight method to accommodate this?  Would you need to make changes in the rest of your code?
2. In the current implementation of the game, each Square class keeps track of its color (white or black). However, you may have noticed that the color of the square is never used. Why would we even want the square to track its color if it does not affect the logic of the game?
3. Suppose you were to implement a closed version of Knight's Tour (the knight has to end at the same square that it started). How would you change your code to implement this?
4. Suppose we were to allow the knight be started at any square on the board. What changes/additions would you need to make to your code?
5. What happens if you try to play a game on a 2x2 board?  Copy and paste the output of the game as your answer to this question.
6. Intuitively, why does the game on a 3x3 board have no solution?
7. You may have noticed that even on solvable gameboards you can get yourself in trouble quite fast, that is, reach a state where the knight has no more valid moves but the game has not been solved yet. Give one example of such a state of the game on a 5x5 board, where the knight gets stuck with the fewest number of moves possible. Include a copy of only the final state of the game with your answer. (Hint: you can get in trouble in as few as 4 moves.)

This section outlines the major requirements of the assignment.  Your solution to the assignment must meet each of these requirements.  Be sure to read the announcements frequently and ask questions if you need clarification.

1. Include name, login, lecture, and lab section information at the top of all assignment files.
2. Follow the style and commenting standards for CS 302.  This includes:
   • including javadoc comments for every portion of the public interface of every class.
   • using symbolic names wherever they are appropriate.
   • using visibility modifiers appropriately; data members should be private and publicly accessible methods should be public.
3. Follow the specifications exactly, i.e., each method you implement must have the correct spelling, the correct return type, and the correct parameter type(s) and must behave according to the specifications.
4. Follow the output specifications as shown in the sample output file.  You may use different wording for your user prompts but the user must be asked to enter information in the exact same order as the sample output file.
5. The GameBoardTester class must contain code to test every method and constructor of the GameBoard class.
6. The KnightApp class must use the GameBoard class to create a GameBoard object and perform the actions on it as specified.
7. The GameBoard class must use the Grid class to create a Grid object and perform the actions on it as specified.
8. The KnightApp class should in no circumstances attempt to use an instance of the Grid class. The dependency should be as follows: KnightApp -> GameBoard -> Grid -> Square
9. Submit your answers to the questions in a text-only file (no Word documents) named questions.txt.
10. Use the Handin program to hand in all work electronically.

• You should do this assignment as a separate project in Eclipse.
• Make sure you read through the entire programming assignment description before you start writing any code.
• I'm lost. There are too many things to figure out. Where do I start? A good starting point would be to read the whole assignment first (even if some parts don't make sense). Then try to draw on paper a diagram of all the classes you need to write and we provide to you and indicate the "responsibilities" of each. You should notice that the dependency pattern here is KnightApp -> GameBoard -> Grid -> Square. You should start writing your code "backwards", starting with the Square class (testing to make sure it works correctly), then test if the Grid works with your Square, then write the GameBoard, GameBoardTester, and finally the KnightApp.
• How do I modify a square? Note that the Grid class provides only a getSquare(int, int) method, but no setSquare. The getSquare, however, returns a reference (or a handle) to a square in the Grid, not a copy of it! Thus if you invoke a method like setStatus(int) on the reference returned to you, it will affect the actual square in the grid.
• Pair Programmers: don't forget to create a text-only README file that provides both students' information.  This file must be handed in to each student's handin directory.

Use the Handin program to hand in your work (see the instructions on how to use the Handin program). Students working in pairs will only submit one copy of all program files, except the README file described below.

Only hand in the files listed below; do not hand in any other files.  These files may be handed in any time prior to the due date.  Note: you may hand in your files before the deadline as many times as you wish.  We suggest you use your handin directory to keep your most recent working copy as you develop your solution.

Required files for this assignment

• Java source code files (program files):
  • Square.java
  • GameBoard.java
  • KnightApp.java
  • GameBoardTester.java
  
  
• Two javadoc files:
  • Square.html
  • GameBoard.html
  
  
• One text file of answers to the questions:
  • questions.txt
  
  
• Pair Programming students must also submit a README file: All students working in pairs must read the Pair Programming Guidelines and submit a README file.  Each student working in a pair must hand in this file to his/her own handin directory.  Copy, complete, and hand in the file that is linked here:
  • README.txt