Assignment 5

The Assignment

http://www2.hawaii.edu/~tp_250/ICS211/Fall03/hw05.htm

Comments

I recommend your recursive method returns an array or String of moves. How you want to implement this is up to you. (You can still get an A (9.5/10) if you only want to determine whether it's possible, and not report the actual trail.)

Also, you have to decide what format you want to record moves in:

• Coordinates (column, row): "3-4" or "3, 4"
• Coordinates (row, column): "4-3" or "4, 3"
• Lettered Coordinates: (column, row): "B3"
• Array indexes: "3-2" or "3, 2"
• Squares to move: "+2, -1;"
• Direction to move: "EN" or "ES"
• Square number to move to: "25" or "13"
• Some other method, such as chess notation or your own invention.

Whatever you decide, make sure you explain your system, both in your program documenation and whenever you print results to the screen. Do you give row or column first? Does numbering start at the top or the bottom corner? Does numbering start at 0 or 1? Etc.

If you want your program to work faster that just a brute-force, try-every-possibility technique, do a Web search for "knight's tour algorithm". For example, Warnsdorff's algorithm--rating each potential move in terms of the number of possible second moves from the new location, with a lower rating being better--might help you.

Also, keep in mind that arrays are like objects when it comes to using them as arguments to a method call. They are pass by reference, not pass by value. That means if you pass an array (or array of arrays, such as your chess board) to a method, that method will change the original array. (The array does not get copied; there is only one copy of the array.) This can lead to problems in recursive calls, since if you backtrack, you need to undo any changes to the board as you do. (Or, to avoid having to do this, you need to create a new copy of the array for each method call.)

Ask me in lab if you have any questions about this.

Grading

This assignment will be out of 10 points. You will get points for the following:

2.5 - Your program compiles without error

1.5 - Good documentation and follows ICS Java Coding Standards.

See this note on documenting your code. Use descriptive variable names, use internal capitalization for names, consistently indent and space code, etc.

3.5 - Correctly solves the Knight's Trail puzzle.

Allows for boards of different sizes. Allows the Knight to start at different positions. The Knight visits every square once and only once. Uses a recursive technique relying on backtracking.

0.5 - Reports the final trail of moves in some way

(It's hard to trouble-shoot without it!) Clearly explaining your system is work 0.3/0.5.

2 - Testing

As requested in the assignment, write a brief report on the results of your testing.

Since boards smaller than 3x4 are impossible cases, tell me for at least each of the following 10 cases:

for (int m = 3; m <=4; m++){
  for (int n = 4; n <= 8; n++) {
    //is a solution possible
    // for a m x n sized board?
  }
}

is a solution possible, impossible, or dependent on which square you start on?

What was your experience trying larger values for m and n?