COSC 1010 Introduction to Software Problem Solving

Fall 2010

Homework Assignment #7

"To iterate is human, to recurse divine."
-- L. Peter Deutsch

Due: Wednesday, November 3rd, 11:00am CDT
Submit: Turn in all both of your Java source files using the D2L Dropbox: Project7.java ChessBoard.java.
Work may be completed in teams of two. (These should be freshly allocated teams for the second half of the term.) The names of both partners must appear in a comment block at the top of your files for credit to be given.

Knights-A-Visiting

A millenia old chess riddle challenges a person to move a knight on an empty board such that every square on the board is visited exaclty once. For more on the history and significance of this problem, see the Wikipedia entry on the Knight's Tour.

Your task for this project is build a general solution finder for the problem that recursively searches for a successful tour on an n x m board, given as input the board size and the starting position of the knight.

Background

The chess piece called, "the knight," moves in a unique L-shaped pattern. From a square near the middle of a chessboard, a single move consists of either two horizontal spaces and a single vertical space, or two vertical spaces and a horizontal space. Like all chess pieces, the knight cannot move out of the boundaries of the chessboard. Thus, a knight can have up to 8 moves from a given starting location, fewer if it is near the board edge.

A chessboard has 64 squares, organized into eight rows and eight columns, alternating in color. The color of a square is of no importance when moving a knight. For the purposes of this problem, we're going to generalize to allow rectangular chessboards of any dimension.

For a given board size, various clever algorithms exist for quickly detecting or constructing a successful knight's tour; none of these are necessary or appropriate for this project. Your task is to construct a simple, recursive, brute-force search of the possibilities. A modern computer can find solutions for an 8x8 board with some starting positions in under five seconds. This problem has exponential complexity as specified, so solutions for bigger boards can take a lot longer.

I recommend solving this problem with two classes, one to represent the chessboard, and one to encode the solution strategy. My ChessBoard class contains a private, two-dimensional array of integers to represent the board, and includes the following methods:

public ChessBoard(int rows, int cols). A constructor.

public void print(). Prints out the board.

public boolean isEmpty(int row, int col). Returns true if the square at the specified row and column in the board is empty.

public void place(int row, int col, int n). Places the nth knight at square (row,col) on the board.

public void unplace(int row, int col). Removes a knight from (row,col) on the board when a move doesn't work out.

public int getRows(). Returns the size of the current board in rows.

public int getCols(). Returns the size of the current board in columns.

Example Run

In the examples below, I use text in blue to distinguish the output of the program from the input I typed. This is for purpose of clarity only; your program will not print text in different colors.

Enter number of rows: 8
Enter number of columns: 8
Enter starting row: 0
Enter starting column: 0
52 47 56 45 54  5 22 13
57 44 53  4 23 14 25  6
48 51 46 55 26 21 12 15
43 58  3 50 41 24  7 20
36 49 42 27 62 11 16 29
59  2 37 40 33 28 19  8
38 35 32 61 10 63 30 17
 1 60 39 34 31 18  9 64


Enter number of rows: 4
Enter number of columns: 4
Enter starting row: 1
Enter starting column: 3
No solution found for 4x4 board, starting at (1,3).

Notes

The Professor has provided a reference implementation for you to compare against. Change to directory ~brylow/cosc1010/Demos/Project7/ on Morbius, and run java Project7. Note that a correct algorithm may find a different tour from the reference implementation; many board sizes and starting positions have a ton of valid solutions. You just have to find one.